0287: "NP-Complete"

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Moderators General, Prelates, Magistrates

Iluvatar
Posts: 143
Joined: Wed Jan 24, 2007 2:19 pm UTC

0287: "NP-Complete"

http://xkcd.com/c287.html

Awesomeness. I tend to lunch with other software engineering students, so this has come up in conversation more than once. We've never tried to get the waiter to participate though...
Last edited by Iluvatar on Mon Jul 09, 2007 4:07 am UTC, edited 3 times in total.
"Don't you see?!"

"Get out of my bed, Randall, I'm trying to sleep!"

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Contact:
I would just like to say that I love the reference to Chotchkies.

Alpha Omicron
Posts: 2765
Joined: Thu May 10, 2007 1:07 pm UTC
Posted it within a second of you. I was so excited...

*CRY*
Here is a link to a page which leverages aggregation of my tweetbook social blogomedia.

crazyjimbo
Posts: 887
Joined: Fri Apr 20, 2007 11:45 pm UTC
Location: Durham, England
Contact:
Well? What's the solution?

toysbfun
Posts: 171
Joined: Fri Apr 13, 2007 5:14 am UTC
Contact:
crazyjimbo wrote:Well? What's the solution?

Seven mixed fruits is a solution.

Mouffles
Posts: 60
Joined: Fri Jul 06, 2007 10:02 am UTC
Location: New Zealand
But only three people at the table. I say a sampler plate, two hot wings, and one mixed fruit.
In the spirit of taking things too far - the 5x5x5x5x5 Rubik's Cube.

archgoon
Posts: 62
Joined: Wed Jul 26, 2006 6:08 am UTC
Location: Large (But Finite) Dimensional Hilbert Space
Question, do we need to factor in the variable tip?

Also, it's only about 8^6 possibilities. Brute force it.
Fight commutative oppression NOW!
Spoiler:
Harry is Lily's and Snape's love child. The scar is really a permanent transfiguration spell placed by Lilly, a potions expert, that ensures he looks like James. Book Seven was whack.

wocket
Posts: 87
Joined: Thu Jun 28, 2007 3:41 am UTC
Contact:
archgoon wrote:Question, do we need to factor in the variable tip?

