Advent of Code 2024 - Day 09

Mix.install([
  {:kino_aoc, "~> 0.1.7"}
])

Introduction

2024 - Day 09

Puzzle

{:ok, puzzle_input} =
  KinoAOC.download_puzzle("2024", "9", System.fetch_env!("LB_AOC_SESSION"))

Parser

Code - Parser

defmodule Parser do
  def parse(input) do
    input
    |> String.graphemes()
    |> Enum.with_index(fn num, i ->
      disk_size = String.to_integer(num)

      if rem(i, 2) == 0 do
        file_id = div(i, 2)
        {i, {0, [{file_id, disk_size}]}}
      else
        {i, {disk_size, []}}
      end
    end)
    |> Map.new()
  end
end

Tests - Parser

ExUnit.start(autorun: false)

defmodule ParserTest do
  use ExUnit.Case, async: true
  import Parser

  @input "12345"
  @expected %{
    0 => {0, [{0, 1}]},
    1 => {2, []},
    2 => {0, [{1, 3}]},
    3 => {4, []},
    4 => {0, [{2, 5}]}
  }

  test "parse test" do
    actual = parse(@input)
    assert actual == @expected
  end
end

ExUnit.run()

Shared

defmodule Shared do
  def is_file(index), do: rem(index, 2) == 0

  def sum(files) do
    files
    |> Enum.reduce({0, 0}, fn {id, size}, {block, sum} ->
      {
        block + size,
        block..(block + size - 1)
        |> Enum.sum()
        |> Kernel.*(id)
        |> Kernel.+(sum)
      }
    end)
    |> elem(1)
  end
end

Part One

Code - Part 1

defmodule PartOne do
  import Shared

  def solve(input) do
    IO.puts("--- Part One ---")
    IO.puts("Result: #{run(input)}")
  end

  def run(input) do
    disk = Parser.parse(input)
    last_index = Enum.count(disk) - 1
    start_from = if is_file(last_index), do: last_index, else: last_index - 1

    compress(disk, start_from, 1)
    |> sum()
  end

  defp compress(disk, file_index, free_index) when free_index > file_index do
    disk
    |> Enum.sort_by(fn {idx, _} -> idx end)
    |> Enum.filter(fn
      {_, {_, []}} -> false
      _ -> true
    end)
    |> Enum.flat_map(fn {_, {_, files}} -> Enum.reverse(files) end)
  end

  defp compress(disk, file_index, free_index) do
    case Map.get(disk, file_index) do
      {0, []} ->
        compress(disk, file_index - 2, free_index)

      {0, [{id, size}]} ->
        case Map.get(disk, free_index) do
          {0, _} ->
            compress(disk, file_index, free_index + 2)

          {free, files} ->
            claim = min(size, free)
            remain_free = max(free - size, 0)
            remain_files = if size == claim, do: [], else: [{id, size - claim}]

            disk
            |> Map.put(file_index, {0, remain_files})
            |> Map.put(free_index, {remain_free, [{id, claim} | files]})
            |> compress(file_index, free_index)
        end
    end
  end
end

Tests - Part 1

ExUnit.start(autorun: false)

defmodule PartOneTest do
  use ExUnit.Case, async: true
  import PartOne

  @input "2333133121414131402"
  @expected 1928

  test "part one" do
    actual = run(@input)
    assert actual == @expected
  end
end

ExUnit.run()

Solution - Part 1

PartOne.solve(puzzle_input)

Part Two

Code - Part 2

defmodule PartTwo do
  import Shared

  def solve(input) do
    IO.puts("--- Part Two ---")
    IO.puts("Result: #{run(input)}")
  end

  def run(input) do
    disk = Parser.parse(input)
    last_index = Enum.count(disk) - 1
    start_from = if is_file(last_index), do: last_index, else: last_index - 1

    compress(disk, start_from, 1)
    |> sum()
  end

  defp compress(disk, file_index, _) when file_index < 2 do
    disk
    |> Enum.sort_by(fn {idx, _} -> idx end)
    |> Enum.flat_map(fn
      {_, {size, []}} -> [{0, size}]
      {_, {0, files}} -> Enum.reverse(files)
      {_, {remain, files}} -> Enum.reverse([{0, remain} | files])
    end)
  end

  defp compress(disk, file_index, free_index) when free_index > file_index,
    do: compress(disk, file_index - 2, 1)

  defp compress(disk, file_index, free_index) do
    {_, [{id, size}]} = Map.get(disk, file_index)

    case Map.get(disk, free_index) do
      {free, _} when size > free ->
        compress(disk, file_index, free_index + 2)

      {free, files} ->
        disk
        |> Map.put(file_index, {size, []})
        |> Map.put(free_index, {free - size, [{id, size} | files]})
        |> compress(file_index - 2, 1)
    end
  end
end

Tests - Part 2

ExUnit.start(autorun: false)

defmodule PartTwoTest do
  use ExUnit.Case, async: true
  import PartTwo

  @input "2333133121414131402"
  @expected 2858

  test "part two" do
    actual = run(@input)
    assert actual == @expected
  end
end

ExUnit.run()

Solution - Part 2

PartTwo.solve(puzzle_input)