Caleb Weeks

Posted on

# Advent of Code #5 (in Crystal)

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))
end
map
end

@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
``````