4-rings or 4-squares puzzle: Difference between revisions
→{{header|jq}}
Line 3,237:
Since jq is built on back-tracking and optimizes the tail-recursion involved here,
this entry will focus on
Specifically, the number of boxes is unrestricted
====N rings with arbitrary overlaps====
For simplicity, we will associate the letters "a", "b", ... with the integers 0, 1,...▼
In this section, an arbitrary pattern of overlaps can be specified as follows.
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.
Line 3,247 ⟶ 3,250:
[[0,1], [1,2,3], [3,4,5], [5,6]]
The solution
<lang jq># Generate a stream of all the permutations of the input array
def permutations:
Line 3,310 ⟶ 3,313:
There are 2860 solutions for 0 to 9 with replacement.
</pre>
====N boxes with one overlap between adjacent boxes and no uniqueness constraint====
In this subsection, an efficient solution for the N-boxes puzzle in the case of non-uniqueness
(i.e. unrestricted choice of values within the specified range) is given. It is assumed, however,
that each box (except for the last) has exactly one overlap with its successor.
For consistency with the prior section, the pattern can be specified in the same way,
i.e. as a characteristic array, which for the specific problem at hand could be:
[[0,1], [1,2,3], [3,4,5], [5,6]].
<lang jq># rings/3 assumes that each box (except for the last) has exactly one overlap with its successor.
# Input: ignored.
# Output: a stream of solutions, i.e. a stream of arrays.
# $boxes is an array of boxes, each box being a flat array.
# $min and $max define the range of permissible values of items in the boxes (inclusive)
def rings($boxes; $min; $max):
def inrange: $min <= . and . <= $max;
# The following helper function deals with the case when the global per-box sum ($sum) is known.
# Input: an array representing the solution so far, or null.
# Output: the input plus the solution corresponding to the first argument.
# $this is the sum of the previous items in the first box, or 0.
def solve($boxes; $this; $sum):
# The following is a helper function for handling the case when:
# * $sum is known
# * $boxes[0] | length == 1, and
# * $boxes|length>1
def lastInBox($boxes; $this):
. as $in
| ($boxes[1:] | (.[0] |= .[1:])) as $bx
# the first entry in the next box must be the same:
| ($sum - $this) as $next
| select($next | inrange)
| (. + [$next]) | solve( $bx; $next; $sum) ;
. as $in
| if $boxes|length == 0 then $in
else $boxes[0] as $box
| if $box|length == 0
then solve( $boxes[1:]; 0; $sum )
elif $box|length == 1
# is this the last box?
then if $boxes|length == 1
then ($sum - $this) as $next
| select($next | inrange)
| $in + [$next]
else lastInBox($boxes; $this)
end
else # $box|length > 1
range($min; $max + 1) as $first
| select( ($this + $first) <= $sum)
| ($in + [$first]) | solve( [$box[1:]] + $boxes[1:]; $this + $first; $sum)
end
end ;
. as $in
| $boxes[0] as $box
| ($boxes[1:] | .[0] |= .[1:]) as $bx
| [range(0; $box|length) | [range($min; $max + 1)]]
| combinations
| solve($bx; .[-1]; add) ;
def count(s): reduce s as $x (null; .+1);
#'''The specific task'''
# a=0, b=1, etc
def boxes: [[0,1], [1,2,3], [3,4,5], [5,6]];
count(rings(boxes; 0; 9))</lang>
{{out}}
<pre>
2860
</pre>
=={{header|Julia}}==
| |||