Cut a rectangle: Difference between revisions

{{trans|Python}}

V dirs = [(1, 0), (-1, 0), (0, -1), (0, 1)]

I h % 2 != 0

L(h) 1..w

I (w * h) % 2 == 0

{{out}}

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

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

=={{header|Lua}}==

{{trans|C++}}

local t = {}

for i=1,w do

cutRectangle(2, 2)

{{out}}

<pre>[2, 2]

=={{header|Mathematica}}/{{header|Wolfram Language}}==

dirs = AngleVector /@ Most[Range[0, 2 Pi, Pi/2]];

CutRectangle[nm : {n_, m_}] := Module[{start, stop, count, sols},

{j, maxsize}

]][[2, 1]];

{{out}}

<pre>2 * 1: 1

6 * 6: 1018</pre>

Solutions can be visualised using:

cr = CutRectangle[size];

Which outputs graphical objects for each solution.

=={{header|Nim}}==

{{trans|C}}

var

for x in 1..y:

if not odd(x) or not odd(y):

{{out}}

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

<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

<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

=={{header|Python}}==

{{trans|D}}

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

if h % 2: h, w = w, h

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}}

my ($h, $w, $t, @grid) = $hh, $ww, 0;

state $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;

{{out}}

<pre>2 × 1: 1

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

Also, I've discovered a formula for calculating the number of cuts for even &nbsp; '''M''' &nbsp; when &nbsp; '''N''' &nbsp; is &nbsp; '''3'''.

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

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

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.

{{libheader|Wren-fmt}}

Last two are very slooow to emerge (just under 10 mins overall).

var grid = []

}

}

{{out}}

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