0287: "NP-Complete"

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

Moderators: Moderators General, Prelates, Magistrates

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

0287: "NP-Complete"

Postby Iluvatar » Mon Jul 09, 2007 4:01 am UTC

Image
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!"

Your results may vary.

EvanED
Posts: 4330
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Postby EvanED » Mon Jul 09, 2007 4:03 am UTC

I would just like to say that I love the reference to Chotchkies.

User avatar
Alpha Omicron
Posts: 2765
Joined: Thu May 10, 2007 1:07 pm UTC

Postby Alpha Omicron » Mon Jul 09, 2007 4:05 am 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.

User avatar
crazyjimbo
Posts: 887
Joined: Fri Apr 20, 2007 11:45 pm UTC
Location: Durham, England
Contact:

Postby crazyjimbo » Mon Jul 09, 2007 4:06 am UTC

Well? What's the solution?

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

Postby toysbfun » Mon Jul 09, 2007 4:07 am UTC

crazyjimbo wrote:Well? What's the solution?

Seven mixed fruits is a solution.

User avatar
Mouffles
Posts: 60
Joined: Fri Jul 06, 2007 10:02 am UTC
Location: New Zealand

Postby Mouffles » Mon Jul 09, 2007 4:09 am UTC

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.

User avatar
archgoon
Posts: 62
Joined: Wed Jul 26, 2006 6:08 am UTC
Location: Large (But Finite) Dimensional Hilbert Space

Postby archgoon » Mon Jul 09, 2007 4:10 am UTC

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:

Postby wocket » Mon Jul 09, 2007 4:12 am UTC

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.

User avatar
mwn3d
Posts: 44
Joined: Fri Jul 06, 2007 4:19 am UTC
Location: NY
Contact:

Postby mwn3d » Mon Jul 09, 2007 4:13 am UTC

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

Postby woonie » Mon Jul 09, 2007 4:13 am UTC

......................
Last edited by woonie on Fri Jul 15, 2016 3:14 am UTC, edited 1 time in total.

User avatar
Legrow
Posts: 15
Joined: Fri Jun 29, 2007 7:23 am UTC

Postby Legrow » Mon Jul 09, 2007 4:13 am UTC

mixed fruit, sampler platter, two orders of wings

wocket
Posts: 87
Joined: Thu Jun 28, 2007 3:41 am UTC
Contact:

Postby wocket » Mon Jul 09, 2007 4:14 am UTC

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.

User avatar
mwn3d
Posts: 44
Joined: Fri Jul 06, 2007 4:19 am UTC
Location: NY
Contact:

Postby mwn3d » Mon Jul 09, 2007 4:16 am UTC

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.


touché

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

The Haskell answer

Postby chessguy » Mon Jul 09, 2007 4:19 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
7 Mixed Fruit (already mentioned)

I had to register to give this answer :)
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

Postby AlphaPyro » Mon Jul 09, 2007 4:19 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.

User avatar
saxmaniac1987
Can't spell sex
Posts: 825
Joined: Fri Dec 29, 2006 6:58 pm UTC
Location: Killadelphia Burbs
Contact:

Postby saxmaniac1987 » Mon Jul 09, 2007 4:20 am 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

User avatar
Mouffles
Posts: 60
Joined: Fri Jul 06, 2007 10:02 am UTC
Location: New Zealand

Postby Mouffles » Mon Jul 09, 2007 4:21 am UTC

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

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:

Re: The Haskell answer

Postby toysbfun » Mon Jul 09, 2007 4:24 am UTC

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
7 Mixed Fruit (already mentioned)


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

User avatar
Kawa
Posts: 714
Joined: Wed May 02, 2007 12:24 pm UTC
Location: Melbourne, FL/New York City/xkcdia
Contact:

Postby Kawa » Mon Jul 09, 2007 4:25 am UTC

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. :D (Not that he knows. Or cares. Er.)
Kawa likes these things:
Spanish Ninja Bodyguard
math, anime, more!
Origami, Florida
New York, and xkcd.

User avatar
OneLess
Posts: 158
Joined: Wed Mar 21, 2007 5:10 am UTC

