Rosetta Code

Cut a rectangle: Difference between revisions

Page Discussion

Cut a rectangle (view source)

Revision as of 18:25, 7 April 2024

60,906 bytes added ,  1 month ago
m
Added Easylang
(→‎{{header|Kotlin}}: Updated example see https://github.com/dkandalov/rosettacode-kotlin for details)
m (Added Easylang)
 
(39 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.
<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}}
<langsyntaxhighlight lang="scala">// version 1.0.6
 
object RectangleCutter {
Line 1,500 ⟶ 2,400:
}
}
}</langsyntaxhighlight>
 
{{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.
<langsyntaxhighlight lang="perl">use strict;
use warnings;
my @grid = 0;
Line 1,630 ⟶ 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,728 ⟶ 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,734 ⟶ 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,769 ⟶ 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,787 ⟶ 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,824 ⟶ 3,172:
===Faster version===
{{trans|D}}
<langsyntaxhighlight lang="python">try:
import psyco
except ImportError:
Line 1,893 ⟶ 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,946 ⟶ 3,294:
(newline)
(cuts 4 3 #f)
</syntaxhighlight>
</lang>
 
{{out}}
Line 2,054 ⟶ 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 */
/*────────────────────────────────────────────────── 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 10 /*N not specified? Then use default.*/
dir.= 0; dir.0.1= -1; dir.1.0= -1; dir.2.1= 1; dir.3.0= 1 /*the four directions.*/
 
do y=2 to N; say /*calculate rectangles up to size NxN.*/
do x=1 for y; if x//2 & y//2 then iterate /*not if bothBoth X&Y odd? Skip.*/
z= solve(y,x,1); _= comma(z); _= right(_, max(14, length(_))) /*align the output. */
say right(y, 9) "x" right(x, 2) 'rectangle can be cut' _ "way"s(z).
end /*x*/
end /*y*/
Line 2,072 ⟶ 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.*/
s: if arg(1)=1 then return arg(3); return word(arg(2) 's', 1) /*pluralizer.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
solve: procedure expose # dir. @. h len next. w; @.=0 /*zero rectangle coördinates.*/
parse arg h,w,recur /*get values for some args. */
if h//2 then do; t= w; w= h; h= t; if h//2 then return 0
end
if w==1 then return 1
if w==2 then return h
if h==2 then return w /* [↓] % is REXX's integer division.÷*/
cy= h % 2; cx= w % 2; wp= w + 1 /*cut the [XY] rectangle in half. */
len= (h+1) * wp - 1 /*extend the area of the rectangle. */
next.0= '-1'; next.1= -wp; next.2= 1; next.3= wp /*direction & distance.*/
if recur then #= 0
cywp= cy * wp do x=cx+1 to w-1; t=x + cy*wp; @.t=1; _=len - t; @._=1 /*shortcut calculation*/
call walk cy do x=cx+1 to w-1,; t= cywp + x; @.t= 1
_= len - t; @._= 1; call walk cy - 1, x
end /*x*/
end /*x*/
#=#+1
#= # + 1
if h==w then #=# + # /*double the count of rectangle cuts. */
if h==w then #= # + # else if w//2==0 & recur then call solve w, h, 0 /*double rectangle cut count.*/
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*wp; + x; @.t= @.t + 1; _= len - t
@._= @._ + 1
do j=0 for 4; _= t + next.j /*try each of four4 directions.*/
if @._==0 then call walk y + dir.j.0, x + dir.j.1
end /*j*/
@.t= @.t - 1
_= len - t; @._= @._ - 1; return</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default input:}}
<pre>
Line 2,157 ⟶ 3,580:
===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=='' | N=="," then N=10 /*N not specified? Then use default.*/
dir.=0; dir.0.1=-1; dir.1.0=-1; dir.2.1=1; dir.3.0=1 /*the four directions.*/
 
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.*/
z=solve(y,x,1); _=comma(z); _=right(_, max(14, length(_))) /*align the output. */
numeric digits 40 say right(y,9) "x" right(x,2) 'rectangle can be cut' _ "way"s(z)/*be able to handle some big integers. */
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.*/
$= '# @. dir. h len next. w wp'
/*define the default for memoizations. */
do y=start to abs(m); yOdd= y//2; say /*calculate rectangles up to size MxM.*/
do x=1 for y; if x//2 then if yOdd then iterate /*X and Y odd? Skip.*/
z= solve(y, x, 1); zc= comma(z) /*add commas to the result for SOLVE. */
zca= right(zc, max(14,length(zc) ) ) /*align the output for better perusing.*/
say right(y, 9) "x" right(x, 2) 'rectangle can be cut' zca "way"s(z).
end /*x*/
end /*y*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
comma: procedure; arg _?; do k=length(_?)-3 to 1 by -3; _?=insert(',',_?,k); end; return _?
s: if arg(1)=1 then return arg(3); return word(arg(2) 's', 1) /*pluralizer.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
ssolve: procedure expose if arg(1$); @.=1 0 then return arg(3); return word(arg(2) 's', 1) /*pluralizerzero 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
solve: procedure expose # dir. @. h len next. w; @.=0 /*zero rectangle coördinates.*/
parse arg h,w,recur /*get values for some args. */end
if h//2 then do; t= w; w= h; h= t; if h//2 then return 0
end
if w==1 then return 1
if w==2 then return h
if h==2 then return w /* [↓] % is REXX's integer division.*/
cy= h % 2; cx= w % 2; wp= w + 1 /*cut the [XY] rectangle in half. */
len= (h+1) * wp - 1 /*extend the area of the rectangle. */
next.0= '-1'; next.1= -wp; next.2= 1; next.3= wp /*direction & distance.*/
if recurrecurse then #= 0 /*doing recursion ? */
cywp= cy * wp do x=cx+1 to w-1; t=x + cy*wp; @.t=1; _=len - t; @._=1 /*shortcut calculation*/
call walk cy do x=cx+1 to w-1,; t= cywp + x; @.t= 1
__= len - t; @.__= 1; call walk cy - 1, x
end /*x*/
end /*x*/
#=#+1
#= # + 1
if h==w then #=# + # /*double the count of rectangle cuts. */
if h==w then #= # + # else if w//2==0 & recur then call solve w, h, 0 /*double the count of rectangle cuts. */
else if w//2==0 then if recurse then call solve w, h, 0
return #
/*──────────────────────────────────────────────────────────────────────────────────────*/
walk: procedure expose #($); dir. @. h len next. w wp; parse arg y,x
if y==h then do; #= # + 2; return; end end /* ◄──┐ REXX short circuit. */
if x==0 then do; #= # + 2; return; end end /* ◄──┤ " " " */
if x==w then do; #= # + 2; return; end end /* ◄──┤ " " " */
if y==0 then do; #= # + 2; return; end end /* ◄──┤ " " " */
tq=x + y*wp + x; @.tq= @.tq + 1; _= len - t q /* │ordered by most likely ►──┐*/
@._= @._ +1 1 /* └──────────────────────────┘*/
do j=0 for 4; _=t q + next.j /*try each of the four directions.*/
if @._==0 then do; yn= y + dir.j.0; xn=x + dir.j.1
if yn==h then do; #= # + 2; iterate; end
if xn==0 x then do; #=#+2; iterate; enddir.j.1
if xn==w0 then do; #= # + 2; iterate; end
if ynxn==0w 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>
{{out|output|text=&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,258 ⟶ 3,690:
puts "%d x %d: %d" % [w, h, cut_it(w, h)] if (w * h).even?
end
end</langsyntaxhighlight>
 
{{out}}
Line 2,295 ⟶ 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,368 ⟶ 3,800:
 
rec = Rectangle.new(3,4)
puts rec.cut.size</langsyntaxhighlight>
 
{{out}}
Line 2,451 ⟶ 3,883:
=={{header|Rust}}==
{{trans|Python}}
<langsyntaxhighlight 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 {
Line 2,525 ⟶ 3,957:
}
}
</syntaxhighlight>
</lang>
 
=={{header|Tcl}}==
{{trans|C}}
<langsyntaxhighlight lang="tcl">package require Tcl 8.5
 
proc walk {y x} {
Line 2,610 ⟶ 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,648 ⟶ 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
2,023

edits

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