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…)

Produces the answer in 1ms using native Ranges.

import AOC

aoc 2023, 5 do

  def p1(input) do
    {seeds, maps} = process(input)
    Enum.map(seeds, &maps_number(&1, maps)) |> Enum.min
  end

  def map_number([], n), do: n
  def map_number([{range, _} = fun | maps], n) do
    if n in range do
      apply_fun(fun, n)
    else
      map_number(maps, n)
    end
  end

  def apply_fun({range, dest}, n), do: dest+n-range.first

  def process(input) do
    ["seeds: " <> seeds | maps] = input |> String.split("\n\n", trim: true)
    {parse_nums(seeds),
     maps
      |> Enum.map(
        fn map ->
          [_name, elements] = String.split(map, " map:\n")
            elements
            |> String.split("\n", trim: true)
            |> Enum.map(&parse_nums/1)
            |> Enum.map(&create_mapping/1)
        end
      )}
  end

  def create_mapping([dest, source, length]) do
    {source..(source+length-1), dest}
  end

  def map_range(range, []), do: [range]
  def map_range(arg_range, [{fun_range, _} = fun_def | maps]) do
    if Range.disjoint?(fun_range, arg_range) do
      map_range(arg_range, maps)
    else
      fun_lo..fun_hi = fun_range
      arg_lo..arg_hi = arg_range
      lo = [fun_lo, arg_lo] |> Enum.max
      hi = [fun_hi, arg_hi] |> Enum.min
      [apply_fun(fun_def, lo)..apply_fun(fun_def, hi) |
       (if arg_lo < lo, do: map_range(arg_lo..lo-1, maps), else: [])
       ++ (if hi < arg_hi, do: map_range(hi+1..arg_hi, maps), else: [])]
    end
  end

  def map_ranges(ranges, []), do: normalize_ranges(ranges)
  def map_ranges(ranges, [map | maps]) do
    ranges
    |> normalize_ranges()
    |> Enum.map(fn arg -> map_range(arg, map) end)
    |> List.flatten
    |> map_ranges(maps)
  end

  def normalize_ranges(ranges) do
    ranges
    |> Enum.sort()
    |> merge_ranges()
  end

  def merge_ranges([]), do: []
  def merge_ranges([a]), do: [a]
  def merge_ranges([a | [b | ranges]]) do
    if Range.disjoint?(a, b) do
      [a | merge_ranges([b | ranges])]
    else
      merge_ranges([Enum.min([a.first, b.first])..Enum.max(a.last, b.last) | ranges])
    end
  end

  def maps_number(n, maps) do
    Enum.reduce(maps, n, &map_number/2)
  end

  def parse_nums(nums), do: nums |> String.split(" ", trim: true) |> Enum.map(&String.to_integer/1)

  def p2(input) do
    {seeds, maps} = process(input)
    seeds
    |> Enum.chunk_every(2)
    |> Enum.map(fn [start, length] -> start..(start+length-1) end)
    |> map_ranges(maps)
    |> hd
    |> then(&(&1.first))
  end
end

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