DEV Community

Caleb Weeks
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))
      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
Enter fullscreen mode Exit fullscreen mode

Top comments (0)