:ets’s :ordered_set was really useful here.
defmodule Guarding do def read(filename, max_rows, max_cols) do :ets.new(__MODULE__, [:ordered_set, :named_table]) :ets.insert(__MODULE__, {:max_rows, max_rows}) :ets.insert(__MODULE__, {:max_cols, max_cols}) File.stream!(filename) |> Stream.map(&String.trim/1) |> Stream.with_index() |> Stream.flat_map(fn {row, r_idx} -> parse_row(row, r_idx) end) |> Enum.each(fn {:wall, {row, col}} -> :ets.insert(__MODULE__, {{:by_row, row, col}, true}) :ets.insert(__MODULE__, {{:by_col, col, row}, true}) {:start, pos} -> :ets.insert(__MODULE__, {:start, pos}) end) end defp parse_row(row, r_idx) do row |> String.codepoints() |> Enum.with_index() |> Enum.flat_map(fn {".", _} -> [] {"#", c_idx} -> [{:wall, {r_idx, c_idx}}] {"^", c_idx} -> [{:start, {r_idx, c_idx}}] end) end def next_direction(:up), do: :right def next_direction(:right), do: :down def next_direction(:down), do: :left def next_direction(:left), do: :up def next_in_direction(:out_of_bounds), do: nil def next_in_direction({{row, col}, :right}) do case :ets.next(__MODULE__, {:by_row, row, col}) do {:by_row, ^row, next_col} -> {Enum.map(col..(next_col-1), &{row, &1}), {{row, next_col - 1}, :down}} _ -> {Enum.map(col..max_cols(), &{row, &1}), :out_of_bounds} end end def next_in_direction({{row, col}, :left}) do case :ets.prev(__MODULE__, {:by_row, row, col}) do {:by_row, ^row, prev_col} -> {Enum.map((prev_col+1)..col, &{row, &1}), {{row, prev_col + 1}, :up}} _ -> {Enum.map(0..col, &{row, &1}), :out_of_bounds} end end def next_in_direction({{row, col}, :up}) do case :ets.prev(__MODULE__, {:by_col, col, row}) do {:by_col, ^col, prev_row} -> {Enum.map((prev_row+1)..row, &{&1, col}), {{prev_row + 1, col}, :right}} _ -> {Enum.map(0..row, &{&1, col}), :out_of_bounds} end end def next_in_direction({{row, col}, :down}) do case :ets.next(__MODULE__, {:by_col, col, row}) do {:by_col, ^col, next_row} -> {Enum.map(row..(next_row-1), &{&1, col}), {{next_row - 1, col}, :left}} _ -> {Enum.map(row..max_rows(), &{&1, col}), :out_of_bounds} end end def start do pos = :ets.lookup_element(__MODULE__, :start, 2) {pos, :up} end defp max_rows do :ets.lookup_element(__MODULE__, :max_rows, 2) end defp max_cols do :ets.lookup_element(__MODULE__, :max_cols, 2) end end Guarding.read("input.txt", 129, 129) Guarding.start() |> Stream.unfold(&Guarding.next_in_direction/1) |> Enum.to_list() |> List.flatten() |> Enum.uniq() |> length() |> IO.inspect() The idea is to keep two indexes in ETS:
:by_row- the keys here are sorted so that the “next” and “previous” obstacle in a row are accessible with:ets.nextand:ets.prev:by_col- same thing, but for a specific column
This works because of how tuples sort. {:by_row, 5, 0} < {:by_row, 5, 4} < {:by_row, 5, 10}
One case to watch for is when the search “hits the edge” - {:by_row, 4, 4} < {:by_row, 5, 3}, which means the search for the “previous” :by_row for {5,3} hit the edge. The pinned value in each case causes that situation (and :"$end_of_table") to not match.
Part 2 is trickier - being at {3,4} and moving up is distinct from being at {3,4} and moving left, so the output of next_in_direction becomes {{row, col}, dir} tuples.
It also uses a minor optimization and only tries putting obstacles at places that the unmodified route visits, which cuts down the number of possible locations by about 2/3rds for my input.
Part 2:
defmodule Guarding do def read(filename, max_rows, max_cols) do :ets.new(__MODULE__, [:ordered_set, :named_table]) :ets.insert(__MODULE__, {:max_rows, max_rows}) :ets.insert(__MODULE__, {:max_cols, max_cols}) File.stream!(filename) |> Stream.map(&String.trim/1) |> Stream.with_index() |> Stream.flat_map(fn {row, r_idx} -> parse_row(row, r_idx) end) |> Enum.each(fn {:wall, {row, col}} -> :ets.insert(__MODULE__, {{:by_row, row, col}, true}) :ets.insert(__MODULE__, {{:by_col, col, row}, true}) {:start, pos} -> :ets.insert(__MODULE__, {:start, pos}) end) end defp parse_row(row, r_idx) do row |> String.codepoints() |> Enum.with_index() |> Enum.flat_map(fn {".", _} -> [] {"#", c_idx} -> [{:wall, {r_idx, c_idx}}] {"^", c_idx} -> [{:start, {r_idx, c_idx}}] end) end def next_in_direction(:out_of_bounds), do: nil def next_in_direction({{row, col}, :right}) do case :ets.next(__MODULE__, {:by_row, row, col}) do {:by_row, ^row, next_col} -> {Enum.map(col..(next_col-1), &{row, &1, :right}), {{row, next_col - 1}, :down}} _ -> {Enum.map(col..max_cols(), &{row, &1, :right}), :out_of_bounds} end end def next_in_direction({{row, col}, :left}) do case :ets.prev(__MODULE__, {:by_row, row, col}) do {:by_row, ^row, prev_col} -> {Enum.map((prev_col+1)..col, &{row, &1, :left}), {{row, prev_col + 1}, :up}} _ -> {Enum.map(0..col, &{row, &1, :left}), :out_of_bounds} end end def next_in_direction({{row, col}, :up}) do case :ets.prev(__MODULE__, {:by_col, col, row}) do {:by_col, ^col, prev_row} -> {Enum.map((prev_row+1)..row, &{&1, col, :up}), {{prev_row + 1, col}, :right}} _ -> {Enum.map(0..row, &{&1, col, :up}), :out_of_bounds} end end def next_in_direction({{row, col}, :down}) do case :ets.next(__MODULE__, {:by_col, col, row}) do {:by_col, ^col, next_row} -> {Enum.map(row..(next_row-1), &{&1, col, :down}), {{next_row - 1, col}, :left}} _ -> {Enum.map(row..max_rows(), &{&1, col, :down}), :out_of_bounds} end end def start do pos = :ets.lookup_element(__MODULE__, :start, 2) {pos, :up} end defp max_rows do :ets.lookup_element(__MODULE__, :max_rows, 2) end defp max_cols do :ets.lookup_element(__MODULE__, :max_cols, 2) end def loop_with?({new_row, new_col}) do if :ets.member(__MODULE__, {:by_row, new_row, new_col}) do false else :ets.insert(__MODULE__, {{:by_row, new_row, new_col}, true}) :ets.insert(__MODULE__, {{:by_col, new_col, new_row}, true}) result = loop?(start()) :ets.delete(__MODULE__, {:by_row, new_row, new_col}) :ets.delete(__MODULE__, {:by_col, new_col, new_row}) result end end def loop?(start) do start |> Stream.unfold(&next_in_direction/1) |> Stream.concat() |> Stream.transform({MapSet.new(), false}, fn pos, {acc, false} -> if MapSet.member?(acc, pos) do {[true], {acc, true}} else {[false], {MapSet.put(acc, pos), false}} end _, {acc, true} -> {:halt, {acc, true}} end) |> Stream.take(-1) |> Enum.to_list() |> hd() end end # Guarding.read("example.txt", 9, 9) Guarding.read("input.txt", 129, 129) {start_pos, _} = start = Guarding.start() existing_visited = start |> Stream.unfold(&Guarding.next_in_direction/1) |> Enum.to_list() |> List.flatten() |> Enum.map(fn {r, c, _dir} -> {r, c} end) |> Enum.uniq() |> then(& &1 -- [start_pos]) existing_visited |> Enum.filter(&Guarding.loop_with?/1) |> length() |> IO.inspect() 