# Perl Appetizers

You may have noticed that the knapsack problem in today’s comic has two solutions. I thought that (spoiler alert!) the 1, 0, 0, 2, 0, 1 solution was the only one, but 7, 0, 0, 0, 0, 0 — seven orders of mixed fruit — also works. Why did this happen? Well, I checked my numbers with a short Perl script (written while on vacation, with adorable kids climbing on me). It found the right answer in all my tests but broke when it really mattered. Witness the result of this line of Perl:

perl -e ‘print 2.15*7, “n”, 15.05, “n”, (2.15*7 == 15.05) ? “true” : “false”, “n”;’
15.05
15.05
false

Long story short, it claimed 2.15*7 did not equal 15.05, and so it missed the second answer in the search, though it found the first just fine

I know this sort of thing happens with floating-point math, but I didn’t expect it to break this badly and inconsistently on such a simple task. (edit: at that point, I was actually thinking of this as a weight problem (the variable was \$weight), not a monetary problem, so separate cents math wasn’t an obvious choice).

Thank you to Chris Shabsin and Nick Moffitt for helping me pin down the problem.

## 0 thoughts on “Perl Appetizers”

1. OK, so text within <code> tags does not have single quotes and double quotes transformed into “smart” quotes, but otherwise has the same formatting problems as code not within <code> tags.

If <pre> doesn’t work, I wonder if <tt> does?

``` #include <stdio.h> int main(int argc, char* argv[]) { printf("Hello, world!n"); return 0; } ```

Like

2. Um. I think that one goofed up. But the <tt> tags were stripped, at any rate.

One last test:

``` #include <stdio.h> /* */ int main(int argc, char* argv[]) {   printf("Hello, world!n");   return 0; } ```

Like

3. Conclusion: If there is a blank line within a <code> block, everything up to the blank line will be within a <p> block, and will have a CSS style (font and size) that is different from everything that appears afterward. Only if there are no blank lines in the code will the code appear in one <p> block, and have the same CSS style.

Like

4. I don’t think that anyone has pointed out that, had the dining party asked for exactly \$15 of appetizers, there would be just one solution: Fries, a Sampler Plate, and three Mixed Fruits.

Like

5. AFAIK, the usual way of dealing with this (other than not) is to define an acceptable amount of error (epsilon) and see if the (absolute value of) the difference is smaller than it:
perl -e ‘\$EPS = 1e-9; print “equaln” if abs(15.05 – 2.15*7) use strict;

sub cmpf {
my (\$a, \$b) = @_;
my \$EPS = 1e-9;
return 0 if abs(\$a – \$b) < \$EPS;
return (\$a – \$b) < 0 ? -1 : 1;
}

my @vals = (2.15, 2.15*7, 15.05, 19.0);
foreach my \$a (@vals) {
foreach my \$b (@vals) {
my \$c = cmpf(\$a, \$b);
print “\$a ” . (\$c < 0 ? “<” : (\$c > 0 ? “>” : “=”)) . ” \$bn”;
}
}

Like

6. I had assumed that the “seven mixed fruits” solutions was fully intentional, since there is a certain subtle humor in having an NP problem be that “easy.” (I divided \$15.05 by \$2.15 to get an upper bound on how long a brute force calculation would take, and when I saw the answer was an integer I was amused.) Also, in the factoring the time comic the final listed time was prime, which complements the joke somewhat, so I had reason to expect this sort of thing.

But no, it was floating point voodoo to blame, not a peculiar bit of hidden humor.

Like

7. Adding a little contribution in Objective Caml :
– It does not evaluate 2.15 *. 7. = 15.05, as expected because it’s based on C, but since 2.15 *. 7. returns 15.050000, I tried the string comparison and it worked ;)
– A barbarian code (first thing I made when I read the comic :P) and a more proper recursive one:

for i=0 to 7 do
for j=0 to 7 do
for k=0 to 7 do
for l=0 to 7 do
for m=0 to 7 do
for n=0 to 7 do
if (i*215+j*275+k*335+l*355+m*420+n*580)=1505 then
Printf.printf “%i, %i, %i, %i, %i, %i n” i j k l m n
done
done
done
done
done
done;;

—-

let rec invert ?(lst2=[]) lst =
match lst with
|[] -> lst2
|t::q-> invert ~lst2:(t::lst2) q
;;

let rec formlst ?(count=0) lst =
match lst with
|[]->[]
|t::q->if t=1 then formlst ~count:(count+1) q
else count::(formlst q)
;;

let rec printlst lst=
match lst with
|[]->Printf.printf “n”
|t::q->Printf.printf “%i, ” t; printlst q
;;

let rec xkcd pricelist sum order value =
match pricelist with
|[]->if sum = !value then printlst (formlst (invert order))
|t::q->match compare sum !value with
| -1 -> ()
| 0 -> xkcd q sum (0::order) value;
| 1 -> xkcd q sum (0::order) value;
xkcd pricelist sum (1::order) (ref (!value+t))
;;

xkcd [215;275;335;355;420;580] 1505 [] (ref 0);;

(I know I could have been concatenating lists instead of using invert when one result is found, but it’s a tad longer and I prefer to be efficient :P
Also, I had to format the printed list because that was easier than to have a few tests to see if I had to add one to the head of the list, or to add a new zero… Well, doesn’t matter much anyway)

