Cut a rectangle

Cut a rectangle is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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>

1. include <stdlib.h>
2. 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>

1. 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);

1. 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("");

1. 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

Translation of: C

<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 second 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

Translation of: D

<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

Translation of: D

<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

Translation of: C

<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}]

}

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.