Perl Appetizers

Posted on by

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.

147 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;
    }

  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;
    }

  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.

  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.

  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 “equal\n” 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 ? “>” : “=”)) . ” $b\n”;
    }
    }

  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.

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

  9. Pingback: perl

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

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

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

  17. I was playing around with the audio feature.

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

    It made me giggle.

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

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

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

  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 dedeary taeble

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

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

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

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

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

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>