Cut a rectangle: Difference between revisions
m
Added Easylang
m (→optimized: added wording to the output section header.) |
m (Added Easylang) |
||
(34 intermediate revisions by 15 users not shown) | |||
Line 7:
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))
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]];
Line 476 ⟶ 822:
if (!(x & 1) || !(y & 1))
printf("%d x %d: %llu\n", y, x, solve(y, x, true));
}</
{{out}}
<pre>2 x 1: 1
Line 519 ⟶ 865:
10 x 10: 1124140214</pre>
Using the LDC2 compiler the runtime is about 15.98 seconds (the first C entry runs in about 16.75 seconds with GCC).
=={{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>
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
Line 558 ⟶ 1,121:
end
</syntaxhighlight>
<syntaxhighlight lang="eiffel">
class
GRID
Line 723 ⟶ 1,286:
end
</syntaxhighlight>
<syntaxhighlight lang="eiffel">
class
POINT
Line 772 ⟶ 1,335:
end
</syntaxhighlight>
{{out}}
<pre>
Line 820 ⟶ 1,383:
{{trans|Ruby}}
===Count only===
<
defmodule Rectangle do
Line 860 ⟶ 1,423:
if is_even(w * h), do: IO.puts "#{w} x #{h}: #{Rectangle.cut_it(w, h)}"
end)
end)</
{{out}}
Line 898 ⟶ 1,461:
===Show each of the cuts===
{{works with|Elixir|1.2}}
<
def cut(h, w, disp\\true) when rem(h,2)==0 or rem(w,2)==0 do
limit = div(h * w, 2)
Line 974 ⟶ 1,537:
Rectangle.cut(2, 2) |> length |> IO.puts
Rectangle.cut(3, 4) |> length |> IO.puts</
{{out}}
Line 1,057 ⟶ 1,620:
=={{header|Go}}==
{{trans|C}}
<
import "fmt"
Line 1,138 ⟶ 1,701:
}
}
}</
{{out}}
<pre>
Line 1,182 ⟶ 1,745:
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}}==
Line 1,187 ⟶ 1,856:
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.
<
import Data.STRef
import Control.Monad (forM_, when)
Line 1,267 ⟶ 1,936:
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 1,278 ⟶ 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 1,286 ⟶ 1,955:
Example use:
<
┌────┬────┬────┬────┬────┬────┬────┬────┬────┐
│.###│.###│..##│...#│...#│....│....│....│....│
Line 1,310 ⟶ 1,979:
│.##.#│.#..#│#..##│#.###│#####│###.#│##..#│#..#.│#.##.│####.│###..│##...│#....│
│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘</
=={{header|Java}}==
{{works with|Java|7}}
<
public class CutRectangle {
Line 1,379 ⟶ 2,048:
System.out.println();
}
}</
<pre>[2, 2]
Line 1,422 ⟶ 2,091:
[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}}
<
object RectangleCutter {
Line 1,500 ⟶ 2,400:
}
}
}</
{{out}}
Line 1,545 ⟶ 2,445:
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.
<
use warnings;
my @grid = 0;
Line 1,630 ⟶ 2,892:
}
MAIN();</
=={{header|Phix}}==
Using a completely different home-brewed
<!--<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)
<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
<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.
--
<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
<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
<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: #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
Line 1,924 ⟶ 3,082:
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 1,958 ⟶ 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 1,976 ⟶ 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 2,013 ⟶ 3,172:
===Faster version===
{{trans|D}}
<
import psyco
except ImportError:
Line 2,082 ⟶ 3,241:
print "%d x %d: %d" % (y, x, count_only(x, y))
main()</
The output is the same.
=={{header|Racket}}==
<
#lang racket
Line 2,135 ⟶ 3,294:
(newline)
(cuts 4 3 #f)
</syntaxhighlight>
{{out}}
Line 2,243 ⟶ 3,402:
#########
</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===
<
/*────────────────────────────────────────────────── unit dimensions and may be rotated.*/
numeric digits 20 /*be able to handle some big integers. */
parse arg N .; if N=='' | N=="," then N=
dir.= 0; dir.0.1= -1; dir.1.0= -1; dir.2.1= 1; dir.3.0= 1
do y=2 to N; say /*calculate rectangles up to size NxN.*/
do x=1 for y; if x//2 & y//2 then iterate
z= solve(y,x,1); _= comma(z); _= right(_, max(14, length(_))) /*align
say right(y, 9)
end /*x*/
end /*y*/
Line 2,261 ⟶ 3,495:
/*──────────────────────────────────────────────────────────────────────────────────────*/
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 /* [↓]
cy= h % 2; cx= w % 2;
len= (h+1) * wp - 1 /*extend
next.0= '-1';
if recur then #= 0
cywp= cy * wp
_= len - t; @._= 1; call walk cy - 1, x
end /*x*/
#= # + 1
if h==w then #= # + #
else if w//2==0 & recur then call solve w, h, 0
return #
/*──────────────────────────────────────────────────────────────────────────────────────*/
walk: procedure expose #
if y==h | x==0 | x==w | y==0 then do; #= # + 2; return; end
t=
@._= @._ + 1
do j=0 for 4;
if @._==0 then call walk y + dir.j.0, x + dir.j.1
end /*j*/
@.t= @.t - 1
_= len - t;
{{out|output|text= when using the default input:}}
<pre>
Line 2,346 ⟶ 3,580:
===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
parse arg m . /*obtain optional argument from the CL.*/
if m=='' | m=="," then m= 9 /*Not specified? Then use the default.*/
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
s: if arg(1)=1 then return arg(3); return word(arg(2) 's', 1) /*pluralizer.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
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
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;
len= (h+1) * wp - 1
next.0= '-1';
if
cywp= cy * wp
__= len - t; @.__= 1; call walk cy - 1, x
end /*x*/
#= # + 1
if h==w then #= # + #
else if w//2==0 then if recurse then call solve w, h, 0
return #
/*──────────────────────────────────────────────────────────────────────────────────────*/
walk: procedure expose
if y==h then do; #= # + 2; return;
if x==0 then do; #= # + 2; return;
if x==w then do; #= # + 2; return;
if y==0 then do; #= # + 2; return;
@._= @._ +
do j=0 for 4; _=
if @._==0 then do; yn= y + dir.j.0
if yn==h then do; #= # + 2; iterate; end
if xn==
if
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}}
<
if h.odd?
return 0 if w.odd?
Line 2,447 ⟶ 3,690:
puts "%d x %d: %d" % [w, h, cut_it(w, h)] if (w * h).even?
end
end</
{{out}}
Line 2,484 ⟶ 3,727:
===Show each of the cuts===
<
DIRS = [[1, 0], [-1, 0], [0, -1], [0, 1]]
def initialize(h, w)
Line 2,557 ⟶ 3,800:
rec = Rectangle.new(3,4)
puts rec.cut.size</
{{out}}
Line 2,640 ⟶ 3,883:
=={{header|Rust}}==
{{trans|Python}}
<
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 {
Line 2,714 ⟶ 3,957:
}
}
</syntaxhighlight>
=={{header|Tcl}}==
{{trans|C}}
<
proc walk {y x} {
Line 2,799 ⟶ 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}}
<
if(h.isOdd){
if(w.isOdd) return(0);
Line 2,837 ⟶ 4,310:
count + walk(h/2 - 1, w/2);
}
}</
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).
<
if((w*h).isEven) println("%d x %d: %d".fmt(w, h, cut_it(w,h)));
}</
{{out}}
Output is identical.
|