Discussion on: Advent of Code 2020 Solution Megathread - Day 7: Handy Haversacks

[Derk-Jan Karrenbeld]

Part 1 is a reachability problem, Part 2 is a Depth first search. But instead of building a graph, I was lazy and kept a Map of edges.

Here's Ruby:

require 'benchmark'

class BagsContent
  def initialize(name, count:)
    self.name = name
    self.count = Integer(count)
  end

  def to_s
    name
  end

  def to_i
    count
  end

  def inspect
    "#{name} (#{count})"
  end

  private

  attr_accessor :name, :count
end

class BagsBabushka
  def self.from_rules(lines)
    parsed = lines.each_with_object({}) do |line, rules|
      subject, contents = line.split(' contain ')
      subject = subject.gsub(/bags?/, '').strip

      next rules[subject] = [] if contents == 'no other bags.'

      rules[subject] = contents.split(', ').map do |bag|
        match = /^([0-9]+) (.*?) bags?\.?$/.match(bag)
        BagsContent.new(match[2], count: match[1])
      end
    end

    new(parsed)
  end

  def initialize(rules)
    self.rules = rules
  end

  def shiny(target = 'shiny gold')
    potentials = [target]
    targets = {}

    while potentials.length > 0
      matcher = potentials.shift

      self.rules.each do |container, contents|
        contents.each do |content|
          color = content.to_s

          if color == matcher
            potentials.push(container) unless targets.key?(container)
            targets[container] = true
          end
        end
      end
    end

    targets.keys
  end

  def shiny_contents(target = 'shiny gold')
    self.rules[target].inject(0) do |count, content|
      count + content.to_i + content.to_i * shiny_contents(content.to_s)
    end
  end

  private

  attr_accessor :rules
end

rules = File
  .read('input.txt')
  .split(/\n/)

Benchmark.bmbm do |b|
  b.report do
    puts BagsBabushka.from_rules(rules).shiny_contents
  end
end