Advent of Code 2023 - Day 5

Learning Questions & Discussions Coding Challenges
,
1

Setting this down for the night, as after a quick naive solve for quick part 1 I realize that part 2 is by design computationally expensive to solve by repurposing the code used in part 1. Will update if I get part 2 working fast, I think I have the right idea in mind!

Input

Processing

I generated a list of seeds, and a map-of-maps with each key being a transform type, and each value being a map with input ranges as keys and output ranges as values.

Types 
@type seeds :: [integer()]

@type maps :: %{type :: atom => mapping}

@type mapping :: %{Range.t() => Range.t()}

@type input :: {seeds, maps}
Example Input 
{[79, 14, 55, 13],
 %{
   seed_to_soil: %{50..97 => 52..99, 98..99 => 50..51},
   soil_to_fertilizer: %{0..14 => 39..53, 15..51 => 0..36, 52..53 => 37..38},
   fertilizer_to_water: %{
     0..6 => 42..48,
     7..10 => 57..60,
     11..52 => 0..41,
     53..60 => 49..56
   },
   water_to_light: %{18..24 => 88..94, 25..94 => 18..87},
   light_to_temperature: %{45..63 => 81..99, 64..76 => 68..80, 77..99 => 45..67},
   temperature_to_humidity: %{0..68 => 1..69, 69..69 => 0..0},
   humidity_to_location: %{56..92 => 60..96, 93..96 => 56..59}
 }}

Source code available here.

defmodule AoC.Day.Five.Input do
  def parse(input_file \\ System.fetch_env!("INPUT_FILE")) do
    [[seeds] | maps] =
      input_file
      |> File.read!()
      |> String.split("\n\n")
      |> Enum.reject(&(&1 == ""))
      |> Enum.map(&String.split(&1, "\n"))
      |> Enum.map(fn line -> Enum.reject(line, &(&1 == "")) end)

    <<"seeds: ">> <> seeds = seeds
    seeds = seeds |> String.split(" ") |> Enum.map(&String.to_integer/1)

    maps = Map.new(maps, &parse_map/1)

    {seeds, maps}
  end

  def parse_map([name | mappings]) do
    name =
      name
      |> String.trim_trailing(" map:")
      |> String.replace("-", "_")
      |> String.to_atom()

    mappings = Map.new(mappings, &parse_mapping/1)
    {name, mappings}
  end

  def parse_mapping(mapping) do
    [output, input, length] =
      mapping
      |> String.split(" ", parts: 3)
      |> Enum.map(&String.to_integer/1)

    {Range.new(input, input + length - 1, 1), Range.new(output, output + length - 1, 1)}
  end
end

Part One

Solution

The benefit of using ranges here is immediately apparent, as I never have to hydrate a full one to lookup a seed’s location. Instead I just scan through input ranges and use an offset to get the correct output of a mapping. Reduce this through all the mappings, and you’re home free.

Source code available here.

defmodule AoC.Day.Five.Part.One do
  def solve({seeds, maps}) do
    seeds
    |> Enum.map(&lookup_seed_location(&1, maps))
    |> Enum.min()
  end

  def lookup_seed_location(seed, maps) do
    [
      :seed_to_soil,
      :soil_to_fertilizer,
      :fertilizer_to_water,
      :water_to_light,
      :light_to_temperature,
      :temperature_to_humidity,
      :humidity_to_location
    ]
    |> Enum.reduce(seed, &perform_mapping(&2, &1, maps))
  end

  def perform_mapping(input, type, maps) do
    {input, type, maps}

    Enum.find_value(maps[type], input, fn {
                                            input_range = input_start.._,
                                            output_start.._
                                          } ->
      if input in input_range do
        offset = input - input_start
        output_start + offset
      end
    end)
  end
end

Part Two

(Too Slow) Solution

Here we learn that our seed inputs are in fact seed ranges. Tempting to just expand those ranges into lists and push each seed through our single seed lookup from before. However, the full input uses ranges billions of seeds wide and this does not perform!

Clearly, a correct solution will need to be smarter about lookups. Here, using ranges obfuscates what we need to do—take an input start value and offset, and preserve that offset throughout our lookups to avoid ever actually having to materialize our input ranges. I’ll probably rewrite the input handler, and part 1 in terms of it, before tackling part 2 again. Perhaps even tomorrow!

Source code available here.

defmodule AoC.Day.Five.Part.Two do
  import AoC.Day.Five.Part.One

  def solve({seeds, maps}) do
    seeds
    |> seeds_to_seed_ranges()
    |> Enum.map(&Range.to_list/1) # This is Bad™ actually
    |> List.flatten()
    |> Enum.map(&lookup_seed_location(&1, maps))
    |> Enum.min()
  end

  def seeds_to_seed_ranges(seeds) do
    seeds
    |> Enum.chunk_every(2)
    |> Enum.map(&Range.new(List.first(&1), List.first(&1) + List.last(&1) - 1, 1))
  end
end
1 Like
2

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

7 Likes
3

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:

2 Likes
4

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
5

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

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

2 Likes
6

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

