Day 11 - Advent of Code 2023
Mix.install([:kino, :benchee])Links
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#......" <> ...Solution
defmodule Day11 do
defdelegate parse(input), to: __MODULE__.Input
def part1(input) do
solve(input, 2)
end
def part2(input) do
solve(input, 1_000_000)
end
def solve(input, mult) do
grid = parse(input)
find_distances(grid.galaxies, [], grid, mult)
|> Enum.map(&elem(&1, 2))
|> Enum.sum()
end
defp find_distances([_lastg], distances, _grid, _mult), do: distances
defp find_distances([g1 | tail], distances, grid, mult) do
Enum.reduce(tail, distances, fn g2, acc ->
[{g1, g2, calc_distance(g1, g2, grid, mult)} | acc]
end)
|> then(&find_distances(tail, &1, grid, mult))
end
defp calc_distance({x1, y1}, {x2, y2}, grid, mult) do
extra_x = x1..x2 |> Enum.count(&(&1 in grid.empty_x))
extra_y = y1..y2 |> Enum.count(&(&1 in grid.empty_y))
abs(x2 - x1) + abs(y2 - y1) + (extra_x + extra_y) * (mult - 1)
end
defmodule Input do
def parse(input) when is_binary(input) do
input
|> String.splitter("\n", trim: true)
|> parse()
end
def parse(input) do
input
|> Enum.with_index()
|> Enum.reduce(%{}, &parse_line/2)
|> add_max_xy()
|> add_empties()
|> add_galaxies()
end
def 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
defp add_empties(grid) do
grid
|> Map.put(
:empty_y,
0..grid.max_y
|> Enum.reduce([], fn y, acc ->
if Enum.all?(0..grid.max_x, &(grid[{&1, y}] == ?.)) do
[y | acc]
else
acc
end
end)
)
|> Map.put(
:empty_x,
0..grid.max_x
|> Enum.reduce([], fn x, acc ->
if Enum.all?(0..grid.max_y, &(grid[{x, &1}] == ?.)) do
[x | acc]
else
acc
end
end)
)
end
defp add_galaxies(grid) do
Map.put(grid, :galaxies, for({k, ?#} <- grid, do: k))
end
end
end{:module, Day11, <<70, 79, 82, 49, 0, 0, 16, ...>>,
{:module, Day11.Input, <<70, 79, 82, ...>>, {:add_galaxies, 1}}}Expand the universe, then find the length of the shortest path between every pair of galaxies. What is the sum of these lengths?
Your puzzle answer was 10033566.
Day11.part1(input)10033566Starting with the same initial image, expand the universe according to these new rules, then find the length of the shortest path between every pair of galaxies. What is the sum of these lengths?
Your puzzle answer was 560822911938.
Day11.part2(input)560822911938Both 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 Day11Test 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 Day11.part1(input) == 374
end
end
describe "part2/1" do
test "returns expected value", %{input: input} do
assert Day11.solve(input, 10) == 1030
assert Day11.solve(input, 100) == 8410
end
end
end
ExUnit.run()..
Finished in 0.00 seconds (0.00s async, 0.00s sync)
2 tests, 0 failures
Randomized with seed 471315%{total: 2, failures: 0, excluded: 0, skipped: 0}Benchmarking
# https://github.com/bencheeorg/benchee
Benchee.run(
%{
"Part 1" => fn -> Day11.part1(input) end,
"Part 2" => fn -> Day11.part2(input) end
},
memory_time: 2,
reduction_time: 2
)
nilWarning: the benchmark Part 1 is using an evaluated function.
Evaluated functions perform slower than compiled functions.
You can move the Benchee caller to a function in a module and invoke `Mod.fun()` instead.
Alternatively, you can move the benchmark into a benchmark.exs file and run mix run benchmark.exs
Warning: the benchmark Part 2 is using an evaluated function.
Evaluated functions perform slower than compiled functions.
You can move the Benchee caller to a function in a module and invoke `Mod.fun()` instead.
Alternatively, you can move the benchmark into a benchmark.exs file and run mix run benchmark.exs
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 2 4.98 200.91 ms ±0.82% 200.82 ms 203.44 ms
Part 1 4.96 201.65 ms ±1.07% 200.98 ms 206.28 ms
Comparison:
Part 2 4.98
Part 1 4.96 - 1.00x slower +0.73 ms
Memory usage statistics:
Name Memory usage
Part 2 47.32 MB
Part 1 47.32 MB - 1.00x memory usage +0 MB
**All measurements for memory usage were the same**
Reduction count statistics:
Name average deviation median 99th %
Part 2 75.22 M ±0.00% 75.22 M 75.22 M
Part 1 75.22 M ±0.00% 75.22 M 75.22 M
Comparison:
Part 2 75.22 M
Part 1 75.22 M - 1.00x reduction count +0.00012 Mnil