Using :digraph_utils.strong_components to generate the regions made things very simple for part 1. Took me quite a long time to figure out how to count the sides. I was trying to do things as overlapping rectangles where every rectangle has four sides but you subtract sides for intersections but I couldn’t get it to work. Reddit post on counting corners saved me.
defmodule Day12 do
def run(mode) do
graph =
mode
|> input()
|> parse()
part_1(graph) |> IO.inspect(label: :part_1)
part_2(graph) |> IO.inspect(label: :part_2)
end
defp input(:real), do: @real
defp parse(input) do
input
|> graph()
|> regions()
end
defp graph(input) do
graph = :digraph.new()
input
|> String.split("\n", trim: true)
|> Enum.with_index()
|> Enum.each(fn {line, row} ->
line
|> String.graphemes()
|> Enum.with_index()
|> Enum.map(fn {g, col} -> {{row, col}, g} end)
|> Enum.each(fn {{r, c} = coord, char} ->
:digraph.add_vertex(graph, coord, char)
:digraph.add_edge(graph, coord, coord)
end)
end)
Agent.start_link(fn -> %{rows: max_rows, cols: max_cols} end, name: :COUNTERS)
graph
end
defp regions(graph) do
vs = :digraph.vertices(graph) |> Enum.map(&:digraph.vertex(graph, &1))
for {{r1, c1}, l1} <- vs,
{{r2, c2}, l2} <- vs -- [{{r1, c1}, l1}],
l1 == l2,
(r1 == r2 and abs(c1 - c2) == 1) or (c1 == c2 and abs(r1 - r2) == 1) do
:digraph.add_edge(graph, {r1, c1}, {r2, c2})
end
graph
end
defp part_1(graph) do
graph
|> perimeters_and_areas_of_regions()
|> Enum.sum_by(&cost/1)
end
defp part_2(graph) do
graph
|> sides_count_and_areas_of_regions()
|> Enum.sum_by(&cost/1)
end
defp perimeters_and_areas_of_regions(graph) do
graph
|> :digraph_utils.strong_components()
|> Enum.map(fn sub ->
sub = :digraph_utils.subgraph(graph, sub)
area = area(sub)
{area * 4 - perimeter(sub), area}
end)
end
defp perimeter(graph) do
graph
|> :digraph.edges()
|> Enum.map(&:digraph.edge(graph, &1))
|> Enum.map(fn e -> {elem(e, 1), elem(e, 2)} end)
|> Enum.reject(fn {a, b} -> a == b end)
|> Enum.count()
end
defp area(graph) do
:digraph.vertices(graph) |> Enum.count()
end
defp sides_count_and_areas_of_regions(graph) do
graph
|> :digraph_utils.strong_components()
|> Enum.map(fn sub -> :digraph_utils.subgraph(graph, sub) end)
|> Enum.map(fn subg -> {sides(subg), area(subg)} end)
end
defp sides(graph) do
graph
|> :digraph.vertices()
|> Enum.map(fn v ->
{v, :digraph.out_neighbours(graph, v)}
end)
|> Enum.map(fn {v, nbrs} ->
shape(v, nbrs, graph)
end)
|> Enum.sum()
end
defp shape(v, nbr_grp, graph) do
set = MapSet.new(nbr_grp)
cond do
set in l_shape(v) -> 2 - inside_corner_occupied(graph, set, v)
set in t_shape(v) -> 2 - inside_corner_occupied(graph, set, v)
set == cross_shape(v) -> 4 - inside_corner_occupied(graph, set, v)
set in i_shape(v) -> 2
set in long_linear_shape(v) -> 0
isolated(v) -> 4
end
end
defp l_shape({r, c}) do
[[{1, 0}, {0, 1}], [{1, 0}, {0, -1}], [{-1, 0}, {0, 1}], [{-1, 0}, {0, -1}]]
|> Enum.map(fn [{r1, c1}, {r2, c2}] ->
MapSet.new([{r, c}, {r + r1, c + c1}, {r + r2, c + c2}])
end)
end
defp t_shape({r, c}) do
[
[{1, 0}, {0, 1}, {0, -1}],
[{-1, 0}, {0, 1}, {0, -1}],
[{1, 0}, {-1, 0}, {0, 1}],
[{1, 0}, {-1, 0}, {0, -1}]
]
|> Enum.map(fn [{r1, c1}, {r2, c2}, {r3, c3}] ->
MapSet.new([{r, c}, {r + r1, c + c1}, {r + r2, c + c2}, {r + r3, c + c3}])
end)
end
defp cross_shape({r, c}),
do: MapSet.new([{r, c}, {r + 1, c}, {r - 1, c}, {r, c + 1}, {r, c - 1}])
defp i_shape({r, c}) do
[[{0, 0}, {0, 1}], [{0, 0}, {0, -1}], [{0, 0}, {1, 0}], [{0, 0}, {-1, 0}]]
|> Enum.map(fn nbrs ->
nbrs |> Enum.map(fn {dr, dc} -> {r + dr, c + dc} end) |> MapSet.new()
end)
end
defp long_linear_shape({r, c}) do
[
[{0, 0}, {0, 1}, {0, -1}],
[{0, 0}, {1, 0}, {-1, 0}]
]
|> Enum.map(fn nbrs ->
nbrs |> Enum.map(fn {dr, dc} -> {r + dr, c + dc} end) |> MapSet.new()
end)
end
defp isolated(v), do: MapSet.new([v])
defp inside_corner_occupied(graph, set, v) do
[nw(v), sw(v), ne(v), se(v), nw_sw(v), ne_se(v), nw_ne(v), sw_se(v), nsew(v)]
|> Enum.map(fn set1 -> MapSet.difference(set1, set) end)
|> Enum.filter(fn set1 -> MapSet.size(set1) == 1 end)
|> Enum.filter(fn set1 ->
corner = set1 |> MapSet.to_list() |> hd()
corner_occupied?(corner, graph)
end)
|> Enum.count()
end
defp nw({r, c}), do: MapSet.new([{r, c}, {r - 1, c}, {r, c - 1}, {r - 1, c - 1}])
defp sw({r, c}), do: MapSet.new([{r, c}, {r + 1, c}, {r, c - 1}, {r + 1, c - 1}])
defp ne({r, c}), do: MapSet.new([{r, c}, {r - 1, c}, {r, c + 1}, {r - 1, c + 1}])
defp se({r, c}), do: MapSet.new([{r, c}, {r + 1, c}, {r, c + 1}, {r + 1, c + 1}])
defp nw_sw(v), do: MapSet.union(nw(v), sw(v))
defp ne_se(v), do: MapSet.union(ne(v), se(v))
defp nw_ne(v), do: MapSet.union(nw(v), ne(v))
defp sw_se(v), do: MapSet.union(sw(v), se(v))
defp nsew(v), do: MapSet.union(nw_sw(v), ne_se(v))
defp corner_occupied?(corner, graph) do
:digraph.vertex(graph, corner)
end
defp cost({perimeter, area}), do: perimeter * area
end
Day12.run(:test1)
Day12.run(:test2)
Day12.run(:test3)
Day12.run(:test4)
Day12.run(:test5)
Day12.run(:real)
Reading through the posts above I’m really surprised more people did not use :digraph as the grid structure. I really hate implementing all the path tracking stuff by hand so I probably overuse it, but it felt right for this problem.