Tutorial :What's wrong with this algorithm?


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"  


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.


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.



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


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.


V thrff nyy gur cebqhpgf fubhyq or grfgrq gbtrgure :

nccrgvmrefragerrffnynqf*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 : )



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.

Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Next Post »