Day 6 - Advent of Code 2024
Mix.install([:kino, :benchee])Links
Prompt
— Day Day 6: Guard Gallivant —
The Historians use their fancy device again, this time to whisk you all away to the North Pole prototype suit manufacturing lab… in the year 1518! It turns out that having direct access to history is very convenient for a group of historians.
You still have to be careful of time paradoxes, and so it will be important to avoid anyone from 1518 while The Historians search for the Chief. Unfortunately, a single guard is patrolling this part of the lab.
Maybe you can work out where the guard will go ahead of time so that The Historians can search safely?
You start by making a map (your puzzle input) of the situation. For example:
....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...
The map shows the current position of the guard with ^ (to indicate the guard is currently facing up from the perspective of the map). Any obstructions - crates, desks, alchemical reactors, etc. - are shown as #.
Lab guards in 1518 follow a very strict patrol protocol which involves repeatedly following these steps:
- If there is something directly in front of you, turn right 90 degrees.
- Otherwise, take a step forward.
Following the above protocol, the guard moves up several times until she reaches an obstacle (in this case, a pile of failed suit prototypes):
....#.....
....^....#
..........
..#.......
.......#..
..........
.#........
........#.
#.........
......#...Because there is now an obstacle in front of the guard, she turns right before continuing straight in her new facing direction:
....#.....
........>#
..........
..#.......
.......#..
..........
.#........
........#.
#.........
......#...Reaching another obstacle (a spool of several very long polymers), she turns right again and continues downward:
....#.....
.........#
..........
..#.......
.......#..
..........
.#......v.
........#.
#.........
......#...This process continues for a while, but the guard eventually leaves the mapped area (after walking past a tank of universal solvent):
....#.....
.........#
..........
..#.......
.......#..
..........
.#........
........#.
#.........
......#v..
By predicting the guard’s route, you can determine which specific positions in the lab will be in the patrol path. Including the guard’s starting position, the positions visited by the guard before leaving the area are marked with an X:
....#.....
....XXXXX#
....X...X.
..#.X...X.
..XXXXX#X.
..X.X.X.X.
.#XXXXXXX.
.XXXXXXX#.
#XXXXXXX..
......#X..In this example, the guard will visit 41 distinct positions on your map.
Predict the path of the guard. How many distinct positions will the guard visit before leaving the mapped area?
To begin, get your puzzle input.
— Part Two —
Part Two prompt
QUESTION TWO?
Although it hasn’t changed, you can still get your puzzle input.
Input
input = Kino.Input.textarea("Please paste your input file:")input = input |> Kino.Input.read()"....................................#............##........#..#.#..#.........#.............#..............#.......................\n..................##.........#....................##.....#.......#.......................................#..........#.............\n.......#...........#.........................................................................................#.#.#................\n.#..........#...............................#....................................#...#.....#...#.#....................#....#......\n..........#..........................................#............#.........................#..#......#....#..#..........#........\n..........................................................................#..........................................#.........#..\n.....#....#...........................#......#..........#........................#..........#.............#...........#..........#\n................#.......................#...........#.............................#.....#..#..................................#...\n........................................................................#..#.......................................#..............\n........#......................#.....#.......#.............#....#.........#....#........................#.............#...........\n.............#....#.......#........#..#.......##................#.......................................#.........................\n......#..............#.#...#...............#.........................#.....#............#..#.........#...............#............\n..................#...#..............................................#................#.......#................#..................\n....#...#.............#........................#....................................#......#................#......#..............\n..........................................................................................#...#.........##........................\n.............#.#...............#.....#.#......#.............................#.......................................#.....#.......\n.................................................#................................................................#...............\n........#.#......................#......#........#.......................................................#........................\n....#........#......#..................................................................................#............#.............\n...........#.........#.......#...............#........................#........................................................#.#\n........................##..................#........................#..........................................#.............#...\n..........#........#........#.........#..................#.....#..............................#..#..............#.................\n#..............................................................#..#............................#..........#.......................\n.................................................................#...............#...#.#.........#.#.................#...........#\n.....................................#.....................#.....................#........#....#....#.............................\n#..#................#.....#....................................##............#...............#...#..........#.....................\n.................#.....#.....................#................#...........#...................................................#...\n..................................#........#.................#....#..................#.......................................#....\n..#....#............................#................................................##.........................................#.\n...............#......................................................#......##...................................................\n.........................#..................................#................##.#..#.#.................#.......#..................\n.................#................." <> ...Solution
defmodule Day06 do
defdelegate parse(input), to: __MODULE__.Input
def part1(input) do
input
|> parse()
|> walk()
|> Map.get(:seen)
|> MapSet.size()
end
def part2(input) do
grid = input |> parse()
grid
|> walk()
|> Map.get(:seen)
|> MapSet.delete(grid.start_pos)
|> Task.async_stream(fn xy ->
grid
|> Map.put(xy, ?#)
|> walk()
|> case do
:looped -> true
_ -> false
end
end)
|> Enum.count(fn {:ok, res} -> res end)
end
defp walk(grid) do
xy = next_xy(grid)
if MapSet.member?(grid.seen_with_dir, {xy, grid.dir}) do
:looped
else
case grid[xy] do
nil ->
grid
?# ->
grid |> turn_right() |> walk()
?. ->
grid |> step_forward() |> walk()
end
end
end
defp next_xy(%{dir: :U, pos: {x, y}}), do: {x, y - 1}
defp next_xy(%{dir: :R, pos: {x, y}}), do: {x + 1, y}
defp next_xy(%{dir: :D, pos: {x, y}}), do: {x, y + 1}
defp next_xy(%{dir: :L, pos: {x, y}}), do: {x - 1, y}
defp turn_right(grid) do
new_dir =
case grid.dir do
:U -> :R
:R -> :D
:D -> :L
:L -> :U
end
grid
|> Map.put(:dir, new_dir)
end
defp step_forward(grid) do
xy = next_xy(grid)
grid
|> Map.put(:pos, xy)
|> Map.update!(:seen, &MapSet.put(&1, xy))
|> Map.update!(:seen_with_dir, &MapSet.put(&1, {xy, grid.dir}))
end
defmodule Input do
def parse(input) when is_binary(input) do
input
|> String.split("\n", trim: true)
|> parse()
end
def parse(input) do
grid = %{
max_y: length(input),
max_x: input |> List.first() |> String.length()
}
input
|> Enum.with_index(1)
|> Enum.reduce(grid, &parse_line/2)
end
def parse_line({line, y}, grid) do
line
|> String.to_charlist()
|> Enum.with_index(1)
|> Enum.reduce(grid, fn
{?^, x}, acc ->
acc
|> Map.merge(%{
:start_pos => {x, y},
:pos => {x, y},
:seen => MapSet.new([{x, y}]),
:seen_with_dir => MapSet.new([{{x, y}, :U}]),
:dir => :U,
{x, y} => ?.
})
{c, x}, acc ->
Map.put(acc, {x, y}, c)
end)
end
end
end{:module, Day06, <<70, 79, 82, 49, 0, 0, 19, ...>>,
{:module, Day06.Input, <<70, 79, 82, ...>>, {:parse_line, 2}}}Predict the path of the guard. How many distinct positions will the guard visit before leaving the mapped area?
Your puzzle answer was answer one.
Day06.part1(input)4580You need to get the guard stuck in a loop by adding a single new obstruction. How many different positions could you choose for this obstruction?
Your puzzle answer was 1480.
Day06.part2(input)1480Both parts of this puzzle are complete! They provide two gold stars: **
At this point, you should return to your Advent calendar and try another puzzle.
If you still want to see it, you can get your puzzle input.
Tests
ExUnit.start(auto_run: false)
defmodule Day06Test do
use ExUnit.Case, async: false
setup_all do
[
input:
"....#.....\n.........#\n..........\n..#.......\n.......#..\n..........\n.#..^.....\n........#.\n#.........\n......#..."
]
end
describe "part1/1" do
test "returns expected value", %{input: input} do
assert Day06.part1(input) == 41
end
end
describe "part2/1" do
test "returns expected value", %{input: input} do
assert Day06.part2(input) == 6
end
end
end
ExUnit.run()..
Finished in 0.00 seconds (0.00s async, 0.00s sync)
2 tests, 0 failures
Randomized with seed 823797%{total: 2, excluded: 0, failures: 0, skipped: 0}Benchmarking
defmodule Benchmarking do
# https://github.com/bencheeorg/benchee
def run(input) do
Benchee.run(
%{
"Part 1" => fn -> Day06.part1(input) end,
"Part 2" => fn -> Day06.part2(input) end
},
memory_time: 2,
reduction_time: 2
)
nil
end
end{:module, Benchmarking, <<70, 79, 82, 49, 0, 0, 7, ...>>, {:run, 1}}Benchmarking.run(input)Operating System: macOS
CPU Information: Apple M1
Number of Available Cores: 8
Available memory: 8 GB
Elixir 1.15.7
Erlang 26.1.1
Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 2 s
reduction time: 2 s
parallel: 1
inputs: none specified
Estimated total run time: 22 s
Benchmarking Part 1 ...
Benchmarking Part 2 ...
Name ips average deviation median 99th %
Part 1 127.83 0.00782 s ±4.53% 0.00773 s 0.00850 s
Part 2 0.196 5.09 s ±0.00% 5.09 s 5.09 s
Comparison:
Part 1 127.83
Part 2 0.196 - 650.94x slower +5.08 s
Memory usage statistics:
Name average deviation median 99th %
Part 1 19.60 MB ±0.00% 19.60 MB 19.60 MB
Part 2 24.64 MB ±0.00% 24.64 MB 24.64 MB
Comparison:
Part 1 19.60 MB
Part 2 24.64 MB - 1.26x memory usage +5.04 MB
Reduction count statistics:
Name Reduction count
Part 1 0.29 M
Part 2 8.60 M - 30.15x reduction count +8.31 M
**All measurements for reduction count were the same**nil