|
9 x 8: 1812667</lang>
=={{header|D}}==
{{trans|C}}
<lang d>import core.stdc.stdio: printf;
bool isEven(T)(in T x) pure nothrow { return !isOdd(x); }
bool isOdd(T)(in T x) pure nothrow { return x % 2 != 0; }
size_t cutIt(in int hh, in int ww) pure nothrow {
immutable int h = isEven(hh) ? hh : ww;
immutable int w = isEven(hh) ? ww : hh;
if (isOdd(h)) return 0;
if (w == 1) return 1;
immutable int[4] next = [w + 1, -w - 1, -1, 1];
immutable int len = (h + 1) * (w + 1) - 1;
auto grid = new bool[len + 1];
size_t count;
void walk(in int y, in int x) nothrow {
enum int[2][4] dirs = [[1, 0], [-1, 0], [0, -1], [0, 1]];
if (!y || y == h || !x || x == w) {
count++;
return;
}
immutable int t = y * (w + 1) + x;
grid[t] = grid[len - t] = true;
// Manually unrolled loop
if (!grid[t + next[0]]) walk(y + dirs[0][0], x + dirs[0][1]);
if (!grid[t + next[1]]) walk(y + dirs[1][0], x + dirs[1][1]);
if (!grid[t + next[2]]) walk(y + dirs[2][0], x + dirs[2][1]);
if (!grid[t + next[3]]) walk(y + dirs[3][0], x + dirs[3][1]);
grid[t] = grid[len - t] = false;
}
immutable int t = h / 2 * (w + 1) + w / 2;
if (isOdd(w)) {
grid[t] = grid[t + 1] = true;
walk(h / 2, w / 2 - 1);
immutable res = count;
count = 0;
walk(h / 2 - 1, w / 2);
return res + count * 2;
} else {
grid[t] = true;
walk(h / 2, w / 2 - 1);
if (h == w)
return count * 2;
walk(h / 2 - 1, w / 2);
return count;
}
}
void main() {
foreach (w; 1 .. 11)
foreach (h; 1 .. w + 1)
if (isEven(w * h))
printf("%d x %d: %zd\n", w, h, cutIt(w, h));
}</lang>
Output:
<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>
With DMD compiler it is about twice slower than the first C version, and with LDC compiler it is about 40% faster than the first C version.
===Faster version===
{{trans|C}}
<lang d>import core.stdc.stdio, core.stdc.stdlib,
core.stdc.string, std.typetuple, std.algorithm;
template Range(int stop) {
}
ulong solve(in int hh, in int ww, in intbool recur) nothrow {
h = (hh & 1) ? ww : hh;
w = (hh & 1) ? hh : ww;
if (h & 1) swap(w, h);
if (h & 1) return 0;
if (w == 1) return 1;
len = (h + 1) * (w + 1);
grid = cast(ubyte*)alloca(len);
memsetif (grid, 0,== len--null);
exit(1);
memset(grid, 0, len);
len--;
next[0] = -1;
foreach (x; 1 .. y + 1)
if (!(x & 1) || !(y & 1))
printf("%d x %d: %llu\n", y, x, solve(y, x, 1true));
}</lang>
Output:
About 20% faster than the second C version using the DMD compiler. The output is the same as the first version.
<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>
Using the DMD compiler it's about 20% faster than the second GCC-C version.
=={{header|J}}==
|