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. 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

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

    Like

  12. 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

  13. 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

  14. I was playing around with the audio feature.

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

    It made me giggle.

    Like

  15. 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

  16. 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

  17. 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

  18. 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

  19. 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

  20. 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

  21. 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

  22. 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

  23. 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

  24. 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

  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 derdinanf roueter

    Like

  26. 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

  27. 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