I'd think not, since we're also not factoring in drinks (I'm assuming not everybody is ordering water) or possible main courses and/or desserts.

mwn3d
Posts: 44
Joined: Fri Jul 06, 2007 4:19 am UTC
Location: NY
Contact:
make sure you dont forget the barbecue sandwich as an option....\$6.55.

woonie
Posts: 3
Joined: Mon Jul 09, 2007 4:11 am UTC
......................
Last edited by woonie on Fri Jul 15, 2016 3:14 am UTC, edited 1 time in total.

Legrow
Posts: 15
Joined: Fri Jun 29, 2007 7:23 am UTC
mixed fruit, sampler platter, two orders of wings

wocket
Posts: 87
Joined: Thu Jun 28, 2007 3:41 am UTC
Contact:
mwn3d wrote:make sure you dont forget the barbecue sandwich as an option....\$6.55.

It's not actually an option, since it is not under the "Appetizers" heading, but rather the "Sandwiches" heading.

mwn3d
Posts: 44
Joined: Fri Jul 06, 2007 4:19 am UTC
Location: NY
Contact:
wocket wrote:
mwn3d wrote:make sure you dont forget the barbecue sandwich as an option....\$6.55.

It's not actually an option, since it is not under the "Appetizers" heading, but rather the "Sandwiches" heading.

chessguy
Posts: 2
Joined: Mon Jul 09, 2007 4:13 am UTC

mwn3d wrote:make sure you dont forget the barbecue sandwich as an option....\$6.55.

That's not an appetizer. Look at the menu: that's clearly a separate section. There are only 2 solutions:
Prelude> let g = [0..10] in [[a,b,c,d,e,f] | a <- g, b <- g, c <- g, d <- g, e <
- g, f <- g, abs(a*2.15+b*2.75+c*3.35+d*3.55+e*4.2+f*5.8-15.05)<0.001]
[[1.0,0.0,0.0,2.0,0.0,1.0],[7.0,0.0,0.0,0.0,0.0,0.0]]

That is:
1 Mixed Fruit, 2 Hot Wings, 1 sampler plate, (EDIT: already mentioned) or

Last edited by chessguy on Mon Jul 09, 2007 4:20 am UTC, edited 1 time in total.

AlphaPyro
Posts: 16
Joined: Mon May 21, 2007 4:18 am UTC
When I was in high school, my ARML team would always stop at McDonalds on the morning on the way to the competition. We were all allowed to spend up to \$5; anything over had to come out of our wallets. We were given the full menus in advance, so we always tried to figure out ways to spend every penny.

saxmaniac1987
Can't spell sex
Posts: 825
Joined: Fri Dec 29, 2006 6:58 pm UTC
I don't think I have ever seen mixed fruit under the same menu heading as mozzarella sticks.
"A witty saying proves nothing" - Voltaire

Mouffles
Posts: 60
Joined: Fri Jul 06, 2007 10:02 am UTC
Location: New Zealand
chessguy wrote:That is:
1 Mixed Fruit, 2 Hot Wings, 1 sampler plate, or

You beat me to it. I just came up with the same answer.
In the spirit of taking things too far - the 5x5x5x5x5 Rubik's Cube.

toysbfun
Posts: 171
Joined: Fri Apr 13, 2007 5:14 am UTC
Contact:

chessguy wrote:There are only 2 solutions:
Prelude> let g = [0..10] in [[a,b,c,d,e,f] | a <- g, b <- g, c <- g, d <- g, e <
- g, f <- g, abs(a*2.15+b*2.75+c*3.35+d*3.55+e*4.2+f*5.8-15.05)<0.001]
[[1.0,0.0,0.0,2.0,0.0,1.0],[7.0,0.0,0.0,0.0,0.0,0.0]]

That is:
1 Mixed Fruit, 2 Hot Wings, 1 sampler plate, (EDIT: already mentioned) or

I feel like I was cheated in my math classes..

Kawa
Posts: 714
Joined: Wed May 02, 2007 12:24 pm UTC
Location: Melbourne, FL/New York City/xkcdia
Contact:
saxmaniac1987 wrote:I don't think I have ever seen mixed fruit under the same menu heading as mozzarella sticks.

I know! But it's awesome. An Office Space reference and a math-filled comic on my nineteenth birthday! Thanks, Randall. (Not that he knows. Or cares. Er.)
Kawa likes these things:
Spanish Ninja Bodyguard
math, anime, more!
Origami, Florida
New York, and xkcd.

OneLess
Posts: 158
Joined: Wed Mar 21, 2007 5:10 am UTC
saxmaniac1987 wrote:I don't think I have ever seen mixed fruit under the same menu heading as mozzarella sticks.

I agree, it's like the anti-matter/matter of the restaurant world. You bring healthy food and mozzarella sticks onto the same table and they annihilate each other.

That, though, is the brilliance of Chotchkies. That and flair.

archgoon
Posts: 62
Joined: Wed Jul 26, 2006 6:08 am UTC
Location: Large (But Finite) Dimensional Hilbert Space
And if I had just gone straight to Mathematica and not wasted time trying to code a solution in python I could have tied with you Mouffles.

That or not have asked silly questions.
Fight commutative oppression NOW!
Spoiler:
Harry is Lily's and Snape's love child. The scar is really a permanent transfiguration spell placed by Lilly, a potions expert, that ensures he looks like James. Book Seven was whack.

Mighty Jalapeno
Inne Juste 7 Dayes I Wille Make You A Hero!
Posts: 11265
Joined: Mon May 07, 2007 9:16 pm UTC
Location: Prince George In A Can
Contact:
Is it supposed to be a gag page or what?
Last edited by Mighty Jalapeno on Mon Jul 09, 2007 4:53 am UTC, edited 1 time in total.

tyr
Posts: 4
Joined: Mon May 07, 2007 5:47 am UTC
I'll admit it, I went to Wikipedia to check out this knapsack problem.

_sandswipe_
Posts: 18
Joined: Wed Jul 04, 2007 5:45 pm UTC
Location: Kansas City Mo
Contact:
Looking at the wikipedia page for the knapsack problem, I am astounded that they don't mention how everyone who has ever played a western RPG has been thwarted by it in the guise of 'over encumbrance.' I cannot count how many times I was moving through a dungeon in oblivion two pounds under the limit, happened upon some marginally better boots, and spent half an hour trying to figure out which spell ingredients and rings were expendable.

Also, the hair of the one on the left looks exactly like choices girl. Purposeful resemblance or limit of medium?

oblivimous
Posts: 139
Joined: Tue Nov 07, 2006 6:36 pm UTC
Location: Fremont, CA
I came up with the (2x wings, sampler, fruit) solution in my head in about twenty seconds. However I started from the assumption that: mmm, wings.

blind visionary
Posts: 185
Joined: Sat Jun 02, 2007 8:23 pm UTC
Location: The Internet
Contact:
I'm so glad that when I come here, I find a bunch of other people who's first thought is to try and solve it.

Arancaytar
Posts: 1642
Joined: Thu Mar 15, 2007 12:54 am UTC
Location: 52.44°N, 13.55°E
Contact:
1 Mixed Fruit
2 Hot Wings
1 Sampler Plate

There must be others I can't figure out in my head; but I'll get coding later today and will have an algorithm implemented for any given problem this afternoon.
Last edited by Arancaytar on Mon Jul 09, 2007 5:12 am UTC, edited 1 time in total.

wocket
Posts: 87
Joined: Thu Jun 28, 2007 3:41 am UTC
Contact:
oblivimous wrote:I started from the assumption that: mmm, wings.

That's not so much an assumption as a universal law.

oblivimous
Posts: 139
Joined: Tue Nov 07, 2006 6:36 pm UTC
Location: Fremont, CA
Reading up on the travelling salesman reminded me of a something I've wondered for a while: What method do Google maps, MapQuest, etc. use to find the fastest possible route?

UserGoogol
Posts: 90
Joined: Mon Jan 29, 2007 5:58 am UTC
I just divided \$15.05 by \$2.75 just to get a rough idea of how hard it would be to brute force it, and when I got an integer I laughed hard.

Bakemaster
pretty nice future dick
Posts: 8933
Joined: Fri Jul 06, 2007 2:33 pm UTC
Location: One of those hot places
If I were serving that table during the lunch or dinner rush I'd probably just give them three sampler plates, charge them \$15.05 and call it a special. Or if I didn't like the cuts of their respective jibs, three side salads. And say the dressing was extra.

c0 = 2.13085531 × 1014 smoots per fortnight
"Apparently you can't summon an alternate timeline clone of your inner demon, guys! Remember that." —Noc

UmbrageOfSnow
Not Fully Human
Posts: 354
Joined: Sun Apr 22, 2007 7:06 am UTC
Location: Insomnia Island
Contact:
Arancaytar wrote:1 Mixed Fruit
2 Hot Wings
1 Sampler Plate

There must be others I can't figure out in my head; but I'll get coding later today and will have an algorithm implemented for any given problem this afternoon.

There is only one other, and you could have figured it out in your head with a little luck.

I solved it once in my head but read the wrong value I was trying to solve for, so just went to the computer. Sadly this computer doesn't have Mathematica or MATLAB on it yet, it is new and I don't use it for actual work, so I had to do it in C, with the help of a friend.
yellie wrote:Confession: I just had to look up the word ubiquitous because I kept seeing it all over the place and had no idea what it meant.

curious and questioning
Posts: 214
Joined: Fri Jun 08, 2007 3:27 am UTC
Location: inside the birdhouse in your soul
Contact:
Nobody's posted alt-text yet?

Alt: General solutions get you a 50% tip.

And I started trying random cobinations of things and would have eventually got it, except I refreshed the forum page first and looked at other people's answers.
[insert quote here]

__Kit
Posts: 1576
Joined: Tue May 08, 2007 5:12 am UTC
Location: 16/M/NZ
Contact:
7 'mixed fruits' is a rip-off for over \$15, their new problem will be their crapping their pants.
Last edited by __Kit on Mon Jul 09, 2007 6:24 am UTC, edited 1 time in total.
=]

