Advent of Code 2023 - Day 5

This problem scared me like here we go with big numbers … c’mon, day five!?

My solution for part 2 was to pass the initial ranges to each map. The top iterator is over the input maps because I felt it would be simpler to keep a list of ranges to translate at each step. But I guess it could be possible to pass each seed range to each map before translating the next seed range.

Anyway:

• initialize the current ranges with the seed ranges
• for the first “mapper” (like seed-to-soil), translate all current ranges from source to destination. This may require to cut the current ranges at boundaries. For instance if the current range is 10..20 and the mapper is source=0..15 dest=100..115 then this returns a translated range 100..105 (for the 10..15 part) and an other range of 16..20 that was not matched by the mapper.
• After each range split and translation we have a bunch of translated ranges and a residue of unmatched ranges. According to the rules those are valid ranges, so we concat the two lists and that is our new current ranges.
• Continue the same process for each remaining mapper.
• Finally, take the range that has the lowest .first and return that .first.

defmodule AdventOfCode.Y23.Day5 do
  alias AoC.Input, warn: false

  def read_file(file, _part) do
    Input.read!(file)
  end

  def parse_input(input, _part) do
    blocks = input |> String.trim_trailing() |> String.split("\n\n")

    [
      "seeds: " <> seeds_raw,
      "seed-to-soil map:\n" <> seed_to_soil_raw,
      "soil-to-fertilizer map:\n" <> soil_to_fertilizer_raw,
      "fertilizer-to-water map:\n" <> fertilizer_to_water_raw,
      "water-to-light map:\n" <> water_to_light_raw,
      "light-to-temperature map:\n" <> light_to_temperature_raw,
      "temperature-to-humidity map:\n" <> temperature_to_humidity_raw,
      "humidity-to-location map:\n" <> humidity_to_location_raw
    ] = blocks

    %{
      seeds: int_list(seeds_raw),
      seed_to_soil: parse_ranges(seed_to_soil_raw),
      soil_to_fertilizer: parse_ranges(soil_to_fertilizer_raw),
      fertilizer_to_water: parse_ranges(fertilizer_to_water_raw),
      water_to_light: parse_ranges(water_to_light_raw),
      light_to_temperature: parse_ranges(light_to_temperature_raw),
      temperature_to_humidity: parse_ranges(temperature_to_humidity_raw),
      humidity_to_location: parse_ranges(humidity_to_location_raw)
    }
  end

  defp int_list(line) do
    line |> String.split(" ") |> Enum.map(&String.to_integer/1)
  end

  defp parse_ranges(lines) do
    lines
    |> String.split("\n")
    |> Enum.map(&parse_range/1)
  end

  defp parse_range(line) do
    [dest_0, source_0, len] = int_list(line)

    source_range = source_0..(source_0 + len - 1)//1
    dest_range = dest_0..(dest_0 + len - 1)//1
    {source_range, dest_range}
  end

  def part_one(problem) do
    locations = Enum.map(problem.seeds, &find_location(&1, problem))
    Enum.min(locations)
  end

  @path [
    :seed_to_soil,
    :soil_to_fertilizer,
    :fertilizer_to_water,
    :water_to_light,
    :light_to_temperature,
    :temperature_to_humidity,
    :humidity_to_location
  ]

  defp find_location(seed, data) do
    Enum.reduce(@path, seed, fn tl_key, id -> translate(Map.fetch!(data, tl_key), id) end)
  end

  defp translate(ranges, id) do
    case Enum.find(ranges, fn {source_range, _dest_range} -> id in source_range end) do
      {source_range, dest_range} ->
        diff = id - source_range.first
        dest_range.first + diff

      nil ->
        id
    end
  end

  def part_two(problem) do
    ranges =
      problem.seeds
      |> Enum.chunk_every(2)
      |> Enum.map(fn [first, last] -> first..(first + last - 1) end)

    final_ranges = Enum.reduce(@path, ranges, &translate_ranges(Map.fetch!(problem, &1), &2))

    Enum.min_by(final_ranges, & &1.first).first
  end

  defp translate_ranges(mappers, ranges) do
    # For each mapper, split all the ranges into those that are covered by the
    # mapper source and those that are not. The latter can be consumed by the
    # next mapper and so on.
    #
    # Finally return the covered ranges translated by the mapper and the
    # leftover as-is, as they are valid ranges but map 1:1.

    Enum.flat_map_reduce(mappers, ranges, fn {source, _} = mapper, rest_ranges ->
      {covered_ranges, rest_ranges} = split_ranges(rest_ranges, source)
      {Enum.map(covered_ranges, &translate_range(&1, mapper)), rest_ranges}
    end)
    |> case do
      {translated, as_is} -> translated ++ as_is
    end
  end

  defp translate_range(range, {source, dest}) do
    diff = dest.first - source.first
    Range.shift(range, diff)
  end

  defp split_ranges(ranges, source) do
    split_ranges(ranges, source, {[], []})
  end

  defp split_ranges([r | ranges], source, {covered_ranges, rest_ranges}) do
    case split_range(r, source) do
      {nil, rest} ->
        split_ranges(ranges, source, {covered_ranges, rest ++ rest_ranges})

      {covered, nil} ->
        split_ranges(ranges, source, {covered ++ covered_ranges, rest_ranges})

      {covered, rest} ->
        split_ranges(ranges, source, {covered ++ covered_ranges, rest ++ rest_ranges})
    end
  end

  defp split_ranges([], _source, acc) do
    acc
  end

  def split_range(range, source)

  def split_range(ra.._rz = range, _sa..sz) when sz < ra do
    {nil, [range]}
  end

  def split_range(_ra..rz = range, sa.._sz) when sa > rz do
    {nil, [range]}
  end

  def split_range(ra..rz = range, sa..sz) when sa <= ra and sz >= rz do
    {[range], nil}
  end

  def split_range(ra..rz, sa..sz) when sa >= ra and sz >= rz do
    {[sa..rz], [ra..(sa - 1)]}
  end

  def split_range(ra..rz, sa..sz) when sa <= ra and sz <= rz do
    {[ra..sz], [(sz + 1)..rz]}
  end

  def split_range(ra..rz, sa..sz) when sa >= ra and sz <= rz do
    {[sa..sz], [ra..(sa - 1), (sz + 1)..rz]}
  end
