Thanks for your advice.
23s is not a typo.
Good to know the ETS table is allocated elsewhere than the process’s heap. I don’t know why changing in to MapSet.member?/2 has a notable effect, isn’t that Kernel.in/2 calls Enumerable.member?/2 which in turn calls MapSet.member/2?
I suppose that the overhead for the extra function calls is noticeable when in is called very frequently.
It was fun to wait aaaaall the way to the next morning only to find out
i looked at your code and used some of your ideas and incoroporated them into my own code for Part2.
https://github.com/jarlah/advent_of_code/blob/master/lib/2024/day_6/Part2.ex#L16
My part1 worked without using map with coord keys. That worked perfectly with list of coords. This is my first AOC in 16 years since i started developing and i have NEVER gotten use of using maps for quick lookups. So its been digged way back into my memory as a go to solution … Been mostly frontend and backend, with “normal” problems. (ok, ok, maybe some few times, but seldom …)=\
it uses 17-18 seconds though on the full input (AMD Ryzen 1700, 8 cores, 16 virtual) .. could be my struct usage and patter matching maybe. EDIT: actually on github workflow it ran in 8 seconds .. so i guess its highly machine dependant
This was great knowledge, thanks! I tested it out and, indeed, using :binary.at was much faster than String.at. I get roughly equal runtime for part 2 with :binary.at as I do when I convert the input into a Map and use Map.get. Both of which are at least two orders of magnitude faster than String.at in this case.
I got some sleep yesterday, but that means I’m playing catch-up.
Here’s pt1 for me:
#!/usr/bin/env elixir
defmodule Day6.Part1 do
@westward_facing_guard ~c"<" |> List.first()
@eastward_facing_guard ~c">" |> List.first()
@northward_facing_guard ~c"^" |> List.first()
@southward_facing_guard ~c"v" |> List.first()
@guard_chars [
@northward_facing_guard,
@southward_facing_guard,
@eastward_facing_guard,
@westward_facing_guard
]
@obstacle ~c"#" |> List.first()
@open_space ~c"." |> List.first()
@seen ~c"X" |> List.first()
defp parse(str) do
[row | _tail] =
rows =
str
|> String.split("\n")
|> Enum.map(&to_charlist/1)
height = Enum.count(rows)
length = Enum.count(row)
{x, y} =
guard_position =
rows
|> Enum.with_index()
|> Enum.reduce_while(
{nil, nil},
fn {charlist, y_index}, {nil, nil} ->
x_index =
charlist
|> Enum.find_index(fn c ->
c in @guard_chars
end)
if is_nil(x_index), do: {:cont, {nil, nil}}, else: {:halt, {x_index, y_index}}
end
)
guard_row =
rows
|> Enum.at(y)
orientation =
guard_row
|> Enum.at(x)
sanitized_guard_row =
guard_row
|> Enum.map(fn
c -> if c in @guard_chars, do: @open_space, else: c
end)
rows = (rows |> Enum.take(y)) ++ [sanitized_guard_row] ++ (rows |> Enum.drop(y + 1))
%{
map: %{
rows: rows,
height: height,
length: length
},
guard_position: guard_position,
orientation: orientation
}
end
@next_orientation %{
@northward_facing_guard => @eastward_facing_guard,
@eastward_facing_guard => @southward_facing_guard,
@southward_facing_guard => @westward_facing_guard,
@westward_facing_guard => @northward_facing_guard
}
defp mark_map(
%{
map: %{
rows: rows,
height: height,
length: length
},
guard_position: {x, y} = guard_position,
orientation: orientation
} = state,
acc
) do
row_above =
if y == 0, do: :off_the_map, else: y - 1
row_below =
if y == height - 1, do: :off_the_map, else: y + 1
column_before =
if x == 0, do: :off_the_map, else: x - 1
column_after =
if x == length - 1, do: :off_the_map, else: x + 1
current_row =
rows
|> Enum.at(y)
current_value =
current_row
|> Enum.at(x)
marked_row = (current_row |> Enum.take(x)) ++ [@seen] ++ (current_row |> Enum.drop(x + 1))
rows = (rows |> Enum.take(y)) ++ [marked_row] ++ (rows |> Enum.drop(y + 1))
{guard_position, orientation} =
case orientation do
@northward_facing_guard ->
next_is_obstacle? =
if row_above == :off_the_map do
false
else
rows |> Enum.at(row_above) |> Enum.at(x) == @obstacle
end
if next_is_obstacle? do
{guard_position, @next_orientation[orientation]}
else
{{x, row_above}, orientation}
end
@southward_facing_guard ->
next_is_obstacle? =
if row_below == :off_the_map do
false
else
rows |> Enum.at(row_below) |> Enum.at(x) == @obstacle
end
if next_is_obstacle? do
{guard_position, @next_orientation[orientation]}
else
{{x, row_below}, orientation}
end
@eastward_facing_guard ->
next_is_obstacle? =
if column_after == :off_the_map do
false
else
rows |> Enum.at(y) |> Enum.at(column_after) == @obstacle
end
if next_is_obstacle? do
{guard_position, @next_orientation[orientation]}
else
{{column_after, y}, orientation}
end
@westward_facing_guard ->
next_is_obstacle? =
if column_before == :off_the_map do
false
else
rows |> Enum.at(y) |> Enum.at(column_before) == @obstacle
end
if next_is_obstacle? do
{guard_position, @next_orientation[orientation]}
else
{{column_before, y}, orientation}
end
end
increase = if current_value == @seen, do: 0, else: 1
{%{
state
| map: %{state.map | rows: rows},
guard_position: guard_position,
orientation: orientation
}, increase + acc}
end
defp count_newly_traversed(state) do
Stream.repeatedly(fn -> nil end)
|> Enum.reduce_while(
{state, 0},
fn nil = _ignored, {%{guard_position: {x, y}} = state, acc} ->
if x == :off_the_map or y == :off_the_map do
{:halt, {state, acc}}
else
{:cont, mark_map(state, acc)}
end
end
)
|> elem(1)
end
def solve() do
File.read!("06/input.txt")
|> parse()
|> count_newly_traversed()
|> IO.puts()
end
end
Day6.Part1.solve()
And part2:
#!/usr/bin/env elixir
defmodule Day6.Part1 do
@westward_facing_guard ~c"<" |> List.first()
@eastward_facing_guard ~c">" |> List.first()
@northward_facing_guard ~c"^" |> List.first()
@southward_facing_guard ~c"v" |> List.first()
@guard_chars [
@northward_facing_guard,
@southward_facing_guard,
@eastward_facing_guard,
@westward_facing_guard
]
@obstacle ~c"#" |> List.first()
@open_space ~c"." |> List.first()
defp parse(str) do
[row | _tail] =
rows =
str
|> String.split("\n")
|> Enum.map(&to_charlist/1)
height = Enum.count(rows)
length = Enum.count(row)
{x, y} =
guard_position =
rows
|> Enum.with_index()
|> Enum.reduce_while(
{nil, nil},
fn {charlist, y_index}, {nil, nil} ->
x_index =
charlist
|> Enum.find_index(fn c ->
c in @guard_chars
end)
if is_nil(x_index), do: {:cont, {nil, nil}}, else: {:halt, {x_index, y_index}}
end
)
possible_spawn_points =
for j <- 0..(height - 1) do
for i <- 0..(length - 1) do
if rows |> Enum.at(j) |> Enum.at(i) == @open_space, do: {i, j}, else: nil
end
|> Enum.filter(fn i -> not is_nil(i) end)
end
|> List.flatten()
orientation =
rows
|> Enum.at(y)
|> Enum.at(x)
%{
initial_state: %{
map: %{
rows: rows,
height: height,
length: length
},
guard_position: guard_position,
orientation: orientation
},
possible_spawn_points: possible_spawn_points
}
end
@next_orientation %{
@northward_facing_guard => @eastward_facing_guard,
@eastward_facing_guard => @southward_facing_guard,
@southward_facing_guard => @westward_facing_guard,
@westward_facing_guard => @northward_facing_guard
}
defp store(
seen,
%{
map: %{
rows: rows,
height: height,
length: length
},
guard_position: {x, y} = guard_position,
orientation: orientation
} = state
) do
row_above =
if y == 0, do: :off_the_map, else: y - 1
row_below =
if y == height - 1, do: :off_the_map, else: y + 1
column_before =
if x == 0, do: :off_the_map, else: x - 1
column_after =
if x == length - 1, do: :off_the_map, else: x + 1
seen =
seen
|> MapSet.put({guard_position, orientation})
{guard_position, orientation} =
case orientation do
@northward_facing_guard ->
next_is_obstacle? =
if row_above == :off_the_map do
false
else
rows |> Enum.at(row_above) |> Enum.at(x) == @obstacle
end
if next_is_obstacle? do
{guard_position, @next_orientation[orientation]}
else
{{x, row_above}, orientation}
end
@southward_facing_guard ->
next_is_obstacle? =
if row_below == :off_the_map do
false
else
rows |> Enum.at(row_below) |> Enum.at(x) == @obstacle
end
if next_is_obstacle? do
{guard_position, @next_orientation[orientation]}
else
{{x, row_below}, orientation}
end
@eastward_facing_guard ->
next_is_obstacle? =
if column_after == :off_the_map do
false
else
rows |> Enum.at(y) |> Enum.at(column_after) == @obstacle
end
if next_is_obstacle? do
{guard_position, @next_orientation[orientation]}
else
{{column_after, y}, orientation}
end
@westward_facing_guard ->
next_is_obstacle? =
if column_before == :off_the_map do
false
else
rows |> Enum.at(y) |> Enum.at(column_before) == @obstacle
end
if next_is_obstacle? do
{guard_position, @next_orientation[orientation]}
else
{{column_before, y}, orientation}
end
end
{
%{
state
| map: %{state.map | rows: rows},
guard_position: guard_position,
orientation: orientation
},
seen
}
end
defp place_obstacle(%{map: %{rows: rows}} = state, x, y) do
row =
rows
|> Enum.at(y)
obstructed_row =
(row |> Enum.take(x)) ++ [@obstacle] ++ (row |> Enum.drop(x + 1))
rows = (rows |> Enum.take(y)) ++ [obstructed_row] ++ (rows |> Enum.drop(y + 1))
%{state | map: %{state.map | rows: rows}}
end
defp count_if_loop(state) do
Stream.repeatedly(fn -> nil end)
|> Enum.reduce_while(
{state, MapSet.new()},
fn nil = _ignored,
{%{guard_position: {x, y} = guard_position, orientation: orientation} = state, seen} ->
cond do
x == :off_the_map or y == :off_the_map ->
{:halt, 0}
seen |> MapSet.member?({guard_position, orientation}) ->
{:halt, 1}
true ->
{:cont, seen |> store(state)}
end
end
)
end
defp count_creatable_loops(
%{initial_state: initial_state, possible_spawn_points: possible_spawn_points}
) do
possible_spawn_points
|> Enum.reduce(
0,
fn {x, y}, acc ->
acc +
(initial_state
|> place_obstacle(x, y)
|> count_if_loop())
end
)
end
def solve() do
File.read!("06/input.txt")
|> parse()
|> count_creatable_loops()
|> IO.puts()
end
end
Day6.Part1.solve()
I may come back and try to improve perf here. Part 2 took about 1m25s to run on a Intel® Core™ i7-10510U CPU @ 1.80GHz × 8
Code golfing did not spark joy on this one so I took a crack at performance on Part 2 and got it down to the 300-400ms range:
Name ips average deviation median 99th %
part_2_fast_async 2.65 377.78 ms ±0.66% 377.81 ms 381.36 ms
part_2_fast 2.27 440.13 ms ±1.12% 439.49 ms 452.15 ms
defmodule Aoc2024.Day06Fast do
def part2(file) do
file
|> main()
|> Enum.reduce(0, &(&2 + cycle_count(&1)))
end
def part2_async(file) do
file
|> main()
|> Task.async_stream(&cycle_count/1, ordered: false)
|> Enum.reduce(0, fn {:ok, num}, sum -> sum + num end)
end
def main(file) do
rows =
file
|> File.read!()
|> String.trim()
|> String.split("\n")
|> Enum.map(&String.to_charlist/1)
n = length(rows)
grid =
for {row, i} <- Enum.with_index(rows, 1),
{val, j} <- Enum.with_index(row, 1),
into: %{},
do: {{i, j}, val}
h =
for i <- 1..n, into: %{} do
ranges =
1..n
|> Enum.filter(&(Map.get(grid, {i, &1}) == ?#))
|> Enum.reduce([1..n], &ranges_split(&2, &1))
{i, ranges}
end
v =
for j <- 1..n, into: %{} do
ranges =
1..n
|> Enum.filter(&(Map.get(grid, {&1, j}) == ?#))
|> Enum.reduce([1..n], &ranges_split(&2, &1))
{j, ranges}
end
ranges = {h, v}
{position, direction} = Enum.find(grid, fn {_, val} -> val not in [?., ?#] end)
path =
steps(direction, position, ranges, grid)
|> Stream.chunk_every(2, 1, :discard)
|> Stream.flat_map(fn [{{a, b}, dir}, {{c, d}, _}] ->
for i <- a..c, j <- b..d, do: {{i, j}, dir}
end)
grid = Map.put(grid, position, ?.)
:persistent_term.put(__MODULE__, {grid, ranges})
path
|> Stream.uniq_by(&elem(&1, 0))
|> Stream.chunk_every(2, 1, :discard)
end
def cycle_count([{turning, _}, {turning, _}]), do: 0
def cycle_count([{prev_position, prev_direction}, {{i, j} = position, _}]) do
{grid, {h, v}} = :persistent_term.get(__MODULE__)
grid = Map.put(grid, position, ?#)
ranges =
{Map.update!(h, i, &ranges_split(&1, j)), Map.update!(v, j, &ranges_split(&1, i))}
steps(prev_direction, prev_position, ranges, grid)
|> Stream.drop(1)
|> Enum.reduce_while(MapSet.new(), fn x, visited ->
if MapSet.member?(visited, x) do
{:halt, :cycle}
else
{:cont, MapSet.put(visited, x)}
end
end)
|> case do
:cycle -> 1
_ -> 0
end
end
def turn_90(?^), do: ?>
def turn_90(?>), do: ?v
def turn_90(?v), do: ?<
def turn_90(?<), do: ?^
def turn_270(?^), do: ?<
def turn_270(?>), do: ?^
def turn_270(?v), do: ?>
def turn_270(?<), do: ?v
def step(?^, {row, col}, i), do: {row - i, col}
def step(?>, {row, col}, i), do: {row, col + i}
def step(?v, {row, col}, i), do: {row + i, col}
def step(?<, {row, col}, i), do: {row, col - i}
def find_range(d, {i, j}, {ranges, _}) when d in [?<, ?>] do
Enum.find(Map.get(ranges, i), fn range -> j in range end)
end
def find_range(d, {i, j}, {_, ranges}) when d in [?^, ?v] do
Enum.find(Map.get(ranges, j), fn range -> i in range end)
end
def steps(direction0, position0, ranges, grid) do
Stream.unfold({true, position0, direction0}, fn {cont?, {i, j} = curr, direction} ->
if cont? do
%{first: first, last: last} = find_range(direction, curr, ranges)
next =
case direction do
?^ -> {first, j}
?> -> {i, last}
?v -> {last, j}
?< -> {i, first}
end
prev_direction = turn_270(direction)
{{curr, direction},
{Map.has_key?(grid, step(prev_direction, curr, 1)), next, turn_90(direction)}}
else
nil
end
end)
end
def ranges_split(ranges, x) do
{left, [range | right]} = Enum.split_while(ranges, &(x not in &1))
left ++ range_split(range, x) ++ right
end
def range_split(a..c//1, a), do: [(a + 1)..c]
def range_split(a..c//1, c), do: [a..(c - 1)]
def range_split(a..c//1, b) when a < b and b < c, do: [a..(b - 1), (b + 1)..c]
end
The code is a mess so I’ll highlight the important part.
The main approach is to use ranges to traverse the path instead of individual grid cells. Here’s the range representation of the grid for input 1:
# Row ranges
%{1 => [1..4, 6..10], 2 => [1..9], ..., 10 => [1..6, 8..10]}
# Col ranges
%{1 => [1..8, 10..10], 2 => [1..6, 8..10], ..., 10 => [1..1, 3..10]}
Each row/col is represented as a list of ranges of .s with gaps for #s. This way, we don’t need to traverse each dot when walking left/right on a row or up/down on a col. We can simply jump to the :first/:last of the appropriate range. That cuts down significantly on how much work we need to do.
I did try a Task.async + :persistent_term approach but it yielded very little speed up. I haven’t tried other optimizations yet. Looks like @bjorng’s 200ish ms solution is the one to beat. I may have a look through to see if I can steal anything 
Part one was much easier than I thought it was going to be at first. Mine runs in ~1.28ms on my machine.
I even tried tracking nodes as both a map and a list. Turns out it’s pretty similar, see benchmark at the end.
def day_6_1() do
grid = File.read!("./day_6_input.txt")
max_width = map_width(grid, 0)
{x, y} = find_start(grid, {0, 0})
walk(grid, :up, {x, y}, max_width, [{x, y}])
end
def map_width(<<@new_line, _::binary>>, count), do: count + 1
def map_width(<<_::binary-size(1), rest::binary>>, count), do: map_width(rest, count + 1)
@block "#"
defp walk(grid, direction, coords, max_width, visited) do
new_coords = coord_for_direction(direction, coords)
case move(grid, new_coords, max_width) do
:exited_map -> length(Enum.uniq(visited))
:block -> walk(grid, turn_right(direction), coords, max_width, visited)
:cont -> walk(grid, direction, new_coords, max_width, [new_coords | visited])
end
end
defp coord_for_direction(:up, {x, y}), do: {x, y - 1}
defp coord_for_direction(:down, {x, y}), do: {x, y + 1}
defp coord_for_direction(:left, {x, y}), do: {x - 1, y}
defp coord_for_direction(:right, {x, y}), do: {x + 1, y}
defp move(grid, {x, y}, max) do
# The grid is square so these are the same (the input file gets saved with a new line at the end)
if x < 0 || y < 0 || x > max - 2 || y > max - 2 do
:exited_map
else
<<_::binary-size(x + max * y), rest::binary>> = grid
case rest do
<<@block, _::binary>> -> :block
_ -> :cont
end
end
end
defp turn_right(:up), do: :right
defp turn_right(:down), do: :left
defp turn_right(:left), do: :up
defp turn_right(:right), do: :down
@caret "^"
def find_start(<<@caret, _::binary>>, {x, y}), do: {x, y}
def find_start(<<@new_line, rest::binary>>, {_, y}), do: find_start(rest, {0, y + 1})
def find_start(<<_::binary-size(1), rest::binary>>, {x, y}), do: find_start(rest, {x + 1, y})
The benchmark below shows my approach with visited nodes as a map and visited nodes as a list.
The map version did this instead:
def day_6_1_map() do
grid = File.read!("./day_6_input.txt")
max_width = map_width(grid, 0)
{x, y} = find_start(grid, {0, 0})
walk_map(grid, :up, {x, y}, max_width, %{ {x, y} => 1})
end
defp walk_map(grid, direction, coords, max_width, visited) do
new_coords = coord_for_direction(direction, coords)
case move(grid, new_coords, max_width) do
:exited_map -> map_size(visited)
:block -> walk_map(grid, turn_right(direction), coords, max_width, visited)
:cont -> walk_map(grid, direction, new_coords, max_width, Map.put_new(visited, new_coords, 1))
end
end
Benchmarking Day 6 1 LIST ...
Benchmarking Day 6 1 MAP ...
Calculating statistics...
Formatting results...
Name ips average deviation median 99th %
Day 6 1 MAP 774.25 1.29 ms ±16.84% 1.26 ms 1.70 ms
Day 6 1 LIST 763.53 1.31 ms ±7.03% 1.28 ms 1.56 ms
Comparison:
Day 6 1 MAP 774.25
Day 6 1 LIST 763.53 - 1.01x slower +0.0181 ms
Memory usage statistics:
Name Memory usage
Day 6 1 MAP 2.26 MB
Day 6 1 LIST 2.41 MB - 1.07x memory usage +0.157 MB
**All measurements for memory usage were the same**
Reduction count statistics:
Name Reduction count
Day 6 1 MAP 63.96 K
Day 6 1 LIST 74.58 K - 1.17x reduction count +10.63 K
**All measurements for reduction count were the same**
I ended up with a bunch of duplicated code between part 1 and part 2. The biggest challenge was figuring out what I was doing wrong that was making part 2 really slow. It turned out to be how I was checking for loops by creating a list of the visited nodes and searching it at each node. Changing that to a MapSet got me to a solution.
defmodule Aoc2024.Day6 do
@moduledoc false
@guard_up "^"
@guard_right ">"
@guard_down "v"
@guard_left "<"
@obstruction "#"
@visited "X"
defp get_input(file) do
File.read!(file)
|> String.split("\n")
|> Enum.filter(fn line_data -> line_data != "" end)
|> Enum.map(&String.split(&1, "", trim: true))
end
defp visit(grid, {x, y}) do
List.update_at(grid, y, fn row -> List.replace_at(row, x, @visited) end)
end
defp patrol(map, obstructions) do
width = length(List.first(map))
# Find the guard, then patrol.
indexed =
map
|> List.flatten()
|> Enum.with_index()
{guard, i} =
List.keyfind(indexed, @guard_up, 0) ||
List.keyfind(indexed, @guard_down, 0) ||
List.keyfind(indexed, @guard_left, 0) ||
List.keyfind(indexed, @guard_right, 0)
facing =
case guard do
@guard_up -> :up
@guard_down -> :down
@guard_left -> :left
@guard_right -> :right
end
start = {Integer.mod(i, width), Integer.floor_div(i, width), facing}
bounds = {length(List.first(map)) - 1, length(map) - 1}
patrol(map, obstructions, bounds, start)
end
defp patrol(map, obstructions, bounds = {last_x, last_y}, loc = {x, y, _facing}, route \\ []) do
map = visit(map, {x, y})
next = {next_x, next_y, _next_facing} = look(obstructions, loc, bounds)
route = route ++ [loc]
if next_x < 0 or next_y < 0 or next_x > last_x or next_y > last_y do
{map, route}
else
patrol(map, obstructions, bounds, next, route)
end
end
defp walk(obstructions, loc, bounds = {last_x, last_y}, visited \\ MapSet.new()) do
next = {next_x, next_y, _next_facing} = look(obstructions, loc, bounds)
cond do
next_x < 0 or next_y < 0 or next_x > last_x or next_y > last_y ->
0
MapSet.member?(visited, loc) ->
1
true ->
walk(obstructions, next, bounds, MapSet.put(visited, loc))
end
end
defp look(obstructions, {x, y, :up}, {last_x, last_y}) do
ahead = {x, y - 1}
if y > 0 and MapSet.member?(obstructions, ahead) do
look(obstructions, {x, y, :right}, {last_x, last_y})
else
Tuple.append(ahead, :up)
end
end
defp look(obstructions, {x, y, :down}, {last_x, last_y}) do
ahead = {x, y + 1}
if y < last_y and MapSet.member?(obstructions, ahead) do
look(obstructions, {x, y, :left}, {last_x, last_y})
else
Tuple.append(ahead, :down)
end
end
defp look(obstructions, {x, y, :left}, {last_x, last_y}) do
ahead = {x - 1, y}
if x > 0 and MapSet.member?(obstructions, ahead) do
look(obstructions, {x, y, :up}, {last_x, last_y})
else
Tuple.append(ahead, :left)
end
end
defp look(obstructions, {x, y, :right}, {last_x, last_y}) do
ahead = {x + 1, y}
if x < last_x and MapSet.member?(obstructions, ahead) do
look(obstructions, {x, y, :down}, {last_x, last_y})
else
Tuple.append(ahead, :right)
end
end
def part1(file) do
map = get_input(file)
width = length(List.first(map))
obstructions =
map
|> List.flatten()
|> Enum.with_index()
|> Enum.reduce([], fn {space, i}, acc ->
if space == @obstruction do
[{Integer.mod(i, width), Integer.floor_div(i, width)} | acc]
else
acc
end
end)
|> MapSet.new()
{map, _} = patrol(map, obstructions)
map
|> List.flatten()
|> Enum.frequencies()
|> Map.get(@visited)
end
def part2(file) do
map = get_input(file)
last_x = length(List.first(map)) - 1
last_y = length(map) - 1
width = length(List.first(map))
indexed =
map
|> List.flatten()
|> Enum.with_index()
{guard, guard_idx} =
List.keyfind(indexed, @guard_up, 0) ||
List.keyfind(indexed, @guard_down, 0) ||
List.keyfind(indexed, @guard_left, 0) ||
List.keyfind(indexed, @guard_right, 0)
facing =
case guard do
@guard_up -> :up
@guard_down -> :down
@guard_left -> :left
@guard_right -> :right
end
start = {Integer.mod(guard_idx, width), Integer.floor_div(guard_idx, width), facing}
obstructions =
indexed
|> Enum.reduce([], fn {space, i}, acc ->
if space == @obstruction do
[{Integer.mod(i, width), Integer.floor_div(i, width)} | acc]
else
acc
end
end)
|> MapSet.new()
{_, route} = patrol(map, obstructions)
visited =
route
|> Enum.map(fn {x, y, _} -> {x, y} end)
|> Enum.filter(fn loc -> loc != start end)
|> Enum.uniq()
# Put an obstruction at each visited location and see if it loops.
visited
|> Enum.map(fn loc ->
MapSet.put(obstructions, loc)
|> walk(start, {last_x, last_y})
end)
|> Enum.sum()
end
end
: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.next and :ets.prev:by_col - same thing, but for a specific columnThis 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()