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.
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.
Lots of exponential solutions here. For small problem sizes, the subset-sum problem has a pseudo-quadratic solution.
P == NP
Cuius rei demonstrationem mirabilem sane detexi. Hanc marginis exiguitas non caperet.
for(;;){$p=0;for(0..5){$p+=qw(215 275 335 355 420 580)[$_]*$v[$_];}if($p==1505){print(join(’ ‘,@v).”\n”);}if($p
for(;;){$p=0;for(0..5){$p+=qw(215 275 335 355 420 580)[$_]*$v[$_];}if($p==1505){print(join(’ ‘,@v).”\n”);}
if($p
Oh. This forum software aborts whenever it sees a ‘less than’ symbol?
test
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 ! >= …
<
<HAHA IM TYPING LESS THANS>
Use <
</HAHA IM TYPING LESS THANS>
Testing:
No, no, no, it’s pronounced like this: “I’m in ur blag, typin mah less thans!”
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;}}}}
Hooray – thanks! Perhaps the version of wordpress needs upgrading, cause that’s lame-o.
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…
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…
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.
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.
who knew the Fibonacci sequence could be so hot! :)
What about sales tax? 5% in Massachusetts.
Congratulations on getting a link from Neil Gaiman’s blog!
Your comic is fucking shit.
Please do the world a favour and stop making it.
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.
I’m supposing “Xenobiologista” is a reference to the ender series?
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.
“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.
Not to be confused with “THE fucking shit”, which, believe it or not, means something completely different.
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)
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.
That comic is again brilliant. And this discussion even funnier. 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 )
Agreed, the spam protection should require at least basic algebra. (but not BASIC, or Al-Gebra)
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;
}
I’ve just read your whole comic archive and I’ve realized that you’re my second soulmate.
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…
Nope, proxy is too impersonal for that =D
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
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.
I agree with the comments about the spam protection.
These guys: http://random.irb.hr/signup.php have a much better approach.
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 :)
Great bookstore cartoon, and by the way have you seen the parody of xkcd that the Irregular Webcomic guy did recently?
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?
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.
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.
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) ’())
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.
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 )
Nope, didn’t turn out. YOu’ll have to imagine the indenting yourself :)
Yes, I tried using a “pre” HTML tag.
I wonder if this works? Testing:
line1 (no indent)
line2 (indent with ” “)
line3 (indent with “ ”)
line4 (indent with ”   “);
line5 (indent with ”   “)
line6 (indent with “ ”)
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 , [])
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;
}