78 lines
2.3 KiB
Elixir
78 lines
2.3 KiB
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
|