Cut a rectangle: Difference between revisions
Added Wren
m (→optimized: added/changed comments and whitespace.) |
(Added Wren) |
||
Line 3,020:
}} 10</lang>
Output is identical.
=={{header|Wren}}==
{{trans|C}}
{{libheader|Wren-fmt}}
Last two are very slooow to emerge (just under 10 mins overall).
<lang ecmascript>import "/fmt" for Fmt
var grid = []
var w = 0
var h = 0
var len = 0
var cnt = 0
var next = [0] * 4
var dir = [[0, -1], [-1, 0], [0, 1], [1, 0]]
var walk // recursive
walk = Fn.new { |y, x|
if (y == 0 || y == h || x == 0 || x == w) {
cnt = cnt + 2
return
}
var t = y * (w + 1) + x
grid[t] = grid[t] + 1
grid[len-t] = grid[len-t] + 1
for (i in 0..3) {
if (grid[t + next[i]] == 0) {
System.write("") // guard against VM recursion bug
walk.call(y + dir[i][0], x + dir[i][1])
}
}
grid[t] = grid[t] - 1
grid[len-t] = grid[len-t] - 1
}
var solve // recursive
solve = Fn.new { |hh, ww, recur|
h = hh
w = ww
if (h&1 != 0) {
var t = w
w = h
h = t
}
if (h&1 != 0) return 0
if (w == 1) return 1
if (w == 2) return h
if (h == 2) return w
var cy = (h/2).floor
var cx = (w/2).floor
len = (h + 1) * (w + 1)
grid = List.filled(len, 0)
len = len - 1
next[0] = -1
next[1] = -w - 1
next[2] = 1
next[3] = w + 1
if (recur) cnt = 0
var x = cx + 1
while (x < w) {
var t = cy * (w + 1) + x
grid[t] = 1
grid[len-t] = 1
walk.call(cy - 1, x)
x = x + 1
}
cnt = cnt + 1
if (h == w) {
cnt = cnt * 2
} else if ((w&1 == 0) && recur) {
System.write("") // guard against VM recursion bug
solve.call(w, h, false)
}
return cnt
}
for (y in 1..10) {
for (x in 1..y) {
if ((x&1 == 0) || (y&1 ==0)) {
Fmt.print("$2d x $2d : $d", y, x, solve.call(y, x, true))
}
}
}</lang>
{{out}}
<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|zkl}}==
| |||