README.md

example command to run

$ time ruby xkcd.rb big.txt

big.txt

100
one,1
two,2
three,3
seven,7

menu.txt

$15.05
mixed fruit,$2.15
french fries,$2.75
side salad,$3.35
hot wings,$3.55
mozzarella sticks,$4.20
sampler plate,$5.80

xkcd.rb

# frozen_string_literal: true

class Xkcd
  ITEM = Struct.new(:name, :cost)

  def initialize(filename)
    fh = File.open(filename)
    @answers = []
    @total = pennies(fh.readline)
    @items = fh.each_line.map do |line|
      item = line.split(',')
      raise 'invalid file' unless item.count == 2

      ITEM.new(item.first, pennies(item.last))
    end
    fh.close
  end

  def run
    item_pack([], items.sort_by(&:cost))
    answers.each do |answer|
      puts answer.map(&:name).join(', ')
    end
  end

  def item_pack(left, right)
    while (curr = right.pop)
      sublist = left + [curr]
      subtotal = sum(sublist)

      next if subtotal > total

      @answers << sublist if subtotal == total
      item_pack(sublist, right + [curr])

    end
  end

  attr_reader :answers

  private

  attr_reader :total, :items

  def pennies(value)
    value.gsub(/[^0-9]/, '').to_i
  end

  def sum(items)
    items.reduce(0) { |sum, i| sum + i.cost }
  end
end

Xkcd.new(ARGV.first).run