xkcd and ugly code

[Sharon Phillips]

Hi,

I read this xkcd strip the other day (http://www.xkcd.com/c287.html)
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 ;-) 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= a*menu[0] +
b*menu[1] +
c*menu[2] +
d*menu[3] +
e*menu[4] +
f*menu[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

 

[SonOfLilit]

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.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; "#{amount} *
$#{menu}" }.
push("------ #{total}").join("\n")

 

[gabriele renzi]

Hi,

I read this xkcd strip the other day (http://www.xkcd.com/c287.html)
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 ;-) 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.

 

[James Edward Gray II]

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 Gray II