0287: "NPComplete"
Moderators: Moderators General, Prelates, Magistrates
 space_raptor
 Posts: 1497
 Joined: Fri Nov 17, 2006 5:02 pm UTC
 Location: Calgary
 Contact:
I used the Traveling Salesman approach that was mentioned.
And I got 1 mixed fruit, 1 french fries, 1 side salad, and 1 hot wings.
So 1 mixed fruit, 1 french fries, 1 side salad, and 1 hot wing equals $11.80. If one were to also add the sticks, then the price would be too much, so I also added sales tax and tip to the equation. With 5 cents as tax, then its $11.85. They would then tip $3.20 to get to final amount.
And I got 1 mixed fruit, 1 french fries, 1 side salad, and 1 hot wings.
So 1 mixed fruit, 1 french fries, 1 side salad, and 1 hot wing equals $11.80. If one were to also add the sticks, then the price would be too much, so I also added sales tax and tip to the equation. With 5 cents as tax, then its $11.85. They would then tip $3.20 to get to final amount.
Fiddly wrote:I thought the knapsack problem is maximizing utility subject to capacity constraints. The problem described here seems a bit different.
It's NP complete, so it can be translated into any other NP complete problem (in polynomial time), including subset sum (the obvious one), knapsack, travelling salesman, etc.
Brom wrote:I used the Traveling Salesman approach that was mentioned.
And I got 1 mixed fruit, 1 french fries, 1 side salad, and 1 hot wings.
So 1 mixed fruit, 1 french fries, 1 side salad, and 1 hot wing equals $11.80. If one were to also add the sticks, then the price would be too much, so I also added sales tax and tip to the equation. With 5 cents as tax, then its $11.85. They would then tip $3.20 to get to final amount.
I don't really see how this is a viable solution, since the server was instructed to bring out EXACTLY $15.05 worth of appetizers, and there was no way they could know what their tip would be beforehand.
Actually, the INITIAL pathing data returned by Google Maps was outright purchased from another company along with the map data and the pathing is revised over time as queries are performed.Alky wrote: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 lineartime 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.
For instance, you'll query up a certain route, and Google will start with the vendorprovided path, and then recursively try to find a better route for each "leg". It'll spend a given amount of time trying to figure this out, and then give you what it has in the interests of responsiveness. It'll then store the changes and continue revising as queries overlap the one you made. There may also be a 24/7 optimizer running.
So, each return isn't guaranteed to be optimal, but the more often a route is "traveled", the more optimized it will become. This allows an absolute minimum of precomputing to be done (in other words, no, there is no giant supercomputer that calculates every possible route from ab) and still produces very accurate results pretty quickly (Because most Google Maps queries are actually pretty short, it may be able to perform the full optimization in the first shot). No insane amounts of I/O necessary. Just read in the existing path data, and the road data within a certain distance of the path, which is a pretty small amount of data.
 UmbrageOfSnow
 Not Fully Human
 Posts: 354
 Joined: Sun Apr 22, 2007 7:06 am UTC
 Location: Insomnia Island
 Contact:
wocket wrote:Brom wrote:I used the Traveling Salesman approach that was mentioned.
And I got 1 mixed fruit, 1 french fries, 1 side salad, and 1 hot wings.
So 1 mixed fruit, 1 french fries, 1 side salad, and 1 hot wing equals $11.80. If one were to also add the sticks, then the price would be too much, so I also added sales tax and tip to the equation. With 5 cents as tax, then its $11.85. They would then tip $3.20 to get to final amount.
I don't really see how this is a viable solution, since the server was instructed to bring out EXACTLY $15.05 worth of appetizers, and there was no way they could know what their tip would be beforehand.
Also, this doesn't even seem solutionlike. You shouldn't be able to just fudge away everything with tax and tip, or it isn't really a puzzle at all, just a cost of dinner. And how is that a "Traveling Salesman approach"? I mean did he make a weighted graph somewhere in there that I missed?
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.
 Omniferous
 Posts: 7
 Joined: Wed Jul 04, 2007 4:56 am UTC
 voodooKobra
 You just....
 Posts: 159
 Joined: Mon Mar 12, 2007 4:34 am UTC
 Contact:
