Solve the no connection puzzle: Difference between revisions
jq
(jq) |
|||
Line 501:
Tested 12094 positions and did 20782 swaps.
</pre>
=={{header|jq}}==
{{works with|jq|1.4}}
We present a generate-and-test solver for a slightly more general version of the problem, in which there are N pegs and holes, and in which the connectedness of holes is defined by an array such that holes i and j are connected if and only if [i,j] is a member of the
array.
The jq index origin is 0, and so in the following, the pegs and
holes are internally numbered from 0 to (N-1) inclusive. That is, we interpret a permutation, p, of 0 .. (N-1) as meaning that the i-th peg is numbered p[i], for i in 0 .. (N-1).
However the pretty-print function shows solutions using the 1-to-8 numbering scheme for pegs, and the A-to-H lettering scheme for holes.
'''Part 1: Generic functions'''
<lang jq># Short-circuit determination of whether (a|condition)
# is true for all a in array:
def forall(array; condition):
def check:
. as $ix
| if $ix == (array|length) then true
elif (array[$ix] | condition) then ($ix + 1) | check
else false
end;
0 | check;
# permutations of 0 .. (n-1)
def permutations(n):
# Given a single array, generate a stream by inserting n at different positions:
def insert(m;n):
if m >= 0 then (.[0:m] + [n] + .[m:]), insert(m-1;n) else empty end;
if n==0 then []
elif n == 1 then [1]
else
permutations(n-1) | insert(n-1; n)
end;
# Count the number of items in a stream
def count(f): reduce f as $_ (0; .+1);</lang>
'''Part 2: The no-connections puzzle for N pegs and holes'''
<lang jq># Generate a stream of solutions.
# Input should be the connections array, i.e. an array of [i,j] pairs;
# N is the number of pegs and holds.
def solutions(N):
def abs: if . < 0 then -. else . end;
# Is the proposed permutation (the input) ok?
def ok(connections):
. as $p
| forall( connections;
(($p[.[0]] - $p[.[1]])|abs) != 1 );
. as $connections | permutations(N) | select(ok($connections);</lang>
'''Part 3: The 8-peg no-connection puzzle'''
<lang jq># The connectedness matrix:
# In this table, 0 represents "A", etc, and an entry [i,j]
# signifies that the holes with indices i and j are connected.
def connections:
[[0, 2], [0, 3], [0, 4],
[1, 3], [1, 4], [1, 5],
[6, 2], [6, 3], [6, 4],
[7, 3], [7, 4], [7, 5],
[2, 3], [3, 4], [4, 5]]
;
def solve:
connections | solutions(8);
# pretty-print a solution for the 8-peg puzzle
def pp:
def pegs: ["A", "B", "C", "D", "E", "F", "G", "H"];
. as $in
| ("
A B
/|\\ /|\\
/ | X | \\
/ |/ \\| \\
C - D - E - F
\\ |\\ /| /
\\ | X | /
\\|/ \\|/
G H
" | explode) as $board
| (pegs | map(explode)) as $letters
| $letters
| reduce range(0;length) as $i ($board; index($letters[$i]) as $ix | .[$ix] = $in[$i] + 48)
| implode;</lang>
'''Examples''':
<lang jq># To print all the solutions:
# solve | pp
# To count the number of solutions:
count(solve)</lang>
{{out}}
16
=={{header|Prolog}}==
| |||