Day 14 - Advent of Code 2023
Mix.install([:kino, :benchee])Links
Input
input = Kino.Input.textarea("Please paste your input file:")input = input |> Kino.Input.read()".....O..#....O.O.....OO#...#.....#...........O#..OO...#O##..#.....#...O.OO...#.O......OO#...OO...O..\nOOO....#O.#..O#.#.OO...OO..O##...O.....O.O...#.O.......OOO.O...#.....#.#.O....O.O.....#...#.OOOO.O..\n...O..#...#O..#......O#.......#..O##O.#....##......O.O...O..#O.O..##..#..#O......##...OO.#.O#..O...#\n.O..#...##O..#....#...O.O...#........O.O..#...O..#O.O.....#O...OO.#....O..O....OO##OO#...O#.O#...#.#\n#.O......O.#.O..OO.O..#....#.OO....#.#..#..O#.O....OO......#.##O...#.OO........O..OO...OOO#O.#O#.O.#\n...##.O.#O.O.##.#..O....#.#..#.OO.O...#....#.O..O#O.O.O..O...O.O..##...O#..#.......O.O......#O.#O...\n.O.O..O..O#.O.O..O.O..O..O..............#...O#O#.O.#.##..........##O....O.O...........O..O..O#...#..\n...#O.O.OO#..O..#.#...#O...O..#...#.........O...#OO#...#.O#....O...##..O...O.#O#.O#...O.O...#OO.O#..\n...##.##.O...O..#..#O.O.O...O.##..#.#.O..OO.O......OO..#..O.O..#..#.......O..O.....OO.OOO.O..O..#O.#\n....#O.O...#OO..O.O............O.....#O..#O#...#.........O.O..O...OO....#..O..##.O..####O#O.#.......\n.OOO.......##..O..#O.OO.##.....O....#..OO.#O.......OO..........OO..O..O#...#..O..##.O........#....O.\n....#.O#...#OO..............O..O.O...O...O...O....O###....O.#OO...O#.OO.#...#.#.##.....O...........O\n.......#O##..#......#.O.#.......O#.#.O#O#..#.#...O.....O..O#..O..#.O#....O..#.......O..O..#O........\nO..O.#.O...#....##...#.....O..#.#......O..#O..#.OO..O.##.........O#O.#....#..#.###OOOO..#OO.#O.O.O#.\n...O##O.#.............#..O.O....O#.....#OO...OOO......O#.O...#O#.#..#....O..#.#..O..#.O...OO.....O..\n...O......#..O.#.#..##....O..#....#..O.#.......#..O...##O.O.......#..O.OO..O..........O....##.....#.\n........#O##..O....#....#.....O...O.O.O.OO..O........#..#.O.........O.....O..O.O..#O.O...O...#..##..\n.O.#.....O.O.#..##O#.....#.#..O......O..##.#.#....##...O...OO.#..........OO.#O#OOO..#....#.#...O.#..\n....#...#.OO....#..OO#.#OO.O....OO..#..O....OO.......##.##O####O.O.O#..#....O.O......O.....#.O..O...\n.O#O#........O.#...O#O..#O...O.#..#.#..O#........O###..O..#...#..O.##..#............O.......O..O....\n........#.O.....O...O.....##.....##.#.#.#....OO####.#..O#....#O...#.O#..O.O.#.O......O..#..O.....O..\n..O#..##O.OOOO...OO....OO#.#.O.....#.#......#...#OO#...####O#....O...O.O.O.O#....O.##OO#..O.#.O..##.\n.##...............#.O#OO.#.......#...#O.#.OOO#.O...#....#....O#..O.#..O...O#...#..O#.O#O#........OO#\n...#......##...#.#O..O......O#O.O..OOO..O##....#....O.#..O....#........OO#.#...#.O#..O....O.O##..O#.\n.OO......O.....O...##..#...#....O.#....O....O...........OO.#.#..#...#.O#O.#.#......#.O......O.O#.#.#\nO.O....#O...##.O..#O.O...#...O.......O.OO...O.O#.....#..#.O#.....O.O...........O.....O...O.....#....\n.#O#..O....O.......#..OOOO.....O.....####...#.......O...O#O...O..#..#...##.#.....#....O....#...##...\n........O.O#OO#..#.O.....#.OOO......OO#.#.....O.#..#O.........#OOO......O..#......O..##....#O....#.#\n..O..#O.....##..#.OO..O..........OO..O...#.##O.#.#..O.O#.#.#......OOO......#..O..#.O....O#...OO#....\n...#.OOO.O......O#O...O.O.OO....OO#.....O.O.O#.....O##.OO......#......OOO#O.OO.O#...#.....O....OO...\n...#.#O..O...##.#.###.O.#...#.#....O.OO...O.O.O.O...#.#.O....#OO#.OO...#O...#O...OO.O..O..O....O..O#\n.##.O......#.##.....O...OO#...O.....O..#.....O.........#....O..#....O.####......#...#........O#..OO.\n.#.#.O.#.O#..OO.#....O...#.O...O..#.O.....#OO....#.O.O.O......OO...#.#.O#O#OO.#O.O.....O.........#..\n..#.#..O...#..#.....OO.#O...O#...OO.O...O#....##O....#.#...OO.#.....#.O#.....O.....O...#.#O.....#...\n.O..OO#.#OO...O..#..........OO.............##..####...#.O....O...#.#...O#..O.O..OO.#....OOO..#...OO.\n#...#....#.........OOOO....OO....O#O..........#..O#..O...#.OOO.....OO.......OO.##...O.#....OOO...##.\n#.........#OO#.O.#..##.#.##O...#...OO....O#O......#.......O.O...#O...O.O.#O##O#..O....O#.#......O.#.\n...O..O#..#...##..O....O..O......O.O#...OO.......##......OO..#.O....#.##O.OO....#.O.#.OO..O....O.#..\n.O..O.#.O.#............O....#....#....#.#.....#...OO#...OO.##OO.#..#....#....#.O#.OO#.#.O.O#..O.....\n.OO#O...#.#......O...#...O##.O....O#...O..O..O..O.#O..#..###OO..#..O##O.#.O...O#O...OO.O..#.#O#..#.#\n#..OOOO...OOO.O..#O...OO##....O#..OO...O.O.#....#O#O...." <> ...Solution
defmodule Day14 do
defdelegate parse(input), to: __MODULE__.Input
alias __MODULE__.Cache
def part1(input) do
input
|> parse()
|> roll(:north)
|> calc_load()
end
def part2(input) do
input
|> parse()
|> roll_cycle_loop()
end
defp calc_load(grid) do
Enum.reduce(grid.max_y..0, 0, fn y, total ->
num_rounded = Enum.count(0..grid.max_x, &(grid[{&1, y}] == ?O))
total + num_rounded * (grid.max_y + 1 - y)
end)
end
defp roll_cycle_loop(grid) do
{:ok, cache} = Cache.start_link([])
Cache.put(cache, string_grid(grid), 0)
roll_cycle_loop(grid, cache, 0)
end
defp roll_cycle_loop(grid, cache, count) do
new_grid = roll_cycle(grid)
grid_key = string_grid(new_grid)
case Cache.get(cache, grid_key) do
nil ->
Cache.put(cache, grid_key, count + 1)
Cache.put(cache, count + 1, calc_load(new_grid))
roll_cycle_loop(new_grid, cache, count + 1)
value ->
lookup_index = value + rem(1_000_000_000 - value, count - value + 1)
Cache.get(cache, lookup_index)
end
end
defp roll_cycle(grid) do
grid
|> roll(:north)
|> roll(:west)
|> roll(:south)
|> roll(:east)
end
defp roll(grid, :north) do
roll(grid, :north, 1..grid.max_y, 0..grid.max_x, fn y, x -> {x, y} end)
end
defp roll(grid, :south) do
roll(grid, :south, (grid.max_y - 1)..0, 0..grid.max_x, fn y, x -> {x, y} end)
end
defp roll(grid, :west) do
roll(grid, :west, 1..grid.max_x, 0..grid.max_y, fn x, y -> {x, y} end)
end
defp roll(grid, :east) do
roll(grid, :east, (grid.max_x - 1)..0, 0..grid.max_y, fn x, y -> {x, y} end)
end
defp roll(grid, direction, range1, range2, xy_fun) do
range1
|> Enum.reduce(grid, fn a, acc ->
range2
|> Enum.reduce(acc, fn b, acc ->
xy = xy_fun.(a, b)
case acc[xy] do
?O ->
new_xy = find_resting_xy(xy, acc, direction)
acc
|> Map.put(xy, ?.)
|> Map.put(new_xy, ?O)
_ ->
acc
end
end)
end)
end
defp find_resting_xy({x, y}, grid, :north) do
{
x,
Enum.find(y..0, &(grid[{x, &1 - 1}] != ?.))
}
end
defp find_resting_xy({x, y}, grid, :south) do
{
x,
Enum.find(y..grid.max_y, &(grid[{x, &1 + 1}] != ?.))
}
end
defp find_resting_xy({x, y}, grid, :west) do
{
Enum.find(x..0, &(grid[{&1 - 1, y}] != ?.)),
y
}
end
defp find_resting_xy({x, y}, grid, :east) do
{
Enum.find(x..grid.max_x, &(grid[{&1 + 1, y}] != ?.)),
y
}
end
def string_grid(grid) do
grid
|> string_rows()
|> to_string()
end
def string_rows(grid) do
0..grid.max_y
|> Enum.map(fn y ->
0..grid.max_x
|> Enum.map(fn x -> grid[{x, y}] end)
|> to_string()
end)
end
def print_grid(grid, label) do
IO.puts(label)
grid |> string_rows() |> Enum.each(&IO.puts/1)
grid
end
defmodule Cache do
use Agent
def start_link(_opts) do
Agent.start_link(fn -> %{} end)
end
def get(cache, key) do
Agent.get(cache, &Map.get(&1, key))
end
def put(cache, key, value) do
Agent.update(cache, &Map.put(&1, key, value))
end
end
defmodule Input do
def parse(input) do
input
|> String.splitter("\n", trim: true)
|> Stream.with_index()
|> Enum.reduce(%{}, &parse_line/2)
|> add_max_xy()
end
defp parse_line({line, row}, grid) do
line
|> String.to_charlist()
|> Enum.with_index()
|> Enum.reduce(grid, fn {char, col}, acc ->
Map.put(acc, {col, row}, char)
end)
end
defp add_max_xy(grid) do
x = Map.keys(grid) |> Enum.map(&elem(&1, 0)) |> Enum.max()
y = Map.keys(grid) |> Enum.map(&elem(&1, 1)) |> Enum.max()
Map.merge(grid, %{max_x: x, max_y: y})
end
end
end{:module, Day14, <<70, 79, 82, 49, 0, 0, 35, ...>>,
{:module, Day14.Input, <<70, 79, 82, ...>>, {:add_max_xy, 1}}}Tilt the platform so that the rounded rocks all roll north. Afterward, what is the total load on the north support beams?
Your puzzle answer was 103614.
Day14.part1(input)103614Run the spin cycle for 1000000000 cycles. Afterward, what is the total load on the north support beams?
Your puzzle answer was 83790.
Day14.part2(input)83790Both 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 Day14Test do
use ExUnit.Case, async: false
setup_all do
[
input:
"O....#....\nO.OO#....#\n.....##...\nOO.#O....O\n.O.....O#.\nO.#..O.#.#\n..O..#O..O\n.......O..\n#....###..\n#OO..#...."
]
end
describe "part1/1" do
test "returns expected value", %{input: input} do
assert Day14.part1(input) == 136
end
end
describe "part2/1" do
test "returns expected value", %{input: input} do
assert Day14.part2(input) == 64
end
end
end
ExUnit.run()..
Finished in 0.00 seconds (0.00s async, 0.00s sync)
2 tests, 0 failures
Randomized with seed 811435%{total: 2, failures: 0, excluded: 0, skipped: 0}Benchmarking
defmodule Benchmarking do
def run(input) do
Benchee.run(
%{
"Part 1" => fn -> Day14.part1(input) end,
"Part 2" => fn -> Day14.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 Pro
Number of Available Cores: 10
Available memory: 32 GB
Elixir 1.15.6
Erlang 26.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 198.84 0.00503 s ±7.26% 0.00493 s 0.00598 s
Part 2 0.59 1.70 s ±6.80% 1.70 s 1.80 s
Comparison:
Part 1 198.84
Part 2 0.59 - 337.26x slower +1.69 s
Memory usage statistics:
Name average deviation median 99th %
Part 1 0.00763 GB ±0.01% 0.00763 GB 0.00763 GB
Part 2 2.01 GB ±0.00% 2.01 GB 2.01 GB
Comparison:
Part 1 0.00763 GB
Part 2 2.01 GB - 262.92x memory usage +2.00 GB
Reduction count statistics:
Name average deviation median 99th %
Part 1 0.45 M ±0.00% 0.45 M 0.45 M
Part 2 156.09 M ±0.00% 156.09 M 156.09 M
Comparison:
Part 1 0.45 M
Part 2 156.09 M - 348.48x reduction count +155.64 Mnil
