# Advent of Code 2024

```elixir
Mix.install([
  {:req, "~> 0.5.8"}
])
```

## Common

```elixir
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)
```

[![Run in Livebook](https://livebook.dev/badge/v1/blue.svg)](https://livebook.dev/run?url=https%3A%2F%2Fraw.githubusercontent.com%2Fleifmetcalf%2Faoc-2024%2Frefs%2Fheads%2Ftrunk%2Faoc2024.livemd)

```elixir
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
```

```elixir
import Prelude
```

## Day 1

```elixir
defmodule Day1 do
  def input() do
    File.read!("/home/leif/Documents/aoc/1")
  end
  def parse(input) do
    parse_grid(input) |> transpose()
  end
end
```

```elixir
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
```

```elixir
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

```elixir
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
```

```elixir
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
```

```elixir
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

```elixir
defmodule Day3 do
  def input() do
    File.read!("/home/leif/Documents/aoc/3")
  end
end
```

```elixir
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
```

```elixir
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

```elixir
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
```

```elixir
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
```

```elixir
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

```elixir
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
```

```elixir
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
```

```elixir
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

```elixir
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
```

```elixir
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
```

```elixir
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

```elixir
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

```elixir
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
```

```elixir
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

```elixir
defmodule Day9 do
  def input() do
    """
    2333133121414131402
    """

    File.read!("/home/leif/Documents/aoc/9")
  end
end
```

```elixir
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
```

```elixir
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

```elixir
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
```