Postby OneLess » Mon Jul 09, 2007 4:31 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.

User avatar
archgoon
Posts: 62
Joined: Wed Jul 26, 2006 6:08 am UTC
Location: Large (But Finite) Dimensional Hilbert Space

Postby archgoon » Mon Jul 09, 2007 4:32 am UTC

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.

User avatar
Mighty Jalapeno
Inne Juste 7 Dayes I Wille Make You A Hero!
Posts: 11262
Joined: Mon May 07, 2007 9:16 pm UTC
Location: Prince George In A Can
Contact:

Postby Mighty Jalapeno » Mon Jul 09, 2007 4:34 am UTC

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

Postby tyr » Mon Jul 09, 2007 4:51 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:

Postby _sandswipe_ » Mon Jul 09, 2007 5:05 am UTC

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

Postby oblivimous » Mon Jul 09, 2007 5:08 am UTC

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.

User avatar
blind visionary
Posts: 185
Joined: Sat Jun 02, 2007 8:23 pm UTC
Location: The Internet
Contact:

Postby blind visionary » Mon Jul 09, 2007 5:10 am UTC

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.

User avatar
Arancaytar
Posts: 1642
Joined: Thu Mar 15, 2007 12:54 am UTC
Location: 52.44°N, 13.55°E
Contact:

Postby Arancaytar » Mon Jul 09, 2007 5:12 am UTC

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:

Postby wocket » Mon Jul 09, 2007 5:12 am UTC

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

Postby oblivimous » Mon Jul 09, 2007 5:15 am UTC

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?

User avatar
UserGoogol
Posts: 90
Joined: Mon Jan 29, 2007 5:58 am UTC

Postby UserGoogol » Mon Jul 09, 2007 5:27 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.

User avatar
Bakemaster
pretty nice future dick
Posts: 8915
Joined: Fri Jul 06, 2007 2:33 pm UTC
Location: One of those hot places

Postby Bakemaster » Mon Jul 09, 2007 5:30 am UTC

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.
Image
c0 = 2.13085531 × 1014 smoots per fortnight
"Apparently you can't summon an alternate timeline clone of your inner demon, guys! Remember that." —Noc

User avatar
UmbrageOfSnow
Not Fully Human
Posts: 354
Joined: Sun Apr 22, 2007 7:06 am UTC
Location: Insomnia Island
Contact:

Postby UmbrageOfSnow » Mon Jul 09, 2007 5:31 am UTC

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.

User avatar
curious and questioning
Posts: 214
Joined: Fri Jun 08, 2007 3:27 am UTC
Location: inside the birdhouse in your soul
Contact:

Postby curious and questioning » Mon Jul 09, 2007 5:34 am UTC

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]

User avatar
__Kit
Posts: 1576
Joined: Tue May 08, 2007 5:12 am UTC
Location: 16/M/NZ
Contact:

Postby __Kit » Mon Jul 09, 2007 5:41 am UTC

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

Postby jakerg22 » Mon Jul 09, 2007 5:41 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

Postby Risita » Mon Jul 09, 2007 5:42 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! :wink:

ptveite
Posts: 159
Joined: Tue Dec 12, 2006 3:15 pm UTC

Postby ptveite » Mon Jul 09, 2007 5:45 am 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"

User avatar
Mighty Jalapeno
Inne Juste 7 Dayes I Wille Make You A Hero!
Posts: 11262
Joined: Mon May 07, 2007 9:16 pm UTC
Location: Prince George In A Can
Contact:

Postby Mighty Jalapeno » Mon Jul 09, 2007 5:46 am UTC

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

Postby Karrion » Mon Jul 09, 2007 5:51 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 imagine it's Dijkstra's algorithm or a variant of it. I've used it before for similar problems.

Edit: beaten to it :-(

User avatar
Strilanc
Posts: 646
Joined: Fri Dec 08, 2006 7:18 am UTC

Postby Strilanc » Mon Jul 09, 2007 5:55 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.

What's even more interesting about this is the lack of a wikipedia article.
Don't pay attention to this signature, it's contradictory.


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: No registered users and 22 guests