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.
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;
}
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;
}
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.
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.
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”;
}
}
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.
lol @ floating point registers + truncation + perl
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)
perl
Visit Today http://Www.fastuploadfiles.com MAx 1Gb file
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.
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
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)
yo dead ass dis web site is really fucken ass not one black person will eva visit dis web site!!!!!!!!!!!!!!!!!!!!!!!!!!
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!
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…)
It is better to use ‘eq’ for that operation, not ‘==’.
I was playing around with the audio feature.
And instead of saying “I am” it says “I A-M”.
It made me giggle.
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)
Perl appetizers?