Solve triangle solitaire puzzle: Difference between revisions
→{{header|jq}}
m (→{{header|Wren}}: Minor tidy) |
|||
Line 1,120:
Move 12 = {s=14, j=13, e=12}
Move 13 = {s=11, j=12, e=13}
</pre>
=={{header|jq}}==
'''Works with jq, the C implementation of jq'''
'''Works with gojq, the Go implementation of jq'''
This entry presents functions for handling a triangular solitaire
board of arbitrary size.
More specifically, the triples defining the "legal moves" need not be
specified explicitly. These triples are instead computed by the
function `triples($depth)`, which emits the triples [$x, $over, $y]
corresponding to a peg at position $x being potentially able to jump
over a peg (at $over) to position $y, or vice versa, where $x < $over.
The `solve` function can be used to generate all solutions, as
illustrated below for the standard-size board.
The position of the initial "hole" can also be specified.
The holes in the board are numbered sequentially beginning from 1 at
the top of the triangle. Since jq arrays have an index origin of 0,
the array representing the board has a "dummy element" at index 0.
<syntaxhighlight lang="jq">
### General utilities
def array($n): . as $in | [range(0;$n)|$in];
def count(s): reduce s as $_ (0; .+1);
# Is . equal to the number of items in the (possibly empty) stream?
def countEq(s):
. == count(limit(. + 1; s));
def lpad($len): tostring | ($len - length) as $l | (" " * $l) + .;
### Solitaire
# Emit a stream of the relevant triples for a triangle of the given $height,
# specifically [$x, $over, $y] for $x < $y
def triples($height):
def triples: range(0; length - 2) as $i | .[$i: $i+3];
def stripes($n):
def next:
. as [$r1, $r2, $r3]
| ($r3[-1]+1) as $x
| [$r2, $r3, [range($x; $x + ($r3|length) + 1)]];
limit($n; recurse(next)) ;
def lefts:
. as [$r1, $r2, $r3]
| range(0; $r1|length) as $i
| [$r1[$i], $r2[$i], $r3[$i]];
def rights:
. as [$r1, $r2, $r3]
| range(0; $r1|length) as $i
| [$r1[$i], $r2[$i+1], $r3[$i+2]];
($height * ($height+1) / 2) as $max
| [[1], [2,3], [4,5,6]] | stripes($height)
| . as [$r1, $r2, $r3]
| ($r1|triples),
(if $r3[-1] <= $max then lefts, rights else empty end) ;
# For depth <= 10, use single characters to represent pegs, e.g. A for 10.
# Input: {depth, board}
def drawBoard:
def hex: [if . < 10 then 48 + . else 55 + . end] | implode;
def p: map(. + " ") | add;
# Generate the sequence [$i, $n] for the hole numbers of the left-hand side
def seq: recurse( .[1] += .[0] | .[0] += 1) | .[1] += 1;
.depth as $depth
| def tr: if $depth > 11 then lpad(3) elif . == "-" then . else hex end;
[range(0; 1 + ($depth * ($depth + 1) / 2)) as $i | if .board[$i] then $i else "-" end | tr]
| limit($depth; ([1,0] | seq) as [$n, $s] | ((1 + $depth - $n)*" ") + (.[$s:$s+$n] | p )) ;
# "All solutions"
# Input: as produced by init($depth; $emptyStart)
def solve:
def solved:
.board as $board
| 1 | countEq($board[] | select(.)) ;
[triples(.depth)] as $triples # cache the triples
| def solver:
# move/3 tries in both directions
# It is assumed that .board($over) is true
def move($peg; $over; $source):
if (.board[$peg] == false) and .board[$source]
then .board[$peg] = true
| .board[$source] = false
| .board[$over] = false
| .solutions += [ [$peg, $over, $source] ]
| solver
| if .emit == true then .
else # revert
.solutions |= .[:-1]
| .board[$peg] = false
| .board[$source] = true
| .board[$over] = true
end
end ;
if solved then .emit = true
else
foreach $triples[] as [$x, $over, $y] (.;
if .board[$over]
then move($x; $over; $y),
move($y; $over; $x)
else .
end )
| select(.emit)
end;
solver;
# .board[0] is a dummy position
def init($depth; $emptyStart):
{ $depth,
board: (true | array(1 + $depth * (1+$depth) / 2))
}
| .board[0] = false
| .board[$emptyStart] = false;
# Display the sequence of moves to a solution
def display($depth):
init($depth; 1)
| . as $init
| drawBoard,
" Original setup\n",
(first(solve) as $solve
| $init
| foreach ($solve.solutions[]) as [$peg, $over, $source] (.;
.board[$peg] = true
| .board[$over] = false
| .board[$source] = false;
drawBoard,
"Peg \($source) jumped over peg \($over) to land on \($peg)\n" ) ) ;
display(6),
"\nTotal number of solutions for a board of height 5 is \(init(5; 1) | count(solve))"
</syntaxhighlight>
{{output}}
<pre style="height:20lh;overflow:auto>
-
2 3
4 5 6
7 8 9 A
B C D E F
G H I J K L
Original setup
1
- 3
- 5 6
7 8 9 A
B C D E F
G H I J K L
Peg 4 jumped over peg 2 to land on 1
1
2 3
- - 6
7 8 - A
B C D E F
G H I J K L
Peg 9 jumped over peg 5 to land on 2
-
- 3
4 - 6
7 8 - A
B C D E F
G H I J K L
Peg 1 jumped over peg 2 to land on 4
1
- -
4 - -
7 8 - A
B C D E F
G H I J K L
Peg 6 jumped over peg 3 to land on 1
1
2 -
- - -
- 8 - A
B C D E F
G H I J K L
Peg 7 jumped over peg 4 to land on 2
-
- -
4 - -
- 8 - A
B C D E F
G H I J K L
Peg 1 jumped over peg 2 to land on 4
-
- -
4 5 -
- - - A
B - D E F
G H I J K L
Peg 12 jumped over peg 8 to land on 5
-
- -
- - 6
- - - A
B - D E F
G H I J K L
Peg 4 jumped over peg 5 to land on 6
-
- -
- - 6
7 - - A
- - D E F
- H I J K L
Peg 16 jumped over peg 11 to land on 7
-
- -
- - 6
7 - 9 A
- - - E F
- H - J K L
Peg 18 jumped over peg 13 to land on 9
-
- -
- - -
7 - - A
- - D E F
- H - J K L
Peg 6 jumped over peg 9 to land on 13
-
- -
- - 6
7 - - -
- - D E -
- H - J K L
Peg 15 jumped over peg 10 to land on 6
-
- -
- - 6
7 - - -
- - D E -
- H I - - L
Peg 20 jumped over peg 19 to land on 18
-
- -
- - 6
7 - - -
- - D E -
- - - J - L
Peg 17 jumped over peg 18 to land on 19
-
- -
- - 6
7 8 - -
- - - E -
- - - - - L
Peg 19 jumped over peg 13 to land on 8
-
- -
- - 6
- - 9 -
- - - E -
- - - - - L
Peg 7 jumped over peg 8 to land on 9
-
- -
- - -
- - - -
- - D E -
- - - - - L
Peg 6 jumped over peg 9 to land on 13
-
- -
- - -
- - - -
- - - - F
- - - - - L
Peg 13 jumped over peg 14 to land on 15
-
- -
- - -
- - - A
- - - - -
- - - - - -
Peg 21 jumped over peg 15 to land on 10
Total number of solutions for a board of depth 5: 13987
</pre>
Line 1,161 ⟶ 1,465:
end
</syntaxhighlight>{{out}}
<pre style="height:20lh;overflow:auto>
Starting board:
0
| |||