Cut a rectangle: Difference between revisions
(Removed first D entry, small improvements in remaining entry) |
(Fixed comment to D entry) |
||
Line 523: | Line 523: | ||
10 x 9: 99953769 |
10 x 9: 99953769 |
||
10 x 10: 1124140214</pre> |
10 x 10: 1124140214</pre> |
||
Using the DMD compiler it's about 20% faster than the |
Using the DMD compiler it's about 20% faster than the first GCC-C version. |
||
=={{header|J}}== |
=={{header|J}}== |
Revision as of 00:17, 11 February 2012
Given a rectangle made of m × n squares, if m and n are not both odd, it's possible to cut a path through the rectangle along the square edges such that the rectangle splits into two connected pieces with the same shape (after rotating one of them by 180°). All such paths for 2 × 2 and 4 × 3 rectangles are shown below.
Write a program to calculate the number of different ways to cut an m × n rectangle. Optionally, show each of the cuts.
Possibly related task: Maze generation for depth-first search.
C
Exhaustive search on the cutting path. Symmetric configurations are only calculated once, which helps with larger sized grids. <lang c>#include <stdio.h>
- include <stdlib.h>
- include <string.h>
typedef unsigned char byte; byte *grid = 0;
int w, h, len; unsigned long long cnt;
static int next[4], dir[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}}; void walk(int y, int x) { int i, t;
if (!y || y == h || !x || x == w) { cnt += 2; return; }
t = y * (w + 1) + x; grid[t]++, grid[len - t]++;
for (i = 0; i < 4; i++) if (!grid[t + next[i]]) walk(y + dir[i][0], x + dir[i][1]);
grid[t]--, grid[len - t]--; }
unsigned long long solve(int hh, int ww, int recur) { int t, cx, cy, x;
h = hh, w = ww;
if (h & 1) t = w, w = h, h = t; if (h & 1) return 0; if (w == 1) return 1; if (w == 2) return h; if (h == 2) return w;
cy = h / 2, cx = w / 2;
len = (h + 1) * (w + 1); grid = realloc(grid, len); memset(grid, 0, len--);
next[0] = -1; next[1] = -w - 1; next[2] = 1; next[3] = w + 1;
if (recur) cnt = 0; for (x = cx + 1; x < w; x++) { t = cy * (w + 1) + x; grid[t] = 1; grid[len - t] = 1; walk(cy - 1, x); } cnt++;
if (h == w) cnt *= 2; else if (!(w & 1) && recur) solve(w, h, 0);
return cnt; }
int main() { int y, x; for (y = 1; y <= 10; y++) for (x = 1; x <= y; x++) if (!(x & 1) || !(y & 1)) printf("%d x %d: %llu\n", y, x, solve(y, x, 1));
return 0; }</lang>output<lang>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</lang>
More awkward solution: after compiling, run ./a.out -v [width] [height]
for display of cuts.
<lang c>#include <stdio.h>
- include <stdlib.h>
typedef unsigned char byte; int w = 0, h = 0, verbose = 0; unsigned long count = 0;
byte **hor, **ver, **vis; byte **c = 0;
enum { U = 1, D = 2, L = 4, R = 8 };
byte ** alloc2(int w, int h) { int i; byte **x = calloc(1, sizeof(byte*) * h + h * w); x[0] = (byte *)&x[h]; for (i = 1; i < h; i++) x[i] = x[i - 1] + w; return x; }
void show() { int i, j, v, last_v; printf("%ld\n", count);
- if 0
for (i = 0; i <= h; i++) { for (j = 0; j <= w; j++) printf("%d ", hor[i][j]); puts(""); } puts("");
for (i = 0; i <= h; i++) { for (j = 0; j <= w; j++) printf("%d ", ver[i][j]); puts(""); } puts("");
- endif
for (i = 0; i < h; i++) { if (!i) v = last_v = 0; else last_v = v = hor[i][0] ? !last_v : last_v;
for (j = 0; j < w; v = ver[i][++j] ? !v : v) printf(v ? "\033[31m[]" : "\033[33m{}"); puts("\033[m"); } putchar('\n'); }
void walk(int y, int x) { if (x < 0 || y < 0 || x > w || y > h) return;
if (!x || !y || x == w || y == h) { ++count; if (verbose) show(); return; }
if (vis[y][x]) return; vis[y][x]++; vis[h - y][w - x]++;
if (x && !hor[y][x - 1]) { hor[y][x - 1] = hor[h - y][w - x] = 1; walk(y, x - 1); hor[y][x - 1] = hor[h - y][w - x] = 0; } if (x < w && !hor[y][x]) { hor[y][x] = hor[h - y][w - x - 1] = 1; walk(y, x + 1); hor[y][x] = hor[h - y][w - x - 1] = 0; }
if (y && !ver[y - 1][x]) { ver[y - 1][x] = ver[h - y][w - x] = 1; walk(y - 1, x); ver[y - 1][x] = ver[h - y][w - x] = 0; }
if (y < h && !ver[y][x]) { ver[y][x] = ver[h - y - 1][w - x] = 1; walk(y + 1, x); ver[y][x] = ver[h - y - 1][w - x] = 0; }
vis[y][x]--; vis[h - y][w - x]--; }
void cut(void) { if (1 & (h * w)) return;
hor = alloc2(w + 1, h + 1); ver = alloc2(w + 1, h + 1); vis = alloc2(w + 1, h + 1);
if (h & 1) { ver[h/2][w/2] = 1; walk(h / 2, w / 2); } else if (w & 1) { hor[h/2][w/2] = 1; walk(h / 2, w / 2); } else { vis[h/2][w/2] = 1;
hor[h/2][w/2-1] = hor[h/2][w/2] = 1; walk(h / 2, w / 2 - 1); hor[h/2][w/2-1] = hor[h/2][w/2] = 0;
ver[h/2 - 1][w/2] = ver[h/2][w/2] = 1; walk(h / 2 - 1, w/2); } }
void cwalk(int y, int x, int d) { if (!y || y == h || !x || x == w) { ++count; return; } vis[y][x] = vis[h-y][w-x] = 1;
if (x && !vis[y][x-1]) cwalk(y, x - 1, d|1); if ((d&1) && x < w && !vis[y][x+1]) cwalk(y, x + 1, d|1); if (y && !vis[y-1][x]) cwalk(y - 1, x, d|2); if ((d&2) && y < h && !vis[y + 1][x]) cwalk(y + 1, x, d|2);
vis[y][x] = vis[h-y][w-x] = 0; }
void count_only(void) { int t; long res; if (h * w & 1) return; if (h & 1) t = h, h = w, w = t;
vis = alloc2(w + 1, h + 1); vis[h/2][w/2] = 1;
if (w & 1) vis[h/2][w/2 + 1] = 1; if (w > 1) { cwalk(h/2, w/2 - 1, 1); res = 2 * count - 1; count = 0; if (w != h) cwalk(h/2+1, w/2, (w & 1) ? 3 : 2);
res += 2 * count - !(w & 1); } else { res = 1; } if (w == h) res = 2 * res + 2; count = res; }
int main(int c, char **v) { int i;
for (i = 1; i < c; i++) { if (v[i][0] == '-' && v[i][1] == 'v' && !v[i][2]) { verbose = 1; } else if (!w) { w = atoi(v[i]); if (w <= 0) goto bail; } else if (!h) { h = atoi(v[i]); if (h <= 0) goto bail; } else goto bail; } if (!w) goto bail; if (!h) h = w;
if (verbose) cut(); else count_only();
printf("Total: %ld\n", count); return 0;
bail: fprintf(stderr, "bad args\n"); return 1; }</lang>
Common Lisp
Count only. <lang lisp>(defun cut-it (w h &optional (recur t))
(if (oddp (* w h)) (return-from cut-it 0)) (if (oddp h) (rotatef w h)) (if (= w 1) (return-from cut-it h))
(let ((cnt 0)
(m (make-array (list (1+ h) (1+ w)) :element-type 'bit :initial-element 0)) (cy (truncate h 2)) (cx (truncate w 2)))
(setf (aref m cy cx) 1) (if (oddp w) (setf (aref m cy (1+ cx)) 1))
(labels ((walk (y x turned)
(when (or (= y 0) (= y h) (= x 0) (= x w)) (incf cnt (if turned 2 1)) (return-from walk))
(setf (aref m y x) 1) (setf (aref m (- h y) (- w x)) 1) (loop for i from 0 for (dy dx) in '((0 -1) (-1 0) (0 1) (1 0)) while (or turned (< i 2)) do (let ((y2 (+ y dy)) (x2 (+ x dx))) (when (zerop (aref m y2 x2)) (walk y2 x2 (or turned (> i 0)))))) (setf (aref m (- h y) (- w x)) 0) (setf (aref m y x) 0)))
(walk cy (1- cx) nil) (cond ((= h w) (incf cnt cnt))
((oddp w) (walk (1- cy) cx t)) (recur (incf cnt (cut-it h w nil))))
cnt)))
(loop for w from 1 to 9 do
(loop for h from 1 to w do
(if (evenp (* w h)) (format t "~d x ~d: ~d~%" w h (cut-it w h)))))</lang>output<lang>2 x 1: 2 2 x 2: 2 3 x 2: 3 4 x 1: 4 4 x 2: 4 4 x 3: 9 4 x 4: 22 5 x 2: 5 5 x 4: 39 6 x 1: 6 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: 8 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</lang>
D
<lang d>import core.stdc.stdio, core.stdc.stdlib,
core.stdc.string, std.typetuple;
template Range(int stop) {
static if (stop <= 0) alias TypeTuple!() Range; else alias TypeTuple!(Range!(stop-1), stop-1) Range;
}
__gshared enum int[2][4] dir = [[0, -1], [-1, 0], [0, 1], [1, 0]];
__gshared ubyte* grid; __gshared int w, h, len; __gshared ulong cnt; __gshared int[4] next;
void walk(in int y, in int x) nothrow {
if (!y || y == h || !x || x == w) { cnt += 2; return; }
immutable int t = y * (w + 1) + x; grid[t]++; grid[len - t]++;
foreach (i; Range!4) // manual loop unroll if (!grid[t + next[i]]) walk(y + dir[i][0], x + dir[i][1]);
grid[t]--; grid[len - t]--;
}
ulong solve(in int hh, in int ww, in bool recur) nothrow {
h = (hh & 1) ? ww : hh; w = (hh & 1) ? hh : ww;
if (h & 1) return 0; if (w == 1) return 1; if (w == 2) return h; if (h == 2) return w;
immutable int cy = h / 2; immutable int cx = w / 2;
len = (h + 1) * (w + 1); grid = cast(ubyte*)alloca(len); if (grid == null) exit(1); memset(grid, 0, len); len--;
next[0] = -1; next[1] = -w - 1; next[2] = 1; next[3] = w + 1;
if (recur) cnt = 0; foreach (x; cx + 1 .. w) { immutable int t = cy * (w + 1) + x; grid[t] = 1; grid[len - t] = 1; walk(cy - 1, x); } cnt++;
if (h == w) cnt *= 2; else if (!(w & 1) && recur) solve(w, h, 0);
return cnt;
}
void main() {
foreach (y; 1 .. 11) foreach (x; 1 .. y + 1) if (!(x & 1) || !(y & 1)) printf("%d x %d: %llu\n", y, x, solve(y, x, true));
}</lang> Output:
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
Using the DMD compiler it's about 20% faster than the first GCC-C version.
J
<lang j>init=: - {. 1: NB. initial state: 1 square choosen prop=: < {:,~2 ~:/\ ] NB. propagate: neighboring squares (vertically) poss=: I.@,@(prop +. prop"1 +. prop&.|. +. prop&.|."1) keep=: poss -. <:@#@, - I.@, NB. symmetrically valid possibilities N=: <:@-:@#@, NB. how many neighbors to add step=: [: ~.@; <@(((= i.@$) +. ])"0 _~ keep)"2 all=: step^:N@init</lang>
In other words, starting with a boolean matrix with one true square in one corner, make a list of all false squares which neighbor a true square, and then make each of those neighbors true, independently (discarding duplicate matrices from the resulting sequence of boolean matrices), and repeat this N times where N is (total cells divided by two)-1. Then discard those matrices where inverting them (boolean not), then flipping on horizontal and vertical axis is not an identity.
(In other words, this implementation uses a breadth first search -- breadth first searches tend to be natural in J because of the parallelism they offer.)
Example use:
<lang j> '.#' <"2@:{~ all 3 4 ┌────┬────┬────┬────┬────┬────┬────┬────┬────┐ │.###│.###│..##│...#│...#│....│....│....│....│ │.#.#│..##│..##│..##│.#.#│..##│.#.#│#.#.│##..│ │...#│...#│..##│.###│.###│####│####│####│####│ └────┴────┴────┴────┴────┴────┴────┴────┴────┘
$ all 4 5
39 4 5
3 13$ '.#' <"2@:{~ all 4 5
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐ │.####│.####│.####│.####│.####│.####│..###│..###│..###│..###│..###│...##│...##│ │.####│.##.#│.#..#│..###│...##│....#│.####│.##.#│..###│...##│....#│.####│..###│ │....#│.#..#│.##.#│...##│..###│.####│....#│.#..#│...##│..###│.####│....#│...##│ │....#│....#│....#│....#│....#│....#│...##│...##│...##│...##│...##│..###│..###│ ├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤ │...##│...##│...##│....#│....#│....#│....#│....#│....#│.....│.....│.....│.....│ │...##│....#│.#..#│.####│..###│...##│....#│.#..#│.##.#│.####│..###│...##│....#│ │..###│.####│.##.#│....#│...##│..###│.####│.##.#│.#..#│....#│...##│..###│.####│ │..###│..###│..###│.####│.####│.####│.####│.####│.####│#####│#####│#####│#####│ ├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤ │.....│.....│.....│.....│.....│.....│.....│.....│.....│.....│.....│.....│.....│ │.#..#│.##.#│..##.│...#.│.....│.#...│.##..│#.##.│#..#.│#....│##...│###..│####.│ │.##.#│.#..#│#..##│#.###│#####│###.#│##..#│#..#.│#.##.│####.│###..│##...│#....│ │#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│ └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘</lang>
Python
<lang python>def cut_it(h, w):
dirs = ((1, 0), (-1, 0), (0, -1), (0, 1)) if h & 1: h, w = w, h if h & 1: return 0 if w == 1: return 1 count = 0
next = [w + 1, -w - 1, -1, 1] blen = (h + 1) * (w + 1) - 1 grid = [False] * (blen + 1)
def walk(y, x, count): if not y or y == h or not x or x == w: return count + 1
t = y * (w + 1) + x grid[t] = grid[blen - t] = True
if not grid[t + next[0]]: count = walk(y + dirs[0][0], x + dirs[0][1], count) if not grid[t + next[1]]: count = walk(y + dirs[1][0], x + dirs[1][1], count) if not grid[t + next[2]]: count = walk(y + dirs[2][0], x + dirs[2][1], count) if not grid[t + next[3]]: count = walk(y + dirs[3][0], x + dirs[3][1], count)
grid[t] = grid[blen - t] = False return count
t = h // 2 * (w + 1) + w // 2 if w & 1: grid[t] = grid[t + 1] = True count = walk(h // 2, w // 2 - 1, count) res = count count = 0 count = walk(h // 2 - 1, w // 2, count) return res + count * 2 else: grid[t] = True count = walk(h // 2, w // 2 - 1, count) if h == w: return count * 2 count = walk(h // 2 - 1, w // 2, count) return count
def main():
for w in xrange(1, 10): for h in xrange(1, w + 1): if not((w * h) & 1): print "%d x %d: %d" % (w, h, cut_it(w, h))
main()</lang> Output:
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
Faster version
<lang python>try:
import psyco
except ImportError:
pass
else:
psyco.full()
w, h = 0, 0 count = 0 vis = []
def cwalk(y, x, d):
global vis, count, w, h if not y or y == h or not x or x == w: count += 1 return
vis[y][x] = vis[h - y][w - x] = 1
if x and not vis[y][x - 1]: cwalk(y, x - 1, d | 1) if (d & 1) and x < w and not vis[y][x+1]: cwalk(y, x + 1, d|1) if y and not vis[y - 1][x]: cwalk(y - 1, x, d | 2) if (d & 2) and y < h and not vis[y + 1][x]: cwalk(y + 1, x, d | 2)
vis[y][x] = vis[h - y][w - x] = 0
def count_only(x, y):
global vis, count, w, h count = 0 w = x h = y
if (h * w) & 1: return count if h & 1: w, h = h, w
vis = [[0] * (w + 1) for _ in xrange(h + 1)] vis[h // 2][w // 2] = 1
if w & 1: vis[h // 2][w // 2 + 1] = 1
res = 0 if w > 1: cwalk(h // 2, w // 2 - 1, 1) res = 2 * count - 1 count = 0 if w != h: cwalk(h // 2 + 1, w // 2, 3 if (w & 1) else 2)
res += 2 * count - (not (w & 1)) else: res = 1
if w == h: res = 2 * res + 2 return res
def main():
for y in xrange(1, 10): for x in xrange(1, y + 1): if not (x & 1) or not (y & 1): print "%d x %d: %d" % (y, x, count_only(x, y))
main()</lang> The output is the same.
Tcl
<lang tcl>package require Tcl 8.5
proc walk {y x} {
global w ww h cnt grid len if {!$y || $y==$h || !$x || $x==$w} {
incr cnt 2 return
} set t [expr {$y*$ww + $x}] set m [expr {$len - $t}] lset grid $t [expr {[lindex $grid $t] + 1}] lset grid $m [expr {[lindex $grid $m] + 1}] if {![lindex $grid [expr {$y*$ww + $x-1}]]} {
walk $y [expr {$x-1}]
} if {![lindex $grid [expr {($y-1)*$ww + $x}]]} {
walk [expr {$y-1}] $x
} if {![lindex $grid [expr {$y*$ww + $x+1}]]} {
walk $y [expr {$x+1}]
} if {![lindex $grid [expr {($y+1)*$ww + $x}]]} {
walk [expr {$y+1}] $x
} lset grid $t [expr {[lindex $grid $t] - 1}] lset grid $m [expr {[lindex $grid $m] - 1}]
}
- Factored out core of [solve]
proc SolveCore {} {
global w ww h cnt grid len set ww [expr {$w+1}] set cy [expr {$h / 2}] set cx [expr {$w / 2}]
set len [expr {($h+1) * $ww}] set grid [lrepeat $len 0] incr len -1
for {set x $cx;incr x} {$x < $w} {incr x} {
set t [expr {$cy*$ww+$x}] lset grid $t 1 lset grid [expr {$len - $t}] 1 walk [expr {$cy - 1}] $x
} incr cnt
} proc solve {H W} {
global w h cnt set h $H set w $W if {$h & 1} {
set h $W set w $H
} if {$h & 1} {
return 0
} if {$w==1} {return 1} if {$w==2} {return $h} if {$h==2} {return $w}
set cnt 0 SolveCore if {$h==$w} {
incr cnt $cnt
} elseif {!($w & 1)} {
lassign [list $w $h] h w SolveCore
} return $cnt
}
apply {{limit} {
for {set yy 1} {$yy <= $limit} {incr yy} {
for {set xx 1} {$xx <= $yy} {incr xx} { if {!($xx&1 && $yy&1)} { puts [format "%d x %d: %ld" $yy $xx [solve $yy $xx]] } }
}
}} 10</lang> Output is identical.