Cut a rectangle: Difference between revisions
Content deleted Content added
Updated D entry |
|||
| (99 intermediate revisions by 31 users not shown) | |||
Line 1:
{{
[[file:rect-cut.svg]]
Write a program
Possibly related task: [[Maze generation]] for depth-first search.
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F cut_it(=h, =w)
V dirs = [(1, 0), (-1, 0), (0, -1), (0, 1)]
I h % 2 != 0
swap(&h, &w)
I h % 2 != 0
R 0
I w == 1
R 1
V count = 0
V next = [w + 1, -w - 1, -1, 1]
V blen = (h + 1) * (w + 1) - 1
V grid = [0B] * (blen + 1)
F walk(Int y, x, =count) -> Int
I y == 0 | y == @h | x == 0 | x == @w
R count + 1
V t = y * (@w + 1) + x
@grid[t] = @grid[@blen - t] = 1B
L(i) 4
I !@grid[t + @next[i]]
count = @walk(y + @dirs[i][0], x + @dirs[i][1], count)
@grid[t] = @grid[@blen - t] = 0B
R count
V t = h I/ 2 * (w + 1) + w I/ 2
I w % 2 != 0
grid[t] = grid[t + 1] = 1B
count = walk(h I/ 2, w I/ 2 - 1, count)
V res = count
count = 0
count = walk(h I/ 2 - 1, w I/ 2, count)
R res + count * 2
E
grid[t] = 1B
count = walk(h I/ 2, w I/ 2 - 1, count)
I h == w
R count * 2
count = walk(h I/ 2 - 1, w I/ 2, count)
R count
L(w) 1..9
L(h) 1..w
I (w * h) % 2 == 0
print(‘#. x #.: #.’.format(w, h, cut_it(w, h)))</syntaxhighlight>
{{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
</pre>
=={{header|C}}==
Exhaustive search on the cutting path. Symmetric configurations are only calculated once, which helps with larger sized grids.
<
#include <stdlib.h>
#include <string.h>
Line 89 ⟶ 175:
return 0;
}</
2 x 2: 2
3 x 2: 3
Line 128 ⟶ 214:
10 x 8: 11736888
10 x 9: 99953769
10 x 10: 1124140214</
More awkward solution: after compiling, run <code>./a.out -v [width] [height]</code> for display of cuts.
<
#include <stdlib.h>
Line 321 ⟶ 407:
bail: fprintf(stderr, "bad args\n");
return 1;
}</
=={{header|C#}}==
{{trans|Java}}
<syntaxhighlight lang="C#">
using System;
using System.Collections.Generic;
public class CutRectangle
{
private static int[][] dirs = new int[][] { new int[] { 0, -1 }, new int[] { -1, 0 }, new int[] { 0, 1 }, new int[] { 1, 0 } };
public static void Main(string[] args)
{
CutRectangleMethod(2, 2);
CutRectangleMethod(4, 3);
}
static void CutRectangleMethod(int w, int h)
{
if (w % 2 == 1 && h % 2 == 1)
return;
int[,] grid = new int[h, w];
Stack<int> stack = new Stack<int>();
int half = (w * h) / 2;
long bits = (long)Math.Pow(2, half) - 1;
for (; bits > 0; bits -= 2)
{
for (int i = 0; i < half; i++)
{
int r = i / w;
int c = i % w;
grid[r, c] = (bits & (1L << i)) != 0 ? 1 : 0;
grid[h - r - 1, w - c - 1] = 1 - grid[r, c];
}
stack.Push(0);
grid[0, 0] = 2;
int count = 1;
while (stack.Count > 0)
{
int pos = stack.Pop();
int r = pos / w;
int c = pos % w;
foreach (var dir in dirs)
{
int nextR = r + dir[0];
int nextC = c + dir[1];
if (nextR >= 0 && nextR < h && nextC >= 0 && nextC < w)
{
if (grid[nextR, nextC] == 1)
{
stack.Push(nextR * w + nextC);
grid[nextR, nextC] = 2;
count++;
}
}
}
}
if (count == half)
{
PrintResult(grid, h, w);
}
}
}
static void PrintResult(int[,] arr, int height, int width)
{
for (int i = 0; i < height; i++)
{
for (int j = 0; j < width; j++)
{
Console.Write(arr[i, j] + (j == width - 1 ? "" : ", "));
}
Console.WriteLine();
}
Console.WriteLine();
}
}
</syntaxhighlight>
{{out}}
<pre>
2, 2
0, 0
2, 0
2, 0
2, 2, 2, 2
2, 2, 0, 0
0, 0, 0, 0
2, 2, 2, 0
2, 2, 0, 0
2, 0, 0, 0
2, 2, 0, 0
2, 2, 0, 0
2, 2, 0, 0
2, 0, 0, 0
2, 2, 0, 0
2, 2, 2, 0
2, 2, 2, 2
0, 2, 0, 2
0, 0, 0, 0
2, 2, 2, 2
2, 0, 2, 0
0, 0, 0, 0
2, 2, 2, 0
2, 0, 2, 0
2, 0, 0, 0
2, 0, 0, 0
2, 0, 2, 0
2, 2, 2, 0
2, 2, 2, 2
0, 0, 2, 2
0, 0, 0, 0
</pre>
=={{header|C++}}==
{{trans|Java}}
<syntaxhighlight lang="cpp">#include <array>
#include <iostream>
#include <stack>
#include <vector>
const std::array<std::pair<int, int>, 4> DIRS = {
std::make_pair(0, -1),
std::make_pair(-1, 0),
std::make_pair(0, 1),
std::make_pair(1, 0),
};
void printResult(const std::vector<std::vector<int>> &v) {
for (auto &row : v) {
auto it = row.cbegin();
auto end = row.cend();
std::cout << '[';
if (it != end) {
std::cout << *it;
it = std::next(it);
}
while (it != end) {
std::cout << ", " << *it;
it = std::next(it);
}
std::cout << "]\n";
}
}
void cutRectangle(int w, int h) {
if (w % 2 == 1 && h % 2 == 1) {
return;
}
std::vector<std::vector<int>> grid(h, std::vector<int>(w));
std::stack<int> stack;
int half = (w * h) / 2;
long bits = (long)pow(2, half) - 1;
for (; bits > 0; bits -= 2) {
for (int i = 0; i < half; i++) {
int r = i / w;
int c = i % w;
grid[r][c] = (bits & (1 << i)) != 0 ? 1 : 0;
grid[h - r - 1][w - c - 1] = 1 - grid[r][c];
}
stack.push(0);
grid[0][0] = 2;
int count = 1;
while (!stack.empty()) {
int pos = stack.top();
stack.pop();
int r = pos / w;
int c = pos % w;
for (auto dir : DIRS) {
int nextR = r + dir.first;
int nextC = c + dir.second;
if (nextR >= 0 && nextR < h && nextC >= 0 && nextC < w) {
if (grid[nextR][nextC] == 1) {
stack.push(nextR * w + nextC);
grid[nextR][nextC] = 2;
count++;
}
}
}
}
if (count == half) {
printResult(grid);
std::cout << '\n';
}
}
}
int main() {
cutRectangle(2, 2);
cutRectangle(4, 3);
return 0;
}</syntaxhighlight>
{{out}}
<pre>[2, 2]
[0, 0]
[2, 0]
[2, 0]
[2, 2, 2, 2]
[2, 2, 0, 0]
[0, 0, 0, 0]
[2, 2, 2, 0]
[2, 2, 0, 0]
[2, 0, 0, 0]
[2, 2, 0, 0]
[2, 2, 0, 0]
[2, 2, 0, 0]
[2, 0, 0, 0]
[2, 2, 0, 0]
[2, 2, 2, 0]
[2, 2, 2, 2]
[0, 2, 0, 2]
[0, 0, 0, 0]
[2, 2, 2, 2]
[2, 0, 2, 0]
[0, 0, 0, 0]
[2, 2, 2, 0]
[2, 0, 2, 0]
[2, 0, 0, 0]
[2, 0, 0, 0]
[2, 0, 2, 0]
[2, 2, 2, 0]
[2, 2, 2, 2]
[0, 0, 2, 2]
[0, 0, 0, 0]</pre>
=={{header|Common Lisp}}==
Count only.
<
(if (oddp (* w h)) (return-from cut-it 0))
(if (oddp h) (rotatef w h))
(if (= w 1) (return-from cut-it
(let ((cnt 0)
Line 367 ⟶ 713:
(loop for h from 1 to w do
(if (evenp (* w h))
(format t "~d x ~d: ~d~%" w h (cut-it w h)))))</
2 x 2: 2
3 x 2: 3
Line 396 ⟶ 742:
9 x 4: 553
9 x 6: 31721
9 x 8: 1812667</
=={{header|D}}==
{{trans|C}}
<
enum int[2][4] dir = [[0, -1], [-1, 0], [0, 1], [1, 0]];
__gshared ubyte[] grid;
__gshared
__gshared ulong cnt;
__gshared
void walk(in
if (!y || y == h || !x || x == w) {
cnt += 2;
Line 422 ⟶ 761:
}
immutable
grid[t]++;
grid[len - t]++;
foreach (immutable i;
if (!grid[t + next[i]])
walk(y + dir[i][0], x + dir[i][1]);
Line 434 ⟶ 773:
}
ulong solve(in
h = (hh & 1) ? ww : hh;
w = (hh & 1) ? hh : ww;
Line 443 ⟶ 782:
if (h == 2) return w;
immutable
immutable
len = (h + 1) * (w + 1);
{
// grid.length =
auto ptr = cast(T*)alloca(len * T.sizeof);
if (ptr == null)
exit(1);
Line 457 ⟶ 797:
len--;
if (recur)
cnt = 0;
foreach (immutable x; cx + 1 .. w) {
immutable
grid[t] = 1;
grid[len - t] = 1;
Line 482 ⟶ 818:
void main() {
foreach (immutable uint y; 1 .. 11)
foreach (immutable uint x; 1 .. y + 1)
if (!(x & 1) || !(y & 1))
printf("%d x %d: %llu\n", y, x, solve(y, x, true));
}</
{{out}}
<pre>2 x 1: 1
2 x 2: 2
Line 528 ⟶ 864:
10 x 9: 99953769
10 x 10: 1124140214</pre>
Using the
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
{{Trans|C}}
<syntaxhighlight lang="delphi">
program Cut_a_rectangle;
{$APPTYPE CONSOLE}
uses
System.SysUtils;
var
grid: array of byte;
w, h, len: Integer;
cnt: UInt64;
next: array of Integer;
dir: array of array of Integer = [[0, -1], [-1, 0], [0, 1], [1, 0]];
procedure walk(y, x: Integer);
var
i, t: Integer;
begin
if (y = 0) or (y = h) or (x = 0) or (x = w) then
begin
inc(cnt);
Exit;
end;
t := y * (w + 1) + x;
inc(grid[t]);
inc(grid[len - t]);
for i := 0 to 3 do
if grid[t + next[i]] = 0 then
walk(y + dir[i][0], x + dir[i][1]);
dec(grid[t]);
dec(grid[len - t]);
end;
function solve(hh, ww: Integer; recur: Boolean): UInt64;
var
t, cx, cy, x, i: Integer;
begin
h := hh;
w := ww;
if Odd(h) then
begin
t := w;
w := h;
h := t;
end;
if Odd(h) then
Exit(0);
if w = 1 then
Exit(1);
if w = 2 then
Exit(h);
if h = 2 then
Exit(w);
cy := h div 2;
cx := w div 2;
len := (h + 1) * (w + 1);
setlength(grid, len);
for i := 0 to High(grid) do
grid[i] := 0;
dec(len);
next := [-1, -w - 1, 1, w + 1];
if recur then
cnt := 0;
for x := cx + 1 to w - 1 do
begin
t := cy * (w + 1) + x;
grid[t] := 1;
grid[len - t] := 1;
walk(cy - 1, x);
end;
Inc(cnt);
if h = w then
inc(cnt, 2)
else if not odd(w) and recur then
solve(w, h, False);
Result := cnt;
end;
var
y, x: Integer;
begin
for y := 1 to 10 do
for x := 1 to y do
if not Odd(x) or not Odd(y) then
writeln(format('%d x %d: %d', [y, x, solve(y, x, True)]));
Readln;
end.</syntaxhighlight>
{{out}}
See [[#C]]
=={{header|EasyLang}}==
{{trans|C}}
<syntaxhighlight lang=text>
global grid[] blen w h cnt .
dir[][] = [ [ 0 -1 ] [ -1 0 ] [ 0 1 ] [ 1 0 ] ]
#
proc walk y x . .
if y = 0 or y = h or x = 0 or x = w
cnt += 2
return
.
t = y * (w + 1) + x
grid[t] += 1
grid[blen - t] += 1
for i to 4
dx = dir[i][1]
dy = dir[i][2]
d = dx + dy * (w + 1)
if grid[t + d] = 0
walk y + dy x + dx
.
.
grid[t] -= 1
grid[blen - t] -= 1
.
proc solve hh ww recur . .
w = ww
h = hh
if h mod 2 = 1
swap h w
.
if h mod 2 = 1
cnt = 0
return
.
if w = 1
cnt = 1
return
.
if w = 2
cnt = h
return
.
if h = 2
cnt = w
return
.
cy = h div 2 ; cx = w div 2
blen = (h + 1) * (w + 1)
grid[] = [ ]
len grid[] blen
blen -= 1
if recur = 1
cnt = 0
.
for x = cx + 1 to w - 1
t = cy * (w + 1) + x
grid[t] = 1
grid[blen - t] = 1
walk cy - 1 x
.
cnt += 1
if h = w
cnt *= 2
elif w mod 2 = 0 and recur = 1
solve w h 0
.
.
proc main . .
for y = 1 to 8
for x = 1 to y
if x mod 2 = 0 or y mod 2 = 0
solve y x 1
print y & " x " & x & ": " & cnt
.
.
.
.
main
</syntaxhighlight>
{{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
</pre>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
APPLICATION
create
make
feature {NONE} -- Initialization
make
-- Finds solution for cut a rectangle up to 10 x 10.
local
i, j, n: Integer
r: GRID
do
n := 10
from
i := 1
until
i > n
loop
from
j := 1
until
j > i
loop
if i.bit_and (1) /= 1 or j.bit_and (1) /= 1 then
create r.make (i, j)
r.print_solution
end
j := j + 1
end
i := i + 1
end
end
end
</syntaxhighlight>
<syntaxhighlight lang="eiffel">
class
GRID
create
make
feature {NONE}
n: INTEGER
m: INTEGER
feature
print_solution
-- Prints solution to cut a rectangle.
do
calculate_possibilities
io.put_string ("Rectangle " + n.out + " x " + m.out + ": " + count.out + " possibilities%N")
end
count: INTEGER
-- Number of solutions
make (a_n: INTEGER; a_m: INTEGER)
-- Initialize Problem with 'a_n' and 'a_m'.
require
a_n > 0
a_m > 0
do
n := a_n
m := a_m
count := 0
end
calculate_possibilities
-- Select all possible starting points.
local
i: INTEGER
do
if (n = 1 or m = 1) then
count := 1
end
from
i := 0
until
i > n or (n = 1 or m = 1)
loop
solve (create {POINT}.make_with_values (i, 0), create {POINT}.make_with_values (n - i, m), create {LINKED_LIST [POINT]}.make, create {LINKED_LIST [POINT]}.make)
i := i + 1
variant
n - i + 1
end
from
i := 0
until
i > m or (n = 1 or m = 1)
loop
solve (create {POINT}.make_with_values (n, i), create {POINT}.make_with_values (0, m - i), create {LINKED_LIST [POINT]}.make, create {LINKED_LIST [POINT]}.make)
i := i + 1
variant
m - i + 1
end
end
feature {NONE}
solve (p, q: POINT; visited_p, visited_q: LINKED_LIST [POINT])
-- Recursive solution of cut a rectangle.
local
possible_next: LINKED_LIST [POINT]
next: LINKED_LIST [POINT]
opposite: POINT
do
if p.negative or q.negative then
elseif p.same (q) then
add_solution
else
possible_next := get_possible_next (p)
create next.make
across
possible_next as x
loop
if x.item.x >= n or x.item.y >= m then
-- Next point cannot be on the border. Do nothing.
elseif x.item.same (q) then
add_solution
elseif not contains (x.item, visited_p) and not contains (x.item, visited_q) then
next.extend (x.item)
end
end
across
next as x
loop
-- Move in one direction
-- Calculate the opposite end of the cut by moving into the opposite direction (compared to p -> x)
create opposite.make_with_values (q.x - (x.item.x - p.x), q.y - (x.item.y - p.y))
visited_p.extend (p)
visited_q.extend (q)
solve (x.item, opposite, visited_p, visited_q)
-- Remove last point again
visited_p.finish
visited_p.remove
visited_q.finish
visited_q.remove
end
end
end
get_possible_next (p: POINT): LINKED_LIST [POINT]
-- Four possible next points.
local
q: POINT
do
create Result.make
--up
create q.make_with_values (p.x + 1, p.y)
if q.valid and q.x <= n and q.y <= m then
Result.extend (q);
end
--down
create q.make_with_values (p.x - 1, p.y)
if q.valid and q.x <= n and q.y <= m then
Result.extend (q)
end
--left
create q.make_with_values (p.x, p.y - 1)
if q.valid and q.x <= n and q.y <= m then
Result.extend (q)
end
--right
create q.make_with_values (p.x, p.y + 1)
if q.valid and q.x <= n and q.y <= m then
Result.extend (q)
end
end
add_solution
-- Increment count.
do
count := count + 1
end
contains (p: POINT; set: LINKED_LIST [POINT]): BOOLEAN
-- Does set contain 'p'?
do
set.compare_objects
Result := set.has (p)
end
end
</syntaxhighlight>
<syntaxhighlight lang="eiffel">
class
POINT
create
make, make_with_values
feature
make_with_values (a_x: INTEGER; a_y: INTEGER)
-- Initialize x and y with 'a_x' and 'a_y'.
do
x := a_x
y := a_y
end
make
-- Initialize x and y with 0.
do
x := 0
y := 0
end
x: INTEGER
y: INTEGER
negative: BOOLEAN
-- Are x or y negative?
do
Result := x < 0 or y < 0
end
same (other: POINT): BOOLEAN
-- Does x and y equal 'other's x and y?
do
Result := (x = other.x) and (y = other.y)
end
valid: BOOLEAN
-- Are x and y valid points?
do
Result := (x > 0) and (y > 0)
end
end
</syntaxhighlight>
{{out}}
<pre>
Rectangle 2 x 1: 1 possibilities
Rectangle 2 x 2: 2 possibilities
Rectangle 3 x 2: 3 possibilities
Rectangle 4 x 1: 1 possibilities
Rectangle 4 x 2: 4 possibilities
Rectangle 4 x 3: 9 possibilities
Rectangle 4 x 4: 22 possibilities
Rectangle 5 x 2: 5 possibilities
Rectangle 5 x 4: 39 possibilities
Rectangle 6 x 1: 1 possibilities
Rectangle 6 x 2: 6 possibilities
Rectangle 6 x 3: 23 possibilities
Rectangle 6 x 4: 90 possibilities
Rectangle 6 x 5: 263 possibilities
Rectangle 6 x 6: 1018 possibilities
Rectangle 7 x 2: 7 possibilities
Rectangle 7 x 4: 151 possibilities
Rectangle 7 x 6: 2947 possibilities
Rectangle 8 x 1: 1 possibilities
Rectangle 8 x 2: 8 possibilities
Rectangle 8 x 3: 53 possibilities
Rectangle 8 x 4: 340 possibilities
Rectangle 8 x 5: 1675 possibilities
Rectangle 8 x 6: 11174 possibilities
Rectangle 8 x 7: 55939 possibilities
Rectangle 8 x 8: 369050 possibilities
Rectangle 9 x 2: 9 possibilities
Rectangle 9 x 4: 553 possibilities
Rectangle 9 x 6: 31721 possibilities
Rectangle 9 x 8: 1812667 possibilities
Rectangle 10 x 1: 1 possibilities
Rectangle 10 x 2: 10 possibilities
Rectangle 10 x 3: 115 possibilities
Rectangle 10 x 4: 1228 possibilities
Rectangle 10 x 5: 10295 possibilities
Rectangle 10 x 6: 118276 possibilities
Rectangle 10 x 7: 1026005 possibilities
Rectangle 10 x 8: 11736888 possibilities
Rectangle 10 x 9: 99953769 possibilities
Rectangle 10 x 10: 1124140214 possibilities
</pre>
=={{header|Elixir}}==
{{trans|Ruby}}
===Count only===
<syntaxhighlight lang="elixir">import Integer
defmodule Rectangle do
def cut_it(h, w) when is_odd(h) and is_odd(w), do: 0
def cut_it(h, w) when is_odd(h), do: cut_it(w, h)
def cut_it(_, 1), do: 1
def cut_it(h, 2), do: h
def cut_it(2, w), do: w
def cut_it(h, w) do
grid = List.duplicate(false, (h + 1) * (w + 1))
t = div(h, 2) * (w + 1) + div(w, 2)
if is_odd(w) do
grid = grid |> List.replace_at(t, true) |> List.replace_at(t+1, true)
walk(h, w, div(h, 2), div(w, 2) - 1, grid) + walk(h, w, div(h, 2) - 1, div(w, 2), grid) * 2
else
grid = grid |> List.replace_at(t, true)
count = walk(h, w, div(h, 2), div(w, 2) - 1, grid)
if h == w, do: count * 2,
else: count + walk(h, w, div(h, 2) - 1, div(w, 2), grid)
end
end
defp walk(h, w, y, x, grid, count\\0)
defp walk(h, w, y, x,_grid, count) when y in [0,h] or x in [0,w], do: count+1
defp walk(h, w, y, x, grid, count) do
blen = (h + 1) * (w + 1) - 1
t = y * (w + 1) + x
grid = grid |> List.replace_at(t, true) |> List.replace_at(blen-t, true)
Enum.reduce(next(w), count, fn {nt, dy, dx}, cnt ->
if Enum.at(grid, t+nt), do: cnt, else: cnt + walk(h, w, y+dy, x+dx, grid)
end)
end
defp next(w), do: [{w+1, 1, 0}, {-w-1, -1, 0}, {-1, 0, -1}, {1, 0, 1}] # {next,dy,dx}
end
Enum.each(1..9, fn w ->
Enum.each(1..w, fn h ->
if is_even(w * h), do: IO.puts "#{w} x #{h}: #{Rectangle.cut_it(w, h)}"
end)
end)</syntaxhighlight>
{{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
</pre>
===Show each of the cuts===
{{works with|Elixir|1.2}}
<syntaxhighlight lang="elixir">defmodule Rectangle do
def cut(h, w, disp\\true) when rem(h,2)==0 or rem(w,2)==0 do
limit = div(h * w, 2)
start_link
grid = make_grid(h, w)
walk(h, w, grid, 0, 0, limit, %{}, [])
if disp, do: display(h, w)
result = Agent.get(__MODULE__, &(&1))
Agent.stop(__MODULE__)
MapSet.to_list(result)
end
defp start_link do
Agent.start_link(fn -> MapSet.new end, name: __MODULE__)
end
defp make_grid(h, w) do
for i <- 0..h-1, j <- 0..w-1, into: %{}, do: {{i,j}, true}
end
defp walk(h, w, grid, x, y, limit, cut, select) do
grid2 = grid |> Map.put({x,y}, false) |> Map.put({h-x-1,w-y-1}, false)
select2 = [{x,y} | select] |> Enum.sort
unless cut[select2] do
if length(select2) == limit do
Agent.update(__MODULE__, fn set -> MapSet.put(set, select2) end)
else
cut2 = Map.put(cut, select2, true)
search_next(grid2, select2)
|> Enum.each(fn {i,j} -> walk(h, w, grid2, i, j, limit, cut2, select2) end)
end
end
end
defp dirs(x, y), do: [{x+1, y}, {x-1, y}, {x, y-1}, {x, y+1}]
defp search_next(grid, select) do
(for {x,y} <- select, {i,j} <- dirs(x,y), grid[{i,j}], do: {i,j})
|> Enum.uniq
end
defp display(h, w) do
Agent.get(__MODULE__, &(&1))
|> Enum.each(fn select ->
grid = Enum.reduce(select, make_grid(h,w), fn {x,y},grid ->
%{grid | {x,y} => false}
end)
IO.puts to_string(h, w, grid)
end)
end
defp to_string(h, w, grid) do
text = for x <- 0..h*2, into: %{}, do: {x, String.duplicate(" ", w*4+1)}
text = Enum.reduce(0..h, text, fn i,acc ->
Enum.reduce(0..w, acc, fn j,txt ->
to_s(txt, i, j, grid)
end)
end)
Enum.map_join(0..h*2, "\n", fn i -> text[i] end)
end
defp to_s(text, i, j, grid) do
text = if grid[{i,j}] != grid[{i-1,j}], do: replace(text, i*2, j*4+1, "---"), else: text
text = if grid[{i,j}] != grid[{i,j-1}], do: replace(text, i*2+1, j*4, "|"), else: text
replace(text, i*2, j*4, "+")
end
defp replace(text, x, y, replacement) do
len = String.length(replacement)
Map.update!(text, x, fn str ->
String.slice(str, 0, y) <> replacement <> String.slice(str, y+len..-1)
end)
end
end
Rectangle.cut(2, 2) |> length |> IO.puts
Rectangle.cut(3, 4) |> length |> IO.puts</syntaxhighlight>
{{out}}
<pre style="height:64ex;overflow:scroll">
+---+---+
| |
+---+---+
| |
+---+---+
+---+---+
| | |
+ + +
| | |
+---+---+
2
+---+---+---+---+
| |
+ + +---+---+
| | |
+---+---+ + +
| |
+---+---+---+---+
+---+---+---+---+
| |
+ +---+ +---+
| | | | |
+---+ +---+ +
| |
+---+---+---+---+
+---+---+---+---+
| |
+---+ +---+ +
| | | | |
+ +---+ +---+
| |
+---+---+---+---+
+---+---+---+---+
| |
+---+---+ + +
| | |
+ + +---+---+
| |
+---+---+---+---+
+---+---+---+---+
| | |
+ + +---+ +
| | |
+ +---+ + +
| | |
+---+---+---+---+
+---+---+---+---+
| | |
+ +---+ + +
| | | | |
+ + +---+ +
| | |
+---+---+---+---+
+---+---+---+---+
| | |
+ + + + +
| | |
+ + + + +
| | |
+---+---+---+---+
+---+---+---+---+
| | |
+ +---+ + +
| | |
+ + +---+ +
| | |
+---+---+---+---+
+---+---+---+---+
| | |
+ + +---+ +
| | | | |
+ +---+ + +
| | |
+---+---+---+---+
9
</pre>
=={{header|Go}}==
{{trans|C}}
<syntaxhighlight lang="go">package main
import "fmt"
var grid []byte
var w, h, last int
var cnt int
var next [4]int
var dir = [4][2]int{{0, -1}, {-1, 0}, {0, 1}, {1, 0}}
func walk(y, x int) {
if y == 0 || y == h || x == 0 || x == w {
cnt += 2
return
}
t := y*(w+1) + x
grid[t]++
grid[last-t]++
for i, d := range dir {
if grid[t+next[i]] == 0 {
walk(y+d[0], x+d[1])
}
}
grid[t]--
grid[last-t]--
}
func solve(hh, ww, recur int) int {
h = hh
w = ww
if h&1 != 0 {
h, w = w, h
}
switch {
case h&1 == 1:
return 0
case w == 1:
return 1
case w == 2:
return h
case h == 2:
return w
}
cy := h / 2
cx := w / 2
grid = make([]byte, (h+1)*(w+1))
last = len(grid) - 1
next[0] = -1
next[1] = -w - 1
next[2] = 1
next[3] = w + 1
if recur != 0 {
cnt = 0
}
for x := cx + 1; x < w; x++ {
t := cy*(w+1) + x
grid[t] = 1
grid[last-t] = 1
walk(cy-1, x)
}
cnt++
if h == w {
cnt *= 2
} else if w&1 == 0 && recur != 0 {
solve(w, h, 0)
}
return cnt
}
func main() {
for y := 1; y <= 10; y++ {
for x := 1; x <= y; x++ {
if x&1 == 0 || y&1 == 0 {
fmt.Printf("%d x %d: %d\n", y, x, solve(y, x, 1))
}
}
}
}</syntaxhighlight>
{{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|Groovy}}==
{{trans|Java}}
<syntaxhighlight lang="groovy">class CutRectangle {
private static int[][] dirs = [[0, -1], [-1, 0], [0, 1], [1, 0]]
static void main(String[] args) {
cutRectangle(2, 2)
cutRectangle(4, 3)
}
static void cutRectangle(int w, int h) {
if (w % 2 == 1 && h % 2 == 1) {
return
}
int[][] grid = new int[h][w]
Stack<Integer> stack = new Stack<>()
int half = (int) ((w * h) / 2)
long bits = (long) Math.pow(2, half) - 1
for (; bits > 0; bits -= 2) {
for (int i = 0; i < half; i++) {
int r = (int) (i / w)
int c = i % w
grid[r][c] = (bits & (1 << i)) != 0 ? 1 : 0
grid[h - r - 1][w - c - 1] = 1 - grid[r][c]
}
stack.push(0)
grid[0][0] = 2
int count = 1
while (!stack.empty()) {
int pos = stack.pop()
int r = (int) (pos / w)
int c = pos % w
for (int[] dir : dirs) {
int nextR = r + dir[0]
int nextC = c + dir[1]
if (nextR >= 0 && nextR < h && nextC >= 0 && nextC < w) {
if (grid[nextR][nextC] == 1) {
stack.push(nextR * w + nextC)
grid[nextR][nextC] = 2
count++
}
}
}
}
if (count == half) {
printResult(grid)
}
}
}
static void printResult(int[][] arr) {
for (int[] a : arr) {
println(Arrays.toString(a))
}
println()
}
}</syntaxhighlight>
{{out}}
<pre>[2, 2]
[0, 0]
[2, 0]
[2, 0]
[2, 2, 2, 2]
[2, 2, 0, 0]
[0, 0, 0, 0]
[2, 2, 2, 0]
[2, 2, 0, 0]
[2, 0, 0, 0]
[2, 2, 0, 0]
[2, 2, 0, 0]
[2, 2, 0, 0]
[2, 0, 0, 0]
[2, 2, 0, 0]
[2, 2, 2, 0]
[2, 2, 2, 2]
[0, 2, 0, 2]
[0, 0, 0, 0]
[2, 2, 2, 2]
[2, 0, 2, 0]
[0, 0, 0, 0]
[2, 2, 2, 0]
[2, 0, 2, 0]
[2, 0, 0, 0]
[2, 0, 0, 0]
[2, 0, 2, 0]
[2, 2, 2, 0]
[2, 2, 2, 2]
[0, 0, 2, 2]
[0, 0, 0, 0]</pre>
=={{header|Haskell}}==
{{trans|Python}}
Calculation of the cuts happens in the ST monad, using a mutable STVector and a mutable STRef. The program style is therefore very imperative.
The strictness annotations in the Env type are necessary; otherwise, unevaluated thunks of updates of "env" would pile up with each recursion, ending in a stack overflow.
<syntaxhighlight lang="haskell">import qualified Data.Vector.Unboxed.Mutable as V
import Data.STRef
import Control.Monad (forM_, when)
import Control.Monad.ST
dir :: [(Int, Int)]
dir = [(1, 0), (-1, 0), (0, -1), (0, 1)]
data Env = Env { w, h, len, count, ret :: !Int, next :: ![Int] }
cutIt :: STRef s Env -> ST s ()
cutIt env = do
e <- readSTRef env
when (odd $ h e) $ modifySTRef env $ \en -> en { h = w e,
w = h e }
e <- readSTRef env
if odd (h e)
then modifySTRef env $ \en -> en { ret = 0 }
else
if w e == 1
then modifySTRef env $ \en -> en { ret = 1 }
else do
let blen = (h e + 1) * (w e + 1) - 1
t = (h e `div` 2) * (w e + 1) + (w e `div` 2)
modifySTRef env $ \en -> en { len = blen,
count = 0,
next = [ w e + 1, (negate $ w e) - 1, -1, 1] }
grid <- V.replicate (blen + 1) False
case odd (w e) of
True -> do
V.write grid t True
V.write grid (t + 1) True
walk grid (h e `div` 2) (w e `div` 2 - 1)
e1 <- readSTRef env
let res1 = count e1
modifySTRef env $ \en -> en { count = 0 }
walk grid (h e `div` 2 - 1) (w e `div` 2)
modifySTRef env $ \en -> en { ret = res1 +
(count en * 2) }
False -> do
V.write grid t True
walk grid (h e `div` 2) (w e `div` 2 - 1)
e2 <- readSTRef env
let count2 = count e2
if h e == w e
then modifySTRef env $ \en -> en { ret =
count2 * 2 }
else do
walk grid (h e `div` 2 - 1)
(w e `div` 2)
modifySTRef env $ \en -> en { ret =
count en }
where
walk grid y x = do
e <- readSTRef env
if y <= 0 || y >= h e || x <= 0 || x >= w e
then modifySTRef env $ \en -> en { count = count en + 1 }
else do
let t = y * (w e + 1) + x
V.write grid t True
V.write grid (len e - t) True
forM_ (zip (next e) [0..3]) $ \(n, d) -> do
g <- V.read grid (t + n)
when (not g) $
walk grid (y + fst (dir !! d)) (x + snd (dir !! d))
V.write grid t False
V.write grid (len e - t) False
cut :: (Int, Int) -> Int
cut (x, y) = runST $ do
env <- newSTRef $ Env { w = y, h = x, len = 0, count = 0, ret = 0, next = [] }
cutIt env
result <- readSTRef env
return $ ret result
main :: IO ()
main = do
mapM_ (\(x, y) -> when (even (x * y)) (putStrLn $
show x ++ " x " ++ show y ++ ": " ++ show (cut (x, y))))
[ (x, y) | x <- [1..10], y <- [1..x] ]
</syntaxhighlight>
With GHC -O3 the run-time is about 39 times the D entry.
=={{header|J}}==
<
prop=: < {:,~2 ~:/\ ] NB. propagate: neighboring squares (vertically)
poss=: I.@,@(prop +. prop"1 +. prop&.|. +. prop&.|."1)
Line 538 ⟶ 1,947:
N=: <:@-:@#@, NB. how many neighbors to add
step=: [: ~.@; <@(((= i.@$) +. ])"0 _~ keep)"2
all=: step^:N@init</
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.
Line 546 ⟶ 1,955:
Example use:
<
┌────┬────┬────┬────┬────┬────┬────┬────┬────┐
│.###│.###│..##│...#│...#│....│....│....│....│
Line 570 ⟶ 1,979:
│.##.#│.#..#│#..##│#.###│#####│###.#│##..#│#..#.│#.##.│####.│###..│##...│#....│
│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘</
=={{header|Java}}==
{{works with|Java|7}}
<syntaxhighlight lang="java">import java.util.*;
public class CutRectangle {
private static int[][] dirs = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
public static void main(String[] args) {
cutRectangle(2, 2);
cutRectangle(4, 3);
}
static void cutRectangle(int w, int h) {
if (w % 2 == 1 && h % 2 == 1)
return;
int[][] grid = new int[h][w];
Stack<Integer> stack = new Stack<>();
int half = (w * h) / 2;
long bits = (long) Math.pow(2, half) - 1;
for (; bits > 0; bits -= 2) {
for (int i = 0; i < half; i++) {
int r = i / w;
int c = i % w;
grid[r][c] = (bits & (1 << i)) != 0 ? 1 : 0;
grid[h - r - 1][w - c - 1] = 1 - grid[r][c];
}
stack.push(0);
grid[0][0] = 2;
int count = 1;
while (!stack.empty()) {
int pos = stack.pop();
int r = pos / w;
int c = pos % w;
for (int[] dir : dirs) {
int nextR = r + dir[0];
int nextC = c + dir[1];
if (nextR >= 0 && nextR < h && nextC >= 0 && nextC < w) {
if (grid[nextR][nextC] == 1) {
stack.push(nextR * w + nextC);
grid[nextR][nextC] = 2;
count++;
}
}
}
}
if (count == half) {
printResult(grid);
}
}
}
static void printResult(int[][] arr) {
for (int[] a : arr)
System.out.println(Arrays.toString(a));
System.out.println();
}
}</syntaxhighlight>
<pre>[2, 2]
[0, 0]
[2, 0]
[2, 0]
[2, 2, 2, 2]
[2, 2, 0, 0]
[0, 0, 0, 0]
[2, 2, 2, 0]
[2, 2, 0, 0]
[2, 0, 0, 0]
[2, 2, 0, 0]
[2, 2, 0, 0]
[2, 2, 0, 0]
[2, 0, 0, 0]
[2, 2, 0, 0]
[2, 2, 2, 0]
[2, 2, 2, 2]
[0, 2, 0, 2]
[0, 0, 0, 0]
[2, 2, 2, 2]
[2, 0, 2, 0]
[0, 0, 0, 0]
[2, 2, 2, 0]
[2, 0, 2, 0]
[2, 0, 0, 0]
[2, 0, 0, 0]
[2, 0, 2, 0]
[2, 2, 2, 0]
[2, 2, 2, 2]
[0, 0, 2, 2]
[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}}==
{{trans|C}}
<syntaxhighlight lang="julia">
const count = [0]
const dir = [[0, -1], [-1, 0], [0, 1], [1, 0]]
function walk(y, x, h, w, grid, len, next)
if y == 0 || y == h || x == 0 || x == w
count[1] += 2
return
end
t = y * (w + 1) + x
grid[t + 1] += UInt8(1)
grid[len - t + 1] += UInt8(1)
for i in 1:4
if grid[t + next[i] + 1] == 0
walk(y + dir[i][1], x + dir[i][2], h, w, grid, len, next)
end
end
grid[t + 1] -= 1
grid[len - t + 1] -= 1
end
function cutrectangle(hh, ww, recur)
if isodd(hh)
h, w = ww, hh
else
h, w = hh, ww
end
if isodd(h)
return 0
elseif w == 1
return 1
elseif w == 2
return h
elseif h == 2
return w
end
cy = div(h, 2)
cx = div(w, 2)
len = (h + 1) * (w + 1)
grid = zeros(UInt8, len)
len -= 1
next = [-1, -w - 1, 1, w + 1]
if recur
count[1] = 0
end
for x in cx + 1:w - 1
t = cy * (w + 1) + x
grid[t + 1] = 1
grid[len - t + 1] = 1
walk(cy - 1, x, h, w, grid, len, next)
end
count[1] += 1
if h == w
count[1] *= 2
elseif iseven(w) && recur
cutrectangle(w, h, false)
end
return count[1]
end
function runtest()
for y in 1:10, x in 1:y
if iseven(x) || iseven(y)
println("$y x $x: $(cutrectangle(y, x, true))")
end
end
end
runtest()
</syntaxhighlight> {{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>
=={{header|Kotlin}}==
{{trans|C}}
<syntaxhighlight lang="scala">// version 1.0.6
object RectangleCutter {
private var w: Int = 0
private var h: Int = 0
private var len: Int = 0
private var cnt: Long = 0
private lateinit var grid: ByteArray
private val next = IntArray(4)
private val dir = arrayOf(
intArrayOf(0, -1),
intArrayOf(-1, 0),
intArrayOf(0, 1),
intArrayOf(1, 0)
)
private fun walk(y: Int, x: Int) {
if (y == 0 || y == h || x == 0 || x == w) {
cnt += 2
return
}
val t = y * (w + 1) + x
grid[t]++
grid[len - t]++
(0..3).filter { grid[t + next[it]] == 0.toByte() }
.forEach { walk(y + dir[it][0], x + dir[it][1]) }
grid[t]--
grid[len - t]--
}
fun solve(hh: Int, ww: Int, recur: Boolean): Long {
var t: Int
h = hh
w = ww
if ((h and 1) != 0) {
t = w
w = h
h = t
}
if ((h and 1) != 0) return 0L
if (w == 1) return 1L
if (w == 2) return h.toLong()
if (h == 2) return w.toLong()
val cy = h / 2
val cx = w / 2
len = (h + 1) * (w + 1)
grid = ByteArray(len)
len--
next[0] = -1
next[1] = -w - 1
next[2] = 1
next[3] = w + 1
if (recur) cnt = 0L
for (x in cx + 1 until w) {
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 and 1) == 0 && recur) solve(w, h, false)
return cnt
}
}
fun main(args: Array<String>) {
for (y in 1..10) {
for (x in 1..y) {
if ((x and 1) == 0 || (y and 1) == 0) {
println("${"%2d".format(y)} x ${"%2d".format(x)}: ${RectangleCutter.solve(y, x, true)}")
}
}
}
}</syntaxhighlight>
{{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|Lua}}==
{{trans|C++}}
<syntaxhighlight lang="lua">function array1D(w, d)
local t = {}
for i=1,w do
table.insert(t, d)
end
return t
end
function array2D(h, w, d)
local t = {}
for i=1,h do
table.insert(t, array1D(w, d))
end
return t
end
function push(s, v)
s[#s + 1] = v
end
function pop(s)
return table.remove(s, #s)
end
function empty(s)
return #s == 0
end
DIRS = {
{0, -1},
{-1, 0},
{0, 1},
{1, 0}
}
function printResult(aa)
for i,u in pairs(aa) do
io.write("[")
for j,v in pairs(u) do
if j > 1 then
io.write(", ")
end
io.write(v)
end
print("]")
end
end
function cutRectangle(w, h)
if w % 2 == 1 and h % 2 == 1 then
return nil
end
local grid = array2D(h, w, 0)
local stack = {}
local half = math.floor((w * h) / 2)
local bits = 2 ^ half - 1
while bits > 0 do
for i=1,half do
local r = math.floor((i - 1) / w)
local c = (i - 1) % w
if (bits & (1 << (i - 1))) ~= 0 then
grid[r + 1][c + 1] = 1
else
grid[r + 1][c + 1] = 0
end
grid[h - r][w - c] = 1 - grid[r + 1][c + 1]
end
push(stack, 0)
grid[1][1] = 2
local count = 1
while not empty(stack) do
local pos = pop(stack)
local r = math.floor(pos / w)
local c = pos % w
for i,dir in pairs(DIRS) do
local nextR = r + dir[1]
local nextC = c + dir[2]
if nextR >= 0 and nextR < h and nextC >= 0 and nextC < w then
if grid[nextR + 1][nextC + 1] == 1 then
push(stack, nextR * w + nextC)
grid[nextR + 1][nextC + 1] = 2
count = count + 1
end
end
end
end
if count == half then
printResult(grid)
print()
end
-- loop end
bits = bits - 2
end
end
cutRectangle(2, 2)
cutRectangle(4, 3)</syntaxhighlight>
{{out}}
<pre>[2, 2]
[0, 0]
[2, 0]
[2, 0]
[2, 2, 2, 2]
[2, 2, 0, 0]
[0, 0, 0, 0]
[2, 2, 2, 0]
[2, 2, 0, 0]
[2, 0, 0, 0]
[2, 2, 0, 0]
[2, 2, 0, 0]
[2, 2, 0, 0]
[2, 0, 0, 0]
[2, 2, 0, 0]
[2, 2, 2, 0]
[2, 2, 2, 2]
[0, 2, 0, 2]
[0, 0, 0, 0]
[2, 2, 2, 2]
[2, 0, 2, 0]
[0, 0, 0, 0]
[2, 2, 2, 0]
[2, 0, 2, 0]
[2, 0, 0, 0]
[2, 0, 0, 0]
[2, 0, 2, 0]
[2, 2, 2, 0]
[2, 2, 2, 2]
[0, 0, 2, 2]
[0, 0, 0, 0]</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[CutRectangle]
dirs = AngleVector /@ Most[Range[0, 2 Pi, Pi/2]];
CutRectangle[nm : {n_, m_}] := Module[{start, stop, count, sols},
If[OddQ[n] \[And] OddQ[m], Return[<|"Count" -> 0, "Solutions" -> {}|>]];
start = {0, 0};
stop = nm;
ClearAll[ValidPosition, ValidRoute, ProceedStep];
ValidPosition[{x_, y_}] := 0 <= x <= n \[And] 0 <= y <= m;
ValidRoute[route_List] := Module[{},
If[MatchQ[route[[All, 1]], {0 .., Except[0] .., 0, ___}], Return[False]]; (* once it leaves the left border, don't return (disjoint pieces) *)
If[MatchQ[route[[All, 2]], {0 .., Except[0] .., 0, ___}], Return[False]];(* once it leaves the bottom border, don't return (disjoint pieces) *)
True
];
ProceedStep[nnmm : {nn_, mm_}, steps1_List, steps2_List] := Module[{nextposs, newsteps1, newsteps2, route},
If[Last[steps1] == Last[steps2],
route = Join[Most[steps1], Reverse[steps2]];
If[ValidRoute[route],
count++;
AppendTo[sols, route];
]
,
If[Length[steps1] >= 2,
If[Take[steps1, -2] == Reverse[Take[steps2, -2]],
route = Join[Most[steps1], Reverse[Most[steps2]]];
If[ValidRoute[route],
count++;
AppendTo[sols, route];
]
]
]
];
nextposs = {Last[steps1] + #, Last[steps2] - #} & /@ dirs;
nextposs //= Select[First/*ValidPosition];
nextposs //= Select[Last/*ValidPosition];
nextposs //= Select[! MemberQ[steps1, First[#]] &];
nextposs //= Select[! MemberQ[steps2, Last[#]] &];
nextposs //= Select[! MemberQ[Most[steps2], First[#]] &];
nextposs //= Select[! MemberQ[Most[steps1], Last[#]] &];
Do[
newsteps1 = Append[steps1, First[np]];
newsteps2 = Append[steps2, Last[np]];
ProceedStep[nnmm, newsteps1, newsteps2]
,
{np, nextposs}
]
];
count = 0;
sols = {};
ProceedStep[nm, {start}, {stop}];
<|"Count" -> count, "Solutions" -> sols|>
]
maxsize = 6;
sols = Reap[Do[
If[EvenQ[i] \[Or] EvenQ[j],
If[i >= j,
Sow@{i, j, CutRectangle[{i, j}]["Count"]}
]
],
{i, maxsize},
{j, maxsize}
]][[2, 1]];
Column[Row[{#1, " \[Times] ", #2, ": ", #3}] & @@@ sols]</syntaxhighlight>
{{out}}
<pre>2 * 1: 1
2 * 2: 2
3 * 2: 3
4 * 1: 1
4 * 2: 4
4 * 3: 9
4 * 4: 22
5 * 2: 5
5 * 4: 39
6 * 1: 1
6 * 2: 6
6 * 3: 23
6 * 4: 90
6 * 5: 263
6 * 6: 1018</pre>
Solutions can be visualised using:
<syntaxhighlight lang="mathematica">size = {4, 3};
cr = CutRectangle[size];
Graphics[{Style[Rectangle[{0, 0}, size], FaceForm[], EdgeForm[Red]], Style[Arrow[#], Black], Style[Point[#], Black]}, ] & /@ cr["Solutions"]</syntaxhighlight>
Which outputs graphical objects for each solution.
=={{header|Nim}}==
{{trans|C}}
<syntaxhighlight lang="nim">import strformat
var
w, h: int
grid: seq[byte]
next: array[4, int]
count: int
const Dirs = [[0, -1], [-1, 0], [0, 1], [1, 0]]
template odd(n: int): bool = (n and 1) != 0
#------------------------------------------------------------------------------
proc walk(y, x: int) =
if y == 0 or y == h or x == 0 or x == w:
inc count, 2
return
let t = y * (w + 1) + x
inc grid[t]
inc grid[grid.high - t]
for i, dir in Dirs:
if grid[t + next[i]] == 0:
walk(y + dir[0], x + dir[1])
dec grid[t]
dec grid[grid.high - t]
#------------------------------------------------------------------------------
proc solve(y, x: int; recursive: bool): int =
h = y
w = x
if odd(h): swap w, h
if odd(h): return 0
if w == 1: return 1
if w == 2: return h
if h == 2: return w
let cy = h div 2
let cx = w div 2
grid = newSeq[byte]((w + 1) * (h + 1))
next[0] = -1
next[1] = -w - 1
next[2] = 1
next[3] = w + 1
if recursive: count = 0
for x in (cx + 1)..<w:
let t = cy * (w + 1) + x
grid[t] = 1
grid[grid.high - t] = 1
walk(cy - 1, x)
inc count
if h == w:
count *= 2
elif not odd(w) and recursive:
discard solve(w, h, false)
result = count
#——————————————————————————————————————————————————————————————————————————————
for y in 1..10:
for x in 1..y:
if not odd(x) or not odd(y):
echo &"{y:2d} x {x:2d}: {solve(y, x, true)}"</syntaxhighlight>
{{out}}
Result obtained in 4.3 seconds.
<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|Perl}}==
{{trans|C}}
Output is identical to C's.
<syntaxhighlight lang="perl">use strict;
use warnings;
my @grid = 0;
my ($w, $h, $len);
my $cnt = 0;
my @next;
my @dir = ([0, -1], [-1, 0], [0, 1], [1, 0]);
sub walk {
my ($y, $x) = @_;
if (!$y || $y == $h || !$x || $x == $w) {
$cnt += 2;
return;
}
my $t = $y * ($w + 1) + $x;
$grid[$_]++ for $t, $len - $t;
for my $i (0 .. 3) {
if (!$grid[$t + $next[$i]]) {
walk($y + $dir[$i]->[0], $x + $dir[$i]->[1]);
}
}
$grid[$_]-- for $t, $len - $t;
}
sub solve {
my ($hh, $ww, $recur) = @_;
my ($t, $cx, $cy, $x);
($h, $w) = ($hh, $ww);
if ($h & 1) { ($t, $w, $h) = ($w, $h, $w); }
if ($h & 1) { return 0; }
if ($w == 1) { return 1; }
if ($w == 2) { return $h; }
if ($h == 2) { return $w; }
{
use integer;
($cy, $cx) = ($h / 2, $w / 2);
}
$len = ($h + 1) * ($w + 1);
@grid = ();
$grid[$len--] = 0;
@next = (-1, -$w - 1, 1, $w + 1);
if ($recur) { $cnt = 0; }
for ($x = $cx + 1; $x < $w; $x++) {
$t = $cy * ($w + 1) + $x;
@grid[$t, $len - $t] = (1, 1);
walk($cy - 1, $x);
}
$cnt++;
if ($h == $w) {
$cnt *= 2;
} elsif (!($w & 1) && $recur) {
solve($w, $h);
}
return $cnt;
}
sub MAIN {
print "ok\n";
my ($y, $x);
for my $y (1 .. 10) {
for my $x (1 .. $y) {
if (!($x & 1) || !($y & 1)) {
printf("%d x %d: %d\n", $y, $x, solve($y, $x, 1));
}
}
}
}
MAIN();</syntaxhighlight>
=={{header|Phix}}==
Using a completely different home-brewed algorithm, slightly sub-optimal as noted in the code.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">show</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- max number to show
-- (nb mirrors are not shown)</span>
<span style="color: #000000;">chance</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1000</span> <span style="color: #000080;font-style:italic;">-- 1=always, 2=50%, 3=33%, etc</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">grid</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">gh</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- = length(grid),</span>
<span style="color: #000000;">gw</span> <span style="color: #000080;font-style:italic;">-- = length(grid[1])</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ty1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ty2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tx1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tx2</span> <span style="color: #000080;font-style:italic;">-- target {y,x}s</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">mirror</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- plant/reset ch and the symmetric copy</span>
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch</span>
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">gh</span><span style="color: #0000FF;">-</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">gw</span><span style="color: #0000FF;">-</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">UP</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">DOWN</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">LEFT</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">dyx</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span>
<span style="color: #000000;">chx</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"-||-"</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">search</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">level</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">level</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]!=</span><span style="color: #008000;">'x'</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">mirror</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'x'</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dyx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">],</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">yy</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xx</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">*</span><span style="color: #000000;">3</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">chx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">mirror</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'-'</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">mirror</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">meet</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">yy</span><span style="color: #0000FF;">=</span><span style="color: #000000;">ty1</span> <span style="color: #008080;">or</span> <span style="color: #000000;">yy</span><span style="color: #0000FF;">=</span><span style="color: #000000;">ty2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">xx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">tx1</span> <span style="color: #008080;">or</span> <span style="color: #000000;">xx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">tx2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">meet</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">show</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chance</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">chance</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">show</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">g</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (make copy/avoid reset)
-- fill in(/overwrite) the last cut, if any</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ty1</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">ty2</span> <span style="color: #008080;">then</span> <span style="color: #000000;">g</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ty1</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tx1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'|'</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">tx1</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">tx2</span> <span style="color: #008080;">then</span> <span style="color: #000000;">g</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ty1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">tx1</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">tx1</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"--"</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"\n\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">yy</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xx</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">'+'</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- (minor gain)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">=</span><span style="color: #000000;">RIGHT</span> <span style="color: #008080;">to</span> <span style="color: #000000;">LEFT</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- (kinda true!)</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yy</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">level</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">mirror</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">,</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'-'</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">mirror</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">,</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">level</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- ((level=0)==leave outer edges 'x' for next iteration)</span>
<span style="color: #000000;">mirror</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'+'</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">count</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">make_grid</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">w</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- The outer edges are 'x'; the inner '+' become 'x' when visited.
-- Likewise edges are cuts but the inner ones get filled in later.</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tb</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"x"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">w</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"--"</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">hz</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'x'</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">w</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">'x'</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">vt</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"|"</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #000000;">w</span><span style="color: #0000FF;">*</span><span style="color: #000000;">3</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"|\n"</span>
<span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tb</span><span style="color: #0000FF;">&</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">vt</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h</span><span style="color: #0000FF;">),</span><span style="color: #000000;">hz</span><span style="color: #0000FF;">)&</span><span style="color: #000000;">tb</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- set size (for mirroring) and target info:</span>
<span style="color: #000000;">gh</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">gw</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">ty1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">h</span><span style="color: #0000FF;">+</span><span style="color: #7060A8;">even</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">ty2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ty1</span><span style="color: #0000FF;">+</span><span style="color: #7060A8;">odd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">2</span>
<span style="color: #000000;">tx1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">w</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">3</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #000000;">tx2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tx1</span><span style="color: #0000FF;">+</span><span style="color: #7060A8;">odd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">w</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">3</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">side</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">w</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">make_grid</span><span style="color: #0000FF;">(</span><span style="color: #000000;">w</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- search top to mid-point</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">last</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #000000;">h</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">last</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- left to right</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">last</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">even</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">last</span> <span style="color: #000080;font-style:italic;">-- (un-double the centre line)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">count</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #000080;font-style:italic;">--atom t0 = time()
-- nb sub-optimal: obviously "grid" was designed for easy display, rather than speed.</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">7</span><span style="color: #0000FF;">:</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- 24s
--for y=1 to 10 do -- (gave up on >10x8)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">y</span> <span style="color: #008080;">do</span>
<span style="color: #000080;font-style:italic;">-- for x=1 to min(y,8) do -- 4 mins 16s (with y to 10)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">even</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">*</span><span style="color: #000000;">y</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">side</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">y</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">side</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d x %d: %d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">--?elapsed(time()-t0)</span>
<!--</syntaxhighlight>-->
{{out}}
Includes two random grids
<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
x--x--x--x--x--x--x
| |
x--x + + + + x
| | |
x x x--x--x + x
| | | | |
x x--x x--x + x
| | |
x + x--x x--x x
| | | | |
x + x--x--x x x
| | |
x + + + + x--x
| |
x--x--x--x--x--x--x
x--x--x--x--x--x--x--x
| |
x + x--x--x--x--x x
| | | |
x--x--x x--x--x x x
| | | | |
x x--x x--x x--x x
| | | | |
x x x--x--x x--x--x
| | | |
x x--x--x--x--x + x
| |
x--x--x--x--x--x--x--x
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
</pre>
It is about 6 times slower under pwa/p2js, hence capped at 7 (which makes it complete in 0.2s).
=={{header|Python}}==
{{trans|D}}
<
dirs = ((1, 0), (-1, 0), (0, -1), (0, 1))
if h
if h
if w == 1: return 1
count = 0
Line 605 ⟶ 3,117:
t = h // 2 * (w + 1) + w // 2
if w
grid[t] = grid[t + 1] = True
count = walk(h // 2, w // 2 - 1, count)
Line 623 ⟶ 3,135:
for w in xrange(1, 10):
for h in xrange(1, w + 1):
if not((w * h)
print "%d x %d: %d" % (w, h, cut_it(w, h))
main()</
Output:
<pre>2 x 1: 1
Line 660 ⟶ 3,172:
===Faster version===
{{trans|D}}
<
import psyco
except ImportError:
Line 729 ⟶ 3,241:
print "%d x %d: %d" % (y, x, count_only(x, y))
main()</
The output is the same.
=={{header|Racket}}==
<syntaxhighlight lang="racket">
#lang racket
(define (cuts W H [count 0]) ; count = #f => visualize instead
(define W1 (add1 W)) (define H1 (add1 H))
(define B (make-vector (* W1 H1) #f))
(define (fD d) (cadr (assq d '([U D] [D U] [L R] [R L] [#f #f] [#t #t]))))
(define (fP p) (- (* W1 H1) p 1))
(define (Bset! p d) (vector-set! B p d) (vector-set! B (fP p) (fD d)))
(define center (/ (fP 0) 2))
(when (integer? center) (Bset! center #t))
(define (run c* d)
(define p (- center c*))
(Bset! p d)
(let loop ([p p])
(define-values [q r] (quotient/remainder p W1))
(if (and (< 0 r W) (< 0 q H))
(for ([d '(U D L R)])
(define n (+ p (case d [(U) (- W1)] [(D) W1] [(L) -1] [(R) 1])))
(unless (vector-ref B n) (Bset! n (fD d)) (loop n) (Bset! n #f)))
(if count (set! count (add1 count)) (visualize B W H))))
(Bset! p #f))
(when (even? W) (run (if (odd? H) (/ W1 2) W1) 'D))
(when (even? H) (run (if (odd? W) 1/2 1) 'R))
(or count (void)))
(define (visualize B W H)
(define W2 (+ 2 (* W 2))) (define H2 (+ 1 (* H 2)))
(define str (make-string (* H2 W2) #\space))
(define (Sset! i c) (string-set! str i c))
(for ([i (in-range (- W2 1) (* W2 H2) W2)]) (Sset! i #\newline))
(for ([i (in-range 0 (- W2 1))]) (Sset! i #\#) (Sset! (+ i (* W2 H 2)) #\#))
(for ([i (in-range 0 (* W2 H2) W2)]) (Sset! i #\#) (Sset! (+ i W2 -2) #\#))
(for* ([i (add1 W)] [j (add1 H)])
(define p (* 2 (+ i (* j W2))))
(define b (vector-ref B (+ i (* j (+ W 1)))))
(cond [b (Sset! p #\#)
(define d (case b [(U) (- W2)] [(D) W2] [(R) 1] [(L) -1]))
(when (integer? d) (Sset! (+ p d) #\#))]
[(equal? #\space (string-ref str p)) (Sset! p #\.)]))
(display str) (newline))
(printf "Counts:\n")
(for* ([W (in-range 1 10)] [H (in-range 1 (add1 W))]
#:unless (and (odd? W) (odd? H)))
(printf "~s x ~s: ~s\n" W H (cuts W H)))
(newline)
(cuts 4 3 #f)
</syntaxhighlight>
{{out}}
<pre>
Counts:
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
#########
# # #
# . # . #
# # #
# . # . #
# # #
#########
#########
# # #
# ### . #
# # #
# . ### #
# # #
#########
#########
# # #
# ### # #
# # # # #
# # ### #
# # #
#########
#########
# #
# ### ###
# # # # #
### ### #
# #
#########
#########
# #
##### . #
# # #
# . #####
# #
#########
#########
# # #
# . ### #
# # #
# ### . #
# # #
#########
#########
# # #
# # ### #
# # # # #
# ### # #
# # #
#########
#########
# #
### ### #
# # # # #
# ### ###
# #
#########
#########
# #
# . #####
# # #
##### . #
# #
#########
</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{trans|C}}
<syntaxhighlight lang="raku" line>sub solve($hh, $ww, $recurse) {
my ($h, $w, $t, @grid) = $hh, $ww, 0;
state $cnt;
$cnt = 0 if $recurse;
($t, $w, $h) = ($w, $h, $w) if $h +& 1;
return 0 if $h == 1;
return 1 if $w == 1;
return $h if $w == 2;
return $w if $h == 2;
my ($cy, $cx) = ($h, $w) «div» 2;
my $len = ($h + 1) × ($w + 1);
@grid[$len--] = 0;
my @next = -1, -$w-1, 1, $w+1;
for $cx+1 ..^ $w -> $x {
$t = $cy × ($w + 1) + $x;
@grid[$_] = 1 for $t, $len-$t;
walk($cy - 1, $x);
}
sub walk($y, $x) {
constant @dir = <0 -1 0 1> Z <-1 0 1 0>;
$cnt += 2 and return if not $y or $y == $h or not $x or $x == $w;
my $t = $y × ($w+1) + $x;
@grid[$_]++ for $t, $len-$t;
walk($y + @dir[$_;0], $x + @dir[$_;1]) if not @grid[$t + @next[$_]] for 0..3;
@grid[$_]-- for $t, $len-$t;
}
$cnt++;
if $h == $w { $cnt ×= 2 }
elsif $recurse and not $w +& 1 { solve($w, $h, False) }
$cnt
}
((1..9 X 1..9).grep:{ .[0] ≥ .[1] }).flat.map: -> $y, $x {
say "$y × $x: " ~ solve $y, $x, True unless $x +& 1 and $y +& 1;
}</syntaxhighlight>
{{out}}
<pre>2 × 1: 1
2 × 2: 2
3 × 2: 3
4 × 1: 1
4 × 2: 4
4 × 3: 9
4 × 4: 22
5 × 2: 5
5 × 4: 39
6 × 1: 1
6 × 2: 6
6 × 3: 23
6 × 4: 90
6 × 5: 263
6 × 6: 1018
7 × 2: 7
7 × 4: 151
7 × 6: 2947
8 × 1: 1
8 × 2: 8
8 × 3: 53
8 × 4: 340
8 × 5: 1675
8 × 6: 11174
8 × 7: 55939
8 × 8: 369050
9 × 2: 9
9 × 4: 553
9 × 6: 31721
9 × 8: 1812667</pre>
=={{header|REXX}}==
===idiomatic===
<syntaxhighlight lang="rexx">/*REXX program cuts rectangles into two symmetric pieces, the rectangles are cut along */
/*────────────────────────────────────────────────── unit dimensions and may be rotated.*/
numeric digits 20 /*be able to handle some big integers. */
parse arg N .; if N=='' | N=="," then N= 10 /*N not specified? Then use default.*/
dir.= 0; dir.0.1= -1; dir.1.0= -1; dir.2.1= 1; dir.3.0= 1 /*the four directions*/
do y=2 to N; say /*calculate rectangles up to size NxN.*/
do x=1 for y; if x//2 & y//2 then iterate /*Both X&Y odd? Skip.*/
z= solve(y,x,1); _= comma(z); _= right(_, max(14, length(_))) /*align output.*/
say right(y, 9) "x" right(x, 2) 'rectangle can be cut' _ "way"s(z).
end /*x*/
end /*y*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
comma: procedure; arg _; do k=length(_)-3 to 1 by -3; _=insert(',',_,k); end; return _
s: if arg(1)=1 then return arg(3); return word( arg(2) 's', 1) /*pluralizer.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
solve: procedure expose # @. dir. h len next. w; @.= 0 /*zero rectangle coördinates.*/
parse arg h,w,recur /*get values for some args. */
if h//2 then do; t= w; w= h; h= t; if h//2 then return 0
end
if w==1 then return 1
if w==2 then return h
if h==2 then return w /* [↓] % is REXX's integer ÷*/
cy= h % 2; cx= w % 2; wp= w + 1 /*cut the rectangle in half. */
len= (h+1) * wp - 1 /*extend area of rectangle. */
next.0= '-1'; next.1= -wp; next.2= 1; next.3= wp /*direction & distance*/
if recur then #= 0
cywp= cy * wp /*shortcut calculation*/
do x=cx+1 to w-1; t= cywp + x; @.t= 1
_= len - t; @._= 1; call walk cy - 1, x
end /*x*/
#= # + 1
if h==w then #= # + # /*double rectangle cut count.*/
else if w//2==0 & recur then call solve w, h, 0
return #
/*──────────────────────────────────────────────────────────────────────────────────────*/
walk: procedure expose # @. dir. h len next. w wp; parse arg y,x
if y==h | x==0 | x==w | y==0 then do; #= # + 2; return; end
t= y*wp + x; @.t= @.t + 1; _= len - t
@._= @._ + 1
do j=0 for 4; _= t + next.j /*try each of 4 directions.*/
if @._==0 then call walk y + dir.j.0, x + dir.j.1
end /*j*/
@.t= @.t - 1
_= len - t; @._= @._ - 1; return</syntaxhighlight>
{{out|output|text= when using the default input:}}
<pre>
2 x 1 rectangle can be cut 1 way.
2 x 2 rectangle can be cut 2 ways.
3 x 2 rectangle can be cut 3 ways.
4 x 1 rectangle can be cut 1 way.
4 x 2 rectangle can be cut 4 ways.
4 x 3 rectangle can be cut 9 ways.
4 x 4 rectangle can be cut 22 ways.
5 x 2 rectangle can be cut 5 ways.
5 x 4 rectangle can be cut 39 ways.
6 x 1 rectangle can be cut 1 way.
6 x 2 rectangle can be cut 6 ways.
6 x 3 rectangle can be cut 23 ways.
6 x 4 rectangle can be cut 90 ways.
6 x 5 rectangle can be cut 263 ways.
6 x 6 rectangle can be cut 1,018 ways.
7 x 2 rectangle can be cut 7 ways.
7 x 4 rectangle can be cut 151 ways.
7 x 6 rectangle can be cut 2,947 ways.
8 x 1 rectangle can be cut 1 way.
8 x 2 rectangle can be cut 8 ways.
8 x 3 rectangle can be cut 53 ways.
8 x 4 rectangle can be cut 340 ways.
8 x 5 rectangle can be cut 1,675 ways.
8 x 6 rectangle can be cut 11,174 ways.
8 x 7 rectangle can be cut 55,939 ways.
8 x 8 rectangle can be cut 369,050 ways.
9 x 2 rectangle can be cut 9 ways.
9 x 4 rectangle can be cut 553 ways.
9 x 6 rectangle can be cut 31,721 ways.
9 x 8 rectangle can be cut 1,812,667 ways.
10 x 1 rectangle can be cut 1 way.
10 x 2 rectangle can be cut 10 ways.
10 x 3 rectangle can be cut 115 ways.
10 x 4 rectangle can be cut 1,228 ways.
10 x 5 rectangle can be cut 10,295 ways.
10 x 6 rectangle can be cut 118,276 ways.
10 x 7 rectangle can be cut 1,026,005 ways.
10 x 8 rectangle can be cut 11,736,888 ways.
10 x 9 rectangle can be cut 99,953,769 ways.
10 x 10 rectangle can be cut 1,124,140,214 ways.
</pre>
===optimized===
This version replaced the (first) multiple clause '''if''' instructions in the '''walk''' subroutine with a
<br>''short circuit'' version. Other optimizations were also made. This made the program about '''20%''' faster.
<br><br>A test run was executed to determine the order of the '''if''' statements (by counting which
<br>comparison would yield the most benefit by placing it first).
Also, I've discovered a formula for calculating the number of cuts for even '''M''' when '''N''' is '''3'''.
<syntaxhighlight lang="rexx">/*REXX program cuts rectangles into two symmetric pieces, the rectangles are cut along */
/*────────────────────────────────────────────────── unit dimensions and may be rotated.*/
numeric digits 40 /*be able to handle some big integers. */
parse arg m . /*obtain optional argument from the CL.*/
if m=='' | m=="," then m= 9 /*Not specified? Then use the default.*/
if m<0 then start= max(2, abs(m) ) /*<0? Then just use this size rectangle*/
else start= 2 /*start from two for regular invocation*/
dir.= 0; dir.0.1= -1; dir.1.0= -1; dir.2.1= 1; dir.3.0= 1 /*the 4 directions.*/
$= '# @. dir. h len next. w wp'
/*define the default for memoizations. */
do y=start to abs(m); yOdd= y//2; say /*calculate rectangles up to size MxM.*/
do x=1 for y; if x//2 then if yOdd then iterate /*X and Y odd? Skip.*/
z= solve(y, x, 1); zc= comma(z) /*add commas to the result for SOLVE. */
zca= right(zc, max(14,length(zc) ) ) /*align the output for better perusing.*/
say right(y, 9) "x" right(x, 2) 'rectangle can be cut' zca "way"s(z).
end /*x*/
end /*y*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
comma: procedure; arg ?; do k=length(?)-3 to 1 by -3; ?=insert(',',?,k); end; return ?
s: if arg(1)=1 then return arg(3); return word(arg(2) 's', 1) /*pluralizer.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
solve: procedure expose ($); @.= 0 /*zero rectangle coördinates.*/
parse arg h,w,recurse /*get values for some args. */
if w==3 then do; z= h % 2 + 2; return 2**z - (z + z) + 1
end
if h//2 then do; t= w; w= h; h= t; if h//2 then return 0
end
if w==1 then return 1
if w==2 then return h
if h==2 then return w /* [↓] % is REXX's integer division.*/
cy= h % 2; cx= w % 2; wp= w + 1 /*cut the [XY] rectangle in half. */
len= (h+1) * wp - 1 /*extend the area of the rectangle. */
next.0= '-1'; next.1= -wp; next.2= 1; next.3= wp /*direction & distance*/
if recurse then #= 0 /*doing recursion ? */
cywp= cy * wp /*shortcut calculation*/
do x=cx+1 to w-1; t= cywp + x; @.t= 1
__= len - t; @.__= 1; call walk cy - 1, x
end /*x*/
#= # + 1
if h==w then #= # + # /*double the count of rectangle cuts. */
else if w//2==0 then if recurse then call solve w, h, 0
return #
/*──────────────────────────────────────────────────────────────────────────────────────*/
walk: procedure expose ($); parse arg y,x
if y==h then do; #= # + 2; return; end /* ◄──┐ REXX short circuit. */
if x==0 then do; #= # + 2; return; end /* ◄──┤ " " " */
if x==w then do; #= # + 2; return; end /* ◄──┤ " " " */
if y==0 then do; #= # + 2; return; end /* ◄──┤ " " " */
q= y*wp + x; @.q= @.q + 1; _= len - q /* │ordered by most likely ►──┐*/
@._= @._ + 1 /* └──────────────────────────┘*/
do j=0 for 4; _= q + next.j /*try each of the four directions.*/
if @._==0 then do; yn= y + dir.j.0
if yn==h then do; #= # + 2; iterate; end
xn= x + dir.j.1
if xn==0 then do; #= # + 2; iterate; end
if xn==w then do; #= # + 2; iterate; end
if yn==0 then do; #= # + 2; iterate; end
call walk yn, xn
end
end /*j*/
@.q= @.q - 1; _= len - q; @._= @._ - 1; return</syntaxhighlight>
{{out|output|text= is the same as the idiomatic version (above).}} <br><br>
=={{header|Ruby}}==
{{trans|Python}}
<syntaxhighlight lang="ruby">def cut_it(h, w)
if h.odd?
return 0 if w.odd?
h, w = w, h
end
return 1 if w == 1
nxt = [[w+1, 1, 0], [-w-1, -1, 0], [-1, 0, -1], [1, 0, 1]] # [next,dy,dx]
blen = (h + 1) * (w + 1) - 1
grid = [false] * (blen + 1)
walk = lambda do |y, x, count=0|
return count+1 if y==0 or y==h or x==0 or x==w
t = y * (w + 1) + x
grid[t] = grid[blen - t] = true
nxt.each do |nt, dy, dx|
count += walk[y + dy, x + dx] unless grid[t + nt]
end
grid[t] = grid[blen - t] = false
count
end
t = h / 2 * (w + 1) + w / 2
if w.odd?
grid[t] = grid[t + 1] = true
count = walk[h / 2, w / 2 - 1]
count + walk[h / 2 - 1, w / 2] * 2
else
grid[t] = true
count = walk[h / 2, w / 2 - 1]
return count * 2 if h == w
count + walk[h / 2 - 1, w / 2]
end
end
for w in 1..9
for h in 1..w
puts "%d x %d: %d" % [w, h, cut_it(w, h)] if (w * h).even?
end
end</syntaxhighlight>
{{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
</pre>
===Show each of the cuts===
<syntaxhighlight lang="ruby">class Rectangle
DIRS = [[1, 0], [-1, 0], [0, -1], [0, 1]]
def initialize(h, w)
raise ArgumentError if (h.odd? and w.odd?) or h<=0 or w<=0
@h, @w = h, w
@limit = h * w / 2
end
def cut(disp=true)
@cut = {}
@select = []
@result = []
@grid = make_grid
walk(0,0)
display if disp
@result
end
def make_grid
Array.new(@h+1) {|i| Array.new(@w+1) {|j| true if i<@h and j<@w }}
end
def walk(y, x)
@grid[y][x] = @grid[@h-y-1][@w-x-1] = false
@select.push([y,x])
select = @select.sort
unless @cut[select]
@cut[select] = true
if @select.size == @limit
@result << select
else
search_next.each {|yy,xx| walk(yy,xx)}
end
end
@select.pop
@grid[y][x] = @grid[@h-y-1][@w-x-1] = true
end
def search_next
nxt = {}
@select.each do |y,x|
DIRS.each do |dy, dx|
nxt[[y+dy, x+dx]] = true if @grid[y+dy][x+dx]
end
end
nxt.keys
end
def display
@result.each do |select|
@grid = make_grid
select.each {|y,x| @grid[y][x] = false}
puts to_s
end
end
def to_s
text = Array.new(@h*2+1) {" " * (@w*4+1)}
for i in 0..@h
for j in 0..@w
text[i*2][j*4+1,3] = "---" if @grid[i][j] != @grid[i-1][j]
text[i*2+1][j*4] = "|" if @grid[i][j] != @grid[i][j-1]
text[i*2][j*4] = "+"
end
end
text.join("\n")
end
end
rec = Rectangle.new(2,2)
puts rec.cut.size
rec = Rectangle.new(3,4)
puts rec.cut.size</syntaxhighlight>
{{out}}
<pre style="height:64ex;overflow:scroll">
+---+---+
| | |
+ + +
| | |
+---+---+
+---+---+
| |
+---+---+
| |
+---+---+
2
+---+---+---+---+
| | |
+ + +---+ +
| | |
+ +---+ + +
| | |
+---+---+---+---+
+---+---+---+---+
| | |
+ + + + +
| | |
+ + + + +
| | |
+---+---+---+---+
+---+---+---+---+
| | |
+ +---+ + +
| | | | |
+ + +---+ +
| | |
+---+---+---+---+
+---+---+---+---+
| |
+ + +---+---+
| | |
+---+---+ + +
| |
+---+---+---+---+
+---+---+---+---+
| |
+ +---+ +---+
| | | | |
+---+ +---+ +
| |
+---+---+---+---+
+---+---+---+---+
| | |
+ +---+ + +
| | |
+ + +---+ +
| | |
+---+---+---+---+
+---+---+---+---+
| | |
+ + +---+ +
| | | | |
+ +---+ + +
| | |
+---+---+---+---+
+---+---+---+---+
| |
+---+ +---+ +
| | | | |
+ +---+ +---+
| |
+---+---+---+---+
+---+---+---+---+
| |
+---+---+ + +
| | |
+ + +---+---+
| |
+---+---+---+---+
9
</pre>
=={{header|Rust}}==
{{trans|Python}}
<syntaxhighlight lang="rust">
fn cwalk(mut vis: &mut Vec<Vec<bool>>, count: &mut isize, w: usize, h: usize, y: usize, x: usize, d: usize) {
if x == 0 || y == 0 || x == w || y == h {
*count += 1;
return;
}
vis[y][x] = true;
vis[h - y][w - x] = true;
if x != 0 && ! vis[y][x - 1] {
cwalk(&mut vis, count, w, h, y, x - 1, d | 1);
}
if d & 1 != 0 && x < w && ! vis[y][x+1] {
cwalk(&mut vis, count, w, h, y, x + 1, d | 1);
}
if y != 0 && ! vis[y - 1][x] {
cwalk(&mut vis, count, w, h, y - 1, x, d | 2);
}
if d & 2 != 0 && y < h && ! vis[y + 1][x] {
cwalk(&mut vis, count, w, h, y + 1, x, d | 2);
}
vis[y][x] = false;
vis[h - y][w - x] = false;
}
fn count_only(x: usize, y: usize) -> isize {
let mut count = 0;
let mut w = x;
let mut h = y;
if (h * w) & 1 != 0 {
return count;
}
if h & 1 != 0 {
std::mem::swap(&mut w, &mut h);
}
let mut vis = vec![vec![false; w + 1]; h + 1];
vis[h / 2][w / 2] = true;
if w & 1 != 0 {
vis[h / 2][w / 2 + 1] = true;
}
let mut res;
if w > 1 {
cwalk(&mut vis, &mut count, w, h, h / 2, w / 2 - 1, 1);
res = 2 * count - 1;
count = 0;
if w != h {
cwalk(&mut vis, &mut count, w, h, h / 2 + 1, w / 2, if w & 1 != 0 { 3 } else { 2 });
}
res += 2 * count - if w & 1 == 0 { 1 } else { 0 };
}
else {
res = 1;
}
if w == h {
res = 2 * res + 2;
}
res
}
fn main() {
for y in 1..10 {
for x in 1..y + 1 {
if x & 1 == 0 || y & 1 == 0 {
println!("{} x {}: {}", y, x, count_only(x, y));
}
}
}
}
</syntaxhighlight>
=={{header|Tcl}}==
{{trans|C}}
<
proc walk {y x} {
Line 815 ⟶ 4,042:
}
}
}} 10</
Output is identical.
=={{header|Wren}}==
{{trans|C}}
{{libheader|Wren-fmt}}
Last two are very slooow to emerge (about 7¼ mins overall).
<syntaxhighlight lang="wren">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) {
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) {
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))
}
}
}</syntaxhighlight>
{{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|XPL0}}==
{{trans|C}}
Works on Raspberry Pi. ReallocMem is not available in the DOS versions. Takes about 40 seconds on Pi4.
<syntaxhighlight lang "XPL0">include xpllib; \for Print
char Grid;
int W, H, Len, Cnt;
int Next(4), Dir;
proc Walk(Y, X);
int Y, X;
int I, T;
[if Y=0 or Y=H or X=0 or X=W then
[Cnt:= Cnt+2; return];
T:= Y * (W + 1) + X;
Grid(T):= Grid(T)+1;
Grid(Len-T):= Grid(Len-T)+1;
for I:= 0 to 4-1 do
if Grid(T + Next(I)) = 0 then
Walk(Y+Dir(I,0), X+Dir(I,1));
Grid(T):= Grid(T)-1;
Grid(Len-T):= Grid(Len-T)-1;
];
func Solve(HH, WW, Recur);
int HH, WW, Recur;
int T, CX, CY, X;
[H:= HH; W:= WW;
if H & 1 then [T:= W; W:= H; H:= T];
if H & 1 then return 0;
if W = 1 then return 1;
if W = 2 then return H;
if H = 2 then return W;
CY:= H/2; CX:= W/2;
Len:= (H + 1) * (W + 1);
Grid:= ReallocMem(Grid, Len);
FillMem(Grid, 0, Len); Len:= Len-1;
Next(0):= -1;
Next(1):= -W - 1;
Next(2):= 1;
Next(3):= W + 1;
if Recur then Cnt:= 0;
for X:= CX+1 to W-1 do
[T:= CY * (W + 1) + X;
Grid(T):= 1;
Grid(Len - T):= 1;
Walk(CY - 1, X);
];
Cnt:= Cnt+1;
if H = W then Cnt:= Cnt * 2
else if (W&1) = 0 and Recur then Solve(W, H, 0);
return Cnt;
];
int Y, X;
[Grid:= 0;
Dir:= [[0, -1], [-1, 0], [0, 1], [1, 0]];
for Y:= 1 to 10 do
for X:= 1 to Y do
if (X&1) = 0 or (Y&1) = 0 then
Print("%d x %d: %d\n", Y, X, Solve(Y, X, 1));
]</syntaxhighlight>
{{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}}==
{{trans|Ruby}}
<syntaxhighlight lang="zkl">fcn cut_it(h,w){
if(h.isOdd){
if(w.isOdd) return(0);
t,h,w=h,w,t; // swap w,h: a,b=c,d --> a=c; b=d; so need a tmp
}
if(w==1) return(1);
nxt :=T(T(w+1, 1,0), T(-w-1, -1,0), T(-1, 0,-1), T(1, 0,1)); #[next, dy,dx]
blen:=(h + 1)*(w + 1) - 1;
grid:=(blen + 1).pump(List(),False); //-->L(False,False...)
walk:='wrap(y,x){ // lambda closure
if(y==0 or y==h or x==0 or x==w) return(1);
count,t:=0,y*(w + 1) + x;
grid[t]=grid[blen - t]=True;
foreach nt,dy,dx in (nxt){
if(not grid[t + nt]) count+=self.fcn(y + dy, x + dx,vm.pasteArgs(2));
}
grid[t]=grid[blen - t]=False;
count
};
t:=h/2*(w + 1) + w/2;
if(w.isOdd){
grid[t]=grid[t + 1]=True;
count:=walk(h/2, w/2 - 1);
count + walk(h/2 - 1, w/2)*2;
}else{
grid[t]=True;
count:=walk(h/2, w/2 - 1);
if(h==w) return(count*2);
count + walk(h/2 - 1, w/2);
}
}</syntaxhighlight>
Note the funkiness in walk: vm.pasteArgs. This is because zkl functions are unaware of their scope, so a closure is needed (when calling walk) to capture state (nxt, blen, grid, h, w). Rather than creating a closure object each call, that state is passed in the arg list. So, when doing recursion, that state needs to be restored to the stack (the compiler isn't smart enough to recognize this case).
<syntaxhighlight lang="zkl">foreach w,h in ([1..9],[1..w]){
if((w*h).isEven) println("%d x %d: %d".fmt(w, h, cut_it(w,h)));
}</syntaxhighlight>
{{out}}
Output is identical.
<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
...
9 x 2: 9
9 x 4: 553
9 x 6: 31721
</pre>
{{omit from|GUISS}}
{{omit from|Lilypond}}
{{omit from|TPP}}
[[Category:Geometry]]
| |||