Advent of Code 2024
Mix.install([
{:req, "~> 0.5.8"}
])
Common
session = File.read!("/home/leif/Documents/aoc/session") |> String.trim()
Enum.each(1..11, fn n ->
file = "/home/leif/Documents/aoc/#{n}"
if not File.exists?(file) do
File.write!(
file,
Req.get!("https://adventofcode.com/2024/day/#{n}/input",
headers: %{cookie: "session=#{session}"}
).body
)
end
end)
defmodule TopologicalSort do
def topological_sort(vertices, edges) do
adj =
Enum.reduce(edges, Map.new(vertices, &{&1, []}), fn
{a, b}, adj -> Map.update!(adj, a, &[b | &1])
end)
n_parents =
Enum.reduce(edges, Map.new(vertices, &{&1, 0}), fn
{_, b}, n_parents -> Map.update!(n_parents, b, &(&1 + 1))
end)
orphans = Enum.filter(vertices, &(n_parents[&1] == 0))
sorted =
Stream.unfold({n_parents, orphans}, fn
{_, []} ->
nil
{n_parents, [v | orphans]} ->
{v,
Enum.reduce(adj[v], {n_parents, orphans}, fn child, {n_parents, orphans} ->
n_parents = Map.update!(n_parents, child, &(&1 - 1))
orphans = if n_parents[child] == 0, do: [child | orphans], else: orphans
{n_parents, orphans}
end)}
end)
|> Enum.reverse()
if length(sorted) == length(vertices), do: sorted
end
end
defmodule Prelude do
def parse_grid(input, pat \\ nil) do
input
|> String.split("\n", trim: true)
|> Enum.map(fn row ->
if(is_nil(pat), do: String.split(row), else: String.split(row, pat))
|> Enum.map(&String.to_integer/1)
end)
end
def transpose(xs) do
List.zip(xs) |> Enum.map(&Tuple.to_list/1)
end
def list_to_map(xs) do
xs |> Stream.with_index(fn x, i -> {i, x} end) |> Map.new()
end
def grid_to_map(grid) do
grid
|> Enum.with_index(fn row, r -> row |> Enum.with_index(fn x, c -> {{r, c}, x} end) end)
|> Enum.concat()
|> Map.new()
end
def pairs(xs) do
Enum.reduce(xs, {xs, []}, fn x, {[_ | rest], acc} ->
{rest, [Enum.map(rest, &{x, &1}) | acc]}
end)
|> elem(1)
|> Enum.reverse()
|> Enum.concat()
end
def find_index_2d(grid, f) do
Enum.find_value(Stream.with_index(grid), fn {row, r} ->
if c = Enum.find_index(row, f), do: {r, c}
end)
end
def contains_dup?(enumerable) do
enumerable
|> Enum.reduce_while(MapSet.new(), fn x, acc ->
if x in acc, do: {:halt, :contains_dup}, else: {:cont, MapSet.put(acc, x)}
end) == :contains_dup
end
def indices_uniq(enumerable) do
Map.new(Stream.with_index(enumerable))
end
def indices_2d(grid) do
grid
|> grid_to_map
|> Enum.reduce(%{}, fn {p, x}, acc ->
update_in(acc, [x], fn
xs ->
xs = if is_nil(xs), do: [], else: xs
[p | xs]
end)
end)
end
defdelegate topological_sort(vertices, edges), to: TopologicalSort
end
import Prelude
Day 1
defmodule Day1 do
def input() do
File.read!("/home/leif/Documents/aoc/1")
end
def parse(input) do
parse_grid(input) |> transpose()
end
end
defmodule Day1.Part1 do
@doc """
iex> Day1.input() |> Day1.Part1.go()
1506483
"""
def go(input) do
Day1.parse(input)
|> Enum.map(&Enum.sort/1)
|> Enum.zip_with(fn [x, y] -> abs(x - y) end)
|> Enum.sum()
end
end
defmodule Day1.Part2 do
@doc """
iex> Day1.input() |> Day1.Part2.go()
23126924
"""
def go(input) do
[xs, ys] = Day1.parse(input)
freqs = Enum.frequencies(ys)
Enum.map(xs, &(&1 * Map.get(freqs, &1, 0))) |> Enum.sum()
end
end
Day 2
defmodule Day2 do
def input() do
File.read!("/home/leif/Documents/aoc/2")
end
def parse(input) do
parse_grid(input)
end
def unsafe_index(row) do
Enum.chunk_every(row, 3, 1, :discard)
|> Enum.find_index(fn [x, y, z] ->
(y - x) * (z - y) <= 0 or abs(y - x) not in 1..3 or abs(z - y) not in 1..3
end)
end
end
defmodule Day2.Part1 do
@doc """
iex> Day2.input() |> Day2.Part1.go()
220
"""
def go(input) do
Day2.parse(input) |> Enum.count(&(Day2.unsafe_index(&1) |> is_nil()))
end
end
defmodule Day2.Part2 do
@doc """
iex> Day2.input() |> Day2.Part2.go()
296
"""
def go(input) do
Day2.parse(input)
|> Enum.count(fn row ->
i = Day2.unsafe_index(row)
is_nil(i) or
Enum.any?(0..2, &(List.delete_at(row, i + &1) |> Day2.unsafe_index() |> is_nil()))
end)
end
end
Day 3
defmodule Day3 do
def input() do
File.read!("/home/leif/Documents/aoc/3")
end
end
defmodule Day3.Part1 do
@doc """
iex> Day3.input() |> Day3.Part1.go()
166905464
"""
def go(input) do
Regex.scan(~r/mul\((\d+),(\d+)\)/, input, capture: :all_but_first)
|> Enum.map(fn [x, y] -> String.to_integer(x) * String.to_integer(y) end)
|> Enum.sum()
end
end
defmodule Day3.Part2 do
@doc """
iex> Day3.input() |> Day3.Part2.go()
72948684
"""
def go(input) do
Regex.scan(~r/(mul)\((\d+),(\d+)\)|(do)\(\)|(don\'t)\(\)/, input, capture: :all_but_first)
|> Enum.reduce({0, 1}, fn
["mul", x, y], {acc, mask} ->
{acc + mask * String.to_integer(x) * String.to_integer(y), mask}
["", "", "", "do"], {acc, _} ->
{acc, 1}
["", "", "", "", "don't"], {acc, _} ->
{acc, 0}
end)
|> elem(0)
end
end
Day 4
defmodule Day4 do
def input() do
File.read!("/home/leif/Documents/aoc/4")
end
def parse(input) do
input
|> String.split()
|> Enum.map(fn line -> String.codepoints(line) |> Enum.map(&String.to_atom/1) end)
end
end
defmodule Day4.Part1 do
@doc """
iex> Day4.input() |> Day4.Part1.go()
2644
"""
def go(input) do
grid = input |> Day4.parse()
map = grid |> grid_to_map()
for(
r <- 0..(length(grid) - 1),
c <- 0..(length(List.first(grid)) - 1),
do:
[
[{r, c}, {r + 1, c}, {r + 2, c}, {r + 3, c}],
[{r, c}, {r - 1, c}, {r - 2, c}, {r - 3, c}],
[{r, c}, {r, c + 1}, {r, c + 2}, {r, c + 3}],
[{r, c}, {r, c - 1}, {r, c - 2}, {r, c - 3}],
[{r, c}, {r + 1, c + 1}, {r + 2, c + 2}, {r + 3, c + 3}],
[{r, c}, {r + 1, c - 1}, {r + 2, c - 2}, {r + 3, c - 3}],
[{r, c}, {r - 1, c - 1}, {r - 2, c - 2}, {r - 3, c - 3}],
[{r, c}, {r - 1, c + 1}, {r - 2, c + 2}, {r - 3, c + 3}]
]
|> Enum.count(fn line -> Enum.map(line, &map[&1]) == [:X, :M, :A, :S] end)
)
|> Enum.sum()
end
end
defmodule Day4.Part2 do
@doc """
iex> Day4.input() |> Day4.Part2.go()
1952
"""
def go(input) do
grid = input |> Day4.parse()
map = grid |> grid_to_map()
for(
r <- 0..(length(grid) - 1),
c <- 0..(length(List.first(grid)) - 1),
do:
if Enum.map(
[{r, c}, {r + 1, c + 1}, {r + 1, c - 1}, {r - 1, c + 1}, {r - 1, c - 1}],
&map[&1]
) in [
[:A, :M, :M, :S, :S],
[:A, :M, :S, :M, :S],
[:A, :S, :M, :S, :M],
[:A, :S, :S, :M, :M]
] do
1
else
0
end
)
|> Enum.sum()
end
end
Day 5
defmodule Day5 do
def input() do
File.read!("/home/leif/Documents/aoc/5")
end
def parse(input) do
[rules, updates] = String.split(input, "\n\n")
rules = parse_grid(rules, "|") |> Enum.map(&List.to_tuple/1)
updates = parse_grid(updates, ",")
{rules, updates}
end
def sorted?(update, rules) do
indices = indices_uniq(update)
Enum.all?(rules, fn {a, b} ->
i = indices[a]
j = indices[b]
is_nil(i) or is_nil(j) or i < j
end)
end
end
defmodule Day5.Part1 do
@doc """
iex> Day5.input() |> Day5.Part1.go()
7074
"""
def go(input) do
{rules, updates} = input |> Day5.parse()
rules = MapSet.new(rules)
Enum.filter(updates, &Day5.sorted?(&1, rules))
|> Enum.map(fn update -> Enum.at(update, div(length(update), 2)) end)
|> Enum.sum()
end
end
defmodule Day5.Part2 do
@doc """
iex> Day5.input() |> Day5.Part2.go()
4828
"""
def go(input) do
{rules, updates} = input |> Day5.parse()
rules = MapSet.new(rules)
Enum.map(updates, fn update ->
relevant_rules = Enum.filter(rules, fn {a, b} -> a in update and b in update end)
if Day5.sorted?(update, rules) do
0
else
sorted = topological_sort(update, relevant_rules)
Enum.at(sorted, div(length(sorted), 2))
end
end)
|> Enum.sum()
end
end
Day 6
defmodule Day6 do
def input() do
File.read!("/home/leif/Documents/aoc/6")
end
def parse(input) do
input
|> String.split()
|> Enum.map(fn line -> String.to_charlist(line) end)
end
def wander(coords, guard_pos) do
Stream.iterate({guard_pos, {-1, 0}}, fn {{r, c}, {dr, dc}} ->
{dr, dc} =
Stream.iterate({dr, dc}, fn {dr, dc} -> {dc, -dr} end)
|> Enum.find(fn {dr, dc} -> coords[{r + dr, c + dc}] != ?# end)
{{r + dr, c + dc}, {dr, dc}}
end)
end
def trodden(coords, guard_pos) do
Day6.wander(coords, guard_pos)
|> Stream.map(&elem(&1, 0))
|> Stream.uniq()
|> Stream.take_while(&Map.has_key?(coords, &1))
end
end
defmodule Day6.Part1 do
@doc"""
iex> Day6.input() |> Day6.Part1.go()
5239
"""
def go(input) do
grid = input |> Day6.parse()
guard_pos = find_index_2d(grid, &(&1 == ?^))
coords = grid_to_map(grid)
Day6.trodden(coords, guard_pos) |> Enum.count()
end
end
defmodule Day6.Part2 do
defp has_loop?(coords, guard_pos) do
Day6.wander(coords, guard_pos)
|> Stream.take_while(&Map.has_key?(coords, elem(&1, 0)))
|> contains_dup?()
end
def go(input) do
grid = input |> Day6.parse()
guard_pos = find_index_2d(grid, &(&1 == ?^))
coords = grid_to_map(grid)
trodden = Day6.trodden(coords, guard_pos)
Enum.count(
trodden,
&has_loop?(Map.put(coords, &1, ?#), guard_pos)
)
end
end
Day 7
defmodule Day7 do
def input() do
File.read!("/home/leif/Documents/aoc/7")
end
def parse(input) do
input
|> String.split("\n", trim: true)
|> Enum.map(fn line ->
[objective, xs] = String.split(line, ": ")
objective = String.to_integer(objective)
xs = String.split(xs) |> Enum.map(&String.to_integer/1)
{objective, xs}
end)
end
def go(input) do
input
|> parse()
|> Stream.filter(fn {objective, xs} -> go_rec(objective, Enum.reverse(xs)) end)
|> Stream.map(&elem(&1, 0))
|> Enum.sum()
end
defp go_rec(obj, [x]) do
obj == x
end
defp go_rec(obj, [x | xs]) do
next_power_of_10 =
cond do
x < 10 -> 10
x < 100 -> 100
x < 1000 -> 1000
end
(rem(obj, next_power_of_10) == x and go_rec(div(obj, next_power_of_10), xs)) or
(rem(obj, x) == 0 and go_rec(div(obj, x), xs)) or
(x <= obj and go_rec(obj - x, xs))
end
end
Day 8
defmodule Day8 do
def input() do
File.read!("/home/leif/Documents/aoc/8")
end
def parse(input) do
input
|> String.split()
|> Enum.map(fn line -> String.to_charlist(line) end)
end
end
defmodule Day8.Part2 do
@doc """
iex> Day8.input() |> Day8.Part2.go()
1019
"""
def go(input) do
grid = Day8.parse(input)
rows = length(grid)
cols = length(List.first(grid))
Day8.parse(input)
|> indices_2d
|> Map.delete(?.)
|> Stream.flat_map(fn {_, ps} ->
pairs(ps)
|> Stream.flat_map(fn {{r1, c1}, {r2, c2}} ->
Stream.concat(
Stream.iterate({r1, c1}, fn {r, c} -> {r + r2 - r1, c + c2 - c1} end)
|> Stream.take_while(fn {r, c} -> r in 0..(rows - 1) and c in 0..(cols - 1) end),
Stream.iterate({r1, c1}, fn {r, c} -> {r + r1 - r2, c + c1 - c2} end)
|> Stream.take_while(fn {r, c} -> r in 0..(rows - 1) and c in 0..(cols - 1) end)
)
end)
end)
|> Stream.uniq()
|> Enum.count()
end
end
Day 9
defmodule Day9 do
def input() do
"""
2333133121414131402
"""
File.read!("/home/leif/Documents/aoc/9")
end
end
defmodule Day9.Part1 do
require Integer
@doc """
iex> Day9.input() |> Day9.Part1.go()
6390180901651
"""
def go(input) do
arr =
input
|> String.trim()
|> String.codepoints()
|> Stream.map(&String.to_integer/1)
|> Stream.with_index()
|> Enum.flat_map(fn {x, i} ->
Stream.duplicate(if(Integer.is_even(i), do: div(i, 2), else: nil), x)
end)
i = Enum.find_index(arr, &is_nil/1)
j = length(arr) - 1
map = list_to_map(arr)
Stream.iterate({map, i, j}, fn
{map, i, j} ->
cond do
is_nil(map[j]) ->
{map, i, j - 1}
not is_nil(map[i]) ->
{map, i + 1, j}
true ->
{%{map | i => map[j], j => map[i]}, i + 1, j - 1}
end
end)
|> Enum.find(fn {_, i, j} -> i >= j end)
|> elem(0)
|> Enum.map(fn
{_, nil} -> 0
{i, x} -> i * x
end)
|> Enum.sum()
end
end
defmodule Day9.Part2 do
require Integer
@doc """
iex> Day9.input() |> Day9.Part2.go()
6412390114238
"""
def go(input) do
{_, files, frees} =
input
|> String.trim()
|> String.codepoints()
|> Stream.map(&String.to_integer/1)
|> Enum.chunk_every(2, 2, [0])
|> Enum.reduce({0, [], []}, fn [file, free], {i, files, frees} ->
{i + file + free, [{i, file} | files], [{i + file, free} | frees]}
end)
frees = Map.new(Stream.with_index(Enum.reverse(frees)), fn {i, x} -> {x, i} end)
Enum.reduce(Enum.reverse(Stream.with_index(Enum.reverse(files))), {0, frees}, fn
{{file_index, file}, file_order}, {acc, frees} ->
case Enum.find(0..(file_order - 1)//1, fn i -> frees[i] |> elem(1) >= file end) do
nil ->
{acc + file_order * div((file_index + file_index + file - 1) * file, 2), frees}
free_order ->
{free_index, free} = frees[free_order]
{acc + file_order * div((free_index + free_index + file - 1) * file, 2),
%{frees | free_order => {free_index + file, free - file}}}
end
end)
|> elem(0)
end
end
Day 10
Day 11
defmodule Day11 do
require Integer
def input() do
File.read!("/home/leif/Documents/aoc/11")
end
@doc """
iex> Day11.input() |> Day11.go(75)
221280540398419
"""
def go(input, n) do
input
|> String.split()
|> Enum.map(&String.to_integer/1)
|> Enum.reduce({0, Map.new()}, fn x, {acc, memo} ->
{r, memo} = rec(memo, n, x)
{acc + r, memo}
end)
|> elem(0)
end
def rec(memo, 0, _) do
{1, memo}
end
def rec(memo, i, x) do
case memo[{i, x}] do
nil ->
{r, memo} =
case x do
0 ->
rec(memo, i - 1, 1)
_ ->
len = length(Integer.digits(x))
cond do
Integer.is_even(len) ->
mask = 10 ** div(len, 2)
{r1, memo} = rec(memo, i - 1, div(x, mask))
{r2, memo} = rec(memo, i - 1, rem(x, mask))
{r1 + r2, memo}
true ->
rec(memo, i - 1, 2024 * x)
end
end
{r, Map.put(memo, {i, x}, r)}
r ->
{r, memo}
end
end
end