end

With my input I have 153 ranges after the last step. It takes between 1 and 2 milliseconds for part 2 (I never have consistent times on my machine…)

Pretty fast solution using :gb_trees.

The keys in the trees are {source_low, source_high} and the corresponding values are {destination_low, destination_high} (I don’t like the idea of length, so I just want to convert them to ranges, but comparison of ranges gives warning, so I just convert them to {low, high}).

Maybe using :gb_trees is an overkill. I realized that I can just sort them.

Here’s the Livebook file:

https://github.com/Aetherus/advent-of-code/blob/master/2023/day-05.livemd

My beginner’s solution, Day 05 part 1

defmodule Day05 do

  def part1(input) do
    almanac = parse(input)

    for seed <- almanac.seed do 
      source_to_destination(almanac.map, seed)
    end
    |> Enum.min
 end

  def source_to_destination([], source), do: source
  def source_to_destination([map | tail], source) do
    destination = map # map here is a list of keyword lists
      |> Enum.find(fn x -> source in x[:source_range] end)
      |> case do
          nil -> source
          x   -> source + x[:distance]
         end
    # IO.inspect([source: source, destination: destination])
    source_to_destination(tail, destination)
  end

  def parse(str) do
    [seeds_str | tail] = str
      |> String.split("\n\n")
        
    seeds = seeds_str
    |> String.trim_leading("seeds: ")
    |> String.split
    |> Enum.map(&String.to_integer/1)
    
    maps = tail
    |> Enum.map(&parse_map/1)

    %{seed: seeds, map: maps}
  end

  def parse_map(str) do
    str
    |> String.split("\n")
    |> Enum.drop(1)
    |> Enum.map(fn line -> line
        |> String.split
        |> Enum.map(&String.to_integer/1)
        |> then(fn [a, b, c] -> 
            [destination_range_start: a,
             source_range_start: b,
             range_length: c,
             source_range: b..b+c-1,
             distance: a-b] end)
        end)
  end
    
end

Part 2 left me wishing I had some version of the local accumulators proposal.

The triply-nested for-reduce comprehension in my solution was a real headache to think through.

https://github.com/midouest/advent-of-code-2023/blob/main/notebooks/day05.livemd

Took me a while to figure out how to split the ranges properly, but pretty happy with the 7ms runtime:

https://github.com/ramuuns/aoc/blob/master/2023/day-05.ex

Ha. I was also wishing for the local accumulation proposal in Part 2. My colleagues are brute forcing this and materializing the ranges just made my 64GB RAM run out lol. I just ended up splitting the ranges and it runs instantaneously.

src: public-apps/05.livemd · shritesh/aoc2023 at main
deployed: https://shritesh-aoc2023.hf.space/apps/05/hhtya3nyedp7srni6f6gj3xsynsv3dt5gg2rrggwv43cm327

You do not need to materialise ranges, as you can reduce them on line.

My solutions for today:

