Solve the no connection puzzle: Difference between revisions

Content added Content deleted
No edit summary
(→‎{{header|jq}}: revise for jq 1.6)
Line 2,564: Line 2,564:


=={{header|jq}}==
=={{header|jq}}==
{{works with|jq|1.4}}
{{works with|jq|1.6}}
'''Also works with gojq, the Go implementation of jq'''

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
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.
array.
Line 2,574: Line 2,576:


'''Part 1: Generic functions'''
'''Part 1: Generic functions'''
<syntaxhighlight lang="jq"># Short-circuit determination of whether (a|condition)
<syntaxhighlight lang="jq">
⚫
# permutations of 0 .. (n-1) inclusive
# 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):
def permutations(n):
# Given a single array, generate a stream by inserting n at different positions:
# Given a single array, generate a stream by inserting n at different positions:
Line 2,597: Line 2,589:


# Count the number of items in a stream
# Count the number of items in a stream
def count(f): reduce f as $_ (0; .+1);</syntaxhighlight>
def count(f): reduce f as $_ (0; .+1);
</syntaxhighlight>

'''Part 2: The no-connections puzzle for N pegs and holes'''
'''Part 2: The no-connections puzzle for N pegs and holes'''
<syntaxhighlight lang="jq"># Generate a stream of solutions.
<syntaxhighlight lang="jq">
# Generate a stream of solutions.
# Input should be the connections array, i.e. an array of [i,j] pairs;
# Input should be the connections array, i.e. an array of [i,j] pairs;
# N is the number of pegs and holds.
# N is the number of pegs and holds.
Line 2,609: Line 2,602:
def ok(connections):
def ok(connections):
. as $p
. as $p
| forall( connections;
| all( connections[];
(($p[.[0]] - $p[.[1]])|abs) != 1 );
(($p[.[0]] - $p[.[1]])|abs) != 1 );


. as $connections | permutations(N) | select(ok($connections);</syntaxhighlight>
. as $connections | permutations(N) | select(ok($connections));
</syntaxhighlight>
'''Part 3: The 8-peg no-connection puzzle'''
'''Part 3: The 8-peg no-connection puzzle'''
<syntaxhighlight lang="jq"># The connectedness matrix:
<syntaxhighlight lang="jq">
# The connectedness matrix
# In this table, 0 represents "A", etc, and an entry [i,j]
# In this table, 0 represents "A", etc, and an entry [i,j]
# signifies that the holes with indices i and j are connected.
# signifies that the holes with indices i and j are connected.
Line 2,653: Line 2,648:
# To count the number of solutions:
# To count the number of solutions:
# count(solve)
# count(solve)
# => 16


⚫
limit(1; solve) | pp
# jq 1.4 lacks facilities for harnessing generators,
# but the following will suffice here:
def one(f): reduce f as $s
(null; if . == null then $s else . end);

⚫
one(solve) | pp
</syntaxhighlight>
</syntaxhighlight>
{{out}}
{{output}}
<syntaxhighlight lang="sh">$ jq -n -r -f no_connection.jq
Invocation: jq -n -r -f no_connection.jq
<pre>

5 6
5 6
/|\ /|\
/|\ /|\
Line 2,672: Line 2,663:
\ | X | /
\ | X | /
\|/ \|/
\|/ \|/
3 4</syntaxhighlight>
3 4
</pre>


=={{header|Julia}}==
=={{header|Julia}}==
Retrieved from "https://rosettacode.org/wiki/Solve_the_no_connection_puzzle"