Cut a rectangle: Difference between revisions
→{{header|jq}}
m (→{{header|Wren}}: Minor tidy, reran with latest version.) |
|||
Line 1,850:
[0, 0, 2, 2]
[0, 0, 0, 0]</pre>
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]'''
{{works with|jq}}
The program below also works with gojq, the Go implementation of jq,
but gojq's memory consumption will likely limit progress beyond the 10 x 7
line shown below.
<syntaxhighlight lang="jq">
def dir: [[0, -1], [-1, 0], [0, 1], [1, 0]] ;
# input and output: {grid, w, h, len, count, next}
def mywalk($y; $x):
if ($y == 0 or $y == .h or $x == 0 or $x == .w)
then .count += 2
else ($y * (.w + 1) + $x) as $t
| .grid[$t] += 1
| .grid[.len-$t] += 1
| reduce range(0; 4) as $i (.;
if .grid[$t + .next[$i]] == 0
then mywalk($y + dir[$i][0]; $x + dir[$i][1])
else .
end )
| .grid[$t] += -1
| .grid[.len-$t] += -1
end;
# solve/3 returns an integer.
# If $count is null, the value is the count of permissible cuts for an $h x $w rectangle.
# Otherwise, the computed value augments $count.
def solve($h; $w; $count):
if $count then {$count} else {} end
| if $h % 2 == 0
then . + {$h, $w}
else . + {w: $h, h: $w} # swap
end
| if (.h % 2 == 1) then 0
elif (.w == 1) then 1
elif (.w == 2) then .h
elif (.h == 2) then .w
else ((.h/2)|floor) as $cy
| ((.w/2)|floor) as $cx
| .len = (.h + 1) * (.w + 1)
| .grid = [range(0; .len) | 0]
| .len += -1
| .next = [-1, - .w - 1, 1, .w + 1]
| .x = $cx + 1
| until (.x >= .w;
($cy * (.w + 1) + .x) as $t
| .grid[$t] = 1
| .grid[.len-$t] = 1
| mywalk($cy - 1; .x)
| .x += 1 )
| .count += 1
| if .h == .w
then .count * 2
elif (.w % 2 == 0) and $count == null
then solve(.w; .h; .count)
else .count
end
end ;
def task($n):
range (1; $n+1) as $y
| range(1; $y + 1) as $x
| select(($x % 2 == 0) or ($y % 2 == 0))
| "\($y) x \($x) : \(solve($y; $x; null))" ;
task(10)
</syntaxhighlight>
{{output}}
Invocation: jq -nrf cut-a-rectangle.jq
As with Wren, the last two lines are slow to emerge; the last line
(10x10) only emerged after several hours.
<pre>
2 x 1 : 1
2 x 2 : 2
3 x 2 : 3
4 x 1 : 1
4 x 2 : 4
4 x 3 : 9
4 x 4 : 22
5 x 2 : 5
5 x 4 : 39
6 x 1 : 1
6 x 2 : 6
6 x 3 : 23
6 x 4 : 90
6 x 5 : 263
6 x 6 : 1018
7 x 2 : 7
7 x 4 : 151
7 x 6 : 2947
8 x 1 : 1
8 x 2 : 8
8 x 3 : 53
8 x 4 : 340
8 x 5 : 1675
8 x 6 : 11174
8 x 7 : 55939
8 x 8 : 369050
9 x 2 : 9
9 x 4 : 553
9 x 6 : 31721
9 x 8 : 1812667
10 x 1 : 1
10 x 2 : 10
10 x 3 : 115
10 x 4 : 1228
10 x 5 : 10295
10 x 6 : 118276
10 x 7 : 1026005
10 x 8 : 11736888
10 x 9 : 99953769
10 x 10 : 1124140214
</pre>
=={{header|Julia}}==
| |||