Please, my CPU, it needs help!

A classic entry for AoC, in which there is a brute-force option that will melt any CPU.

Today's puzzle was fun! But also frustrating.

The setup is you need to work out the best place to plant some seeds.

Part 1

In part 1, we have a map that looks like:

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

Where each seed maps to some soil, soil to fertilizer, fertilizer to water and so on, until you reach a location.

The location with the lowest number is the closest, and we're tasked with finding the lowest location! The mapping is super convoluted, and probably best read in full here: https://adventofcode.com/2023/day/5#part1

This was the body of my code for the first part:

seeds = input  
          .first  
          .gsub("seeds: ", "")  
          .split(" ")  
          .map(&:to_i)  

seeds_to_soil = get_map(input: input, name: "seed-to-soil map:")  
soil_to_fert = get_map(input: input, name: "soil-to-fertilizer map:")  
fert_to_water = get_map(input: input, name: "fertilizer-to-water map:")  
water_to_light = get_map(input: input, name: "water-to-light map:")  
light_to_temp = get_map(input: input, name: "light-to-temperature map:")  
temp_to_humidity = get_map(input: input, name: "temperature-to-humidity map:")  
humidity_to_location = get_map(input: input, name: "humidity-to-location map:")  

closest_seed = seeds.map do |seed|  
  sts = resolve_map(val: seed, target: seeds_to_soil)  
  stf = resolve_map(val: sts, target: soil_to_fert)  
  ftw = resolve_map(val: stf, target: fert_to_water)  
  wtl = resolve_map(val: ftw, target: water_to_light)  
  wtl = resolve_map(val: wtl, target: light_to_temp)  
  ltt = resolve_map(val: wtl, target: temp_to_humidity)  
  resolve_map(val: ltt, target: humidity_to_location)  
end.min  

closest_seed

First build a list of seed numbers, then build the map for each section, and finally resolve each map.

def get_map(input: ,name:)  
  seeds_to_soil_index = input.find_index(name)  

  maps = input[seeds_to_soil_index+1..-1].take_while {|v| v != ""}  

  maps.map do |map|  
    map.split(" ").map(&:to_i)  
  end.map do |map|  
    [[map[0], map[0]+map[2]], [map[1], map[1]+map[2]]]  
  end  
end

get_map constructs the source and destination maps for each section

def resolve_map(val:, target:)  
  match = target.detect { |t|  
    val >= t[1].first && val <= t[1].last  
  }

  match.nil? ? val : match[0].first + (val - match[1].first)  
end

resolve_map takes a value and a target map and works out if the value matches a location in that target map by working out the offset of the found item, and adding it to the location of the destination location. If no match is found, the value is passed through.

My first attempt of resolve_map used ranges, and found the index of the passed in val in the range of the destination map. For the test input, that was fine! But for the actual input, where the numbers are in the billions, it was not.

Anyway, this part worked nicely!

⭐️ Success!

Part 2

In part 2, instead of looking for the locations of a handful of seeds, we need to look for the location of hundreds of millions of seeds!

Safe to say that this solution didn't scale, and after leaving it run for 30 mins, it had barely progressed.

I have another idea, to reverse the lookup. That is, start with the lowest locations and see when we match a seed — then that'll be the result.

But that's enough computering for today, and this'll be a problem for future Dan.

🙅🏽‍♀️ No good!

Performance

Super snappy for part 1, stay tuned for part 2

Rehearsal ------------------------------------------
part 1
  0.000526   0.000009   0.000535 (  0.000533)
--------------------------------- total: 0.000535sec

             user     system      total        real
part 1
  0.000253   0.000002   0.000255 (  0.000255)