Rosetta Code

Cut a rectangle: Difference between revisions

Page Discussion

Cut a rectangle (view source)

Revision as of 18:25, 7 April 2024

66,741 bytes added ,  1 month ago
m
Added Easylang
(Added Elixir)
m (Added Easylang)
 
(45 intermediate revisions by 17 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.
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
Line 89 ⟶ 175:
 
return 0;
}</langsyntaxhighlight>output<syntaxhighlight lang="text">2 x 1: 1
2 x 2: 2
3 x 2: 3
Line 128 ⟶ 214:
10 x 8: 11736888
10 x 9: 99953769
10 x 10: 1124140214</langsyntaxhighlight>
 
More awkward solution: after compiling, run <code>./a.out -v [width] [height]</code> for display of cuts.
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
 
Line 321 ⟶ 407:
bail: fprintf(stderr, "bad args\n");
return 1;
}</langsyntaxhighlight>
 
=={{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.
<langsyntaxhighlight lang="lisp">(defun cut-it (w h &optional (recur t))
(if (oddp (* w h)) (return-from cut-it 0))
(if (oddp h) (rotatef w h))
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)))))</langsyntaxhighlight>output<syntaxhighlight lang="text">2 x 1: 2
2 x 2: 2
3 x 2: 3
Line 396 ⟶ 742:
9 x 4: 553
9 x 6: 31721
9 x 8: 1812667</langsyntaxhighlight>
 
=={{header|D}}==
{{trans|C}}
<langsyntaxhighlight lang="d">import core.stdc.stdio, core.stdc.stdlib, core.stdc.string, std.typecons;
 
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));
}</langsyntaxhighlight>
{{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">
<lang Eiffel>
class
APPLICATION
Line 558 ⟶ 1,121:
 
end
</syntaxhighlight>
</lang>
<syntaxhighlight lang="eiffel">
<lang Eiffel>
class
GRID
Line 723 ⟶ 1,286:
 
end
</syntaxhighlight>
</lang>
<syntaxhighlight lang="eiffel">
<lang Eiffel>
class
POINT
Line 772 ⟶ 1,335:
 
end
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 820 ⟶ 1,383:
{{trans|Ruby}}
===Count only===
<langsyntaxhighlight lang="elixir">import Integer
 
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)</langsyntaxhighlight>
 
{{out}}
Line 898 ⟶ 1,461:
===Show each of the cuts===
{{works with|Elixir|1.2}}
<langsyntaxhighlight 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)
Line 974 ⟶ 1,537:
 
Rectangle.cut(2, 2) |> length |> IO.puts
Rectangle.cut(3, 4) |> length |> IO.puts</langsyntaxhighlight>
 
{{out}}
Line 1,057 ⟶ 1,620:
=={{header|Go}}==
{{trans|C}}
<langsyntaxhighlight lang="go">package main
 
import "fmt"
Line 1,138 ⟶ 1,701:
}
}
}</langsyntaxhighlight>
{{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.
<langsyntaxhighlight Haskelllang="haskell">import qualified Data.Vector.Unboxed.Mutable as V
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>
</lang>
With GHC -O3 the run-time is about 39 times the D entry.
 
=={{header|J}}==
 
<langsyntaxhighlight lang="j">init=: - {. 1: NB. initial state: 1 square choosen
prop=: < {:,~2 ~:/\ ] NB. propagate: neighboring squares (vertically)
poss=: I.@,@(prop +. prop"1 +. prop&.|. +. prop&.|."1)
Line 1,278 ⟶ 1,947:
N=: <:@-:@#@, NB. how many neighbors to add
step=: [: ~.@; <@(((= i.@$) +. ])"0 _~ keep)"2
all=: step^:N@init</langsyntaxhighlight>
 
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:
 
<langsyntaxhighlight lang="j"> '.#' <"2@:{~ all 3 4
┌────┬────┬────┬────┬────┬────┬────┬────┬────┐
│.###│.###│..##│...#│...#│....│....│....│....│
Line 1,310 ⟶ 1,979:
│.##.#│.#..#│#..##│#.###│#####│###.#│##..#│#..#.│#.##.│####.│###..│##...│#....│
│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘</langsyntaxhighlight>
 
=={{header|Java}}==
{{works with|Java|7}}
<langsyntaxhighlight lang="java">import java.util.*;
 
public class CutRectangle {
Line 1,379 ⟶ 2,048:
System.out.println();
}
}</langsyntaxhighlight>
 
<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}}
<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.
<langsyntaxhighlight lang="perl">use strict;
use warnings;
my @grid = 0;
Line 1,507 ⟶ 2,892:
}
 
MAIN();</langsyntaxhighlight>
 
