#!/usr/bin/env ruby
#
# http://xkcd.com/c287.html
#

TARGET = 1505

MENU = [
    ["mixed fruit", 215],
    ["french fries", 275],
    ["side salad", 335],
    ["hot wings", 355],
    ["mozzarella sticks", 420],
    ["sampler plate", 580],
]

def set_price(set)
    result = 0
    for i in 0...MENU.length
        result += set[i] * MENU[i][1]
    end
    result
end

def price_to_s(val)
    sprintf("%i.%02i", val / 100, val % 100)
end

def print_set(set)
    puts "--"
    for i in 0...MENU.length
        if set[i] != 0
            puts "#{set[i]}x #{MENU[i][0]} @ #{price_to_s(MENU[i][1])}"
        end
    end
end

def find_solutions(set, vary)

    current_set = set.clone

    loop do
        price = set_price(current_set)

        if price == TARGET
            print_set(current_set)
        end

        if price >= TARGET
            break
        end

        if vary < (MENU.length-1)
            find_solutions(current_set, vary + 1)
        end

        current_set[vary] += 1
    end
end

initial_set = [0] * MENU.length

find_solutions(initial_set, 0)