Xkcd and ugly code

Ruby
1

Hi,

I read this xkcd strip the other day (xkcd: NP-Complete)
and, of course, had to solve it. So I whipped up a quick bit of Ruby
code that gave me the answers. Took about 5 minutes and then I was
happy. Except I wasn’t, because I looked at what I’d written. Ugly
and not dry at all, sopping wet even; basically six nested loops.
I’ll try to reproduce it below.

Trouble is, I then spend the best part of an afternoon (don’t tell my
boss :wink: trying to solve it elegantly, but couldn’t. I did come up
with other ways that worked, but they were pretty cumbersome and slow.

There has to be a ‘ruby way’ to do this. Any suggestions?

Cheers,
Dave

here’s a rough approximation of the code I wrote:

menu= [2.15, 2.75, 3.35, 3.55, 4.20, 5.80]
target= 15.05
0.upto(target/menu[0].to_i) do |a|
0.upto(target/menu[1].to_i) do |b|
0.upto(target/menu[2].to_i) do |c|
0.upto(target/menu[3].to_i) do |d|
0.upto(target/menu[4].to_i) do |e|
0.upto(target/menu[5].to_i) do |f|
if ((total= amenu[0] +
bmenu[1] +
cmenu[2] +
dmenu[3] +
emenu[4] +
fmenu[5]) - target).abs<0.01 then
puts “\n#{a} * $#{menu[0]}”
puts “#{b} * $#{menu[1]}”
puts “#{c} * $#{menu[2]}”
puts “#{d} * $#{menu[3]}”
puts “#{e} * $#{menu[4]}”
puts “#{f} * $#{menu[5]}”
puts “---------------\n $#{total}”
end
end
end
end
end
end
end

2

This is basically a backtracking problem and the best way to deal with
such
problems I think is continuations.

3

Here’s a bit of DRYing up of your code, which isn’t a good idea - as
David mentioned, there are better ways to do this. Note: untested.

menu= [2.15, 2.75, 3.35, 3.55, 4.20, 5.80]
target= 15.05

def r(state, menu, target) # state is an array of indexes. returns nil
unless a solution was found
i = state.length
if i < menu.length
0.upto(target/menu[i].to_i) do |a|
state.shift(a)
retval = r(state, menu, target)
state.unshift
return retval if retval
end
else
total = (0…i-1).inject{0) {|index, m| m += state[index]*menu[i - index]
if (total - target).abs<0.01 then
return state
end
return nil
end
end

total = 0.0

this line is twisted, but I really enjoyed writing it. so it stays.

this isn’t production code anyway. and you’ll have to implement
collect_with_index, I think.

print r([], menu, target).
collect_with_index{|amount, i| total += amount*menu[i]; “#{amount} *
$#{menu[i]}” }.
push("------ #{total}").join("\n")

4

On Sun, 15 Jul 2007 17:08:43 +0900, Sharon P. wrote:

boss :wink: trying to solve it elegantly, but couldn’t. I did come up
with other ways that worked, but they were pretty cumbersome and slow.

There has to be a ‘ruby way’ to do this. Any suggestions?

not sure about the ruby way, but isn’t it a case of the knapsack
problem?
If so, the greedy and the dynamic programming algorithms for it are
quite elegant.

5

On Jul 15, 2007, at 3:08 AM, Sharon P. wrote:

I read this xkcd strip the other day (http://www.xkcd.com/
c287.html) and, of course, had to solve it.

Fun problem. Thanks for sharing.

There has to be a ‘ruby way’ to do this. Any suggestions?

Here’s what I solved it with:

#!/usr/bin/env ruby -wKU

APPETIZERS = { “Mixed Fruit” => 215,
“French Fries” => 275,
“Side Salad” => 335,
“Hot Wings” => 355,
“Mozzarella Sticks” => 420,
“Sampler Plate” => 580 }
TOTAL_PRICE = 1505
MAX_COUNT = TOTAL_PRICE / APPETIZERS.values.min

orders = Hash.new { |all, total| all[total] = Array.new }
orders[0] << Array.new
APPETIZERS.each do |name, price|
orders.to_a.each do |total, items|
1.upto(MAX_COUNT) do |count|
cost = total + price * count
break if cost > TOTAL_PRICE
orders[cost] += items.map { |order| order + [name] * count }
end
end
end

puts “Orders costing $15.05:”
orders[1505].each do |order|
puts( order.uniq.sort.map do |item|
" #{item} * #{order.select { |i| i == item }.size}"
end )
puts
end

END

James Edward G. II