=={{header|Perl 6Phix}}==
Using a completely different home-brewed algorithm, slightly sub-optimal as noted in the code.
{{trans|C}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
 
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
This is a very dumb, straightforward translation of the C code. It is very slow so we'll interrupt the execution and display the partial output.
<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>
<lang perl6>subset Byte of Int where ^256;
<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>
my @grid of Byte = 0;
 
<span style="color: #004080;">sequence</span> <span style="color: #000000;">grid</span>
my Int ($w, $h, $len);
my Int $cnt = 0;
<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>
my @next;
my @dir = [0, -1], [-1, 0], [0, 1], [1, 0];
<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>
sub walk(Int $y, Int $x) {
my ($i, $t);
<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>
if !$y || $y == $h || !$x || $x == $w {
<span style="color: #000080;font-style:italic;">-- plant/reset ch and the symmetric copy</span>
$cnt += 2;
<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>
return;
<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>
$t = $y * ($w + 1) + $x;
@grid[$t]++, @grid[$len - $t]++;
<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>
loop ($i = 0; $i < 4; $i++) {
<span style="color: #000000;">chx</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"-||-"</span>
if !@grid[$t + @next[$i]] {
walk($y + @dir[$i][0], $x + @dir[$i][1]);
<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>
@grid[$t]--, @grid[$len - $t]--;
<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>
sub solve(Int $hh, Int $ww, Int $recur) returns Int {
<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>
my ($t, $cx, $cy, $x);
<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>
$h = $hh, $w = $ww;
<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>
if $h +& 1 { $t = $w, $w = $h, $h = $t; }
<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>
if $h +& 1 { return 0; }
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if $w == 1 { return 1; }
<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>
if $w == 2 { return $h; }
<span style="color: #008080;">if</span> <span style="color: #000000;">meet</span> <span style="color: #008080;">then</span>
if $h == 2 { return $w; }
<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>
$cy = $h div 2, $cx = $w div 2;
<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)
$len = ($h + 1) * ($w + 1);
-- fill in(/overwrite) the last cut, if any</span>
@grid = ();
<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>
@grid[$len--] = 0;
<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>
@next[0] = -1;
<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>
@next[1] = -$w - 1;
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
@next[2] = 1;
<span style="color: #008080;">else</span>
@next[3] = $w + 1;
<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>
if $recur { $cnt = 0; }
<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>
loop ($x = $cx + 1; $x < $w; $x++) {
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
$t = $cy * ($w + 1) + $x;
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
@grid[$t] = 1;
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
@grid[$len - $t] = 1;
<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>
walk($cy - 1, $x);
<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>
$cnt++;
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if $h == $w {
<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>
$cnt *= 2;
<span style="color: #000080;font-style:italic;">-- ((level=0)==leave outer edges 'x' for next iteration)</span>
} elsif !($w +& 1) && $recur {
<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>
solve($w, $h, 0);
<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>
return $cnt;
<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>
my ($y, $x);
<span style="color: #000080;font-style:italic;">-- The outer edges are 'x'; the inner '+' become 'x' when visited.
loop ($y = 1; $y <= 10; $y++) {
-- Likewise edges are cuts but the inner ones get filled in later.</span>
loop ($x = 1; $x <= $y; $x++) {
<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>
if (!($x +& 1) || !($y +& 1)) {
<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>
printf("%d x %d: %d\n", $y, $x, solve($y, $x, 1));
<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>
}</lang>
<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 &gt;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
<pre>
2 x 1: 1
2 x 2: 2
3 x 2: 3
Line 1,605 ⟶ 3,030:
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
Line 1,611 ⟶ 3,066:
8 x 4: 340
8 x 5: 1675
8 x 6: 11174
^C</pre>
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}}
<langsyntaxhighlight lang="python">def cut_it(h, w):
dirs = ((1, 0), (-1, 0), (0, -1), (0, 1))
if h &% 12: h, w = w, h
if h &% 12: return 0
if w == 1: return 1
count = 0
Line 1,646 ⟶ 3,117:
 
t = h // 2 * (w + 1) + w // 2
if w &% 12:
grid[t] = grid[t + 1] = True
count = walk(h // 2, w // 2 - 1, count)
Line 1,664 ⟶ 3,135:
for w in xrange(1, 10):
for h in xrange(1, w + 1):
if not((w * h) &% 12):
print "%d x %d: %d" % (w, h, cut_it(w, h))
 
main()</langsyntaxhighlight>
Output:
<pre>2 x 1: 1
Line 1,701 ⟶ 3,172:
===Faster version===
{{trans|D}}
<langsyntaxhighlight lang="python">try:
import psyco
except ImportError:
Line 1,770 ⟶ 3,241:
print "%d x %d: %d" % (y, x, count_only(x, y))
 
main()</langsyntaxhighlight>
The output is the same.
 
=={{header|Racket}}==
<langsyntaxhighlight lang="racket">
#lang racket
 
Line 1,823 ⟶ 3,294:
(newline)
(cuts 4 3 #f)
</syntaxhighlight>
</lang>
 
{{out}}
Line 1,931 ⟶ 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===
<langsyntaxhighlight lang="rexx">/*REXX program cuts rectangles into two symmetric pieces, the rectangles are cut along */
/*────────────────────────────── 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 /*4the 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 /*not if both /*Both X&Y odd? Skip.*/
_z= solve(y,x,1); _= comma(z); _= right(_, max(1014, length(_))) /*align the 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*/
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 rect. coördinates*/
solve: procedure expose # @. dir. h len next. w; @.= 0 /*zero rectangle coördinates.*/
parse arg hh 1 h,ww 1 w,recur /*obtain the values for some arguments.*/
ifparse arg h//2,w,recur then do; t=w; w=h; h=t; if h//2*get values thenfor returnsome 0args. */
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) * (w+1)wp - 1 /*extend the area of the rectangle. */
next.0= '-1'; next.1= -w-1wp; next.2= 1; next.3=w+1 wp /*direction & distance*/
if recur then #= 0
cywp= cy * wp do x=cx+1 to w-1; t=x+cy /*shortcut calculation*(w+1)/
do x=cx+1 to @.t= w-1; _t=len-t; cywp + @._=1x; call walk cy- @.t= 1,x
_= len - t; end /* @._= 1; call walk cy - 1, x*/
end /*x*/
#=#+1
#= # + 1
if h==w then #=#+# /*double the count of rectangle cuts. */
if h==w then #= # + # /*double rectangle cut count.*/
else if w//2==0 & recur then call solve w,h,0
else if w//2==0 & recur then call solve w, h, 0
return #
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*────────────────────────────────────────────────────────────────────────────*/
walk: procedure expose # dir@. @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=x + y*(wwp +1) x; @.t= @.t + 1; _= len - t
@._= @._ + 1
do j=0 for 4; _ _= t + next.j /*try foureach 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=&nbsp; when using the default input:}}
return</lang>
'''output''' &nbsp; 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 1018 ways.
 
76 x 21 rectangle can be cut 7 ways 1 way.
76 x 42 rectangle can be cut 151 6 ways.
76 x 63 rectangle can be cut 2947 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.
 
87 x 12 rectangle can be cut 1 way 7 ways.
87 x 24 rectangle can be cut 8 151 ways.
87 x 36 rectangle can be cut 53 2,947 ways.
8 x 4 rectangle can be cut 340 ways.
8 x 5 rectangle can be cut 1675 ways.
8 x 6 rectangle can be cut 11174 ways.
8 x 7 rectangle can be cut 55939 ways.
8 x 8 rectangle can be cut 369050 ways.
 
98 x 21 rectangle can be cut 9 ways 1 way.
98 x 42 rectangle can be cut 553 8 ways.
98 x 63 rectangle can be cut 31721 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 82 rectangle can be cut 1812667 9 ways.
10 9 x 14 rectangle can be cut 1 way 553 ways.
10 9 x 26 rectangle can be cut 1031,721 ways.
10 9 x 38 rectangle can be cut 1151,812,667 ways.
 
10 x 4 rectangle can be cut 1228 ways.
10 x 51 rectangle can be cut 10295 ways 1 way.
10 x 62 rectangle can be cut 118276 10 ways.
10 x 73 rectangle can be cut 1026005 115 ways.
10 x 84 rectangle can be cut 11736888 1,228 ways.
10 x 95 rectangle can be cut 99953769 10,295 ways.
10 x 10 6 rectangle can be cut 1124140214 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 &nbsp; '''if''' &nbsp; instructions in the &nbsp; '''walk''' &nbsp; subroutine with a
<br>''short circuit'' version. &nbsp; Other optimizations were also made. &nbsp; This made the program about &nbsp; '''20%''' &nbsp; faster.
<br><br>A test run was executed to determine the order of the &nbsp; '''if''' &nbsp; statements &nbsp; (by counting which
<br>comparison would yield the most benefit by placing it first).
<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=='' 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 /*4 directions.*/
 
Also, I've discovered a formula for calculating the number of cuts for even &nbsp; '''M''' &nbsp; when &nbsp; '''N''' &nbsp; is &nbsp; '''3'''.
do y=2 to N; say /*calculate rectangles up to size NxN.*/
<syntaxhighlight lang="rexx">/*REXX program cuts rectangles into two symmetric pieces, the rectangles are cut along */
do x=1 for y; if x//2 & y//2 then iterate /*not if both X&Y odd.*/
/*────────────────────────────────────────────────── unit dimensions and may be rotated.*/
_=solve(y,x,1); _=right(_,max(10,length(_))) /*align the output. */
numeric digits 40 /*be able to handle some big integers. */
say right(y,9) "x" right(x,2) 'rectangle can be cut' _ "way"s(_)'.'
parse arg m . /*obtain optional argument from the CL.*/
end /*x*/
if m=='' | m=="," then m= 9 /*Not specified? Then use the default.*/
end /*y*/
exit if m<0 then start= max(2, abs(m) ) /*stick<0? a fork in it,Then just we'reuse allthis done.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.*/
s: if arg(1)=1 then return arg(3); return word(arg(2) 's',1) /*pluralizer*/
$= '# @. dir. h len next. w wp'
/*────────────────────────────────────────────────────────────────────────────*/
/*define the default for memoizations. */
solve: procedure expose # dir. @. h len next. w; @.=0 /*zero rect. coördinates*/
do parse arg hhy=start 1 h,wwto 1abs(m); w,recur yOdd= y//2; say /*obtaincalculate rectangles theup valuesto forsize some argumentsMxM.*/
do x=1 for y; if hx//2 then do;if parseyOdd value then witerate h w with t/*X wand h;Y odd? if hSkip.*//2 then return 0
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) * (w+1)wp - 1 /*extend the area of the rectangle. */
next.0= '-1'; next.1= -w-1wp; next.2= 1; next.3=w+1 wp /*direction & distance*/
if recurrecurse then #= 0 /*doing recursion ? */
cywp= cy * wp do x=cx+1 to w-1; t=x+cy /*shortcut calculation*(w+1)/
do @.tx=cx+1; to _=lenw-t1; @._t=1; cywp + x; call walk cy-@.t= 1,x
__= endlen - t; @.__= 1; call walk cy - 1, /*x*/
end /*x*/
#=#+1
#= # + 1
if h==w then #=#+# /*double the count of rectangle cuts. */
if h==w then #= # + # else if w//2==0*double &the recurcount of thenrectangle callcuts. solve w,h,0*/
else if w//2==0 then if recurse then call solve w, h, 0
return #
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*────────────────────────────────────────────────────────────────────────────*/
walk: procedure expose #($); dir. @. h len next. w; 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 /* ◄──┤ " " " */
tq=x + y*(wwp +1) x; @.tq= @.tq + 1; _= len -t q /* │ordered by most likely ►──┐*/
@._= @._ + 1 /* └──────────────────────────┘*/
do j=0 for 4; _ = tq + next.j /*try 4each of the four directions.*/
if @._==0 then do; yn= y + dir.j.0
if yn=y+dir.j.0;=h then do; xn#=x # +dir.j.1 2; iterate; end
if yn==h then do; #xn=#+2; x iterate;+ enddir.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>
@.t=@.t-1
{{out|output|text=&nbsp; is the same as the idiomatic version &nbsp; (above).}} <br><br>
_=len-t; @._=@._-1
return</lang>
'''output''' &nbsp; is the same as the idiomatic version. <br><br>
 
=={{header|Ruby}}==
{{trans|Python}}
<langsyntaxhighlight lang="ruby">def cut_it(h, w)
if h.odd?
return 0 if w.odd?
Line 2,133 ⟶ 3,690:
puts "%d x %d: %d" % [w, h, cut_it(w, h)] if (w * h).even?
end
end</langsyntaxhighlight>
 
{{out}}
Line 2,170 ⟶ 3,727:
 
===Show each of the cuts===
<langsyntaxhighlight lang="ruby">class Rectangle
DIRS = [[1, 0], [-1, 0], [0, -1], [0, 1]]
def initialize(h, w)
Line 2,243 ⟶ 3,800:
 
rec = Rectangle.new(3,4)
puts rec.cut.size</langsyntaxhighlight>
 
{{out}}
Line 2,323 ⟶ 3,880:
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}}
<langsyntaxhighlight lang="tcl">package require Tcl 8.5
 
proc walk {y x} {
Line 2,407 ⟶ 4,042:
}
}
}} 10</langsyntaxhighlight>
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}}
<langsyntaxhighlight lang="zkl">fcn cut_it(h,w){
if(h.isOdd){
if(w.isOdd) return(0);
Line 2,445 ⟶ 4,310:
count + walk(h/2 - 1, w/2);
}
}</langsyntaxhighlight>
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).
<langsyntaxhighlight 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)));
}</langsyntaxhighlight>
{{out}}
Output is identical.
Chkas
1,983

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/202172...363378"