By the way, as far as the running time is concerned, the recursive function ends up to be MUCH faster. Making the program run up to 100â‚¬ (that is, untill it reaches 10000 – I’ve edited the loops to run untill 46 of each, 46 being roughly 10000/215), the recursive one computes around 0.2 seconds (0.8 including the load of prints); wheras I had to stop the iterative one after around 15 seconds :P (Well, gotta admit that’s it’s looping too far when the recursive one isn’t)

Like

8. Pingback: perl

9. I did mine in qBasic, and ran into the same problem. I have run into that problem over and over again when writing code, and I never learn from it.

Like

10. use big numbers !!

\$ perl -Mbignum -e ‘print 2.15*7, “n”, 15.05, “n”, (2.15*7 == 15.05) ? “true” : “false”, “n”;’
15.05
15.05
true

Like

11. I’m not a coder but I found the 7 mixed fruit solution pretty quickly using calc.exe and trial and error. :)

Just a point of note: Looks to me like some of you were over-thinking the numbers – the dining party specified 15.05 of *appetisers*, so the Barbecue sandwich should not be included in the calculations (it’s under a different category on the menu)

Like

12. yo dead ass dis web site is really fucken ass not one black person will eva visit dis web site!!!!!!!!!!!!!!!!!!!!!!!!!!

Like

13. Pseudocode:

function knapsack(num, list):
if list == {} or num a:=knapsack(num-list[0], list)
> if a then return {list[0]} + a
> else return knapsack(num, list[1:])
> endif
endif

Easy, simple… and for all the family!

Like

14. Sorry, I meant:

function knapsack(num, list):
if list == {} or num < 0 then return false
elseif num == 0 then return {}
else
> a:=knapsack(num-list[0], list)
> if a then return {list[0]} + a
> else return knapsack(num, list[1:])
> endif
endif

Easy, simple… and for all the family! (stupid tags…)

Like

15. I was playing around with the audio feature.

And instead of saying “I am” it says “I A-M”.

It made me giggle.

Like

16. I’m not a coder but I found the 7 mixed fruit solution pretty quickly using calc.exe and trial and error. Just a point of note: Looks to me like some of you were over-thinking the numbers – the dining party specified 15.05 of *appetisers*, so the Barbecue sandwich should not be included in the calculations (it’s under a different category on the menu)

Like

17. Perl appetizers?

Like

18. Man i miss programming in turbo pascal..
Guess I’ll have to learn how to use perl, oh yes, i will do that right now!

Like

19. Hello! This article was very good. . Statement is very beautiful, I very rarely comment, today was rare to see such a good article. Published under the heart with emotion.

Like

20. Hello, I was researching the net and I ran into your blog. Keep up the great work. If you are like most people, you certainly want more energy to deal with daily work and running around.

Like

21. Thank you..

Like

22. Really a very beautiful woman and for him I do not know what I’d

Like

23. kartvizit, ekonomik kartvizit, ucuz kartvizit, kartvizit örnekleri, online kartvizit, kartvizit tasarımı

Like

24. This site is very great and indispensable to my thank you to expect continued success with the authorities there are millions of people come easy memlunkalan but I guess I did not bring the language

Like

25. te is very great and indispensable to my thank you to expect continued success with the authorities there are millions of people come easy memlunkalan dlahan metean nurse

Like

26. te is very great and indispensable to my thank you to expect continued success with the authorities there are millions of people come easy memlunkalan dedeary taeble

Like

27. te is very great and indispensable to my thank you to expect continued success with the authorities there are millions of people come easy memlunkalan derrting sepete al

Like

28. te is very great and indispensable to my thank you to expect continued success with the authorities there are millions of people come easy memlunkalan erkemi kadımı lan

Like

29. te is very great and indispensable to my thank you to expect continued success with the authorities there are millions of people come easy memlunkalan serserisin olumsn

Like

30. te is very great and indispensable to my thank you to expect continued success with the authorities there are millions of people come easy memlunkalan dodniems

Like

31. te is very great and indispensable to my thank you to expect continued success with the authorities there are millions of people come easy memlunkalan derdinang rouetr

Like

32. te is very great and indispensable to my thank you to expect continued success with the authorities there are millions of people come easy memlunkalan dasertyy poplurt

Like

33. te is very great and indispensable to my thank you to expect continued success with the authorities there are millions of people come easy memlunkalan derdinanf roueter

Like

34. Thanks for this blog very helpful, owe you a lot.

Like

35. I love comic books.

Like

36. very nice this blog thanks admin

Like

37. There are some really good points you made in your post…very insightful

Like

38. One of the first things I was taught in computer science in the early 1970’s was that monetary calculations of this type should _always_ be done using integer cents. I guess that, as floating point processing has become more robust, that lesson has gone by the wayside.

Like

39. What is that French Appetizer (snails) es’cargot?

Like

40. What is that French Appetizer (snails) es’cargot? LOL…

Like

41. The limits of my language mean the limits of my world”, wrote Ludwig Wittgenstein. With Perl 6, new doors are thrown open simply because of increased flexibility and old and new concepts applied deeper than before. They all — the concepts, not the doors — get mixed into a hearty meal: classes, roles, subroutines, enums, signatures, and the idioms that arise from these.

Like

42. Really good website this is, full of useful information and advice.

Like