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.
July 9th, 2007 at 12:40 pm
Should’ve done the math in cents. ;)
July 9th, 2007 at 12:42 pm
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.
July 9th, 2007 at 12:50 pm
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
July 9th, 2007 at 12:53 pm
Alternatively you could replace your comparisons as follows:
(2.15*7 == 15.05)
becomes
(15.05 - 2.15*7
July 9th, 2007 at 12:54 pm
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.
July 9th, 2007 at 12:55 pm
gah, it thought that was an html tag. lets try this again
15.05 -2.15*7 \
July 9th, 2007 at 12:56 pm
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.
July 9th, 2007 at 12:58 pm
$ 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 < to get <?
July 9th, 2007 at 1:11 pm
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*
July 9th, 2007 at 2:18 pm
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.
July 9th, 2007 at 2:19 pm
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
July 9th, 2007 at 2:25 pm
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
July 9th, 2007 at 2:28 pm
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
July 9th, 2007 at 2:34 pm
What is the difference between a tip calculator and a regular one?
July 9th, 2007 at 2:44 pm
FIXED POINT MATH 4 LIFE!
July 9th, 2007 at 3:28 pm
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" })(?!)/'July 9th, 2007 at 3:51 pm
And here’s a generic version.
#!/usr/bin/perluse 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/;
July 9th, 2007 at 3:59 pm
Bah, that’s impossible to read with the botched indentation.
I’ve reposted the code at http://use.perl.org/~Aristotle/journal/33760
July 9th, 2007 at 4:41 pm
Oaf:
Floating Point math 4.0 life!!!!
July 9th, 2007 at 5:03 pm
“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))
July 9th, 2007 at 5:04 pm
sigh. that’s abs((a-b)/(a+b)) .lt .00001
July 9th, 2007 at 5:25 pm
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.
July 9th, 2007 at 6:11 pm
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).
July 9th, 2007 at 6:48 pm
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..
July 9th, 2007 at 6:59 pm
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.
July 9th, 2007 at 7:04 pm
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++.
July 9th, 2007 at 7:24 pm
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.
July 9th, 2007 at 8:51 pm
…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.
July 9th, 2007 at 9:01 pm
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 :-)
July 9th, 2007 at 9:51 pm
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)
July 10th, 2007 at 1:18 am
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?
July 10th, 2007 at 2:45 am
This is when I realize most of the xkcd readers actually ARE math majors.
I have no in-depth math or programming background.
July 10th, 2007 at 4:20 am
James: It might be more a case of selective exposure here…
July 10th, 2007 at 5:07 am
GriffJon:
I think you mean…
Floating point math 3.99999999999999 life!
July 10th, 2007 at 12:11 pm
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.
July 10th, 2007 at 1:08 pm
Reprehensible? You mean representable, surely? :)
July 10th, 2007 at 3:08 pm
/** 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
July 10th, 2007 at 3:11 pm
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
July 10th, 2007 at 3:21 pm
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.
July 10th, 2007 at 3:59 pm
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 =
July 10th, 2007 at 4:01 pm
Aaag– my post was truncated
July 10th, 2007 at 6:12 pm
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…
July 10th, 2007 at 6:30 pm
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
July 10th, 2007 at 6:33 pm
aaargh same
pastebin link here
http://pastebin.com/m4598625a
July 10th, 2007 at 8:24 pm
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
July 10th, 2007 at 9:05 pm
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.
July 10th, 2007 at 9:27 pm
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).
July 11th, 2007 at 12:21 am
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.
July 11th, 2007 at 1:09 am
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.
July 11th, 2007 at 2:50 am
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.
July 11th, 2007 at 5:02 am
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.
July 11th, 2007 at 8:49 am
Lots of exponential solutions here. For small problem sizes, the subset-sum problem has a pseudo-quadratic solution.
July 11th, 2007 at 11:16 am
P == NP
Cuius rei demonstrationem mirabilem sane detexi. Hanc marginis exiguitas non caperet.
July 11th, 2007 at 11:18 am
for(;;){$p=0;for(0..5){$p+=qw(215 275 335 355 420 580)[$_]*$v[$_];}if($p==1505){print(join(’ ‘,@v).”\n”);}if($p
July 11th, 2007 at 11:20 am
for(;;){$p=0;for(0..5){$p+=qw(215 275 335 355 420 580)[$_]*$v[$_];}if($p==1505){print(join(’ ‘,@v).”\n”);}
if($p
July 11th, 2007 at 11:22 am
Oh. This forum software aborts whenever it sees a ‘less than’ symbol?
test
July 11th, 2007 at 11:26 am
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 ! >= …
July 11th, 2007 at 11:30 am
<
July 11th, 2007 at 11:31 am
<HAHA IM TYPING LESS THANS>
July 11th, 2007 at 11:33 am
Use <
</HAHA IM TYPING LESS THANS>
July 11th, 2007 at 11:34 am
Testing:
No, no, no, it’s pronounced like this: “I’m in ur blag, typin mah less thans!”
July 11th, 2007 at 1:13 pm
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;}}}}
July 11th, 2007 at 1:16 pm
Hooray - thanks! Perhaps the version of wordpress needs upgrading, cause that’s lame-o.
July 11th, 2007 at 4:15 pm
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…
July 11th, 2007 at 4:47 pm
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…
July 12th, 2007 at 2:23 am
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.
July 12th, 2007 at 6:27 am
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.
July 13th, 2007 at 10:01 am
who knew the Fibonacci sequence could be so hot! :)
July 13th, 2007 at 10:06 am
What about sales tax? 5% in Massachusetts.
July 13th, 2007 at 6:41 pm
Congratulations on getting a link from Neil Gaiman’s blog!
July 13th, 2007 at 10:24 pm
Your comic is fucking shit.
Please do the world a favour and stop making it.
July 14th, 2007 at 1:54 am
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.
July 14th, 2007 at 2:54 am
I’m supposing “Xenobiologista” is a reference to the ender series?
July 15th, 2007 at 2:58 pm
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.
July 16th, 2007 at 1:14 am
“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.
July 16th, 2007 at 1:21 am
Not to be confused with “THE fucking shit”, which, believe it or not, means something completely different.
July 16th, 2007 at 9:41 am
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)
July 16th, 2007 at 9:43 am
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.
July 16th, 2007 at 7:00 pm
That comic is again brilliant. And this discussion even funnier. And the spam protection should be more difficult :)
July 16th, 2007 at 11:40 pm
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 )
July 17th, 2007 at 6:57 pm
Agreed, the spam protection should require at least basic algebra. (but not BASIC, or Al-Gebra)
July 17th, 2007 at 7:55 pm
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;
}
July 17th, 2007 at 10:09 pm
I’ve just read your whole comic archive and I’ve realized that you’re my second soulmate.
July 18th, 2007 at 2:44 am
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…
July 18th, 2007 at 5:46 am
Nope, proxy is too impersonal for that =D
July 19th, 2007 at 7:04 am
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
July 19th, 2007 at 3:01 pm
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.
July 20th, 2007 at 11:42 am
I agree with the comments about the spam protection.
These guys: http://random.irb.hr/signup.php have a much better approach.
July 23rd, 2007 at 1:02 pm
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 :)
July 26th, 2007 at 12:21 am
Great bookstore cartoon, and by the way have you seen the parody of xkcd that the Irregular Webcomic guy did recently?
July 26th, 2007 at 6:10 pm
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?
July 27th, 2007 at 1:02 am
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.
August 1st, 2007 at 1:20 am
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.
August 1st, 2007 at 1:23 am
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 \
;(car items) sofar))
(xkcd cost-limit (cdr items) sofar)
))
))
(xkcd 1505 ’(215 275 335 355 420 580) ’())
August 2nd, 2007 at 4:21 pm
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.
August 2nd, 2007 at 6:21 pm
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 )
August 2nd, 2007 at 6:22 pm
Nope, didn’t turn out. YOu’ll have to imagine the indenting yourself :)
Yes, I tried using a “pre” HTML tag.
August 6th, 2007 at 9:19 pm
I wonder if this works? Testing:
line1 (no indent)
line2 (indent with ” “)
line3 (indent with “ ”)
line4 (indent with ”   “);
line5 (indent with ”   “)
line6 (indent with “ ”)
August 7th, 2007 at 1:18 am
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/</\</g;s/"/\"/g;s/ / \ /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 , [])
August 7th, 2007 at 1:47 pm
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;
}
August 7th, 2007 at 1:52 pm
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;
}
August 7th, 2007 at 1:59 pm
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;
}
August 7th, 2007 at 2:05 pm
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.
September 7th, 2007 at 9:13 am
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.
September 7th, 2007 at 9:41 pm
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”;
}
}
September 10th, 2007 at 2:39 am
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.
September 21st, 2007 at 10:05 am
lol @ floating point registers + truncation + perl
September 23rd, 2007 at 11:26 am
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)
October 1st, 2007 at 12:11 am
perl
Visit Today http://Www.fastuploadfiles.com MAx 1Gb file
October 10th, 2007 at 11:49 am
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.
October 11th, 2007 at 7:47 am
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
October 24th, 2007 at 10:16 am
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)
October 30th, 2007 at 8:18 am
yo dead ass dis web site is really fucken ass not one black person will eva visit dis web site!!!!!!!!!!!!!!!!!!!!!!!!!!
February 16th, 2008 at 12:34 pm
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!
February 16th, 2008 at 12:37 pm
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…)
April 23rd, 2008 at 6:21 pm
It is better to use ‘eq’ for that operation, not ‘==’.
November 8th, 2008 at 1:18 pm
I was playing around with the audio feature.
And instead of saying “I am” it says “I A-M”.
It made me giggle.