# Xkcd and ugly code

**URL:** <https://www.ruby-forum.com/t/xkcd-and-ugly-code/109464>\
**Category:** Ruby\
**Created:** [July 15, 2007, 10:09am UTC](https://www.ruby-forum.com/t/xkcd-and-ugly-code/109464 "2007-07-15T10:09:15Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Sharon\_P](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/7ba0ec/32.png) [@Sharon\_P](https://www.ruby-forum.com/u/Sharon_P)\
**Post date:** [July 15, 2007, 10:09am UTC](https://www.ruby-forum.com/t/xkcd-and-ugly-code/109464/1 "2007-07-15T10:09:15Z")

</div>

Hi,

I read this xkcd strip the other day ([xkcd: NP-Complete](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

---

<div class="post-metadata">

**Author:** ![Sharon\_P](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/7ba0ec/32.png) [@Sharon\_P](https://www.ruby-forum.com/u/Sharon_P)\
**Post date:** [July 15, 2007, 10:25am UTC](https://www.ruby-forum.com/t/xkcd-and-ugly-code/109464/2 "2007-07-15T10:25:16Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Sharon\_P](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/7ba0ec/32.png) [@Sharon\_P](https://www.ruby-forum.com/u/Sharon_P)\
**Post date:** [July 15, 2007, 10:53am UTC](https://www.ruby-forum.com/t/xkcd-and-ugly-code/109464/3 "2007-07-15T10:53:18Z")

</div>

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")

---

<div class="post-metadata">

**Author:** ![Sharon\_P](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/7ba0ec/32.png) [@Sharon\_P](https://www.ruby-forum.com/u/Sharon_P)\
**Post date:** [July 15, 2007, 11:06am UTC](https://www.ruby-forum.com/t/xkcd-and-ugly-code/109464/4 "2007-07-15T11:06:19Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Sharon\_P](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/7ba0ec/32.png) [@Sharon\_P](https://www.ruby-forum.com/u/Sharon_P)\
**Post date:** [July 15, 2007, 6:47pm UTC](https://www.ruby-forum.com/t/xkcd-and-ugly-code/109464/5 "2007-07-15T18:47:00Z")

</div>

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

> I read this xkcd strip the other day ([http://www.xkcd.com/](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