jakerg22
Posts: 1
Joined: Mon Jul 09, 2007 5:35 am UTC
oblivimous wrote:Reading up on the travelling salesman reminded me of a something I've wondered for a while: What method do Google maps, MapQuest, etc. use to find the fastest possible route?

I would imagine Dykstra's Algorithm, but really I don't know. Maybe it is some kind of propritary optimized thing. I know they take speed limits into account, so I think for each node (which would be an intersection, or any place a driving instruction could be given) the path to it has a weight in time, calculated by MPH x distance. I'm not sure if it takes stoplights into account, or stop signs, or if it gives preferential treatment to interstates and highways. But, I'm going to say Dykstra's Algorithm with time (distance x mph) as the path weight.

Anyone know for sure?

Risita
Posts: 5
Joined: Mon Jul 09, 2007 5:35 am UTC
Well, technically speaking, prices don't get more precise than 1 cent (unless you're at a gas station!) so this is really just the integer knapsack problem with everything divided by 100. Polynomial time!

ptveite
Posts: 159
Joined: Tue Dec 12, 2006 3:15 pm UTC
I agree, it's like the anti-matter/matter of the restaurant world. You bring healthy food and mozzarella sticks onto the same table and they annihilate each other.

No dude, the fruit can cover for the mozz stix, they go down to the stomach together and the canteloupe will be all "it's cool, he's with me"

Mighty Jalapeno
Inne Juste 7 Dayes I Wille Make You A Hero!
Posts: 11265
Joined: Mon May 07, 2007 9:16 pm UTC
Location: Prince George In A Can
Contact:
What are any of you talking about? The page won't load, the comic won't load, at least not for me....

Karrion
Posts: 92
Joined: Fri Jun 22, 2007 12:14 am UTC
Location: Melbourne, AU
oblivimous wrote:Reading up on the travelling salesman reminded me of a something I've wondered for a while: What method do Google maps, MapQuest, etc. use to find the fastest possible route?

I imagine it's Dijkstra's algorithm or a variant of it. I've used it before for similar problems.

Edit: beaten to it :-(

Strilanc
Posts: 646
Joined: Fri Dec 08, 2006 7:18 am UTC
oblivimous wrote:Reading up on the travelling salesman reminded me of a something I've wondered for a while: What method do Google maps, MapQuest, etc. use to find the fastest possible route?

They probably use an external memory algorithm, because all of the data might not fit in memory. Interestingly, a lot of problems get a lot harder when you count I/Os instead of operations: most linear-time algorithms in the RAM model take sorting complexity in the I/O model.