Cut a rectangle: Difference between revisions

 

Possibly related task: [[Maze generation]] for depth-first search.

 

=={{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>

 

return 0;

2 x 2: 2

3 x 2: 3

10 x 8: 11736888

10 x 9: 99953769

 

More awkward solution: after compiling, run <code>./a.out -v [width] [height]</code> for display of cuts.

#include <stdlib.h>

 

bail: fprintf(stderr, "bad args\n");

return 1;

 

=={{header|C++}}==

{{trans|Java}}

#include <iostream>

#include <stack>

 

return 0;

{{out}}

<pre>[2, 2]

=={{header|Common Lisp}}==

Count only.

(if (oddp (* w h)) (return-from cut-it 0))

(if (oddp h) (rotatef w h))

(loop for h from 1 to w do

(if (evenp (* w h))

2 x 2: 2

3 x 2: 3

9 x 4: 553

9 x 6: 31721

 

=={{header|D}}==

{{trans|C}}

 

enum int[2][4] dir = [[0, -1], [-1, 0], [0, 1], [1, 0]];

if (!(x & 1) || !(y & 1))

printf("%d x %d: %llu\n", y, x, solve(y, x, true));

{{out}}

<pre>2 x 1: 1

{{libheader| System.SysUtils}}

{{Trans|C}}

program Cut_a_rectangle;

 

writeln(format('%d x %d: %d', [y, x, solve(y, x, True)]));

Readln;

{{out}}

See [[#C]]

=={{header|Eiffel}}==

class

APPLICATION

 

end

class

GRID

 

end

class

POINT

 

end

{{out}}

<pre>

{{trans|Ruby}}

===Count only===

 

defmodule Rectangle do

if is_even(w * h), do: IO.puts "#{w} x #{h}: #{Rectangle.cut_it(w, h)}"

end)

 

{{out}}

===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)

 

Rectangle.cut(2, 2) |> length |> IO.puts

 

{{out}}

=={{header|Go}}==

{{trans|C}}

 

import "fmt"

}

}

{{out}}

<pre>

=={{header|Groovy}}==

{{trans|Java}}

private static int[][] dirs = [[0, -1], [-1, 0], [0, 1], [1, 0]]

 

println()

}

{{out}}

<pre>[2, 2]

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)

show x ++ " x " ++ show y ++ ": " ++ show (cut (x, y))))

[ (x, y) | x <- [1..10], y <- [1..x] ]

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)

N=: <:@-:@#@, NB. how many neighbors to add

step=: [: ~.@; <@(((= i.@$) +. ])"0 _~ keep)"2

 

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.

Example use:

 

┌────┬────┬────┬────┬────┬────┬────┬────┬────┐

│.###│.###│..##│...#│...#│....│....│....│....│

│.##.#│.#..#│#..##│#.###│#####│###.#│##..#│#..#.│#.##.│####.│###..│##...│#....│

│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│#####│

 

=={{header|Java}}==

{{works with|Java|7}}

 

public class CutRectangle {

System.out.println();

}

 

<pre>[2, 2]

[0, 0, 2, 2]

[0, 0, 0, 0]</pre>

 

=={{header|Julia}}==

{{trans|C}}

const count = [0]

const dir = [[0, -1], [-1, 0], [0, 1], [1, 0]]

 

runtest()

2 x 1: 1

2 x 2: 2

=={{header|Kotlin}}==

{{trans|C}}

 

object RectangleCutter {

}

}

 

{{out}}

10 x 10: 1124140214

</pre>

 

=={{header|Perl}}==

{{trans|C}}

Output is identical to C's.

use warnings;

my @grid = 0;

}

 

 

=={{header|Phix}}==

Using a completely different home-brewed algorithm, slightly sub-optimal as noted in the code.

{{out}}

Includes two random grids

10 x 8: 11736888

</pre>

 

=={{header|Python}}==

{{trans|D}}

dirs = ((1, 0), (-1, 0), (0, -1), (0, 1))

if w == 1: return 1

count = 0

 

t = h // 2 * (w + 1) + w // 2

grid[t] = grid[t + 1] = True

count = walk(h // 2, w // 2 - 1, count)

for w in xrange(1, 10):

for h in xrange(1, w + 1):

print "%d x %d: %d" % (w, h, cut_it(w, h))

 

Output:

<pre>2 x 1: 1

===Faster version===

{{trans|D}}

import psyco

except ImportError:

print "%d x %d: %d" % (y, x, count_only(x, y))

 

The output is the same.

 

=={{header|Racket}}==

#lang racket

 

(newline)

(cuts 4 3 #f)

 

{{out}}

(formerly Perl 6)

{{trans|C}}

 

 

@grid[$len--] = 0;

 

walk($cy - 1, $x);

}

 

}

 

}

 

{{out}}

 

=={{header|REXX}}==

===idiomatic===

/*────────────────────────────────────────────────── unit dimensions and may be rotated.*/

numeric digits 20 /*be able to handle some big integers. */

end /*j*/

@.t= @.t - 1

{{out|output|text=&nbsp; when using the default input:}}

<pre>

<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).

/*────────────────────────────────────────────────── unit dimensions and may be rotated.*/

dir.= 0; dir.0.1= -1; dir.1.0= -1; dir.2.1= 1; dir.3.0= 1 /*the 4 directions.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

end

if w==1 then return 1

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*/

cywp= cy * wp /*shortcut calculation*/

do x=cx+1 to w-1; t= cywp + x; @.t= 1

end /*x*/

#= # + 1

if h==w then #= # + # /*double the count of rectangle cuts. */

return #

/*──────────────────────────────────────────────────────────────────────────────────────*/

@._= @._ + 1 /* └──────────────────────────┘*/

call walk yn, xn

end

end /*j*/

{{out|output|text=&nbsp; is the same as the idiomatic version &nbsp; (above).}} <br><br>

 

=={{header|Ruby}}==

{{trans|Python}}

if h.odd?

return 0 if w.odd?

puts "%d x %d: %d" % [w, h, cut_it(w, h)] if (w * h).even?

end

 

{{out}}

 

===Show each of the cuts===

DIRS = [[1, 0], [-1, 0], [0, -1], [0, 1]]

def initialize(h, w)

 

rec = Rectangle.new(3,4)

 

{{out}}

=={{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 {

}

}

 

=={{header|Tcl}}==

{{trans|C}}

 

proc walk {y x} {

}

}

Output is identical.

 

{{trans|C}}

{{libheader|Wren-fmt}}

 

var grid = []

for (i in 0..3) {

if (grid[t + next[i]] == 0) {

walk.call(y + dir[i][0], x + dir[i][1])

}

cnt = cnt * 2

} else if ((w&1 == 0) && recur) {

solve.call(w, h, false)

}

}

}

 

{{out}}

10 x 9 : 99953769

10 x 10 : 1124140214

</pre>

 

=={{header|zkl}}==

{{trans|Ruby}}

if(h.isOdd){

if(w.isOdd) return(0);

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.