Forum: Ruby xkcd and ugly code

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Sharon P. (Guest)
on 2007-07-15 12:09
(Received via mailing list)
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
david karapetyan (Guest)
on 2007-07-15 12:25
(Received via mailing list)
This is basically a backtracking problem and the best way to deal with
such
problems I think is continuations.
SonOfLilit (Guest)
on 2007-07-15 12:53
(Received via mailing list)
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")
gabriele renzi (Guest)
on 2007-07-15 13:06
(Received via mailing list)
On Sun, 15 Jul 2007 17:08:43 +0900, Sharon P. wrote:

> 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 G. (Guest)
on 2007-07-15 20:47
(Received via mailing list)
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
This topic is locked and can not be replied to.