Solve triangle solitaire puzzle: Difference between revisions
Content added Content deleted
m (→{{header|Wren}}: Minor tidy) |
|||
Line 1,120: | Line 1,120: | ||
Move 12 = {s=14, j=13, e=12} |
Move 12 = {s=14, j=13, e=12} |
||
Move 13 = {s=11, j=12, e=13} |
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> |
</pre> |
||
Line 1,161: | Line 1,465: | ||
end |
end |
||
</syntaxhighlight>{{out}} |
</syntaxhighlight>{{out}} |
||
<pre style="height:20lh;overflow:auto> |
|||
<pre> |
|||
Starting board: |
Starting board: |
||
0 |
0 |