1 Like
7

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: Livebook - Day 5

1 Like
8

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

1 Like
9

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.

10

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.

2 Likes
11

I did the splits of the ranges by creating (potentially empty) subranges left of the intersection, the intersection itself and right of the intersection.

12

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 :sweat_smile:

2 Likes
13

Oh yeah, me too. I ran the test suite so much times because I would not believe that splitting the ranges would work with only 4 or 5 clauses. I expected to have to check for //-1 ranges or something, but no.

1 Like
14

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
3 Likes
15

I took a somewhat different approach and coded a program that generated an Elixir module with a set of guarded functions, one for each map. Further, the solution for each seed is a recursive call returning the location.

Here’s a module that solves part 1 in a super quick 80us. I’ve not provided the code that automatically generates this module … it was really messy but super fun to write.

iex(188)> Aoc.Day05.Mappers.run
Closest Location : 226172555
 .. Calculation time: 80 uS

defmodule Aoc.Day05.Mappers do
  def run do
    time = System.monotonic_time(:microsecond)

    answer =
      seeds()
      |> Enum.map(fn seed -> map_unit_num({:seed, seed}) end)
      |> Enum.sort()
      |> hd()

    time = System.monotonic_time(:microsecond) - time

    IO.puts("Closest Location : #{answer}")
    IO.puts(" .. Calculation time: #{time} uS")
  end

  def map_unit_num({:location, dist}), do: dist
  def map_unit_num(unit_num), do: map_unit_num(Aoc.Day05.Mappers.map(unit_num))

  def seeds() do
    [
      3_037_945_983,
      743_948_277,
      2_623_786_093,
      391_282_324,
      195_281_306,
      62_641_412,
      769_611_781,
      377_903_357,
      2_392_990_228,
      144_218_002,
      1_179_463_071,
      45_174_621,
      2_129_467_491,
      226_193_957,
      1_994_898_626,
      92_402_726,
      1_555_863_421,
      340_215_202,
      426_882_817,
      207_194_644
    ]
  end

  def map({:seed, num}) when num in 2_182_201_339..2_212_684_610, do: {:soil, num + 895_805_021}
  def map({:seed, num}) when num in 624_445_326..789_672_169, do: {:soil, num + 179_184_978}
  def map({:seed, num}) when num in 2_745_251_526..3_026_372_471, do: {:soil, num + -351_515_193}
  def map({:seed, num}) when num in 789_672_170..875_365_603, do: {:soil, num + -71_735_300}
  def map({:seed, num}) when num in 410_599_330..438_584_017, do: {:soil, num + 188_117_989}
  def map({:seed, num}) when num in 2_024_628_810..2_182_201_338, do: {:soil, num + 1_974_466_197}
  def map({:seed, num}) when num in 3_026_372_472..3_048_695_274, do: {:soil, num + 579_215_719}
  def map({:seed, num}) when num in 2_678_166_775..2_681_563_693, do: {:soil, num + 877_492_801}
  def map({:seed, num}) when num in 438_584_018..440_364_324, do: {:soil, num + 530_273_130}
  def map({:seed, num}) when num in 2_212_684_611..2_300_144_177, do: {:soil, num + 1_003_543_207}

  def map({:seed, num}) when num in 4_122_083_708..4_213_735_664,
    do: {:soil, num + -1_819_999_332}

  def map({:seed, num}) when num in 0..188_112_121, do: {:soil, num + 970_637_455}
  def map({:seed, num}) when num in 299_146_916..339_559_261, do: {:soil, num + 208_035_312}
  def map({:seed, num}) when num in 1_689_624_457..1_892_569_465, do: {:soil, num + -317_322_423}
  def map({:seed, num}) when num in 191_483_770..193_662_171, do: {:soil, num + 1_178_639_862}
  def map({:seed, num}) when num in 193_662_172..299_146_915, do: {:soil, num + 131_125_032}
  def map({:seed, num}) when num in 2_671_328_191..2_678_166_774, do: {:soil, num + 445_097_279}
  def map({:seed, num}) when num in 875_365_604..958_121_807, do: {:soil, num + -248_663_597}
  def map({:seed, num}) when num in 978_774_853..1_296_097_275, do: {:soil, num + 596_472_190}

  def map({:seed, num}) when num in 4_213_735_665..4_294_967_295,
    do: {:soil, num + -1_078_739_478}

  def map({:seed, num}) when num in 2_681_563_694..2_745_251_525, do: {:soil, num + -656_934_884}
  def map({:seed, num}) when num in 188_112_122..191_483_769, do: {:soil, num + 526_453_100}

  def map({:seed, num}) when num in 1_620_884_480..1_672_007_224,
    do: {:soil, num + -1_073_289_906}

  def map({:seed, num}) when num in 3_374_604_163..3_400_875_651, do: {:soil, num + 154_783_924}
  def map({:seed, num}) when num in 973_428_243..978_535_253, do: {:soil, num + -263_970_032}

  def map({:seed, num}) when num in 3_985_570_976..4_083_932_710,
    do: {:soil, num + -1_272_562_700}

  def map({:seed, num}) when num in 3_048_695_275..3_262_463_008, do: {:soil, num + -960_378_633}
  def map({:seed, num}) when num in 2_300_144_178..2_671_328_190, do: {:soil, num + 1_327_766_816}

  def map({:seed, num}) when num in 4_083_932_711..4_122_083_707,
    do: {:soil, num + -1_409_075_432}

  def map({:seed, num}) when num in 958_121_808..973_428_242, do: {:soil, num + 271_667_837}
  def map({:seed, num}) when num in 3_328_662_676..3_374_604_162, do: {:soil, num + 828_004_860}

  def map({:seed, num}) when num in 1_296_097_276..1_620_884_479,
    do: {:soil, num + -1_296_097_276}

  def map({:seed, num}) when num in 3_320_726_838..3_328_662_675, do: {:soil, num + -212_237_206}
  def map({:seed, num}) when num in 3_667_512_001..3_759_870_273, do: {:soil, num + 535_097_022}
  def map({:seed, num}) when num in 978_535_254..978_774_852, do: {:soil, num + 373_731_547}
  def map({:seed, num}) when num in 1_672_007_225..1_689_624_456, do: {:soil, num + -319_500_825}
  def map({:seed, num}) when num in 440_364_325..547_535_045, do: {:soil, num + 804_731_755}
  def map({:seed, num}) when num in 3_400_875_652..3_667_512_000, do: {:soil, num + -589_505_641}
  def map({:seed, num}) when num in 547_535_046..624_445_325, do: {:soil, num + -117_263_098}
  def map({:seed, num}) when num in 339_559_262..410_599_329, do: {:soil, num + 819_190_315}
  def map({:seed, num}) when num in 3_262_463_009..3_308_994_704, do: {:soil, num + 296_593_486}
  def map({:seed, num}) when num in 3_308_994_705..3_320_726_837, do: {:soil, num + -185_730_651}
  def map({:seed, num}) when num in 3_759_870_274..3_985_570_975, do: {:soil, num + -456_182_889}
  def map({:seed, num}), do: {:soil, num}

  def map({:soil, num}) when num in 2_957_653_952..3_297_634_843,
    do: {:fertilizer, num + -19_779_182}

  def map({:soil, num}) when num in 2_145_122_669..2_337_416_322,
    do: {:fertilizer, num + -258_652_935}

  def map({:soil, num}) when num in 822_424_488..842_203_669,
    do: {:fertilizer, num + 2_455_431_174}

  def map({:soil, num}) when num in 2_393_077_006..2_708_069_579,
    do: {:fertilizer, num + 229_805_190}

  def map({:soil, num}) when num in 3_769_116_301..4_294_967_295,
    do: {:fertilizer, num + -319_239_622}

  def map({:soil, num}) when num in 842_203_670..2_145_122_668,
    do: {:fertilizer, num + -258_652_935}

  def map({:soil, num}) when num in 345_297_835..822_424_487,
    do: {:fertilizer, num + 1_800_457_708}

  def map({:soil, num}) when num in 2_890_661_797..2_957_653_951,
    do: {:fertilizer, num + -811_898_409}

  def map({:soil, num}) when num in 2_708_069_580..2_890_661_796,
    do: {:fertilizer, num + -2_705_419_066}

  def map({:soil, num}) when num in 2_337_416_323..2_340_066_836,
    do: {:fertilizer, num + -2_337_416_323}

  def map({:soil, num}) when num in 2_340_066_837..2_393_077_005,
    do: {:fertilizer, num + -1_809_526_271}

  def map({:soil, num}) when num in 0..345_297_834, do: {:fertilizer, num + 185_242_731}

  def map({:soil, num}) when num in 3_449_876_679..3_769_116_300,
    do: {:fertilizer, num + 525_850_995}

  def map({:soil, num}), do: {:fertilizer, num}
  def map({:fertilizer, num}) when num in 5_168_332..73_380_238, do: {:water, num + 856_308_802}

  def map({:fertilizer, num}) when num in 2_229_711_837..2_258_806_277,
    do: {:water, num + -2_092_742_328}

  def map({:fertilizer, num}) when num in 1_150_509_810..1_268_877_854,
    do: {:water, num + 1_672_739_119}

  def map({:fertilizer, num}) when num in 3_073_610_919..3_127_109_356,
    do: {:water, num + 605_277_365}

  def map({:fertilizer, num}) when num in 3_682_691_325..3_778_925_916,
    do: {:water, num + 265_360_496}

  def map({:fertilizer, num}) when num in 2_387_840_795..2_892_098_588,
    do: {:water, num + -1_085_013_604}

  def map({:fertilizer, num}) when num in 1_926_818_347..2_030_902_289,
    do: {:water, num + -728_075_099}

  def map({:fertilizer, num}) when num in 1_104_177_008..1_150_509_809,
    do: {:water, num + 702_907_977}

  def map({:fertilizer, num}) when num in 619_653_304..879_458_526,
    do: {:water, num + 1_523_442_794}

  def map({:fertilizer, num}) when num in 2_385_211_148..2_387_840_794,
    do: {:water, num + -321_774_202}

  def map({:fertilizer, num}) when num in 445_026_117..480_785_565,
    do: {:water, num + 1_621_040_476}

  def map({:fertilizer, num}) when num in 537_865_723..619_653_303,
    do: {:water, num + -179_857_300}

  def map({:fertilizer, num}) when num in 0..5_168_331, do: {:water, num + 621_204_445}

  def map({:fertilizer, num}) when num in 1_861_632_296..1_926_818_346,
    do: {:water, num + 862_806_608}

  def map({:fertilizer, num}) when num in 2_258_806_278..2_385_211_147,
    do: {:water, num + -405_388_491}

  def map({:fertilizer, num}) when num in 4_141_091_197..4_155_831_937,
    do: {:water, num + -207_780_117}

  def map({:fertilizer, num}) when num in 2_892_098_589..2_901_836_444,
    do: {:water, num + -2_040_359_311}

  def map({:fertilizer, num}) when num in 3_029_323_079..3_073_610_918,
    do: {:water, num + 1_014_963_334}

  def map({:fertilizer, num}) when num in 1_778_018_007..1_861_632_295,
    do: {:water, num + 201_804_650}

  def map({:fertilizer, num}) when num in 2_084_781_230..2_087_851_740,
    do: {:water, num + 17_044_812}

  def map({:fertilizer, num}) when num in 4_268_409_625..4_294_967_295,
    do: {:water, num + -179_835_372}

  def map({:fertilizer, num}) when num in 111_346_117..323_320_166,
    do: {:water, num + 818_342_924}

  def map({:fertilizer, num}) when num in 4_155_831_938..4_268_409_624,
    do: {:water, num + -589_521_341}

  def map({:fertilizer, num}) when num in 2_030_902_290..2_084_781_229,
    do: {:water, num + -1_591_106_286}

  def map({:fertilizer, num}) when num in 1_490_707_297..1_682_651_769,
    do: {:water, num + -1_324_643_347}

  def map({:fertilizer, num}) when num in 888_219_041..1_016_428_035,
    do: {:water, num + -879_458_527}

  def map({:fertilizer, num}) when num in 3_778_925_917..3_836_129_159,
    do: {:water, num + 15_769_926}

  def map({:fertilizer, num}) when num in 3_127_109_357..3_536_155_112,
    do: {:water, num + -97_786_278}

  def map({:fertilizer, num}) when num in 77_722_143..108_335_955,
    do: {:water, num + 2_714_912_973}

  def map({:fertilizer, num}) when num in 4_013_149_435..4_141_091_196,
    do: {:water, num + -574_780_600}

  def map({:fertilizer, num}) when num in 3_620_382_204..3_682_691_324,
    do: {:water, num + 112_004_518}

  def map({:fertilizer, num}) when num in 1_682_651_770..1_778_018_006,
    do: {:water, num + 720_249_551}

  def map({:fertilizer, num}) when num in 879_458_527..888_219_040,
    do: {:water, num + -879_458_527}

  def map({:fertilizer, num}) when num in 2_901_836_445..2_941_616_973,
    do: {:water, num + -2_408_161_501}

  def map({:fertilizer, num}) when num in 3_536_155_113..3_617_567_106,
    do: {:water, num + 315_743_973}

  def map({:fertilizer, num}) when num in 1_268_877_855..1_490_707_296,
    do: {:water, num + 1_229_389_703}

  def map({:fertilizer, num}) when num in 3_836_129_160..4_013_149_434,
    do: {:water, num + 281_817_861}

  def map({:fertilizer, num}) when num in 108_335_956..111_346_116,
    do: {:water, num + 2_681_288_999}

  def map({:fertilizer, num}) when num in 480_785_566..537_865_722,
    do: {:water, num + 660_877_525}

  def map({:fertilizer, num}) when num in 406_826_572..445_026_116,
    do: {:water, num + 1_698_069_981}

  def map({:fertilizer, num}) when num in 1_016_428_036..1_104_177_007,
    do: {:water, num + -482_972_563}

  def map({:fertilizer, num}) when num in 2_087_851_741..2_229_711_836,
    do: {:water, num + -1_461_478_964}

  def map({:fertilizer, num}) when num in 73_380_239..77_722_142,
    do: {:water, num + 2_646_716_761}

  def map({:fertilizer, num}) when num in 3_617_567_107..3_620_382_203,
    do: {:water, num + 497_564_817}

  def map({:fertilizer, num}) when num in 323_320_167..406_826_571,
    do: {:water, num + 444_912_706}

  def map({:fertilizer, num}), do: {:water, num}
  def map({:water, num}) when num in 367_033_980..465_127_811, do: {:light, num + 3_479_848_485}

  def map({:water, num}) when num in 3_292_746_518..3_355_664_500,
    do: {:light, num + -1_414_180_541}

  def map({:water, num}) when num in 661_438_934..700_676_809, do: {:light, num + 3_594_290_486}

  def map({:water, num}) when num in 2_191_298_319..2_492_980_114,
    do: {:light, num + -1_721_707_810}

  def map({:water, num}) when num in 1_999_013_894..2_086_656_168,
    do: {:light, num + -1_617_065_660}

  def map({:water, num}) when num in 199_351_627..355_914_292, do: {:light, num + 3_489_144_459}

  def map({:water, num}) when num in 2_086_656_169..2_191_298_318,
    do: {:light, num + -785_837_416}

  def map({:water, num}) when num in 2_798_447_654..3_022_913_971,
    do: {:light, num + -1_991_907_742}

  def map({:water, num}) when num in 355_914_293..367_033_979, do: {:light, num + 909_422_626}

  def map({:water, num}) when num in 1_914_042_148..1_942_924_673,
    do: {:light, num + -508_581_245}

  def map({:water, num}) when num in 1_942_924_674..1_999_013_893, do: {:light, num + 634_466_396}

  def map({:water, num}) when num in 4_136_990_116..4_145_246_895,
    do: {:light, num + -456_750_810}

  def map({:water, num}) when num in 700_676_810..1_308_631_663, do: {:light, num + 1_240_807_150}
  def map({:water, num}) when num in 3_022_913_972..3_024_737_684, do: {:light, num + 822_144_780}

  def map({:water, num}) when num in 1_308_631_664..1_324_703_045,
    do: {:light, num + 2_931_026_374}

  def map({:water, num}) when num in 4_254_580_741..4_265_809_615,
    do: {:light, num + -1_688_418_546}

  def map({:water, num}) when num in 3_831_845_903..3_842_308_374,
    do: {:light, num + -2_160_053_520}

  def map({:water, num}) when num in 3_842_308_375..4_136_990_115, do: {:light, num + 102_667_922}
  def map({:water, num}) when num in 3_160_062_910..3_292_746_517, do: {:light, num + 130_599_589}

  def map({:water, num}) when num in 1_324_703_046..1_341_426_426,
    do: {:light, num + 1_224_735_768}

  def map({:water, num}) when num in 1_341_426_427..1_368_534_730,
    do: {:light, num + 2_081_919_680}

  def map({:water, num}) when num in 3_355_664_501..3_589_995_189,
    do: {:light, num + -2_324_658_271}

  def map({:water, num}) when num in 4_145_246_896..4_169_609_042,
    do: {:light, num + -2_868_790_290}

  def map({:water, num}) when num in 54_538_430..199_351_626, do: {:light, num + 3_395_915_981}
  def map({:water, num}) when num in 465_127_812..661_438_933, do: {:light, num + 1_217_127_043}

  def map({:water, num}) when num in 1_403_802_338..1_676_593_193,
    do: {:light, num + -1_349_263_908}

  def map({:water, num}) when num in 2_492_980_115..2_798_447_653, do: {:light, num + 140_500_175}

  def map({:water, num}) when num in 4_169_609_043..4_254_580_740,
    do: {:light, num + -574_341_435}

  def map({:water, num}) when num in 3_644_614_138..3_693_212_531,
    do: {:light, num + -402_550_033}

  def map({:water, num}) when num in 4_265_809_616..4_294_967_295,
    do: {:light, num + -1_188_228_416}

  def map({:water, num}) when num in 1_368_534_731..1_403_802_337,
    do: {:light, num + -597_262_426}

  def map({:water, num}) when num in 1_676_593_194..1_914_042_147,
    do: {:light, num + -242_249_765}

  def map({:water, num}) when num in 3_589_995_190..3_644_614_137,
    do: {:light, num + -3_262_665_904}

  def map({:water, num}) when num in 3_024_737_685..3_160_062_909, do: {:light, num + 82_001_195}

  def map({:water, num}) when num in 3_693_212_532..3_831_845_902,
    do: {:light, num + -754_264_703}

  def map({:water, num}), do: {:light, num}

  def map({:light, num}) when num in 2_971_073_270..3_557_284_071,
    do: {:temperature, num + -193_259_972}

  def map({:light, num}) when num in 0..334_152_506, do: {:temperature, num + 1_687_968_665}

  def map({:light, num}) when num in 3_882_460_035..4_018_320_296,
    do: {:temperature, num + 276_646_999}

  def map({:light, num}) when num in 2_095_520_416..2_288_320_627,
    do: {:temperature, num + -2_095_520_416}

  def map({:light, num}) when num in 3_557_284_072..3_560_429_441,
    do: {:temperature, num + 83_387_027}

  def map({:light, num}) when num in 3_560_429_442..3_882_460_034,
    do: {:temperature, num + -1_104_646_737}

  def map({:light, num}) when num in 1_272_848_785..1_539_048_240,
    do: {:temperature, num + 749_272_387}

  def map({:light, num}) when num in 914_869_331..1_272_848_784,
    do: {:temperature, num + -141_352_295}

  def map({:light, num}) when num in 1_539_048_241..2_095_520_415,
    do: {:temperature, num + -407_551_751}

  def map({:light, num}) when num in 4_018_320_297..4_078_989_662,
    do: {:temperature, num + -654_296_197}

  def map({:light, num}) when num in 2_455_782_705..2_971_073_269,
    do: {:temperature, num + 1_188_033_764}

  def map({:light, num}) when num in 334_152_507..914_869_330,
    do: {:temperature, num + -141_352_295}

  def map({:light, num}) when num in 4_078_989_663..4_294_967_295,
    do: {:temperature, num + -654_296_197}

  def map({:light, num}), do: {:temperature, num}

  def map({:temperature, num}) when num in 605_654_847..623_405_527,
    do: {:humidity, num + 3_466_868_465}

  def map({:temperature, num}) when num in 540_191_835..605_654_846,
    do: {:humidity, num + 634_418_183}

  def map({:temperature, num}) when num in 3_792_024_734..3_892_226_981,
    do: {:humidity, num + -1_753_568_827}

  def map({:temperature, num}) when num in 866_566_556..995_025_736,
    do: {:humidity, num + 1_672_830_227}

  def map({:temperature, num}) when num in 2_296_045_868..2_310_760_925,
    do: {:humidity, num + -2_199_703_196}

  def map({:temperature, num}) when num in 1_522_255_720..1_628_956_940,
    do: {:humidity, num + 2_305_075_024}

  def map({:temperature, num}) when num in 4_081_148_893..4_092_289_608,
    do: {:humidity, num + -264_958_865}

  def map({:temperature, num}) when num in 3_892_226_982..4_081_148_892,
    do: {:humidity, num + -2_186_125_258}

  def map({:temperature, num}) when num in 623_405_528..658_755_603,
    do: {:humidity, num + 3_157_434_424}

  def map({:temperature, num}) when num in 1_813_669_629..2_222_662_697,
    do: {:humidity, num + -1_048_052_680}

  def map({:temperature, num}) when num in 3_778_728_770..3_792_024_733,
    do: {:humidity, num + 447_040_718}

  def map({:temperature, num}) when num in 1_645_897_858..1_813_669_628,
    do: {:humidity, num + 1_106_207_687}

  def map({:temperature, num}) when num in 1_121_517_092..1_522_255_719,
    do: {:humidity, num + 1_017_141_063}

  def map({:temperature, num}) when num in 4_155_853_973..4_211_755_816,
    do: {:humidity, num + 83_211_479}

  def map({:temperature, num}) when num in 96_342_672..132_069_065,
    do: {:humidity, num + 3_837_689_293}

  def map({:temperature, num}) when num in 658_755_604..681_480_156,
    do: {:humidity, num + 2_346_517_050}

  def map({:temperature, num}) when num in 4_211_755_817..4_294_967_295,
    do: {:humidity, num + -222_443_984}

  def map({:temperature, num}) when num in 3_186_777_866..3_507_563_180,
    do: {:humidity, num + -2_906_347_414}

  def map({:temperature, num}) when num in 2_310_760_926..2_376_029_195,
    do: {:humidity, num + -2_199_703_196}

  def map({:temperature, num}) when num in 3_659_551_759..3_763_656_210,
    do: {:humidity, num + -3_483_225_759}

  def map({:temperature, num}) when num in 1_628_956_941..1_645_897_857,
    do: {:humidity, num + 266_066_694}

  def map({:temperature, num}) when num in 3_507_563_181..3_639_998_284,
    do: {:humidity, num + 585_771_203}

  def map({:temperature, num}) when num in 132_069_066..311_490_417,
    do: {:humidity, num + 2_895_928_141}

  def map({:temperature, num}) when num in 311_490_418..540_191_834,
    do: {:humidity, num + 1_165_909_889}

  def map({:temperature, num}) when num in 2_225_723_089..2_296_045_867,
    do: {:humidity, num + 709_226_786}

  def map({:temperature, num}) when num in 681_480_157..782_316_974,
    do: {:humidity, num + -80_264_390}

  def map({:temperature, num}) when num in 3_763_656_211..3_778_728_769,
    do: {:humidity, num + -843_778_895}

  def map({:temperature, num}) when num in 3_639_998_285..3_659_551_758,
    do: {:humidity, num + 329_760_074}

  def map({:temperature, num}) when num in 2_613_356_473..3_186_777_865,
    do: {:humidity, num + 594_062_086}

  def map({:temperature, num}) when num in 2_222_662_698..2_225_723_088,
    do: {:humidity, num + 1_867_611_295}

  def map({:temperature, num}) when num in 995_025_737..1_121_517_091,
    do: {:humidity, num + 916_938_815}

  def map({:temperature, num}) when num in 782_316_975..866_566_555,
    do: {:humidity, num + 1_885_538_989}

  def map({:temperature, num}) when num in 2_376_029_196..2_613_356_472,
    do: {:humidity, num + -1_135_956_166}

  def map({:temperature, num}) when num in 4_092_289_609..4_155_853_972,
    do: {:humidity, num + -3_390_237_024}

  def map({:temperature, num}), do: {:humidity, num}

  def map({:humidity, num}) when num in 2_982_177_676..3_004_463_335,
    do: {:location, num + -133_442_994}

  def map({:humidity, num}) when num in 3_717_224_958..3_741_424_830,
    do: {:location, num + -336_748_298}

  def map({:humidity, num}) when num in 734_568_132..834_656_253,
    do: {:location, num + 2_467_362_553}

  def map({:humidity, num}) when num in 4_087_339_561..4_158_513_215,
    do: {:location, num + -3_322_488_201}

  def map({:humidity, num}) when num in 2_953_711_255..2_982_177_675,
    do: {:location, num + -2_765_541_942}

  def map({:humidity, num}) when num in 2_832_231_336..2_844_786_119,
    do: {:location, num + 357_144_565}

  def map({:humidity, num}) when num in 47_909_639..58_477_196,
    do: {:location, num + 3_321_999_463}

  def map({:humidity, num}) when num in 3_741_424_831..3_841_187_208,
    do: {:location, num + -3_693_515_192}

  def map({:humidity, num}) when num in 58_477_197..65_877_216,
    do: {:location, num + 2_812_543_145}

  def map({:humidity, num}) when num in 3_409_715_295..3_556_213_169,
    do: {:location, num + -366_837_269}

  def map({:humidity, num}) when num in 2_734_551_883..2_832_231_335,
    do: {:location, num + -1_538_202_941}

  def map({:humidity, num}) when num in 3_387_790_447..3_409_715_294,
    do: {:location, num + 30_920_724}

  def map({:humidity, num}) when num in 573_552_831..639_385_980,
    do: {:location, num + 1_014_420_310}

  def map({:humidity, num}) when num in 889_063_447..964_405_692,
    do: {:location, num + 231_943_249}

  def map({:humidity, num}) when num in 567_796_360..573_552_830,
    do: {:location, num + 726_232_035}

  def map({:humidity, num}) when num in 499_906_065..567_796_359,
    do: {:location, num + 2_802_112_742}

  def map({:humidity, num}) when num in 2_921_050_411..2_953_711_254,
    do: {:location, num + -6_015_380}

  def map({:humidity, num}) when num in 3_064_299_481..3_366_281_635,
    do: {:location, num + -1_081_877_195}

  def map({:humidity, num}) when num in 4_084_864_539..4_087_339_560,
    do: {:location, num + -3_380_077_830}

  def map({:humidity, num}) when num in 834_656_254..889_063_446,
    do: {:location, num + -535_579_628}

  def map({:humidity, num}) when num in 2_182_055_199..2_389_757_488,
    do: {:location, num + 1_441_368_525}

  def map({:humidity, num}) when num in 2_881_400_789..2_921_050_410,
    do: {:location, num + -2_492_549_080}

  def map({:humidity, num}) when num in 3_592_293_988..3_632_791_283,
    do: {:location, num + -3_444_621_971}

  def map({:humidity, num}) when num in 639_385_981..734_568_131,
    do: {:location, num + 2_308_309_894}

  def map({:humidity, num}) when num in 3_556_213_170..3_592_293_987,
    do: {:location, num + -2_848_951_439}

  def map({:humidity, num}) when num in 2_389_757_489..2_528_415_407,
    do: {:location, num + -105_353_048}

  def map({:humidity, num}) when num in 2_146_687_309..2_182_055_198,
    do: {:location, num + -1_793_203_490}

  def map({:humidity, num}) when num in 441_189_704..499_509_271,
    do: {:location, num + 2_078_436_836}

  def map({:humidity, num}) when num in 3_366_281_636..3_387_790_446,
    do: {:location, num + -2_622_939_087}

  def map({:humidity, num}) when num in 2_844_786_120..2_881_400_788,
    do: {:location, num + 33_634_242}

  def map({:humidity, num}) when num in 4_212_526_404..4_294_967_295,
    do: {:location, num + -3_995_890_670}

  def map({:humidity, num}) when num in 1_235_194_267..1_417_981_971,
    do: {:location, num + 2_205_441_752}

  def map({:humidity, num}) when num in 964_405_693..1_235_194_266,
    do: {:location, num + 1_613_540_415}

  def map({:humidity, num}) when num in 3_877_915_244..3_948_350_380,
    do: {:location, num + -2_424_693_288}

  def map({:humidity, num}) when num in 1_861_705_628..2_146_687_308,
    do: {:location, num + -1_025_680_613}

  def map({:humidity, num}) when num in 499_509_272..499_906_064,
    do: {:location, num + 800_275_594}

  def map({:humidity, num}) when num in 3_948_350_381..4_070_829_900,
    do: {:location, num + -2_088_407_615}

  def map({:humidity, num}) when num in 3_004_463_336..3_064_299_480,
    do: {:location, num + -581_400_976}

  def map({:humidity, num}) when num in 4_070_829_901..4_084_864_538,
    do: {:location, num + -666_153_368}

  def map({:humidity, num}) when num in 4_158_513_216..4_212_526_403,
    do: {:location, num + -2_759_304_448}

  def map({:humidity, num}) when num in 342_162_595..441_189_703,
    do: {:location, num + 958_019_064}

  def map({:humidity, num}) when num in 3_652_908_910..3_717_224_957,
    do: {:location, num + -2_129_251_817}

  def map({:humidity, num}) when num in 1_417_981_972..1_861_705_627,
    do: {:location, num + 2_433_261_668}

  def map({:humidity, num}) when num in 3_632_791_284..3_652_908_909,
    do: {:location, num + 198_334_730}

  def map({:humidity, num}) when num in 2_528_415_408..2_734_551_882,
    do: {:location, num + -874_609_117}

  def map({:humidity, num}) when num in 65_877_217..342_162_594,
    do: {:location, num + 362_624_114}

  def map({:humidity, num}) when num in 3_841_187_209..3_877_915_243,
    do: {:location, num + -1_358_288_704}

  def map({:humidity, num}), do: {:location, num}