defmodule AdventOfCode.Day5 do
  @moduledoc false

  @order [:seed, :soil, :fertilizer, :water, :light, :temperature, :humidity, :location]

  def solve(input, part: 1) do
    {seeds, graph} = parse(input)

    seeds
    |> Stream.map(fn seed ->
      Enum.reduce(0..(length(@order) - 2), seed, fn index, acc ->
        range_maps = graph[Enum.at(@order, index)][Enum.at(@order, index + 1)]

        for range_map <- range_maps,
            acc >= range_map.source_range_start and acc < range_map.source_range_start + range_map.range_length,
            reduce: acc do
          acc ->
            acc - range_map.source_range_start + range_map.destination_range_start
        end
      end)
    end)
    |> Enum.min()
  end

  def solve(input, part: 2) do
    {seeds, graph} = parse(input)

    seeds
    |> Stream.chunk_every(2)
    |> Task.async_stream(fn [seed_range_start, seed_range_length] ->
      seed_range_end = seed_range_start + seed_range_length - 1

      0..(length(@order) - 2)
      |> Enum.reduce([%{start: seed_range_start, end: seed_range_end}], fn index, acc ->
        range_maps = graph[Enum.at(@order, index)][Enum.at(@order, index + 1)]

        range_maps
        |> Enum.reduce(acc, fn range_map, acc ->
          Enum.flat_map(acc, fn seed_range ->
            # do not map a range that has already been mapped, since all
            # "maps" happen at the same time within a round
            if Map.has_key?(seed_range, :kind) and seed_range[:kind] == :mapped do
              [seed_range]
            else
              split_range(seed_range, range_map)
            end
          end)
        end)
        |> Enum.map(fn range ->
          Map.drop(range, [:kind])
        end)
      end)
      |> Stream.map(& &1[:start])
      |> Enum.min()
    end)
    |> Enum.reduce(fn {:ok, min}, acc -> min(min, acc) end)
  end

  @doc """
  Returns

  {
    [79, 14, 55, 13],
    %{
      seed: %{
        soil: [
          %{range_length: 2, destination_range_start: 50, source_range_start: 98},
          ...
        ]
      },
      ...
    }
  }
  """
  def parse(input) do
    [seeds | maps] =
      String.split(input, "\n\n", trim: true)

    seeds =
      ~r/\d+/
      |> Regex.scan(
        seeds
        |> String.split(" ", parts: 2, trim: true)
        |> Enum.at(1)
      )
      |> List.flatten()
      |> Enum.map(&String.to_integer(&1))

    graph =
      Enum.reduce(maps, %{}, fn map, acc ->
        [map_name | ranges] = String.split(map, "\n", trim: true)

        map_name = map_name |> String.split(" ") |> Enum.at(0)

        [source, destination] = map_name |> String.split("-to-") |> Enum.map(&String.to_atom(&1))

        ranges =
          Enum.flat_map(ranges, fn range ->
            range
            |> String.split("\n", trim: true)
            |> Enum.map(fn range ->
              [destination_range_start, source_range_start, range_length] = String.split(range, " ")

              %{
                source_range_start: String.to_integer(source_range_start),
                destination_range_start: String.to_integer(destination_range_start),
                range_length: String.to_integer(range_length)
              }
            end)
          end)

        Map.put(acc, source, Map.put(%{}, destination, ranges))
      end)

    {seeds, graph}
  end

  @doc """
  Splits and maps a range based on a map, sorting the list at the end.
  """
  def split_range(input_range, map) do
    source_range_end = map.source_range_start + map.range_length - 1
    destination_range_end = map.destination_range_start + map.range_length - 1

    map = Map.put(map, :source_range_end, source_range_end)
    map = Map.put(map, :destination_range_end, destination_range_end)

    case {input_range.start, input_range.end} do
      {range_start, range_end} when range_start > source_range_end or range_end < map.source_range_start ->
        # No overlap
        [input_range]

      {range_start, range_end} ->
        # Determine the overlap with the source range
        overlap_start = max(range_start, map.source_range_start)
        overlap_end = min(range_end, source_range_end)

        # Calculate the offset for the destination range
        offset = overlap_start - map.source_range_start
        destination_start = map.destination_range_start + offset
        destination_end = destination_start + (overlap_end - overlap_start)

        ranges = [
          # Before overlap
          if(range_start < overlap_start, do: %{start: range_start, end: overlap_start - 1}),
          # Mapped range
          %{start: destination_start, end: destination_end, kind: :mapped},
          # After overlap
          if(range_end > overlap_end, do: %{start: overlap_end + 1, end: range_end})
        ]

        # Remove nil entries and sort the list
        ranges
        |> Enum.filter(&(&1 != nil))
        |> Enum.sort(&(&1.start <= &2.start))
    end
  end
end