blind visionary wrote: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.
Seconded.
If you need to reach me, email kobrasrealm@gmail.com
in b4 spam
Kobra's Corner  My horriblywritten opinions that aren't worth reading. Seriously; you're better off reading Nietzsche translated into myspace user lingo.
in b4 spam
Kobra's Corner  My horriblywritten opinions that aren't worth reading. Seriously; you're better off reading Nietzsche translated into myspace user lingo.
wing wrote:Actually, the INITIAL pathing data returned by Google Maps was outright purchased from another company along with the map data and the pathing is revised over time as queries are performed.
For instance, you'll query up a certain route, and Google will start with the vendorprovided path, and then recursively try to find a better route for each "leg". It'll spend a given amount of time trying to figure this out, and then give you what it has in the interests of responsiveness. It'll then store the changes and continue revising as queries overlap the one you made. There may also be a 24/7 optimizer running.
So, each return isn't guaranteed to be optimal, but the more often a route is "traveled", the more optimized it will become. This allows an absolute minimum of precomputing to be done (in other words, no, there is no giant supercomputer that calculates every possible route from ab) and still produces very accurate results pretty quickly (Because most Google Maps queries are actually pretty short, it may be able to perform the full optimization in the first shot). No insane amounts of I/O necessary. Just read in the existing path data, and the road data within a certain distance of the path, which is a pretty small amount of data.
You reckon? That'd probably mean asking directions to rural towns in NZ is not going to be very well optimised. It also sounds like quite a bit of data to store...
Edit: Nah, I don't think it stores the most optimal route from A to B: it seems to consistently take longer for longer trips than shorter ones, implying that it's calculating it each time.
jakerg22 wrote:I'm not sure if it takes stoplights into account, or stop signs, or if it gives preferential treatment to interstates and highways.
They do take lights into account; sometimes you see a suggested route that turns one street before a target (rightleftright), instead of simply straight to target (right) if the target's corner has a stoplight.
If the blocks are rectangular (or parallellograms, true) then the suggested speed x length comes to the same, so avoiding the light is what it suggests. But the two extra corners and unforeseeabletraffic (a parking car? a bike? a kid?) slows you down more than the light.
I was going to attach a picture of a routeplanner doing this, in a street I used to live, but it now suggests something else  a longer route avoiding 2 streetlights.
 PotatoEngineer
 Posts: 17
 Joined: Fri Oct 20, 2006 10:57 am UTC
SpitValve wrote:Edit: Nah, I don't think it stores the most optimal route from A to B: it seems to consistently take longer for longer trips than shorter ones, implying that it's calculating it each time.
The approach described works for both long routes and short ones; if the route is broken into several legs, and each leg is processed separately, you should expect a longer total time for longer trips.
 necroforest
 Posts: 195
 Joined: Tue Apr 10, 2007 3:46 pm UTC
 Contact:
I'm suprised nobody has pointed this out  The problem isn't NPComplete, since it's not a decision problem, therefore not in NP.
Also, I figured that google maps would just use the FloydWarshall algorithm (allpairs shortest path; finds the shortest path between every two pairs of vertices, complexity Theta(n^3) ) once on the dataset and be done with it, although now that I think about it n^3 complexity might be pretty rough for that big of a data set (plus the notfittinginmemory thing), especially since most of those routes would never be looked at (your house> every other house in your neighborhood, and reverse dirrections)
Also, I figured that google maps would just use the FloydWarshall algorithm (allpairs shortest path; finds the shortest path between every two pairs of vertices, complexity Theta(n^3) ) once on the dataset and be done with it, although now that I think about it n^3 complexity might be pretty rough for that big of a data set (plus the notfittinginmemory thing), especially since most of those routes would never be looked at (your house> every other house in your neighborhood, and reverse dirrections)
I'm not as glad that I found the people who try to solve it (no offense, of course), I'm just glad that someone posted the solution so I don't have to spend my time solving it. As soon as I read the strip I was cursing Randall for forcing me to come up with a general solution. As it turns out I'd be happy turning in chessguy's work. But I really want to know how he's going to tip me seven fiftytwo and a half.blind visionary wrote: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.
And I really don't like to talk about my flair.
 Arancaytar
 Posts: 1642
 Joined: Thu Mar 15, 2007 12:54 am UTC
 Location: 52.44°N, 13.55°E
 Contact:
