Cut a rectangle: Difference between revisions

Content added Content deleted
(Added Elixir)
Line 519: Line 519:
10 x 10: 1124140214</pre>
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).
Using the LDC2 compiler the runtime is about 15.98 seconds (the first C entry runs in about 16.75 seconds with GCC).

=={{header|Eiffel}}==
=={{header|Eiffel}}==
<lang Eiffel>
<lang Eiffel>
Line 814: Line 815:
Rectangle 10 x 9: 99953769 possibilities
Rectangle 10 x 9: 99953769 possibilities
Rectangle 10 x 10: 1124140214 possibilities
Rectangle 10 x 10: 1124140214 possibilities
</pre>

=={{header|Elixir}}==
{{trans|Ruby}}
===Count only===
<lang elixir>import Integer

defmodule Rectangle do
def cut_it(h, w) when is_odd(h) and is_odd(w), do: 0
def cut_it(h, w) when is_odd(h), do: cut_it(w, h)
def cut_it(_, 1), do: 1
def cut_it(h, 2), do: h
def cut_it(2, w), do: w
def cut_it(h, w) do
grid = List.duplicate(false, (h + 1) * (w + 1))
t = div(h, 2) * (w + 1) + div(w, 2)
if is_odd(w) do
grid = grid |> List.replace_at(t, true) |> List.replace_at(t+1, true)
walk(h, w, div(h, 2), div(w, 2) - 1, grid) + walk(h, w, div(h, 2) - 1, div(w, 2), grid) * 2
else
grid = grid |> List.replace_at(t, true)
count = walk(h, w, div(h, 2), div(w, 2) - 1, grid)
if h == w, do: count * 2,
else: count + walk(h, w, div(h, 2) - 1, div(w, 2), grid)
end
end
defp walk(h, w, y, x, grid, count\\0)
defp walk(h, w, y, x,_grid, count) when y in [0,h] or x in [0,w], do: count+1
defp walk(h, w, y, x, grid, count) do
blen = (h + 1) * (w + 1) - 1
t = y * (w + 1) + x
grid = grid |> List.replace_at(t, true) |> List.replace_at(blen-t, true)
Enum.reduce(next(w), count, fn {nt, dy, dx}, cnt ->
if Enum.at(grid, t+nt), do: cnt, else: cnt + walk(h, w, y+dy, x+dx, grid)
end)
end
defp next(w), do: [{w+1, 1, 0}, {-w-1, -1, 0}, {-1, 0, -1}, {1, 0, 1}] # {next,dy,dx}
end

Enum.each(1..9, fn w ->
Enum.each(1..w, fn h ->
if is_even(w * h), do: IO.puts "#{w} x #{h}: #{Rectangle.cut_it(w, h)}"
end)
end)</lang>

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

===Show each of the cuts===
{{works with|Elixir|1.2}}
<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)
start_link
grid = make_grid(h, w)
walk(h, w, grid, 0, 0, limit, %{}, [])
if disp, do: display(h, w)
result = Agent.get(__MODULE__, &(&1))
Agent.stop(__MODULE__)
MapSet.to_list(result)
end
defp start_link do
Agent.start_link(fn -> MapSet.new end, name: __MODULE__)
end
defp make_grid(h, w) do
for i <- 0..h-1, j <- 0..w-1, into: %{}, do: {{i,j}, true}
end
defp walk(h, w, grid, x, y, limit, cut, select) do
grid2 = grid |> Map.put({x,y}, false) |> Map.put({h-x-1,w-y-1}, false)
select2 = [{x,y} | select] |> Enum.sort
unless cut[select2] do
if length(select2) == limit do
Agent.update(__MODULE__, fn set -> MapSet.put(set, select2) end)
else
cut2 = Map.put(cut, select2, true)
search_next(grid2, select2)
|> Enum.each(fn {i,j} -> walk(h, w, grid2, i, j, limit, cut2, select2) end)
end
end
end
defp dirs(x, y), do: [{x+1, y}, {x-1, y}, {x, y-1}, {x, y+1}]
defp search_next(grid, select) do
(for {x,y} <- select, {i,j} <- dirs(x,y), grid[{i,j}], do: {i,j})
|> Enum.uniq
end
defp display(h, w) do
Agent.get(__MODULE__, &(&1))
|> Enum.each(fn select ->
grid = Enum.reduce(select, make_grid(h,w), fn {x,y},grid ->
%{grid | {x,y} => false}
end)
IO.puts to_string(h, w, grid)
end)
end
defp to_string(h, w, grid) do
text = for x <- 0..h*2, into: %{}, do: {x, String.duplicate(" ", w*4+1)}
text = Enum.reduce(0..h, text, fn i,acc ->
Enum.reduce(0..w, acc, fn j,txt ->
to_s(txt, i, j, grid)
end)
end)
Enum.map_join(0..h*2, "\n", fn i -> text[i] end)
end
defp to_s(text, i, j, grid) do
text = if grid[{i,j}] != grid[{i-1,j}], do: replace(text, i*2, j*4+1, "---"), else: text
text = if grid[{i,j}] != grid[{i,j-1}], do: replace(text, i*2+1, j*4, "|"), else: text
replace(text, i*2, j*4, "+")
end
defp replace(text, x, y, replacement) do
len = String.length(replacement)
Map.update!(text, x, fn str ->
String.slice(str, 0, y) <> replacement <> String.slice(str, y+len..-1)
end)
end
end

Rectangle.cut(2, 2) |> length |> IO.puts
Rectangle.cut(3, 4) |> length |> IO.puts</lang>

{{out}}
<pre style="height:64ex;overflow:scroll">
+---+---+
| |
+---+---+
| |
+---+---+
+---+---+
| | |
+ + +
| | |
+---+---+
2
+---+---+---+---+
| |
+ + +---+---+
| | |
+---+---+ + +
| |
+---+---+---+---+
+---+---+---+---+
| |
+ +---+ +---+
| | | | |
+---+ +---+ +
| |
+---+---+---+---+
+---+---+---+---+
| |
+---+ +---+ +
| | | | |
+ +---+ +---+
| |
+---+---+---+---+
+---+---+---+---+
| |
+---+---+ + +
| | |
+ + +---+---+
| |
+---+---+---+---+
+---+---+---+---+
| | |
+ + +---+ +
| | |
+ +---+ + +
| | |
+---+---+---+---+
+---+---+---+---+
| | |
+ +---+ + +
| | | | |
+ + +---+ +
| | |
+---+---+---+---+
+---+---+---+---+
| | |
+ + + + +
| | |
+ + + + +
| | |
+---+---+---+---+
+---+---+---+---+
| | |
+ +---+ + +
| | |
+ + +---+ +
| | |
+---+---+---+---+
+---+---+---+---+
| | |
+ + +---+ +
| | | | |
+ +---+ + +
| | |
+---+---+---+---+
9
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Cut_a_rectangle"