What's wrong with this algorithm?

Question

This is an abstracted form of the bug that led me into the code that formed the basis of my prior question. It's obvious once you see it, but several professional programmers familiar with the original problem and original language looked over the code and overlooked the bug before we caught it (admittedly, in its native environment it was closer to three pages long).

Please obfuscate your responses so latecomers can have some fun too.

most_bang_for_buck_score = 0.0
most_bang_for_buck_order = []
for appetizer in appetizers
    total_cost     = appetizer.cost
    total_calories = appetizer.calories
    for salad in salads
        total_cost     = total_cost     + salad.cost
        total_calories = total_calories + salad.calories
        for entree in entrees
            total_cost     = total_cost     + entree.cost
            total_calories = total_calories + entree.calories
            for desert in deserts
                total_cost     = total_cost      + desert.cost
                total_calories = total_calories + desert.calories
                if total_calories/total_cost > most_bang_for_buck_score
                    most_bang_for_buck_score = total_calories/total_cost
                    most_bang_for_buck_order = [appetizer,salad,entree,desert]
 print "You'll get the most food energy for your money ordering ",most_bang_for_buck_order,"\n"

Answer 1

ROT13 (or hover on this link to see the non-obfuscated answer as a tooltip)

V qba'g guvax lbh'er erfrggvat gbgny_pbfg/gbgny_pnybevrf ba rnpu cnff. Lbh bhtug gb whfg or fhzzvat rirelguvat hc bapr va gur vaarezbfg ybbc.

Ol gur jnl lbh fnir gur beqre nf bar bs rnpu vgrz, V'z nffhzvat lbh'er bayl fhccbfrq gb or univat bar bs rnpu sbbq pngrtbel.

Answer 2

Sbe rnpu vgrz (nccrgvmre, fnynq, ragerr, qrffreg) lbh'er nqqvat gur pbfg bs gur arj vgrz, ohg lbh'er abg fhogenpgvat bhg gur pbfg bs gur cerivbhf vgrz sebz gur fnzr pngrtbel. Guvf jvyy pnhfr lbh gb fhz gur gbgny pbfg bs nyy vgrzf va nyy pngrtbevrf, vafgrnq bs nyy pbzovangvbaf.

ROT13

Answer 3

V thrff nyy gur cebqhpgf fubhyq or grfgrq gbtrgure :

nccrgvmref*ragerrf*fnynqf*qrfregf = gbgny pbzcnevfbaf

jurernf urer vg frrzf yvxr gurer'f nyjnlf gur fnzr cebqhpg bs gur svefg vgrzf pbzcnerq gb rnpu bs gur qrfregf (v.r. 7 pbzcnevfbaf sbe 7 qrfregf). vfa'g vg ?

...znlor V whfg qba'g trg gur nofgenpgvba : )

ogj, guvf ebg13 fvgr vf terng : )

http://www.rot13.com/index.php

Answer 4

Vf vg ernyyl guvf rnfl? Lbh'er abg erfrggvat gbgny_pbfg be gbgny_pnybevrf va rnpu ybbc vgrengvba.

V pna frr ubj gur oht jbhyq or uneq gb fcbg ol ybbxvat ng gur bhgchg, gubhtu. Gur engvb bs gur gjb inyhrf zvtug abg punatr zhpu rira nf gurve inyhrf terj ovttre.

ROT13, hover to see non-obfuscated as tooltip

Answer 5

Not sure how one would calculate the number of calories in a desert, but I imagine it would be vanishingly small compared to its cost, particularly in today's economy, assuming an entire desert were for sale.

Assuming total_calories and total_cost are some sort of integer data types, each most_bang_for_buck_score will be zero.

I'm guessing the algorithm always prints the first element from each course.

Answer 6

So, the answer is clear from the other posts. I'm just going to use this space to do this in a functional language (Haskell), where this kind of bug doesn't happen.

Just getting the maximum score is easy, assuming lists of (cost, calorie) tuples:

let bang (cost, cal) = cal / cost
 in maximum [bang c1 + bang c2 + bang c3 + bang c4 | 
                                 c1 <- appetizers,
                                 c2 <- salads,
                                 c3 <- entrees,
                                 c4 <- deserts]

If you represent your data as tuples of (name, (cost, calorie)), then it's more annoying. The best way would be to define a maximum function that uses a "key" parameter, like in Python (there might be one already, but I don't know about it). Then, you would just do this:

maximumkey snd [([n1, n2, n3, n4], bang c1 + bang c2 + bang c3 + bang c4) | 
                      (n1, c1) <- appetizers,
                      (n2, c2) <- salads,
                      (n3, c3) <- entrees
                      (n4, c4) <- deserts]

---

To complete the solution. This is how (roughly) how maximum is defined:

maximum xs = foldl1 max xs

So maximumkey is:

maximumkey f xs = foldl1 (\(a,b) -> if (f a) > (f b) then a else b) xs

Note: This is a bit inefficient, since it calls 'f' more than once per element.