end
2 Likes
16

I’m getting slower :snail: Not much to add to the solutions provided above. Here’s my code that calculates the ranges in part 2 (less than 1ms on a Core i5).

  # inside def process_ranges(map_ranges, [item_range | rest]) do
  to_shift = max(source.first, item_range.first)..min(source.last, item_range.last)

  remainders =
    [
      if(item_range.first < source.first, do: item_range.first..(source.first - 1)),
      if(item_range.last > source.last, do: (source.last + 1)..item_range.last)
    ]
    |> Enum.reject(&is_nil/1)

  [Range.shift(to_shift, offset) | process_ranges(map_ranges, remainders ++ rest)]
1 Like
17

I have stolen been inspired by your code and with some personal tweaks to it it ended like that

defmodule Mapping do
  @behaviour Access

  import Kernel, except: [apply: 2]

  defstruct [:values]

  def from_list(lst) do
    %__MODULE__{values: Enum.sort(lst)}
  end

  defp apply({a.._, to}, v), do: v - a + to

  @impl Access
  def fetch(%__MODULE__{values: list}, key) when is_integer(key) do
    {:ok, sorted_find(list, key)}
  end

  def fetch(%__MODULE__{values: map}, %RangeSet{ranges: ranges}) do
    ranges
    |> Enum.flat_map(&map_range(&1, map))
    |> RangeSet.new()
    |> then(&{:ok, &1})
  end

  defp sorted_find([], n), do: n
  defp sorted_find([{a..b, _} = result | _], n) when n in a..b, do: apply(result, n)
  defp sorted_find([{a.._, _} | _], n) when n < a, do: n
  defp sorted_find([_ | rest], n), do: sorted_find(rest, n)

  defp map_range(range, []), do: [range]
  defp map_range(_..hi = range, [{lo.._, _} | _]) when lo > hi, do: [range]
  defp map_range(lo.._ = range, [{_..hi, _} | rest]) when lo > hi, do: map_range(range, rest)

  defp map_range(arg_range, [{fun_range, _} = fun_def | maps]) do
    fun_lo..fun_hi = fun_range
    arg_lo..arg_hi = arg_range
    lo = max(fun_lo, arg_lo)
    hi = min(fun_hi, arg_hi)

    [
      apply(fun_def, lo)..apply(fun_def, hi)
      | if(hi < arg_hi, do: map_range((hi + 1)..arg_hi, maps), else: [])
    ]
  end
