4-rings or 4-squares puzzle: Difference between revisions
→{{header|jq}}
Alextretyak (talk | contribs) (→{{header|11l}}: Shortened version) |
|||
Line 3,231:
2860</pre>
=={{header|jq}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
Since jq is built on back-tracking and optimizes the tail-recursion involved here,
this entry will focus on a generic solution for problems of this sort.
Specifically, the number of boxes is unrestricted, as is the pattern of overlaps.
For simplicity, we will associate the letters "a", "b", ... with the integers 0, 1,...
so that each box can be represented as an array of integers; the
puzzle configuration can then be characterized by an array of such arrays.
For the particular puzzle under consideration, the characteristic array is:
[[0,1], [1,2,3], [3,4,5], [5,6]]
The solution presented here is quite efficient for the family of problems based on permutations.
<lang jq># Generate a stream of all the permutations of the input array
def permutations:
if length == 0 then []
else
range(0;length) as $i
| [.[$i]] + (del(.[$i])|permutations)
end ;
# Permutations of a ... n inclusive
def permutations(a;n):
[range(a;n+1)] | permutations;
# value of a box
# Input: the table of values
def valueOfBox($box):
[ .[ $box[] ]] | add;
def allEqual($boxes):
. as $values
| valueOfBox($boxes[0]) as $sum
| all($boxes[1:][]; . as $box | $values | valueOfBox($box) == $sum);
def combinations($m; $n; $size):
[range(0; $size) | [range($m; $n)]] | combinations;
def count(s): reduce s as $x (null; .+1);
# a=0, b=1, etc
def boxes: [[0,1], [1,2,3], [3,4,5], [5,6]];
def tasks:
"1 to 7:",
(permutations(1;7) | select(allEqual(boxes))),
"\n3 to 9:",
(permutations(3;9) | select(allEqual(boxes))),
"\n0 to 9:\n\(count(permutations(0;9) | select(allEqual(boxes))))",
"\nThere are \(count(combinations(0;10;7) | select(allEqual(boxes)))) solutions for 0 to 9 with replacement."
;
tasks</lang>
{{out}}
<pre>
1 to 7:
[3,7,2,1,5,4,6]
[4,5,3,1,6,2,7]
[4,7,1,3,2,6,5]
[5,6,2,3,1,7,4]
[6,4,1,5,2,3,7]
[6,4,5,1,2,7,3]
[7,2,6,1,3,5,4]
[7,3,2,5,1,4,6]
3 to 9:
[7,8,3,4,5,6,9]
[8,7,3,5,4,6,9]
[9,6,4,5,3,7,8]
[9,6,5,4,3,8,7]
There are 1152 distinct solutions for 0 to 9.
There are 2860 solutions for 0 to 9 with replacement.
</pre>
=={{header|Julia}}==
| |||