Cut a rectangle: Difference between revisions
m
Added Easylang
SqrtNegInf (talk | contribs) m (→{{header|Raku}}: don't be just like C) |
m (Added Easylang) |
||
| (9 intermediate revisions by 7 users not shown) | |||
Line 11:
{{trans|Python}}
<
V dirs = [(1, 0), (-1, 0), (0, -1), (0, 1)]
I h % 2 != 0
Line 58:
L(h) 1..w
I (w * h) % 2 == 0
print(‘#. x #.: #.’.format(w, h, cut_it(w, h)))</
{{out}}
Line 96:
=={{header|C}}==
Exhaustive search on the cutting path. Symmetric configurations are only calculated once, which helps with larger sized grids.
<
#include <stdlib.h>
#include <string.h>
Line 175:
return 0;
}</
2 x 2: 2
3 x 2: 3
Line 214:
10 x 8: 11736888
10 x 9: 99953769
10 x 10: 1124140214</
More awkward solution: after compiling, run <code>./a.out -v [width] [height]</code> for display of cuts.
<
#include <stdlib.h>
Line 407:
bail: fprintf(stderr, "bad args\n");
return 1;
}</
=={{header|C#}}==
{{trans|Java}}
<syntaxhighlight lang="C#">
using System;
using System.Collections.Generic;
public class CutRectangle
{
private static int[][] dirs = new int[][] { new int[] { 0, -1 }, new int[] { -1, 0 }, new int[] { 0, 1 }, new int[] { 1, 0 } };
public static void Main(string[] args)
{
CutRectangleMethod(2, 2);
CutRectangleMethod(4, 3);
}
static void CutRectangleMethod(int w, int h)
{
if (w % 2 == 1 && h % 2 == 1)
return;
int[,] grid = new int[h, w];
Stack<int> stack = new Stack<int>();
int half = (w * h) / 2;
long bits = (long)Math.Pow(2, half) - 1;
for (; bits > 0; bits -= 2)
{
for (int i = 0; i < half; i++)
{
int r = i / w;
int c = i % w;
grid[r, c] = (bits & (1L << i)) != 0 ? 1 : 0;
grid[h - r - 1, w - c - 1] = 1 - grid[r, c];
}
stack.Push(0);
grid[0, 0] = 2;
int count = 1;
while (stack.Count > 0)
{
int pos = stack.Pop();
int r = pos / w;
int c = pos % w;
foreach (var dir in dirs)
{
int nextR = r + dir[0];
int nextC = c + dir[1];
if (nextR >= 0 && nextR < h && nextC >= 0 && nextC < w)
{
if (grid[nextR, nextC] == 1)
{
stack.Push(nextR * w + nextC);
grid[nextR, nextC] = 2;
count++;
}
}
}
}
if (count == half)
{
PrintResult(grid, h, w);
}
}
}
static void PrintResult(int[,] arr, int height, int width)
{
for (int i = 0; i < height; i++)
{
for (int j = 0; j < width; j++)
{
Console.Write(arr[i, j] + (j == width - 1 ? "" : ", "));
}
Console.WriteLine();
}
Console.WriteLine();
}
}
</syntaxhighlight>
{{out}}
<pre>
2, 2
0, 0
2, 0
2, 0
2, 2, 2, 2
2, 2, 0, 0
0, 0, 0, 0
2, 2, 2, 0
2, 2, 0, 0
2, 0, 0, 0
2, 2, 0, 0
2, 2, 0, 0
2, 2, 0, 0
2, 0, 0, 0
2, 2, 0, 0
2, 2, 2, 0
2, 2, 2, 2
0, 2, 0, 2
0, 0, 0, 0
2, 2, 2, 2
2, 0, 2, 0
0, 0, 0, 0
2, 2, 2, 0
2, 0, 2, 0
2, 0, 0, 0
2, 0, 0, 0
2, 0, 2, 0
2, 2, 2, 0
2, 2, 2, 2
0, 0, 2, 2
0, 0, 0, 0
</pre>
=={{header|C++}}==
{{trans|Java}}
<
#include <iostream>
#include <stack>
Line 494 ⟶ 625:
return 0;
}</
{{out}}
<pre>[2, 2]
Line 540 ⟶ 671:
=={{header|Common Lisp}}==
Count only.
<
(if (oddp (* w h)) (return-from cut-it 0))
(if (oddp h) (rotatef w h))
Line 582 ⟶ 713:
(loop for h from 1 to w do
(if (evenp (* w h))
(format t "~d x ~d: ~d~%" w h (cut-it w h)))))</
2 x 2: 2
3 x 2: 3
Line 611 ⟶ 742:
9 x 4: 553
9 x 6: 31721
9 x 8: 1812667</
=={{header|D}}==
{{trans|C}}
<
enum int[2][4] dir = [[0, -1], [-1, 0], [0, 1], [1, 0]];
Line 691 ⟶ 822:
if (!(x & 1) || !(y & 1))
printf("%d x %d: %llu\n", y, x, solve(y, x, true));
}</
{{out}}
<pre>2 x 1: 1
Line 737 ⟶ 868:
{{libheader| System.SysUtils}}
{{Trans|C}}
<syntaxhighlight lang="delphi">
program Cut_a_rectangle;
Line 839 ⟶ 970:
writeln(format('%d x %d: %d', [y, x, solve(y, x, True)]));
Readln;
end.</
{{out}}
See [[#C]]
=={{header|EasyLang}}==
{{trans|C}}
<syntaxhighlight>
global grid[] blen w h cnt .
dir[][] = [ [ 0 -1 ] [ -1 0 ] [ 0 1 ] [ 1 0 ] ]
#
proc walk y x . .
if y = 0 or y = h or x = 0 or x = w
cnt += 2
return
.
t = y * (w + 1) + x
grid[t] += 1
grid[blen - t] += 1
for i to 4
dx = dir[i][1]
dy = dir[i][2]
d = dx + dy * (w + 1)
if grid[t + d] = 0
walk y + dy x + dx
.
.
grid[t] -= 1
grid[blen - t] -= 1
.
proc solve hh ww recur . .
w = ww
h = hh
if h mod 2 = 1
swap h w
.
if h mod 2 = 1
cnt = 0
return
.
if w = 1
cnt = 1
return
.
if w = 2
cnt = h
return
.
if h = 2
cnt = w
return
.
cy = h div 2 ; cx = w div 2
blen = (h + 1) * (w + 1)
grid[] = [ ]
len grid[] blen
blen -= 1
if recur = 1
cnt = 0
.
for x = cx + 1 to w - 1
t = cy * (w + 1) + x
grid[t] = 1
grid[blen - t] = 1
walk cy - 1 x
.
cnt += 1
if h = w
cnt *= 2
elif w mod 2 = 0 and recur = 1
solve w h 0
.
.
proc main . .
for y = 1 to 8
for x = 1 to y
if x mod 2 = 0 or y mod 2 = 0
solve y x 1
print y & " x " & x & ": " & cnt
.
.
.
.
main
</syntaxhighlight>
{{out}}
<pre>
2 x 1: 1
2 x 2: 2
3 x 2: 3
4 x 1: 1
4 x 2: 4
4 x 3: 9
4 x 4: 22
5 x 2: 5
5 x 4: 39
6 x 1: 1
6 x 2: 6
6 x 3: 23
6 x 4: 90
6 x 5: 263
6 x 6: 1018
7 x 2: 7
7 x 4: 151
7 x 6: 2947
8 x 1: 1
8 x 2: 8
8 x 3: 53
8 x 4: 340
8 x 5: 1675
8 x 6: 11174
8 x 7: 55939
8 x 8: 369050
</pre>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 880 ⟶ 1,121:
end
</syntaxhighlight>
<syntaxhighlight lang="eiffel">
class
GRID
Line 1,045 ⟶ 1,286:
end
</syntaxhighlight>
<syntaxhighlight lang="eiffel">
class
POINT
Line 1,094 ⟶ 1,335:
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,142 ⟶ 1,383:
{{trans|Ruby}}
===Count only===
<
defmodule Rectangle do
Line 1,182 ⟶ 1,423:
if is_even(w * h), do: IO.puts "#{w} x #{h}: #{Rectangle.cut_it(w, h)}"
end)
end)</
{{out}}
Line 1,220 ⟶ 1,461:
===Show each of the cuts===
{{works with|Elixir|1.2}}
<
def cut(h, w, disp\\true) when rem(h,2)==0 or rem(w,2)==0 do
limit = div(h * w, 2)
Line 1,296 ⟶ 1,537:
Rectangle.cut(2, 2) |> length |> IO.puts
Rectangle.cut(3, 4) |> length |> IO.puts</
{{out}}
Line 1,379 ⟶ 1,620:
=={{header|Go}}==
{{trans|C}}
<
import "fmt"
Line 1,460 ⟶ 1,701:
}
}
}</
{{out}}
<pre>
Line 1,507 ⟶ 1,748:
=={{header|Groovy}}==
{{trans|Java}}
<
private static int[][] dirs = [[0, -1], [-1, 0], [0, 1], [1, 0]]
Line 1,567 ⟶ 1,808:
println()
}
}</
{{out}}
<pre>[2, 2]
Line 1,615 ⟶ 1,856:
Calculation of the cuts happens in the ST monad, using a mutable STVector and a mutable STRef. The program style is therefore very imperative.
The strictness annotations in the Env type are necessary; otherwise, unevaluated thunks of updates of "env" would pile up with each recursion, ending in a stack overflow.
<
import Data.STRef
import Control.Monad (forM_, when)
Line 1,695 ⟶ 1,936:
show x ++ " x " ++ show y ++ ": " ++ show (cut (x, y))))
[ (x, y) | x <- [1..10], y <- [1..x] ]
</syntaxhighlight>
With GHC -O3 the run-time is about 39 times the D entry.
=={{header|J}}==
<
prop=: < {:,~2 ~:/\ ] NB. propagate: neighboring squares (vertically)
poss=: I.@,@(prop +. prop"1 +. prop&.|. +. prop&.|."1)
Line 1,706 ⟶ 1,947:
N=: <:@-:@#@, NB. how many neighbors to add
step=: [: ~.@; <@(((= i.@$) +. ])"0 _~ keep)"2
all=: step^:N@init</
In other words, starting with a boolean matrix with one true square in one corner, make a list of all false squares which neighbor a true square, and then make each of those neighbors true, independently (discarding duplicate matrices from the resulting sequence of boolean matrices), and repeat this N times where N is (total cells divided by two)-1. Then discard those matrices where inverting them (boolean not), then flipping on horizontal and vertical axis is not an identity.
Line 1,714 ⟶ 1,955:
Example use:
<
┌────┬────┬────┬────┬────┬────┬────┬────┬────┐
│.###│.###│..##│...#│...#│....│....│....│....│
Line 1,738 ⟶ 1,979:
│.##.#│.#..#│#..##│#.###│#####│###.#│##..#│#..#.│#.##.│####.│###..│##...│#....│
│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘</
=={{header|Java}}==
{{works with|Java|7}}
<
public class CutRectangle {
Line 1,807 ⟶ 2,048:
System.out.println();
}
}</
<pre>[2, 2]
Line 1,850 ⟶ 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}}
<
const count = [0]
const dir = [[0, -1], [-1, 0], [0, 1], [1, 0]]
Line 1,922 ⟶ 2,280:
runtest()
</
2 x 1: 1
2 x 2: 2
Line 1,967 ⟶ 2,325:
=={{header|Kotlin}}==
{{trans|C}}
<
object RectangleCutter {
Line 2,042 ⟶ 2,400:
}
}
}</
{{out}}
Line 2,090 ⟶ 2,448:
=={{header|Lua}}==
{{trans|C++}}
<
local t = {}
for i=1,w do
Line 2,194 ⟶ 2,552:
cutRectangle(2, 2)
cutRectangle(4, 3)</
{{out}}
<pre>[2, 2]
Line 2,237 ⟶ 2,595:
[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}}
<
var
Line 2,315 ⟶ 2,762:
for x in 1..y:
if not odd(x) or not odd(y):
echo &"{y:2d} x {x:2d}: {solve(y, x, true)}"</
{{out}}
Line 2,364 ⟶ 2,811:
{{trans|C}}
Output is identical to C's.
<
use warnings;
my @grid = 0;
Line 2,445 ⟶ 2,892:
}
MAIN();</
=={{header|Phix}}==
Using a completely different home-brewed algorithm, slightly sub-optimal as noted in the code.
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">show</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- max number to show
Line 2,562 ⟶ 3,009:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">--?elapsed(time()-t0)</span>
<!--</
{{out}}
Includes two random grids
Line 2,639 ⟶ 3,086:
=={{header|Python}}==
{{trans|D}}
<
dirs = ((1, 0), (-1, 0), (0, -1), (0, 1))
if h % 2: h, w = w, h
Line 2,691 ⟶ 3,138:
print "%d x %d: %d" % (w, h, cut_it(w, h))
main()</
Output:
<pre>2 x 1: 1
Line 2,725 ⟶ 3,172:
===Faster version===
{{trans|D}}
<
import psyco
except ImportError:
Line 2,794 ⟶ 3,241:
print "%d x %d: %d" % (y, x, count_only(x, y))
main()</
The output is the same.
=={{header|Racket}}==
<
#lang racket
Line 2,847 ⟶ 3,294:
(newline)
(cuts 4 3 #f)
</syntaxhighlight>
{{out}}
Line 2,959 ⟶ 3,406:
(formerly Perl 6)
{{trans|C}}
<syntaxhighlight lang="raku" line>sub solve($hh, $ww, $recurse) {
my ($h, $w, $t, @grid)
state $cnt;
$cnt = 0 if $recurse;
return 1 if $w == 1;
return $h if $w == 2;
return $w if $h == 2;
my ($cy, $cx) = ($h, $w) «div» 2;
my
@grid[$len--] = 0;
my @next = -1, -$w-1, 1, $w+1;
@
walk($cy - 1, $x);
}
$cnt += 2 and return if not $y or $y == $h or not $x or $x == $w;
@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;
}
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,
}</
{{out}}
<pre>2 × 1: 1
Line 3,061 ⟶ 3,480:
=={{header|REXX}}==
===idiomatic===
<
/*────────────────────────────────────────────────── unit dimensions and may be rotated.*/
numeric digits 20 /*be able to handle some big integers. */
Line 3,106 ⟶ 3,525:
end /*j*/
@.t= @.t - 1
_= len - t; @._= @._ - 1; return</
{{out|output|text= when using the default input:}}
<pre>
Line 3,166 ⟶ 3,585:
Also, I've discovered a formula for calculating the number of cuts for even '''M''' when '''N''' is '''3'''.
<
/*────────────────────────────────────────────────── unit dimensions and may be rotated.*/
numeric digits 40 /*be able to handle some big integers. */
Line 3,227 ⟶ 3,646:
end
end /*j*/
@.q= @.q - 1; _= len - q; @._= @._ - 1; return</
{{out|output|text= is the same as the idiomatic version (above).}} <br><br>
=={{header|Ruby}}==
{{trans|Python}}
<
if h.odd?
return 0 if w.odd?
Line 3,271 ⟶ 3,690:
puts "%d x %d: %d" % [w, h, cut_it(w, h)] if (w * h).even?
end
end</
{{out}}
Line 3,308 ⟶ 3,727:
===Show each of the cuts===
<
DIRS = [[1, 0], [-1, 0], [0, -1], [0, 1]]
def initialize(h, w)
Line 3,381 ⟶ 3,800:
rec = Rectangle.new(3,4)
puts rec.cut.size</
{{out}}
Line 3,464 ⟶ 3,883:
=={{header|Rust}}==
{{trans|Python}}
<
fn cwalk(mut vis: &mut Vec<Vec<bool>>, count: &mut isize, w: usize, h: usize, y: usize, x: usize, d: usize) {
if x == 0 || y == 0 || x == w || y == h {
Line 3,538 ⟶ 3,957:
}
}
</syntaxhighlight>
=={{header|Tcl}}==
{{trans|C}}
<
proc walk {y x} {
Line 3,623 ⟶ 4,042:
}
}
}} 10</
Output is identical.
Line 3,629 ⟶ 4,048:
{{trans|C}}
{{libheader|Wren-fmt}}
Last two are very slooow to emerge (
<
var grid = []
Line 3,651 ⟶ 4,070:
for (i in 0..3) {
if (grid[t + next[i]] == 0) {
walk.call(y + dir[i][0], x + dir[i][1])
}
Line 3,694 ⟶ 4,112:
cnt = cnt * 2
} else if ((w&1 == 0) && recur) {
solve.call(w, h, false)
}
Line 3,706 ⟶ 4,123:
}
}
}</
{{out}}
Line 3,750 ⟶ 4,167:
10 x 9 : 99953769
10 x 10 : 1124140214
</pre>
=={{header|XPL0}}==
{{trans|C}}
Works on Raspberry Pi. ReallocMem is not available in the DOS versions. Takes about 40 seconds on Pi4.
<syntaxhighlight lang "XPL0">include xpllib; \for Print
char Grid;
int W, H, Len, Cnt;
int Next(4), Dir;
proc Walk(Y, X);
int Y, X;
int I, T;
[if Y=0 or Y=H or X=0 or X=W then
[Cnt:= Cnt+2; return];
T:= Y * (W + 1) + X;
Grid(T):= Grid(T)+1;
Grid(Len-T):= Grid(Len-T)+1;
for I:= 0 to 4-1 do
if Grid(T + Next(I)) = 0 then
Walk(Y+Dir(I,0), X+Dir(I,1));
Grid(T):= Grid(T)-1;
Grid(Len-T):= Grid(Len-T)-1;
];
func Solve(HH, WW, Recur);
int HH, WW, Recur;
int T, CX, CY, X;
[H:= HH; W:= WW;
if H & 1 then [T:= W; W:= H; H:= T];
if H & 1 then return 0;
if W = 1 then return 1;
if W = 2 then return H;
if H = 2 then return W;
CY:= H/2; CX:= W/2;
Len:= (H + 1) * (W + 1);
Grid:= ReallocMem(Grid, Len);
FillMem(Grid, 0, Len); Len:= Len-1;
Next(0):= -1;
Next(1):= -W - 1;
Next(2):= 1;
Next(3):= W + 1;
if Recur then Cnt:= 0;
for X:= CX+1 to W-1 do
[T:= CY * (W + 1) + X;
Grid(T):= 1;
Grid(Len - T):= 1;
Walk(CY - 1, X);
];
Cnt:= Cnt+1;
if H = W then Cnt:= Cnt * 2
else if (W&1) = 0 and Recur then Solve(W, H, 0);
return Cnt;
];
int Y, X;
[Grid:= 0;
Dir:= [[0, -1], [-1, 0], [0, 1], [1, 0]];
for Y:= 1 to 10 do
for X:= 1 to Y do
if (X&1) = 0 or (Y&1) = 0 then
Print("%d x %d: %d\n", Y, X, Solve(Y, X, 1));
]</syntaxhighlight>
{{out}}
<pre>
2 x 1: 1
2 x 2: 2
3 x 2: 3
4 x 1: 1
4 x 2: 4
4 x 3: 9
4 x 4: 22
5 x 2: 5
5 x 4: 39
6 x 1: 1
6 x 2: 6
6 x 3: 23
6 x 4: 90
6 x 5: 263
6 x 6: 1018
7 x 2: 7
7 x 4: 151
7 x 6: 2947
8 x 1: 1
8 x 2: 8
8 x 3: 53
8 x 4: 340
8 x 5: 1675
8 x 6: 11174
8 x 7: 55939
8 x 8: 369050
9 x 2: 9
9 x 4: 553
9 x 6: 31721
9 x 8: 1812667
10 x 1: 1
10 x 2: 10
10 x 3: 115
10 x 4: 1228
10 x 5: 10295
10 x 6: 118276
10 x 7: 1026005
10 x 8: 11736888
10 x 9: 99953769
10 x 10: 1124140214
</pre>
=={{header|zkl}}==
{{trans|Ruby}}
<
if(h.isOdd){
if(w.isOdd) return(0);
Line 3,787 ⟶ 4,310:
count + walk(h/2 - 1, w/2);
}
}</
Note the funkiness in walk: vm.pasteArgs. This is because zkl functions are unaware of their scope, so a closure is needed (when calling walk) to capture state (nxt, blen, grid, h, w). Rather than creating a closure object each call, that state is passed in the arg list. So, when doing recursion, that state needs to be restored to the stack (the compiler isn't smart enough to recognize this case).
<
if((w*h).isEven) println("%d x %d: %d".fmt(w, h, cut_it(w,h)));
}</
{{out}}
Output is identical.
| |||