end

[seeds | maps] =
  puzzle_input
  |> String.split("\n\n", trim: true)

mappings =
  maps
  |> Enum.map(fn map ->
    [_ | lines] = String.split(map, "\n")

    lines
    |> Enum.map(&String.split/1)
    |> Enum.map(fn line ->
      [to, from, len] = Enum.map(line, &String.to_integer/1)
      {from..(from + len - 1), to}
    end)
    |> Mapping.from_list()
  end)

seeds =
  seeds
  |> String.split()
  |> tl()
  |> Enum.map(&String.to_integer/1)

Part 1:

seeds
|> Enum.map(&Enum.reduce(mappings, &1, fn mapping, val -> mapping[val] end))
|> Enum.min()

Part 2:

seeds
|> Enum.chunk_every(2)
|> Enum.map(fn [start, length] -> start..(start + length - 1) end)
|> RangeSet.new()
|> then(&Enum.reduce(mappings, &1, fn map, r -> map[r] end))
|> RangeSet.min()
1 Like
18

At first I tried algorithm to slice and remap ranges, but I was hitting some failing edge case(s) and after writing some few hundreds lines of tests I gave up and wrote a bruteforce algorithm to do reverse search (from location to seed). It took 15secs to find the answer. Now that I have the correct answer I will be able to troubleshoot my 1st approach:)

Full solution: lib/Aoc2023/D05.ex · main · Marius K / aoc-elixir · GitLab

19

When I run your code on the example for part 2 it returns 56 rather than 46. Strangely it returns the correct answer for the real input.

20

Huh, something is not right. Indeed it returns 56 on the test input, yet the real answer is still correct. When I first arrived at the correct answer I had a solution without Task.async_stream/2, and when I incorporated it I only tested the real input. The output seemed identical so I just assumed it worked when posting here. If you switch back to Enum.map/2 and then a regular Enum.min/1 call at the end it works on the test input again just fine. I’ll look into why the discrepancy happens later.

1 Like