Cut a rectangle: Difference between revisions
Content added Content deleted
m (→{{header|Wren}}: Minor tidy, reran with latest version.) |
|||
Line 1,850: | Line 1,850: | ||
[0, 0, 2, 2] |
[0, 0, 2, 2] |
||
[0, 0, 0, 0]</pre> |
[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}}== |
=={{header|Julia}}== |