Same general idea as everyone else’s, except that I explicitly track which ranges have already been mapped. I was struggling with that part for a while (long enough to admit), but the example that helped me figure out the issue was: input_range = %{start: 74, end: 87}, range_map = %{source_range_start: 64, range_length: 13, destination_range_start: 68}. Splitting here will produce two ranges, one of which is a subset of another, but it’s important to keep in mind that the one that’s a subset is the final mapping, while the other one can get transformed. So really the mistake I made was thinking about each mapping within a round as a standalone transformation, whereas they all really should happen at the same time. The solution runs in about 4 ms without Task.async_stream/2, and in around 1 ms with it.

I struggled with this one a ton and really wanted to fix it without looking here for inspiration. I learned a lot from this one, can’t wait to see what others did. I’m floored that some finished this so quickly.

defmodule Mix.Tasks.Day5 do
  use Mix.Task

  def run(_) do
    IO.stream() |> parse() |> part2() |> IO.puts()
  end

  def split_int_list(s, sep) do
    s |> String.split(sep) |> Enum.map(fn n -> Integer.parse(n) |> elem(0) end)
  end

  def parse_line("seeds: " <> seeds) do
    {
      :seeds,
      seeds |> split_int_list(" ")
    }
  end

  def parse_line(line) when line != "" do
    make_range = fn line ->
      [dest_start, source_start, len] = line |> split_int_list(" ")
      {:range, {RangeUtil.from_start(dest_start, len), RangeUtil.from_start(source_start, len)}}
    end

    cap = Regex.run(~r/(\w+)-to-(\w+) map:/, line)

    case cap do
      [_, source, dest] -> {:map_key, {source |> String.to_atom(), dest |> String.to_atom()}}
      nil -> make_range.(line)
    end
  end

  def parse(input) do
    for line <- input,
        line = line |> String.trim(),
        line != "",
        reduce: %{} do
      acc ->
        {type, data} = parse_line(line)

        case type do
          :seeds ->
            ranges = data |> Enum.chunk_every(2)

            acc
            |> Map.put(type, data)
            |> Map.put(
              :ranges,
              ranges |> Stream.map(fn [start, len] -> RangeUtil.from_start(start, len) end)
            )

          :map_key ->
            {source, dest} = data

            acc
            |> Map.update(:maps, %{source => {dest, []}}, fn maps ->
              maps |> Map.put(source, {dest, []})
            end)
            |> Map.put(:last_map_key, source)

          :range ->
            %{last_map_key: last_map_key} = acc

            acc
            |> Map.update!(
              :maps,
              fn maps ->
                maps
                |> Map.update!(last_map_key, fn {dest, ranges} ->
                  {dest, [data | ranges]}
                end)
              end
            )
        end
    end
  end

  def get_location(:location, n, _) when is_integer(n) do
    n
  end

  def get_location(:location, range, _) do
    [range]
  end

  def get_location(source, n, maps) when is_integer(n) do
    {dest, ranges} = maps |> Map.get(source)

    transpose =
      case ranges
           |> Enum.find(fn {_, start} -> n in start end) do
        {dest_range, source_range} -> RangeUtil.transpose(n, source_range, dest_range)
        nil -> n
      end

    get_location(dest, transpose, maps)
  end

  def get_location(source, range, maps) do
    {dest, ranges} = maps |> Map.get(source)

    {transposed, leftover} =
      for {dest_range, source_range} <- ranges,
          reduce: {[], [range]} do
        {transposed_ranges, leftover} ->
          intersection = RangeUtil.intersection(range, source_range)

          offset = intersection.first - source_range.first
          transpose_start = dest_range.first + offset
          transposed = RangeUtil.from_start(transpose_start, intersection |> Range.size())

          {
            [transposed | transposed_ranges] |> Enum.reject(&(&1 == ..)),
            leftover
            |> Enum.flat_map(fn r -> RangeUtil.difference(r, intersection) end)
            |> Enum.reject(&(&1 == ..))
          }
      end

    domain = leftover ++ transposed
    domain |> Stream.flat_map(&get_location(dest, &1, maps))
  end

  def part1(state) do
    for seed <- state.seeds do
      get_location(:seed, seed, state.maps)
    end
    |> Enum.min()
  end

  def part2(state) do
    for range <- state.ranges,
        reduce: nil do
      acc ->
        min(
          acc,
          get_location(:seed, range, state.maps) |> Stream.map(fn u -> u.first end) |> Enum.min()
        )
    end
  end
end

There are fair bit of util libraries in use here, but I think they are pretty self explanatory.

Nice, I came up with almost same solution. I was pleasantly surprised I got it right on the first try, kinda expected to chase off-by-1 errors all morning