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.

117 Responses to “Perl Appetizers”

  1. Ed Says:

    Should’ve done the math in cents. ;)

  2. Matthijs van der Vleuten Says:

    To work around floating point math, you could multiply the prices by 100. That way, you work with cents instead of the base currency, so integer math can be used.

  3. Vorn Says:

    Yeah. the way Real Software That Deals With Money does it is to make cents (or tenths of cents, or in rare occasions hundredths of cents) the unit, instead of dollars.

    Vorn

  4. Steve Says:

    Alternatively you could replace your comparisons as follows:
    (2.15*7 == 15.05)
    becomes
    (15.05 - 2.15*7

  5. JT Olds Says:

    You may very well know all this already, but the reason 2.15*7 != 15.05 is because 2.15*7 is being calculated, and is therefore stored with a different range of precision. It’s usually bad practice to compare floating point numbers for equality because of this, it turns out.
    According to http://docs.sun.com/source/806-3568/ncg_goldberg.html,
    q = 3.0/7.0
    if q = 3.0/7.0 then print “Equal”:
    else print “Not Equal”
    prints “Not Equal” with Borland TurboBasic. The same code *works* in Perl, but I think the basic idea is that in any language, comparing floats is fraught with peril.

    Incidentally, replacing your numeric equality comparison (==) with string equality comparison (eq) fixes the problem.

  6. Steve Says:

    gah, it thought that was an html tag. lets try this again

    15.05 -2.15*7 \

  7. Steve Says:

    Ok, by now you’ve probably guessed that’s supposed to be a less than sign… the rest is as follows

    =0.001)

    Since we’re dealing with cents, the extra will only show up for floating point errors.

  8. Chris Shabsin Says:

    $ perl -e ‘printf(”%.21f %.21f %s\n”, 15.05, 2.15*7.0, (2.15*7.0 == 15.05) ? “true” : “false”);’
    15.050000000000000710543 15.049999999999998934186 false

    Thanks for the opportunity to write my first python script. I’m really glad I happened to decide to multiply everything by 20, calculating in nickels instead of pennies. It would have been really easy to fall into the same trap.

    Steve - maybe try &lt; to get <?

  9. norm Says:

    I thought the IEEE floating point specification and library included logic to ensure these comparisons came out correctly. Does perl use some other floating point library? Or am I incorrect about IEEE?

    OK, now I have to go write a C program. *shakes fist*

  10. Alan De smet Says:

    I whipped up a script to find the answer in Perl. I almost used floating point numbers, thinking, like you, “bah, what are the chances of things going wrong.” Glad I decided at the last minute to do my math in cents. Also, I found it interesting that it’s a pretty easy problem to brute force. I appreciate that the knapsack problem is supposed to be uncomputably difficult (and thus is used for some cryptographic systems), but apparently for small enough sets of options it’s no big deal. At the absolutely worst case you have to test a mere 7^8 (5,764,801), which is trivial on a modern computer. With some simple optimizations to avoid getting the same order with the appetizers ordered in different orders, it ended up being fast enough that I got the two answers within a second on a 1.6Ghz machine with a really quick-and-dirty script.

  11. Montana Rowe Says:

    never compare floats for equality
    as others mentioned above, using cents works well
    in ml, floats belong to a class of numbers that don’t have a well-defined equality operator, so the strong typing won’t allow comparison of that variety, although greater than and less than are allowed

  12. Montana Rowe Says:

    worst case for knapsack with all positive weights
    suppose n weights, smallest weight is m units, and goal weight is g units
    the solution is a string whose alphabet is Zg/m and whose length is n
    so a brute force is O((g/m)^n), which is nonpolynomial

  13. Montana Rowe Says:

    subscript markup didn’t work
    that Zg/m thing is supposed to refer to the set corresponding to the sequence of natural numbers up to the smallest integer greater than or equal to the ratio of g to m

  14. inmylife Says:

    What is the difference between a tip calculator and a regular one?

  15. Oaf Says:

    FIXED POINT MATH 4 LIFE!

  16. Aristotle Pagaltzis Says:

    Why not do it with a backtracking engine?

    perl -e'$_="no" for $mf,$ff,$ss,$hw,$ms,$sp; ("x" x 1505) =~ /\A((x{215})(?{ local $mf = $mf + 1 }))*((x{275})(?{ local $ff = $ff + 1 }))*((x{335})(?{ local $ss = $ss + 1 }))*((x{355})(?{ local $hw = $hw + 1 }))*((x{420})(?{ local $ms = $ms + 1 }))*((x{580})(?{ local $sp = $sp + 1 }))*\z(?{ print "$mf mixed fruit, $ff french fries, $ss side salad, $hw hot wings, $ms mozarella sticks, $sp sampler plate\n" })(?!)/'

  17. Aristotle Pagaltzis Says:

    And here’s a generic version.

    #!/usr/bin/perl
    use strict;
    use warnings;
    use re 'eval';

    my %menu = (
    'mixed fruit' => 215,
    'french fries' => 275,
    'side salad' => 335,
    'hot wings' => 355,
    'mozarella sticks' => 420,
    'sampler plate' => 580,
    );

    my $total = 1505;

    ##########################################

    my %order;

    my @order_test = (
    map qq{
    (?:
    (?: x{$menu{$_}} ) # consume the given number of units

    # worked, so increase the number of orders for this thing;
    # `local` makes this temporally scoped
    (?{ local \$order{ "\Q$_\E" } = \$order{ "\Q$_\E" } + 1 })
    )*
    },
    keys %menu,
    );

    my $menu_evaluator_regex = qr{
    \A @order_test \z # find a match for these orders
    (?{
    my $order = join ', ', (
    map "$order{$_} $_",
    sort { $menu{$a} <=> $menu{$b} }
    keys %order
    );
    print "$order\n";
    })
    (?!) # fail at last possible moment
    # so engine will backtrack for more matches
    }x;

    my $total_units = "x" x $total;

    $total_units =~ m/$menu_evaluator_regex/;

  18. Aristotle Pagaltzis Says:

    Bah, that’s impossible to read with the botched indentation.

    I’ve reposted the code at http://use.perl.org/~Aristotle/journal/33760

  19. GriffJon Says:

    Oaf:

    Floating Point math 4.0 life!!!!

  20. nevinera Says:

    “Yeah. the way Real Software That Deals With Money does it is to make cents (or tenths of cents, or in rare occasions hundredths of cents) the unit, instead of dollars.”
    True. The very concept of a floating point number does not match well with money, as it’s designed with significant digits in mind, while money is always significant to an arbitrarily small quantum. I used to redefine the equals operator to test if abs((a-b)/(a+b))

  21. nevinera Says:

    sigh. that’s abs((a-b)/(a+b)) .lt .00001

  22. poorsod Says:

    Since I know almost exactly nothing about computer coding and stuff: what exactly went wrong?
    Surely multiplying with accuracy of .05 should not produce any errors - it’s COMPUTERS we’re talking about. They can do anything, can’t they?

    Also, what is floating point math(s)? Please don’t confuse me, that’s what Wikipedia is for.

  23. Adam Sjøgren Says:

    Strictly speaking the problem presented to the waiter is a subset-sum problem, not a knapsack problem.

    (A knapsack has a fixed capacity where any solution below (or equal to) the capacity is valid - for subset-sum the sum of a solution has to be exactly equal to the value given, to be valid).

  24. is Says:

    Just for fun I also reproduced a solution in Prolog with constraints enabled. As everybody has pointed out, comparing floats for equality: -5 points on the assignment. Constraining for equality reproduced your [1,0,0,2,0,1] solution quickly and failed to find [7,0,0,0,0,0]. Constraining for target +/- epsilon instead of equality fixed that..

  25. Mike Purvis Says:

    Alan: It’s been a while since I’ve done this stuff, but I think you can realise another fairly simple optimization by sorting the items smallest to largest… it’s at most seven of any one item, so you can start at the beginning of the list trying increasing numbers of the least expensive item with up to seven of each remaining one, but abort the entire branch of the tree once you pass 15.05, since you know that all the remaining items to try are more expensive than the current one.

    Also, if five orders of side salad pushes it over, there’s no need to try any more than four orders of wings. So you can keep a tally of how far each previous level got. Anyhow, yeah.

  26. Kyzentun Says:

    Just on hearsay, COBOL is widely used for real money applications because it has a native BCD (Binary Coded Decimal) type where a nybble is used to store a single decimal digit. Wouldn’t that fix the roundoff errors commonly encountered when using floating point math, since with BCD floats, you could accurately represent the base 10 numbers used for money.

    As for those who think IEEE made a requirement that floating point comparisons like this come out true when they should, I’ve tried 2.15 * 7 in elisp (yes, it’s a weird calculator, but it works) and C++ (gcc), and they both fail. In C++, the output library rounds it to 15.05, so the string comparison mentioned above would also work in C++.

  27. Aristotle Pagaltzis Says:

    poorsod: no, computers cannot do “anything.” In fact they can do almost nothing. All they can do is count from 0 to 1 and no more – just really, really fast.

    In any case, to understand why the problem arises, consider what humans mean whey they say 0.625: this means six 1/10ths, two 1/100ths, and five 1/1000ths. Similarly, a computer stores fractions, like everything else, as powers of 2: 0.625 in decimal is 0.101 in binary, and it means one 1/2th and one 1/8th.

    As you see, in binary, this fraction is much simple than in decimal (which, of course, is because I started with the binary notation…). The opposite, case, however, is more common: a simple decimal fraction like 0.5 can be very very long (or even infinite) if you try to express it in binary. (Much like 1/3 is infinite if you try to express it in decimal, and binary 0.000000000001 is very complicated in decimal (namely, it’s 0.000244140625).)

    So you write 0.5, but the computer sees a long and complicated binary fraction, and the regular precision of fractional numbers (maximum about 80 bits, mostly) may not even be enough to denote that simple decimal fraction exactly.

  28. jonored (Jonathan D.K. Gibbons) Says:

    …And there I go and don’t read the problem clear enough; in everything visible on the screen from the menu, there is one additional $15.05 order, it’s just not in the bounds of the problem…

    That said, 0.5 is perfectly simple in binary, but 0.05 is repeating in binary. .00(0011), I believe.

  29. Mridul Says:

    I wrote a quick and dirty recursive C program, found the two solutions and then thought about the fact that this is more naturally done with scripts … ah well :-)

  30. Matt Says:

    I had the same problem last night with a Python program I used to solve the program. I ended up replacing the equals operator with a simple function that sees if they are ‘close enough’:

    (code is at http://files.cibomahto.com/np.py.txt if it gets garbled during the post)

    #!/usr/bin/env python

    list = 2.15, 2.75, 3.35, 3.55, 4.20, 5.80
    goal = 15.05
    max = 8

    def floatEquals( arga, argb):
    if abs(arga - argb)

  31. Code Nazi Says:

    sense we are posting the solvers…

    I still like the one I did here, if only for it’s conciseness:

    menu(Result) :- pick(1505, [215, 275, 335, 355, 420, 580,655], Result).
    pick(Total, Prices, [X]) :-
    member(X,Prices),
    Total = X.
    pick(Total, Prices, [X|Xs]) :-
    member(X,Prices),
    N is Total - X,
    N > 0,
    pick(N,Prices,Xs).

    Was it intentional to allow the $6.55 BBQ Sandwich to match a solution?

  32. James Says:

    This is when I realize most of the xkcd readers actually ARE math majors.

    I have no in-depth math or programming background.

  33. Ace_NoOne Says:

    James: It might be more a case of selective exposure here…

  34. Hunter Says:

    GriffJon:

    I think you mean…

    Floating point math 3.99999999999999 life!

  35. Kyzentun Says:

    Hunter:
    No, because 4.0 can be precisely represented by floating point numbers, because it’s a power of two. Other numbers than powers of 2 can be precisely represented, I’m just not an FPU, so I don’t know the precise requirements for a number to be precisely reprehensible.

  36. Aristotle Pagaltzis Says:

    Reprehensible? You mean representable, surely? :)

  37. rkeene Says:

    /** By Richard Keeme.
    * This solution is a brute force solution of trying all permutations and
    * selecting the unique ones.
    */
    package np;

    import java.util.ArrayList;
    import java.util.List;

    public final class Np {

    public static final String[] names = { “Mixed Fruit”, “French Fries”,
    “Side Salad”, “Hot Wings”, “Mozzarella Sticks”, “Sampler Plate” };

    public static final int prices[] = { 215, 275, 335, 355, 420, 580 };

    public static final int TARGET = 1505;

    public static int hits = 0;

    public static int permutations = 0;

    public static List goodSolutions = new ArrayList();

    /**
    * @param args
    */
    public static void main(String[] args) {
    System.out
    .println(”Np.main() Solutions to xkcd restaurant problem. R. Keene”);
    for (int n = 1; n 0) {
    System.out.print(”, “);
    }
    System.out.print(names[idxs[i]]);
    }
    System.out.println(”]=” + money(sum));

    System.out.print(”prices [");
    for (int i = 0; i 0) {
    System.out.print(", ");
    }
    System.out.print("" + money(prices[idxs[i]]));
    }
    System.out.println(”]=” + money(sum));
    }

    private static void showSet(Permutator p, int sum) {
    int[] idxs = p.getIdxs();
    System.out.print(”Testing… prices [");
    for (int i = 0; i 0) {
    System.out.print(", ");
    }
    System.out.print("" + money(prices[idxs[i]]));
    }
    System.out.println(”]=” + money(sum));

    }

    private static String money(int m) {
    String s = “” + m;
    if (s.length() == 3) {
    return s.substring(0, 1) + “.” + s.substring(1, 3);
    }
    return s.substring(0, 2) + “.” + s.substring(2, 4);
    }
    }

    /**
    * Returns successive permutations of N numbers between 0 and maxVal.
    *
    */
    final class Permutator {

    int[] idxs;

    int maxVal;

    public Permutator(int n, int maxVal) {
    super();
    idxs = new int[n];
    this.maxVal = maxVal;
    }

    /**
    * is is the same elements maybe in different order.
    *
    * @param is
    * @return
    */
    public boolean same(int[] is) {
    if (is.length != idxs.length) {
    return false;
    }
    int[] a = is.clone();
    for (int i = 0; i

  38. rkeene Says:

    There are two solutions.

    Sampler Plate, Hot Wings, Hot Wings, Mixed Fruit

    and

    Mixed Fruit, Mixed Fruit, Mixed Fruit, Mixed Fruit, Mixed Fruit, Mixed Fruit, Mixed Fruit

  39. rkeene Says:

    Interestingly, my program runs in a blink when you test up to 7 items and all permutations. 8 items is still a blink, 10 items is 5 seconds, 11 items is 25 seconds, and so on. It is order squared. Thus restaurants will not be able to expand the appetizer menu until hardware improves.

  40. is Says:

    ok, I’ll post code too. Here’s the non-genericized version cause it’s shorter and sufficiently illustrative. Note that from/2 is just member/2 with reversed arguments– I needed that to be able to use it as a closure in the apply/2 meta-predicate. Aren’t constraints neat? A first reaction is often “where’s the work being done?”

    go :-
    P = A0*2.15 + A1*2.75 + A2*3.35 + A3*3.55 + A4*4.20 + A5*5.80,
    15.05 >= P - 0.01,
    15.05 =

  41. is Says:

    Aaag– my post was truncated

  42. ln Says:

    Just out of curiosity:
    Are there any optimised algorithms for this? I understand the problem is NP-complete, but there certainly are slower and quicker methods to get a solution…

  43. aris Says:

    my solution in java, quite more short than the above
    I prevented the floating point pitfall from the design step :) yeouw

    package be.badcode.fun.knapstack;

    public class Resolver {
    String menuitems[]={”Mixed fruit”,”French fries”,”Side Salad”,
    “Hot wings”,”Mozzarella sticks”,”Sampler plate”,”Barbecue”};
    int prices[]={215,275,335,355,420,580,655};
    int total=1505;
    static int maxlevel=7;
    void backtrack(int curlevel, int curtotal, int current[]){
    int save=current[curlevel];
    int newprice;
    newprice=curtotal;
    while(newprice

  44. aris Says:

    aaargh same

    pastebin link here
    http://pastebin.com/m4598625a

  45. Alexis Says:

    brilliant to see someone bringing the fun of science back to share with the non-scientists. very refreshing :) I’ve gotten all my friends hooked on your site.

    have a girlfriend? ;) haha

  46. helopticor Says:

    Mathematica doesn’t have any of these problems with decimals, because it knows how important decimal calculation could be. Also, I think that they guy in the comic should buy 51 barbecue sandwiches and sell 55 sampler plates at menu price.

  47. blah! Says:

    All those solutions remind me of a “Coding Horror” post :
    http://www.codinghorror.com/blog/archives/000804.html
    I mean, most of us just can’t resist solving theoretical problems and discussing them ad libitum, though we only reluctantly work on our everyday tasks. Why is that ?
    Well, don’t ask me : as soon as I saw this comic I grabbed a notepad and coded a crappy VBScript (!) solution (it took 4s to run, and 40s when not dismissing previously tested solutions in different orders, and a greedy approximation algorithm gave a 14.95$ order, not bad - I need vacation).

  48. jonored Says:

    kyzentun:
    Anything expressible as a less-than-n-digits binary number multiplied by some power of two is exactly representible as a floating-point number.
    n is a bit less than the number of bits in the number, to allow for the exponent.
    Well, assuming the exponent can be big enough for your number.

    Oddly enough, while 4.0 is uniquely representible, if you keep adding 4.0 to a variable, at some point the variable will stop increasing - because that sum is not representible, and gets rounded back down to the nearest representible number - which is what you just added to.

  49. Gareth Pye Says:

    just remember that representing exsactly 4 in a float will instantly loose you the knowledge that it is exsactly 4, all you will now know is that it is 4+/-epsilon.

  50. spes Says:

    Man, none of this makes any sense to me (Hi! Medieval Studies major (dropped out)), but man, it’s kind of hot all the same.

  51. Jonas Rabbe Says:

    What did not make sense to me was that someone would order more than one of each dish, especially when it’s obvious they’re ordering to share. I’d rather have a little bit of each.

  52. Mauro Persano Says:

    Lots of exponential solutions here. For small problem sizes, the subset-sum problem has a pseudo-quadratic solution.

  53. Fermat Says:

    P == NP

    Cuius rei demonstrationem mirabilem sane detexi. Hanc marginis exiguitas non caperet.

  54. bennet brauer Says:

    for(;;){$p=0;for(0..5){$p+=qw(215 275 335 355 420 580)[$_]*$v[$_];}if($p==1505){print(join(’ ‘,@v).”\n”);}if($p

  55. bennet brauer Says:

    for(;;){$p=0;for(0..5){$p+=qw(215 275 335 355 420 580)[$_]*$v[$_];}if($p==1505){print(join(’ ‘,@v).”\n”);}
    if($p

  56. bennet brauer Says:

    Oh. This forum software aborts whenever it sees a ‘less than’ symbol?

    test

  57. bennet brauer Says:

    for(;;){$p=0;for(0..5){$p+=qw(215 275 335 355 420 580)[$_]*$v[$_];}if($p==1505){print(join(” “,@v).”\n”);}if(!($p>=1505)){$v[0]++;}else{for(0..5){if($_==5){exit;}if($v[$_]){$v[$_]=0;$v[$_+1]++;last;}}}}

    Lamely substituted less than for a ! >= …

  58. Testing Says:

    <

  59. Testing Says:

    <HAHA IM TYPING LESS THANS>

  60. Testing Says:

    Use &lt;
    </HAHA IM TYPING LESS THANS>

  61. Blake Stacey, OM Says:

    Testing:

    No, no, no, it’s pronounced like this: “I’m in ur blag, typin mah less thans!”

  62. bennet brauer Says:

    for(;;){$p=0;for(0..5){$p+=qw(215 275 335 355 420 580)[$_]*$v[$_];}if($p==1505){print(join(” “,@v).”\n”);}if($p<1505)){$v[0]++;}else{for(0..5){if($_==5){exit;}if($v[$_]){$v[$_]=0;$v[$_+1]++;last;}}}}

  63. bennet brauer Says:

    Hooray - thanks! Perhaps the version of wordpress needs upgrading, cause that’s lame-o.

  64. Drew Says:

    The zeppelin returns! We tried the clock trick at ESG at MIT (Building 24, if you ever want to drop in on the frosh and watch them bow at your feet), but unfortunately I’ve never seen a zeppelin come by at noon…

  65. Josh Says:

    Here’s one that bit me the other day, finding the base 10 logarithm of some numbers:

    [josh@columbia] ~ [1002]$ perl -e ‘printf(”log10 of 1000: %d, log10 of 1001: %d\n”, int(log(1000)/log(10)), int(log(1001)/log(10)))’
    log10 of 1000: 2, log10 of 1001: 3
    [josh@columbia] ~ [1003]$

    Hmm, seems like log10(1000) was 3 last time I checked…

  66. justin Says:

    The problem with floating point equality is that most floating point calculations have roundoff error. Calculating the “same” number two different ways will give you two different roundoff errors, so two different answers.

    An easy fix in Perl would be to printf your results to the desired accuracy and string compare.

    When I was doing this sort of thing in Mathematica, I had it convert to symbolic form and back to machine numbers, effectively canonicalizing the machine representation of any particular number. Comparing machine floating point works just fine then.

  67. Mauro Persano Says:

    Fermat: as with many NP-complete problems, there is a polynomial solution for this problem (I wrote a bit about it here). Unfortunately, this does not prove that P=NP, since it’s polynomial in the size of the problem /and/ data, which technically makes it exponential. That’s why I originally wrote /pseudo/-quadratic.

  68. bronwyn Says:

    who knew the Fibonacci sequence could be so hot! :)

  69. Joe Says:

    What about sales tax? 5% in Massachusetts.

  70. A Different Joe Says:

    Congratulations on getting a link from Neil Gaiman’s blog!

  71. Horse Says:

    Your comic is fucking shit.
    Please do the world a favour and stop making it.

  72. Xenobiologista Says:

    Do ALL techy guys do that? Like when we’re lying in bed and my favourite engineer says something apparently random about circuits.

    Ooh…it said “69 comments” when I checked this post.

  73. James Says:

    I’m supposing “Xenobiologista” is a reference to the ender series?

  74. Kaunartist Says:

    Xenobiologista: I don’t know about all, but many. I have been doing the “only walk on some tiles” thing my whole life, and see fibonacci and other sequences in the time of day, and converting times to binary and seeing if there’s a pattern.

    As to this problem, I just did it in my head to find the simplest solution for the waiter. 7 mixed fruit came up right away so I stopped there.

  75. Merus Says:

    “Your comic is fucking shit.
    Please do the world a favour and stop making it.”

    I’m surprised this dude got through the captcha. Poor angry morons.

  76. James Says:

    Not to be confused with “THE fucking shit”, which, believe it or not, means something completely different.

  77. nopcode Says:

    Just for sake of completeness, my haskell solution:

    import List
    krec items taken limit
    | s == limit = [taken]
    | s > limit = []
    | s (krec items (x:taken) limit)) items)
    where s = (sum taken)
    main = print (nub (map sort (krec [580,420,355,335,275,215] [] 1505)))

    (Note that prices identify items so you dont need to keep names or anything)

  78. Daniel Says:

    At least that’s quite a subtle problem. Right now I can’t debug my own javascript without a web tute. The embarrassing thing is that I’m doing an engineering degree…

    On a totally unrelated note, the comic rss and blag rss should be combined.

  79. Kdansky Says:

    That comic is again brilliant. And this discussion even funnier. And the spam protection should be more difficult :)

  80. Xenobiologista Says:

    And the spam protection should be more difficult :)

    What, like making people come up with solutions to mathematics problems? (but please don’t ask me to write code it’s been years =D )

  81. Kyzentun Says:

    Agreed, the spam protection should require at least basic algebra. (but not BASIC, or Al-Gebra)

  82. Kyzentun Says:

    Equation generator in C++: (probably be more useful if it was in PHP, but I don’t know PHP)

    #include <iostream>
    #include <vector>
    #include <math.h>

    using std::cout;
    using std::endl;
    using std::vector;

    void gen_side(vector<double>& nums, vector<int>& opers)
    {
    size_t count= rand() % 5;
    for(size_t n= 0; n < count; ++n)
    {
    nums.push_back(rand() % 50);
    }
    if(count > 0) // Make sure you have two numbers before you start sticking operators in.
    {
    for(size_t n= 0; n < count-1; ++n)
    {
    opers.push_back(rand() % 5); // 0= +, 1= -, 2= *, 3= /, 4= %
    }
    }
    }

    void output_side(vector<double>& nums, vector<int>& opers)
    {
    char opchars[5]= {’+', ‘-’, ‘*’, ‘/’, ‘%’};
    if(nums.empty())
    {
    cout << “0 “;
    return;
    }
    for(size_t n= 0; n < nums.size(); ++n)
    {
    cout << ‘ ‘ << nums[n] << ‘ ‘;
    if(n < opers.size())
    {
    cout << opchars[opers[n]];
    }
    }
    }

    int main()
    {
    char opchars[5]= {’+', ‘-’, ‘*’, ‘/’, ‘%’};
    // Generate the parts of the equation. Some numbers to sum on the left, some to sum on the right, and a coefficient for x.
    vector<double> left, right;
    vector<int> left_opers, right_opers;
    int x_coefficient;
    int x_oper;
    srand(time(NULL));
    // Abstracting the sides this way brings up an interesting thought, what if equations had more than two sides?
    gen_side(left, left_opers);
    gen_side(right, right_opers);
    // Extra right_oper because x_coefficient isn’t in the list.
    x_oper= rand() % 5; // 0= +, 1= -, 2= *, 3= /, 4= %
    x_coefficient= rand() % 20;

    // Output the equation.
    output_side(left, left_opers);
    cout << “= “<< x_coefficient << “x” << ‘ ‘ << opchars[x_oper] << ‘ ‘;
    output_side(right, right_opers);
    cout << endl;

    // Solving the equation is left as an exercise for the reader. Don’t forget to handle the modulus right. :D
    return 0;
    }

  83. Aszcoy Says:

    I’ve just read your whole comic archive and I’ve realized that you’re my second soulmate.

  84. James Says:

    Is the soulmate of your soul mate also your soul mate?

    Is is a transitive process? Can you be a soul mate by proxy?

    Hmm…

  85. Aszcoy Says:

    Nope, proxy is too impersonal for that =D

  86. Jazamatronic Says:

    Just because recursion is fun, and everyone knows that’s what lisp is for:

    (setq menu (list ‘(”mixed fruit” 215)
    ‘(”french fries” 275)
    ‘(”side salad” 335)
    ‘(”hot wings” 355)
    ‘(”mozarella sticks” 420)
    ‘(”sampler plate” 580)))

    (defun peruse_menu (menu current_spend spend_limit items &optional order)
    (let (current_item current_item_name current_item_cost remaining_items this_order)
    (setq current_item (car menu))
    (setq current_item_name (car current_item))
    (setq current_item_cost (cadr current_item))
    (setq remaining_items (cdr menu))
    (dotimes (i (+ 1 items) ‘t)
    (if (eq 0 i) ‘nil (setq current_spend (+ current_spend current_item_cost)))
    (setq this_order (cons (list current_item_name i) order))
    (cond
    ((eq current_spend spend_limit) (print_order this_order))
    ((> current_spend spend_limit) (return ‘nil))
    ((< current_spend spend_limit) (if (eq ‘nil remaining_items) ‘nil (peruse_menu remaining_items current_spend spend_limit (- items i) this_order)))))))

    (defun print_order (order)
    (format t “Order:~%”)
    (dolist (item order) (if (eq (cadr item) 0) ‘nil (format ‘t ” ~S : ~S ~%” (car item) (cadr item)))))

    (time (peruse_menu menu 0 1505 7))

    Loading this file yeilds:
    [1]> (load “knapsack.lisp”)
    ;; Loading file knapsack.lisp …
    Order:
    “sampler plate” : 1
    “hot wings” : 2
    “mixed fruit” : 1
    Order:
    “mixed fruit” : 7
    Real time: 0.01689 sec.
    Run time: 0.016001 sec.
    Space: 111600 Bytes
    ;; Loaded file knapsack.lisp
    T

  87. Ed Says:

    Did my solution in XSLT because a) I wanted some practice and b) there aren’t that many four-consonant word-like things starting with X.

  88. Steve Says:

    I agree with the comments about the spam protection.
    These guys: http://random.irb.hr/signup.php have a much better approach.

  89. Brandon Says:

    Even if 4.0 can be represented in floating point perfectly, I think 3.99999999999999 better represents the pitfalls of floating point comparisons to a point that it superceeds that fact. Besides, you can just assume that the 4 was being calculated rather than directly entered :)

  90. Xenobiologista Says:

    Great bookstore cartoon, and by the way have you seen the parody of xkcd that the Irregular Webcomic guy did recently?

  91. grahamsw Says:

    With thanks to Abelson & the Scussman’s (but in Ansi CLisp)

    (defun md (target-amount kinds-of-appetizer appetizers-so-far )
    (cond ((= 0 target-amount) (print-appetizers appetizers-so-far))
    ((or(> 0 target-amount) (= 0 kinds-of-appetizer)))
    ((progn
    (md target-amount
    (- kinds-of-appetizer 1)
    appetizers-so-far)
    (md (- target-amount (next-appetizer kinds-of-appetizer))
    kinds-of-appetizer
    (append appetizers-so-far (list kinds-of-appetizer)))))))

    (defun next-appetizer (n)
    (cond ((= n 1) 215)
    ((= n 2) 275)
    ((= n 3) 335)
    ((= n 4) 355)
    ((= n 5) 420)
    ((= n 6) 580)))

    (defun print-appetizers (appetizers)
    (format t “~%~A” appetizers))

    (defun make-dishes (target)
    (md target 6 nil))

    (make-dishes 1505)

    FizzBang!

    (Hey, how come your spam filter doesn’t know hex? I am shocked! arbitrary bases I would have let you away with, but base 16?

  92. nightstrike Says:

    As a point of clarification on teh several references to money software and COBOL…… All banking software in America (don’t know about other countries, though banking across the ABA is relatively standardized) is required to maintain 6 decimal places on your account, or 4 decimal places of a penny. So for instance, if you have $100.00 in your account, you really have $100.000000. This is what makes the premise of the Office Space movie so interesting.

  93. Agnoster Says:

    Hmm… couple LISP solutions here. My favorite so far is probably nopcode’s Haskell (though it won’t compile for me), maybe since it looks a lot like my clisp/elisp solution:

    (defun xkcd (cost-limit items sofar)
    (cond ((or (< cost-limit 0) (eq nil items)) ‘())
    ((= cost-limit 0) (list sofar))
    (t (append
    (xkcd (- cost-limit (car items)) items (cons (car items) sofar))
    (xkcd cost-limit (cdr items) sofar)
    ))
    ))

    (xkcd 1505 ‘(215 275 335 355 420 580) ‘())

    Lisp always feels like a “magic eye” kind of thing - you have to sort of de-focus your eyes… and then OMG I SEE THE ANSWER… and then it’s gone again.

  94. Agnoster Says:

    Grr, trying again after an M-x replace string ” “->” ”:

    (defun xkcd (cost-limit items sofar)
      (cond ((or (< cost-limit 0) (eq nil items)) ’())
            ((= cost-limit 0) (list sofar))
            (t (append
                (xkcd (- cost-limit (car items)) items (cons&nbsp\
    ;(car items) sofar))
                (xkcd cost-limit (cdr items) sofar)
                ))
            ))

    (xkcd 1505 ’(215 275 335 355 420 580) ’())

  95. Keith Irwin Says:

    Here’s my layman’s explanation of what went wrong with the rounding:

    Now, first off, computers use base 2 instead of base ten, meaning that all numbers are represented using a combination of the digits 0 and 1 rather than 0,1,2,..,9. However, whatever number base you use, the same kind of rounding problems can occur. So, let’s first demonstrate how such an error could happen in base 10. Let’s consider 4 divided by 3 times 3. Obviously, this should equal 4, but let’s do it one step at a time and have some fixed number of decimal places available. In this case, let’s assume that we can use up to 5 digits. So we can have numbers like 1.2345 or 12.345 or so forth. So, let’s do the steps.

    First we have 4, well if we expand it out to 5 digits, this becomes 4.0000. Next we divide that by 3 (3.0000). The perfectly correct answer would be 1 point 3 repeating, i.e. 1.333333333… with the 3’s carrying on forever without end. However, we only have 5 digits, so we’re going to have to round it. In this case, clearly we should round it down, and we get 1.3333. Next, we multiply it by 3 (3.0000) again. When we multiply it by 3, we get 3.9999. Well, needless to say, 3.9999 is not 4.0000. They’re close, but not the same. What happened was that we had to round down when we divided, but we never rounded anything up. So in our calculations, 4 divided by 3 times 3 does not give us 4 (although 4 times 3 divided by 3 does).

    Some people might look at that and say that the problem is that we didn’t use enough digits. However, no matter how many digits we use, the problem will never go away. If we used 20 digits, we would start with 4.0000000000000000000 and divide it by 3 to get 1.3333333333333333333 and multiply it by 3 again to get 3.9999999999999999999, which again is not quite what we started with. No matter how many digits we use, as long as we don’t have infinitely many, we’re going to run into the same problem.

    What it comes down to is that when we chose a means of representing numbers which is finite in length, we can only represent certain numbers. For instance, if we were only allowed to use 5 digits at a time, we cannot precisely represent the value of 4/3. So what happens is that we round things off to the closest value that we can represent.

    In the case of the program that Randall wrote, it turns out that when representing numbers in base 2, 2.15 cannot be precisely represented and had to be rounded off. So when it was multiplied by 7, the result did not match 15.05.

    In the example above, he shows that when you display 7*2.15 it gives you a number close enough to 15.05 that when it prints out that number with the default settings, it even gets rounded off to 15.05 for display purposes. However, it does not actually equal 15.05.

  96. Chris Cogdon Says:

    And, here’s a version in python. I hope this turns out: there’s no “preview”:

    #! /usr/bin/env python

    def find_all_exacts ( prices, target ):
    len_prices = len(prices)
    results = []

    # General algorithm. Keep adding a price until it busts. Do it in
    # Such a way that we can iterate over every possible combination,
    # by adding on on new prices until we ‘bust’, then removing that item
    # and adding a different item, if that doesn’t bust any more, then
    # keep it and add another item.
    # To avoid repeats, when adding, add the same or later index.

    # ’stack’ represents a list of indexes into our prices list, and is
    # The current possible solution we’re looking at. Prime it
    # with the first possible solution.
    stack = [0]
    while 1:
    # Add up the prices for all the indexes in the stack
    total = 0
    for i in stack:
    total += prices[i]

    if total < target:
    # If we’re still under the total, then add on another index and go
    # around again. Adding on an index that is the same as the top of
    # the stack means we avoid duplicate answers.
    stack.append(stack[-1])
    else:
    # We’re exact, or spot on.
    if total == target:
    # If we’re spot on, record the result
    results.append ( [prices[i] for i in stack] )
    # Now, increment the index on the top of the stack. If that’s the last index,
    # then remove that value, and try the next-to-top, and so on. If we run out,
    # that’s the end of the search, and return what we found.
    while 1:
    if stack[-1] == len_prices-1:
    del stack[-1]
    if not stack:
    return results
    else:
    stack[-1] += 1
    break

    if __name__ == “__main__”:
    print find_all_exacts ( [ 580, 420, 355, 335, 275, 215 ], 1505 )

  97. Chris Cogdon Says:

    Nope, didn’t turn out. YOu’ll have to imagine the indenting yourself :)

    Yes, I tried using a “pre” HTML tag.

  98. Owlmirror Says:

    I wonder if this works? Testing:

    line1 (no indent)
    line2 (indent with ” “)
     line3 (indent with “&nbsp;”)
      line4 (indent with ” &nbsp “);
      line5 (indent with ” &emsp; “)
        line6 (indent with “&nbsp; &nbsp;”)

  99. Owlmirror Says:

    I wonder if this will work, given the above. Well, only one way to find out…

    This is Matt’s Python script from above, slightly modified (using cents and integer math), and transformed with :
    sed ’s/</\&lt;/g;s/"/\&quot;/g;s/  / \&nbsp;/g’

    _________________________________________________________________

    #!/usr/bin/env python

    list = 215, 275, 335, 355, 420, 580
    goal = 1505
    max = 8

    def recursiveCheck( count, set, prevtotal, prevset ):
     for i in range(count):
       currTotal = prevtotal + i*set[0]
       if( currTotal <= goal ):
         if len(set) == 1:
           if ( currTotal == goal ):
             print "=======", currTotal, ":========", prevset + [i]
         else:
           recursiveCheck( count, set[1:], currTotal, prevset + [i] )

    print "Goal = ", goal, ", out of ", list, "\n"
    recursiveCheck( max, list, 0 , [])

  100. Owlmirror Says:

    Testing some more…

    This:
    _________________________________
    /* ‘Hello, World!’ */
    #include <stdio.h>

    int main(int argc, char* argv[])
    {
    printf(”Hello, world!\n”);
    return 0;
    }

    _________________________________
    versus this:
    _________________________________

    /* 'Hello, World!' */
    /* */
    #include <stdio.h>

    int main(int argc, char* argv[])
    {
    printf(”Hello, world!\n”);
    return 0;
    }

  101. Owlmirror Says:

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

  102. Owlmirror Says:

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

  103. Owlmirror Says:

    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.

  104. David Turner Says:

    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.

  105. Nikolas Coukouma Says:

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

  106. UserGoogol Says:

    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.

  107. segfault Says:

    lol @ floating point registers + truncation + perl

  108. Asmadeus Says:

    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)

  109. perl Says:

    perl

    Visit Today http://Www.fastuploadfiles.com MAx 1Gb file

  110. roninkakuhito Says:

    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.

  111. Rafael Garcia-Suarez Says:

    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

  112. TechHeadFred Says:

    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)

  113. jasmine Says:

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

  114. cousteau Says:

    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!

  115. cousteau Says:

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

  116. Pavel Says:

    It is better to use ‘eq’ for that operation, not ‘==’.

  117. video Says:

    I was playing around with the audio feature.

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

    It made me giggle.

Leave a Reply