Advent of Code - Day 5

Mix.install([
  {:kino_aoc, "~> 0.1"},
  # {:benchee, "~> 1.0", only: :dev}
  {:kino_benchee, github: "akoutmos/kino_benchee", branch: "initial_release_prep"}
])

Introduction

Puzzle

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

Parser

Code - Parser

defmodule Parser do
  def parse(input) do
    [seeds | maps] =
      input
      |> String.split("\n\n")

    seeds = seeds |> String.split(["seeds: ", " "], trim: true) |> Enum.map(&String.to_integer/1)

    maps =
      maps
      |> Enum.map(fn map ->
        [name | pairs] =
          map
          |> String.split([" map:", "\n"], trim: true)

        {name,
         pairs
         |> Enum.map(fn pair ->
           pair
           |> String.split(" ", trim: true)
           |> Enum.map(&String.to_integer/1)
         end)}
      end)
      |> Enum.into(%{})

    %{seeds: seeds, maps: maps}
  end
end

Tests - Parser

ExUnit.start(autorun: false)

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

  @input """
  seeds: 79 14 55 13

  seed-to-soil map:
  50 98 2
  52 50 48

  soil-to-fertilizer map:
  0 15 37
  37 52 2
  39 0 15

  fertilizer-to-water map:
  49 53 8
  0 11 42
  42 0 7
  57 7 4

  water-to-light map:
  88 18 7
  18 25 70

  light-to-temperature map:
  45 77 23
  81 45 19
  68 64 13

  temperature-to-humidity map:
  0 69 1
  1 0 69

  humidity-to-location map:
  60 56 37
  56 93 4
  """
  @expected %{
    maps: %{
      "fertilizer-to-water" => [{53..60, -4}, {11..52, -11}, {0..6, 42}, {7..10, 50}],
      "humidity-to-location" => [{56..92, 4}, {93..96, -37}],
      "light-to-temperature" => [{77..99, -32}, {45..63, 36}, {64..76, 4}],
      "seed-to-soil" => [{98..99, -48}, {50..97, 2}],
      "soil-to-fertilizer" => [{15..51, -15}, {52..53, -15}, {0..14, 39}],
      "temperature-to-humidity" => [{69..69, -69}, {0..68, 1}],
      "water-to-light" => [{18..24, 70}, {25..94, -7}]
    },
    seeds: [79, 14, 55, 13]
  }

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

ExUnit.run()

Part One

Code - Part 1

defmodule PartOne do
  @progression [
    "seed-to-soil",
    "soil-to-fertilizer",
    "fertilizer-to-water",
    "water-to-light",
    "light-to-temperature",
    "temperature-to-humidity",
    "humidity-to-location"
  ]

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

  def run(input) do
    %{seeds: seeds, maps: maps} =
      input
      |> Parser.parse()

    seeds
    |> Enum.map(fn seed ->
      Enum.reduce(@progression, seed, fn step, acc ->
        Enum.find_value(maps[step], acc, fn [dest, source, len] ->
          if acc in source..(source + len - 1) do
            acc + dest - source
          else
            nil
          end
        end)
      end)
    end)
    |> Enum.min()
  end
end

Tests - Part 1

ExUnit.start(autorun: false)

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

  @input """
  seeds: 79 14 55 13

  seed-to-soil map:
  50 98 2
  52 50 48

  soil-to-fertilizer map:
  0 15 37
  37 52 2
  39 0 15

  fertilizer-to-water map:
  49 53 8
  0 11 42
  42 0 7
  57 7 4

  water-to-light map:
  88 18 7
  18 25 70

  light-to-temperature map:
  45 77 23
  81 45 19
  68 64 13

  temperature-to-humidity map:
  0 69 1
  1 0 69

  humidity-to-location map:
  60 56 37
  56 93 4
  """
  @expected 35

  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
  @progression [
    "seed-to-soil",
    "soil-to-fertilizer",
    "fertilizer-to-water",
    "water-to-light",
    "light-to-temperature",
    "temperature-to-humidity",
    "humidity-to-location"
  ]

  # random jump value
  @jump 19424

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

  def run(input, jump \\ @jump) do
    %{seeds: seeds, maps: maps} =
      input
      |> Parser.parse()

    seed_ranges =
      seeds
      |> Enum.chunk_every(2)
      |> Enum.map(fn [a, b] -> a..(a + b - 1) end)

    # work backwards - starting with min location of 0 and 
    # iteratively jumping until we find a seed that contained within a of initial seed ranges
    # we have to remember this is likely not the smallest location for which we have a seed
    potential_match =
      Stream.iterate(0, &(&1 + jump))
      |> find_seed_from_location(seed_ranges, maps)

    # once we know we are working with a seed that is within a range
    # try and find the smallest location that has a seed contained in a range
    (potential_match - jump)
    |> Stream.iterate(&(&1 + 1))
    |> find_seed_from_location(seed_ranges, maps)
  end

  def find_seed_from_location(locations, seed_ranges, maps) do
    Enum.find(locations, fn location ->
      seed =
        @progression
        |> Enum.reverse()
        |> Enum.reduce(location, fn step, acc ->
          Enum.find_value(maps[step], acc, fn [dest, source, len] ->
            if acc in dest..(dest + len - 1) do
              acc - dest + source
            else
              nil
            end
          end)
        end)

      Enum.any?(seed_ranges, fn range -> seed in range end)
    end)
  end
end

Tests - Part 2

ExUnit.start(autorun: false)

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

  @input """
  seeds: 79 14 55 13

  seed-to-soil map:
  50 98 2
  52 50 48

  soil-to-fertilizer map:
  0 15 37
  37 52 2
  39 0 15

  fertilizer-to-water map:
  49 53 8
  0 11 42
  42 0 7
  57 7 4

  water-to-light map:
  88 18 7
  18 25 70

  light-to-temperature map:
  45 77 23
  81 45 19
  68 64 13

  temperature-to-humidity map:
  0 69 1
  1 0 69

  humidity-to-location map:
  60 56 37
  56 93 4
  """
  @expected 46

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

ExUnit.run()

Solution - Part 2

PartTwo.solve(puzzle_input)

Benchmarking

defmodule Benchmarks do
  def part1(input) do
    PartOne.run(input)
  end

  def part2(input) do
    PartTwo.run(input)
  end
end

Benchee.run(
  %{
    "day05.part1" => &Benchmarks.part1/1,
    "day05.part2" => &Benchmarks.part2/1
  },
  inputs: %{
    "puzzle" => puzzle_input
  },
  time: 1,
  memory_time: 1,
  reduction_time: 1
)