Re: Solution
spacedman wrote:I have a truly marvellous general solution to these classes of problem but this textbox is too narrow to contain it.
Any forum where Fermat's Last Theorem is considered as good a pop culture reference as All Your Base is a place I want to find out more about.
Ok, I'll admit it  I spent my morning coding a solver for this. It's available at http://rembo.isageek.net/knapsack.php
And yes, you'll have to feed it the prices in cents.
And yes, you'll have to feed it the prices in cents.
1: Remboooo you aught to put some sensible limits on your php script...
2: Prolog n00b ftw:
2: Prolog n00b ftw:
Code: Select all
app(A,B,C,D,E,F):
member(A,[0,1,2,3,4,5,6,7]), %MixedFruit
member(B,[0,1,2,3,4,5,6,7]), %FrenchFried
member(C,[0,1,2,3,4,5]), %SideSalad
member(D,[0,1,2,3,4]), %HotWings
member(E,[0,1,2,3]), %MozzarellaSticks
member(F,[0,1,2]), %SamplerPlate
S is A*215 + B*275 + C*335 + D*355 + E*420 + F*580,
S = 1505.
space_raptor wrote:Alright. What does NPcomplete mean?
Nonrigorous explanation.
Definition: A decision problem is a question which has a yes or no answer for some general set of input. An example would be "is n prime?"
A decision problem is said to be in P if there is an algorithm that solves the problem in time bounded above by a polynomial functions of the length of the input (for an integer, that is essentially log n (if we write in base 2, that is log_2 n, base 10 log_10 n, but since changing base will only alter the value of the log by a constant multiple, the base we use is irrelevant).
A decision problem is said to be in NP if when the problem has an answer of yes, there is a proof of the answer which can be verified in polynomial time. For example, "is n composite" is in NP since the proof is simply presenting some nontrivial factor of the number which can be checked by long division.
A problem P_1 is said to be NPhard if there is a polynomial time algorithm which will reduce any problem P_2 in NP to an equivalent problem in P_1.
A problem is said to be NPcomplete if it is in NP and is NPhard.
It is unknown if P=NP or not, but most computer scientists suspect that they are unequal. There is a million dollar prize for resolving the problem.
We care about these problems for a variety of reasons including being related to cryptography (for example factoring in NP).

 Posts: 161
 Joined: Fri May 25, 2007 8:59 pm UTC
 Location: Cambridge, MA
 Contact:
Re: The Haskell answer
toysbfun wrote: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.815.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..
You aren't the only one.
 thesilentpyro
 Posts: 189
 Joined: Mon Jul 09, 2007 3:08 pm UTC
 Location: In the ashes, dancing with the flames
I caused myself ten minutes of headache when I tried solving it with the assumption that most people, like myself and my family, never order more than one of the same kind of appetizer due to the desire to get more variety for the money. It was only when I couldn't come up with any solution that way that I wrote an Excel macro to do the work for me.
Today is more fun if you leave tomorrow behind.
JoshuaZ wrote:It is unknown if P=NP or not, but most computer scientists suspect that they are unequal. There is a million dollar prize for resolving the problem.
maaayyyyyybe...
mayyyyybe not: http://kryten.mm.rpi.edu/scb_pnp_solved22.pdf
Grant it, that paper is as of yet still pending publication, but the author is well respected.
ehiunno wrote:
maaayyyyyybe...
mayyyyybe not: http://kryten.mm.rpi.edu/scb_pnp_solved22.pdf
Grant it, that paper is as of yet still pending publication, but the author is well respected.
The link posted isn't working for me.
bagh, it wasn't working for me either but it worked before.
http://www.rpi.edu/~brings/
Thats where I got it, I dont know why it is down. Maybe google would turn up more info about the paper.
http://www.rpi.edu/~brings/
Thats where I got it, I dont know why it is down. Maybe google would turn up more info about the paper.
 necroforest
 Posts: 195
 Joined: Tue Apr 10, 2007 3:46 pm UTC
 Contact:
 dekonstruct
 Posts: 38
 Joined: Tue Jan 30, 2007 6:52 pm UTC
 Location: Western New York
 Contact:
 sillybear25
 civilized syllabub
 Posts: 435
 Joined: Tue Jun 19, 2007 2:19 am UTC
 Location: Look at me, I'm putting a metajoke in the Location field.

 Posts: 139
 Joined: Tue Nov 07, 2006 6:36 pm UTC
 Location: Fremont, CA
ok, so my only coding class was on basic in 10th grade high school, about 1993.
10 For a = 0 to 7
20 For b = 0 to 6
30 For c = 0 to 5
40 For d = 0 to 5
50 For e = 0 to 4
60 For f = 0 to 3
70 If 215a + 275b + 335c + 355d + 420e + 580f = 1505 then print a,b,c,d,e,f
80 next f
90 next e
100 next d
110 next c
120 next b
130 next a
Line numbers ftw, and mozerella sticks = 420
10 For a = 0 to 7
20 For b = 0 to 6
30 For c = 0 to 5
40 For d = 0 to 5
50 For e = 0 to 4
60 For f = 0 to 3
70 If 215a + 275b + 335c + 355d + 420e + 580f = 1505 then print a,b,c,d,e,f
80 next f
90 next e
100 next d
110 next c
120 next b
130 next a
Line numbers ftw, and mozerella sticks = 420
I'm pretty sure Google maps gives preferential treatment to interstates and highways.
I once wanted a map from my house to another house across town (c. 100,000 people in my town... it's not too large)...
I ran the query, and google wanted me to get on the interstate just to get across town. Ridiculous.
I once wanted a map from my house to another house across town (c. 100,000 people in my town... it's not too large)...
I ran the query, and google wanted me to get on the interstate just to get across town. Ridiculous.
What the Pfargtl?

 Posts: 69
 Joined: Mon Mar 26, 2007 10:27 pm UTC
 Location: Saskatoon, SK
necroforest wrote:I'm suprised nobody has pointed this out  The problem isn't NPComplete, since it's not a decision problem, therefore not in NP.
Absolutely. The NPComplete problem is determining whether a solution exists. As such a smart waiter would realize that the annoying clients already KNOW there's a solution, beat it out of them, THEN go figure out an alternate solution, and bring them 7 mixed fruit instead of the 1 mixed fruit, 2 hot wings, and 1 sampler plate the pretentious bastards actually wanted.
 Sprocket
 Seymour
 Posts: 5951
 Joined: Mon Mar 26, 2007 6:04 pm UTC
 Location: impaled on Beck's boney hips.
 Contact:
XKCD wrote:General solutions get you a 50% tip
General results  Randall gets a glass of dishwater.
ALT TEXT
General results  Waiter gets fired for assault.
Also: should i include that 50% tip into the soltuion or a .05% Massachusettes prepared food tax?
Last edited by Sprocket on Mon Jul 09, 2007 5:05 pm UTC, edited 2 times in total.
Return to “Individual XKCD Comic Threads”
Who is online
Users browsing this forum: No registered users and 34 guests