At a certain point in Advent of Code, you'll inevitably have a program that is logically correct, but is inefficient enough to become impractical. That's what I ran into today.
Part 1 went relatively smoothly, and although the logic for part 2 was practically identical, the amount of data that needed to be processed increased astronomically. A calculation that took only a second or two turned into hours of processing time (on my admittedly low-powered machine).
I think there is a way to 'collapse' the various resource maps into a single map and analytically determine the answer to part 2. Or at least reduce the amount of algorithmic work. Something better than just 'try all the things'.
But in the interest of progressing in this challenge while maintaining my sanity, I'm going to leave that problem alone... If you figured out a better way to reduce the algorithmic time, please let me know!
Here's the code:
input = File.read("input").strip
class Map
@ranges : Hash(Range(Int64, Int64), Int64)
def initialize(@ranges = {} of Range(Int64, Int64) => Int64)
end
def self.from_str(str)
map = self.new
str.split("\n")[1..].map do |range|
destination, source, length = range.split(' ')
source_range = (source.to_i64..(source.to_i64 + length.to_i64 - 1))
map.add_range(source_range, destination.to_i64)
end
map
end
def add_range(range, value)
@ranges[range] = value
end
def transform(resource)
range = @ranges.find { |range, _| range.includes?(resource) }
range.nil? ? resource : (resource - range[0].begin) + range[1]
end
end
seeds, *maps = input.split("\n\n")
seeds = seeds.lchop("seeds: ").split(' ').map(&.to_i64)
resource_maps = maps.map { |str| Map.from_str(str) }
part1 = seeds.map do |seed|
resource_maps.reduce(seed) do |result, map|
map.transform(result)
end
end.min
seeds = (seeds[14]..(seeds[14] + seeds[15] - 1)).each
part2 = seeds.reduce(6472060) do |min, seed|
location = resource_maps.reduce(seed) do |result, map|
map.transform(result)
end
Math.min(min, location)
end
puts part2
Top comments (0)