0287: "NP-Complete"

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

Moderators: Moderators General, Prelates, Magistrates

User avatar
notzeb
Without Warning
Posts: 627
Joined: Thu Mar 08, 2007 5:44 am UTC
Location: a series of tubes

Postby notzeb » Sun Jul 15, 2007 9:35 am UTC

rlyngsoe wrote:Not to mention that the appetizer problem is not NP hard either, assuming that the menu is fixed with prices convertable to integers, i.e. the only input to the problem is the size of the knapsack (cost of order):

[...]

With this implementation, all the server needs to remember is the procedure and about 43000 tabulated solutions.


It's... so beautiful... :shock:

The worst part is, I can actually imagine a waiter memorizing such an algorithm, just in case.
Zµ«V­jÕ«ZµjÖ­Zµ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«ZµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­Z

User avatar
e946
Posts: 621
Joined: Wed Jul 11, 2007 6:32 am UTC

Postby e946 » Mon Jul 16, 2007 7:12 am UTC

larue708 wrote:So I know I'm a few days late on this one but I just got around to looking at it this afternoon and wrote a small c++ code for the problem it's brute force but it only takes 10-15 minutes to solve the problem if the dollars range gets into the mid-upper hundreds or it solves small numbers almost instantly so here it is

Code: Select all

#include <stdlib.h>
#include <math.h>
#include <stdio.h>
void main(){
    int total=1505;
    int mixedFruit=215;
    int frenchFries=275;
    int sideSalad=335;
    int hotWings=355;
    int samplerPlate=580;
    int mozarellaSticks=420;
    int numSolutions=0;
    int iterator=total/mixedFruit +1;
      for(int i=0;i<iterator;i++){
      for(int j=0;j<iterator;j++){
      for(int k=0;k<iterator;k++){
      for(int l=0;l<iterator;l++){
      for(int m=0;m<iterator;m++){
      for(int n=0;n<iterator;n++){
        int value=i*mixedFruit+j*frenchFries+k*sideSalad+l*hotWings+n*samplerPlate+m*mozarellaSticks;
        if(value==total){
          printf("%d %d %d %d %d %d \n" ,i,j,k,l,m,n);
          numSolutions++;
       }}}}}}}
      if(numSolutions==1) printf("There is %d solution.\n\n",numSolutions);
      else printf("There are %d solutions.\n\n",numSolutions);
      system("PAUSE");
}

So this is the first thing I've posted in the forum yet I've spent countless hours lurking through it. Got to love boredom


I really didn't want to use loops just because they're so rigid. If the comic was suddenly edited so that there were 8 appetizers instead of 6 (The chances of this happening are astronomical), you'd have a lot of changes to make, while someone who uses recursion might just have to add the new appetizers and nothing more. Flexibility FTW.

davidad.net
Posts: 1
Joined: Thu Jul 19, 2007 9:25 pm UTC
Location: MIT
Contact:

Postby davidad.net » Thu Jul 19, 2007 9:48 pm UTC

My GHCi code - a little more generalized than chessguy's:

Code: Select all

Prelude Control.Monad> let menu = [("Mixed Fruit",215),("French Fries",275),("Side Salad",335),("Hot Wings",355),("Mozz Sticks",420),("Sampler Plate",580)]
Prelude Control.Monad> map (filter ((/= 0) . snd) . (zip $ map fst menu)) $ filter ((==) 1505 . sum . (zipWith (*) $ map snd menu)) $ replicateM (length menu) [0..10]
[[("Mixed Fruit",1),("Hot Wings",2),("Sampler Plate",1)],[("Mixed Fruit",7)]]


Data flows, as usual in functional (and especially points-free) programs, from right to left: replicateM generates all possible lists the length of the menu populated with numbers from 0 to 10, (zipWith (*) $ map snd menu) multiplies those numbers by the second entries in the corresponding menu items, sum sums them, (==) 1505 checks if it adds up, filter removes the ones that don't, (zip $ map fst menu) adds the names to the number needed to order, and filter ((/= 0) . snd) removes those orders with quantity 0.

Ghona
Posts: 246
Joined: Mon May 21, 2007 1:28 am UTC

Postby Ghona » Wed Jul 25, 2007 1:12 pm UTC

larsh wrote:
NeoThermic wrote:Bleh. I decided (for some strange reason. I made this choice at 5am without any sleep) not to brute force it, more as to pick a random starting point, and then pick random items until the total was 15.05... However, while it might never find the seven mixed fruits, it did find the other solution of fruit + wings * 2 + sampler plate...

Fun. Has anybody tried sort of a genetic-algorithms approach? E.g. start with a random solution and mutate it, using artificial selection to weed out the less-fit attempts? (What would make a good fitness function though?)


Start with the final value, subtract until you get a negative number, then switch out menu items (or add/subtract more of them) until it's zero.


Here's my general solution.

According to the principles of economics, what something is "worth" is what somebody will pay for it. So here's some random assortment of appetizers, that'll be 15.05
If you're taking me too seriously, you probably are making a mistake.

larsh
Posts: 21
Joined: Wed Jul 11, 2007 8:34 pm UTC

Postby larsh » Wed Jul 25, 2007 3:13 pm UTC

Ghona wrote:
larsh wrote:Fun. Has anybody tried sort of a genetic-algorithms approach? E.g. start with a random solution and mutate it, using artificial selection to weed out the less-fit attempts? (What would make a good fitness function though?)

Start with the final value, subtract until you get a negative number, then switch out menu items (or add/subtract more of them) until it's zero.

So the fitness function is closeness to the target?

The problem with that is that you may be close to the target value, without being close to a solution. In other words, you could get stuck in a local maximum. And that's why this problem is NP-complete... in general, you can't prune your search according to any obvious measure of how close you're getting. So maybe genetic algorithms aren't a good fit for this problem.

User avatar
Graham's Number
Posts: 33
Joined: Mon Jul 09, 2007 9:27 pm UTC

Postby Graham's Number » Sat Sep 08, 2007 9:54 pm UTC

6453893 wrote:I like to give my waiters quadratics to solve. As in, "We'll take three of dessert X and two of Desert Y, where 5X^2-X+$5 Tip=2Y^2-4Y+$3 Tip."

After I've been to a restaurant once, the waiters always keep a decent calculator handy.


Where is this restaurant that has complex numbers as prices?
And you thought a googolplex was big...

Asmadeus
Posts: 2
Joined: Sat Sep 29, 2007 4:49 pm UTC

Re: "NP-Complete" discussion

Postby Asmadeus » Sat Sep 29, 2007 5:07 pm UTC

Sorry to post in such an old thread, but it's for the sake of completeness, since no-one gave a sample code in OCaml (or maybe no-one ever heard of it, which would not suprise me :P)

Code: Select all

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);;

TV4Fun
Posts: 92
Joined: Mon Oct 01, 2007 5:45 am UTC
Location: Certifiable C++ Programmer

Re:

Postby TV4Fun » Mon Oct 01, 2007 10:09 pm UTC

larue708 wrote:So I know I'm a few days late on this one but I just got around to looking at it this afternoon and wrote a small c++ code for the problem it's brute force but it only takes 10-15 minutes to solve the problem if the dollars range gets into the mid-upper hundreds or it solves small numbers almost instantly so here it is

Code: Select all

#include <stdlib.h>
#include <math.h>
#include <stdio.h>
void main(){
    int total=1505;
    int mixedFruit=215;
    int frenchFries=275;
    int sideSalad=335;
    int hotWings=355;
    int samplerPlate=580;
    int mozarellaSticks=420;
    int numSolutions=0;
    int iterator=total/mixedFruit +1;
      for(int i=0;i<iterator;i++){
      for(int j=0;j<iterator;j++){
      for(int k=0;k<iterator;k++){
      for(int l=0;l<iterator;l++){
      for(int m=0;m<iterator;m++){
      for(int n=0;n<iterator;n++){
        int value=i*mixedFruit+j*frenchFries+k*sideSalad+l*hotWings+n*samplerPlate+m*mozarellaSticks;
        if(value==total){
          printf("%d %d %d %d %d %d \n" ,i,j,k,l,m,n);
          numSolutions++;
       }}}}}}}
      if(numSolutions==1) printf("There is %d solution.\n\n",numSolutions);
      else printf("There are %d solutions.\n\n",numSolutions);
      system("PAUSE");
}

So this is the first thing I've posted in the forum yet I've spent countless hours lurking through it. Got to love boredom


Not to nitpick, but that appears to be a C program, not a C++ program.
$_[0] wrote:rule 2:
Once a relationship ends, physical access to all relevant machinery is denied.

mattc
Posts: 1
Joined: Wed Oct 03, 2007 1:09 am UTC

Re: Re:

Postby mattc » Wed Oct 03, 2007 1:18 am UTC

larue708 wrote:

Code: Select all

      for(int i=0;i<iterator;i++){
      for(int j=0;j<iterator;j++){
      for(int k=0;k<iterator;k++){
      for(int l=0;l<iterator;l++){
      for(int m=0;m<iterator;m++){
      for(int n=0;n<iterator;n++){

TV4Fun wrote:Not to nitpick, but that appears to be a C program, not a C++ program.


The initializer list variable declarations seriously suggests C++. Possibly C99.

User avatar
Rummy
Posts: 74
Joined: Sun Sep 23, 2007 8:15 pm UTC
Location: Clinton, MA
Contact:

Re:

Postby Rummy » Wed Oct 03, 2007 7:25 pm UTC

larsh wrote: So maybe genetic algorithms aren't a good fit for this problem.


Agreed. They work better where you're just trying to get "close enough" to a solution not find a particular solution (i.e. the "best" or $16.64 or whatever). I've implemented one here at work and would love to implement one for working on something like "the traveling salesman" problem. A genetic algorithm would be better on a problem like that where you don't start out with the correct answer. The question "find me the shortest path you can" makes fitness easy to calculate and is easier for a genetic algorithm instead of "find me a path that is exactly 19323 miles."

User avatar
Geekthras
3) What if it's delicious?
Posts: 529
Joined: Wed Oct 03, 2007 4:23 am UTC
Location: Around Boston, MA

Re: "NP-Complete" discussion

Postby Geekthras » Thu Oct 04, 2007 1:07 am UTC

Hmmmm Firefox is failing right now. I log on, it says that it was successful, then when I hit return to index, it logs me out.

Anyway, some person posted an online solver in php (I'm thinking of making another Lisp one of the challenge of it)
But it breaks down with
Values: 356 111 43 56 134 548 399 776 440
Knapsack size: 1621

But if you try it in a different order or take all of the numbers past 43 away, it works. Odd.
Wait. With a SPOON?!

TV4Fun
Posts: 92
Joined: Mon Oct 01, 2007 5:45 am UTC
Location: Certifiable C++ Programmer

Re: "NP-Complete" discussion

Postby TV4Fun » Thu Oct 04, 2007 10:33 pm UTC

mattc wrote:The initializer list variable declarations seriously suggests C++. Possibly C99.
The inline declarations of variables are supported by C99, which is considered to be the latest C standard and not a separate language from C.
$_[0] wrote:rule 2:
Once a relationship ends, physical access to all relevant machinery is denied.

User avatar
logoseph
Posts: 6
Joined: Sun Jun 08, 2008 8:24 pm UTC
Location: Texas

Re: "NP-Complete" discussion

Postby logoseph » Mon Jun 09, 2008 2:27 am UTC

Yeah, I don't know how to code, but I knew the trick would be getting the .05, so I grabbed my trusty TI-83+ and input some random things to get a .05 ending. I got 4.2+3.55+2.15+2.15=12.05, then added 3 split to 1.4 (to one 2.15) and 1.6 (to the 4.2) getting 5.8+3.55+3.55+2.15=15.05. I celebrated at getting it in about 3 minutes after trying to use a matrix until I realized I had 6 variables and only one equation. My current Algebra II education limit and lack of coding skills beyond basic HTML will not stop me from solving xkcd problems!

User avatar
JCCyC
Posts: 37
Joined: Sat May 03, 2008 9:51 pm UTC
Location: Rio de Janeiro, Brazil

Re:

Postby JCCyC » Mon Jun 09, 2008 3:22 pm UTC

e946 wrote:I really didn't want to use loops just because they're so rigid. If the comic was suddenly edited so that there were 8 appetizers instead of 6 (The chances of this happening are astronomical), you'd have a lot of changes to make, while someone who uses recursion might just have to add the new appetizers and nothing more. Flexibility FTW.


Totally OT: Yay, I'm not the only one who has a F1 wallpaper. And look, it's Massa's Ferrari too!

User avatar
Goatboy
may become less boring.
Posts: 709
Joined: Thu Dec 13, 2007 3:03 am UTC
Contact:

Re: "NP-Complete" discussion

Postby Goatboy » Tue Jul 15, 2008 12:50 am UTC

My roomate and I came across a conundrum the other day and were intrigued, but not enough to do the math ourselves. This apartment complex laundry room charged $1.30 for a wash and $1.05 for a dry. Laundry services were paid for by buying a card ($5), which could be refilled, but only with $5, $10, or $20 bills. I was just wondering how many loads you would have to do 'til you didn't have change on the card. Ready......Go!
I have nothing to offer anybody except my own confusion.
And some old pictures.

Lunch Meat
Posts: 68
Joined: Fri Jun 20, 2008 6:30 am UTC

Re: "NP-Complete" discussion

Postby Lunch Meat » Tue Jul 15, 2008 5:18 am UTC

Goatboy wrote:My roomate and I came across a conundrum the other day and were intrigued, but not enough to do the math ourselves. This apartment complex laundry room charged $1.30 for a wash and $1.05 for a dry. Laundry services were paid for by buying a card ($5), which could be refilled, but only with $5, $10, or $20 bills. I was just wondering how many loads you would have to do 'til you didn't have change on the card. Ready......Go!


Assuming you dry every time you wash, and the washer and dryer are both not-crap (if your dryer's bad then you may have to dry each load more than once), I'm pretty sure you'd have to 100 loads. You'd put a total of $235 on the card. 235 is 47x5; since 47 is a prime number and not divisible into 100, you can't reduce it anymore.

Of course, sometimes your dryer is bigger than your washer, and you also end up hanging up a lot of your clothes to dry. Then if you wait you can combine two loads in the dryer. I find that depending on the combination of dryable/nondryable clothes I wear each week, doing two or three loads each week, or about 5 every two weeks, I can eliminate about one of those from needing to be dried. Then it's $22.45 for every ten loads. I think you run into the same problem at the end--22.45 is 4.49x5, and 449 is prime. So you have to do 1000 loads. 5 every 2 weeks makes 400 weeks. So it would take you just under 8 years. In my case, of course, that's divided into semesters. At 18 weeks/semester, that's a little over 22 semesters...so now the question is how many semesters do you have to take before you end one with no change on your card, and can you successfully die before the end and evade your student loans...

Someone can feel free to check my math.

I think I like my school's laundry system better. .75/washer, .75/dryer, on prefilled cards which is included in the cost of tuition so we don't even have to think about it.

Random832
Posts: 2525
Joined: Wed Oct 10, 2007 4:38 pm UTC

Re: "NP-Complete" discussion

Postby Random832 » Tue Jul 15, 2008 1:05 pm UTC

Goatboy wrote:My roomate and I came across a conundrum the other day and were intrigued, but not enough to do the math ourselves. This apartment complex laundry room charged $1.30 for a wash and $1.05 for a dry. Laundry services were paid for by buying a card ($5), which could be refilled, but only with $5, $10, or $20 bills. I was just wondering how many loads you would have to do 'til you didn't have change on the card. Ready......Go!


Absolute smallest number is 33 wash and 2 dry for $45.00

You can get close to equal amounts of each with, say, 29 wash 26 dry for $65.00 or 28 wash 32 dry for $70.00

(I did this by generating an enormous table in excel and inspecting the values manually.)

User avatar
Yakk
Poster with most posts but no title.
Posts: 11045
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: "NP-Complete" discussion

Postby Yakk » Tue Jul 15, 2008 2:36 pm UTC

My classical algebra is over 10 years old now. Heh!

130w + 105d = 500c
<->
26w+21d=100c
->
5w=16c mod 21
<->
2w=c mod 3 and 5w=2c mod 7
<->
2w=c mod3 and -w=c mod 7 (<-> w=-c mod 3 and w=-c mod 7)

...

Existing solutions:
29 wash 26 dry for (13 cards) or 28 wash 32 dry for (14 cards)

First one:
29*2 mod 3 = 2*2 mod 3 = 1 mod 3
13 mod 3 = 1 mod 3

-29 mod 7 = -1 mod 7 = 13 mod 7

The second one also works.

...

So we have:
w = 3A-m and c = 3B+m
w = 7X-n and c = 7Y+n

Or:
26(3A-m)+21d=100(3B+m)
and
26(7X-n)+21d=100(7Y+n)

26(3A-m)+21d=100(3B+m)
78A-26m+21d=300B+100m
21d = 300B-78A+126m
7d = 100B-26A+42m
-> 0 == A+B mod 7

26(7X-n)+21d=700Y+100n
182X+21d=700Y+126n
26X+3d=100Y+18n
3d=100Y-26X+18n
-> 0==Y+X mod 3

I don't think there is a way to solve this problem that doesn't end with "and then look", or equivalent. I think ... network optimization? ... might be the branch of C&O that would specialize in solving this kind or problem? Not certain.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Random832
Posts: 2525
Joined: Wed Oct 10, 2007 4:38 pm UTC

Re: "NP-Complete" discussion

Postby Random832 » Tue Jul 15, 2008 3:17 pm UTC

Yakk wrote:I don't think there is a way to solve this problem that doesn't end with "and then look", or equivalent.


Could calculate what changes to each value result in a change of 500 in the result.

Hausdog
Posts: 17
Joined: Mon Mar 16, 2009 2:16 am UTC

"NP-Complete" Discussion

Postby Hausdog » Mon Mar 16, 2009 10:44 pm UTC

Edit: mergened. Please search for the topic before creating a new one. Unless it's one of the real early ones, the chances are, the topic exists. (Such as this one)

I searched for NP Complete and the comic number but still didn't find it. Sorry, anonymod.

Can anyone find an actual answer for this? It can't just be 7 orders of mixed fruit, can it?

Ipskaya
Posts: 2
Joined: Mon Apr 27, 2009 7:42 am UTC

0287: "NP-Complete"

Postby Ipskaya » Mon Apr 27, 2009 7:49 am UTC

Image

Alt-text: General solutions get you a 50% tip.

http://xkcd.com/287/

So has anyone solved this?

User avatar
Cynical Idealist
Posts: 1124
Joined: Mon Sep 15, 2008 10:48 pm UTC

Re: "NP-Complete" Discussion

Postby Cynical Idealist » Mon Apr 27, 2009 9:25 am UTC

Ipskaya wrote:So has anyone solved this?

Yes, people have.

There is already a thread, although it was a bit of a pain to search out ($15.05 is the thing that I knew would find the thread, but if you try that with the forum search its thrown out)
The internet removes the two biggest aids in detecting sarcasm:
1)The tone of voice
2)the assumption that the other person is sane
Elvish Pillager wrote:See? All the problems in our society are caused by violent video games, like FarmVille.

Ipskaya
Posts: 2
Joined: Mon Apr 27, 2009 7:42 am UTC

Re: "NP-Complete" Discussion

Postby Ipskaya » Tue Apr 28, 2009 8:50 am UTC

Sorry about that! I did several searches and nothing came up, so I assumed it hadn't been created. I'll let this die now...

SirCinnamon
Posts: 1
Joined: Sun Jan 17, 2010 5:31 am UTC

0287: "NP-Complete"

Postby SirCinnamon » Sun Jan 17, 2010 5:36 am UTC

http://xkcd.com/287/

7 x Mixed Fruit

First try. Easy. If they all have to be different appetizers:

I think its impossibe. Prove me wrong?

dbmag9
Posts: 29
Joined: Wed Sep 19, 2007 5:13 pm UTC

Re: Comic 287 `NP-Complete`

Postby dbmag9 » Sun Jan 17, 2010 4:13 pm UTC

http://blog.xkcd.com/2007/07/09/perl-appetizers/

xkcd blag wrote: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.
-dbmag9

duncan_roe
Posts: 3
Joined: Wed Jan 20, 2010 6:31 am UTC

Re: Comic 287 `NP-Complete`

Postby duncan_roe » Wed Jan 20, 2010 6:39 am UTC

The below code forms the basis for a general solution (if I was energetic enough to have the program read the numbers or accept them from the command line). It finds the 7xfruit solution. It finds solutions for $15-10 and $15-15 (by recompiling). A version I had where the selections had to be all different said there was no solution. Hope someone finds this interesting

17:13:05$ cat np-c.c
#include <stdio.h>
/*
gcc -g3 -ggdb -Wall -Wmissing-prototypes -Wstrict-prototypes np-c.c -o np-c
*/
static int
solve(int *a, int len, int wanted)
{
int i;
if (wanted == 0)
return 1;
if(wanted < 0)
return 0;
for (i = 0; i < len; i++)
{
if (solve(a, len, wanted - a[i]))
{
printf("%d\n", a[i]);
return 1;
}
}
return 0;
}
int
main(int argc, char **argv)
{
int a[6] = { 215, 275, 335, 355, 420, 580 };
if (!solve(a, 6, 1505))
printf("No solution\n");
return 0;
}

duncan_roe
Posts: 3
Joined: Wed Jan 20, 2010 6:31 am UTC

Re: Comic 287 `NP-Complete`

Postby duncan_roe » Wed Jan 20, 2010 10:23 am UTC

I have a version that outputs all solutions. But it treats different orders of items as different solutions. Working on that...

duncan_roe
Posts: 3
Joined: Wed Jan 20, 2010 6:31 am UTC

Re: Comic 287 `NP-Complete`

Postby duncan_roe » Wed Jan 20, 2010 12:13 pm UTC

This rather ugly program does print each solution only once. It accepts dollar totals as input, so you can try different values as you like. The table of available values is still hard-coded - left as an exercise to read in.

23:03:45$ cat np-c.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
gcc np-c.c -o np-c -ggdb -g3 -Wall -Wstrict-prototypes -Wmissing-prototypes
*/
static int got1;
static int a[6] = { 215, 275, 335, 355, 420, 580 };
static int len = 6;

// RDIM is the max no. of items in a solution.
// For proper generality,
// we would malloc enough to hold dollar amount / cheapest item.
#define RDIM 9 /* Just make it big enough */
int b[RDIM], s[RDIM];

// p holds previous solutios.
// We need to keep as many of these as there are possible solutions.
// The number of solutions increases as the dollar amount does,
// 100 is just a guess.
#define NUMSOLNS 100
static int p[NUMSOLNS][RDIM];

static int level = -1;
static int
compar(const void *i, const void *j)
{
int m = *((int *)i), n = *((int *)j);
if (m == n)
return 0;
if (m < n)
return -1;
return 1;
}
static void
solve(int amt)
{
int i;

if (amt < 0)
return;
if (!amt)
{
got1 = 1;

// We have a result.
// But is it the same as the previous result, but in a different order?
// Strategy: sort a copy of the b (result stack) array,
// then compare with the p (previous result) array
memcpy(s, b, sizeof b);
qsort(s, level + 1, sizeof(int), compar);
for (i = 0; i < NUMSOLNS; i++)
{
if (!p[i][0])
break;
if (!memcmp(s, p[i], sizeof(int) * (level + 1)))
return;
}
if (i == NUMSOLNS)
{
fprintf(stderr, "Too many solutions\n");
exit(1);
}
memcpy(p[i], s, sizeof(int) * (level + 1));

for (i = level; i >= 0; i--)
printf("%d%s", s[i], i ? " " : "");
printf("\n");
return;
}
level++;
for (i = 0; i < len; i++)
{
b[level] = a[i];
solve(amt - a[i]);
}
level--;
return;
}
int
main(int argc, char **argv)
{
int i;

while (1)
{
got1 = 0;
fprintf(stderr, "Enter a total (0 to finish): ");
scanf("%d", &i);
if (!i)
break;
memset(p, 0, sizeof p);
solve(i);
if (!got1)
printf("No solutions\n");
}
return 0;
}
===================================
Sample output:

23:02:53$ ./np-c
Enter a total (0 to finish): 1505
215 215 215 215 215 215 215
580 355 355 215
Enter a total (0 to finish): 1510
420 420 335 335
Enter a total (0 to finish): 1515
355 335 335 275 215
355 335 275 275 275
580 580 355
Enter a total (0 to finish): 1755
420 355 335 215 215 215
420 355 275 275 215 215
355 355 355 355 335
580 420 420 335
Enter a total (0 to finish): 0

liviro
Posts: 1
Joined: Fri Nov 08, 2013 6:48 pm UTC

Re: 0287: "NP-Complete"

Postby liviro » Fri Nov 08, 2013 6:56 pm UTC

I built an interactive thing that does what this comic is asking for, in addition to visualizing it :)

np-food [dot] com

User avatar
PinkShinyRose
Posts: 824
Joined: Mon Nov 05, 2012 6:54 pm UTC
Location: the Netherlands

Re: 0287: "NP-Complete"

Postby PinkShinyRose » Sat Nov 09, 2013 8:31 pm UTC

Now I look at these prices these appetisers seem really cheap (even though they seem more like bar snacks than appetisers), was that normal in 2007 or are US restaurants just cheap compared to western Europe?
liviro wrote:I built an interactive thing that does what this comic is asking for, in addition to visualizing it :)

https://np-food.com/

Awww, it only works for US restaurants :(. Oh, you used a US based online ordering website.

User avatar
WyldOne
Posts: 2
Joined: Wed Jan 04, 2012 11:15 pm UTC

Re: 0287: "NP-Complete"

Postby WyldOne » Mon Apr 03, 2017 5:52 am UTC

Interesting problem.

Just how many people were able to find one solution without resorting to a computer search? how long did it take?

It took me about 15-20 min to find one without. Let me explain my method of solving which seems to be different.
1) as stated it implied there was at least 1 solution.
2) based on the final amount, you could only have an odd number of appetizers with a 5 for the cents.(this turned out to be very important)
3) the items selected for the 10cent column had add up and be 0
4) certain items couldn't be chosen 7 times and still be less than 15.05

so I used more logic than straight math to reduce the items that could be chosen
btw. I did not know or lookup the knapsack reference to find my solution.

with this I found the one of 7 fruit salads.

Frankly I did not look for any more, but came to the forums, because it was implied there were more solutions. so for that yeah, I cheated a bit.

User avatar
mathmannix
Posts: 1401
Joined: Fri Jul 06, 2012 2:12 pm UTC
Location: Washington, DC

Re: 0287: "NP-Complete"

Postby mathmannix » Wed Apr 05, 2017 8:16 pm UTC

PinkShinyRose wrote:Now I look at these prices these appetisers seem really cheap (even though they seem more like bar snacks than appetisers), was that normal in 2007 or are US restaurants just cheap compared to western Europe?


Well... CPI for the Boston area shows July 2007 (when this comic came out) to have a (somewhat arbitrary, proportionally relevant) value of 226.929, compared to 264.865 for January 2017. So let's say a multiplication factor of 1.17 from then to now. Yeah, that still seems a bit low.

From the Applebees appetizer menu:
Sampler [plate] $13.99 (factor of 2.41)
Mozzarella Sticks $8.29 (factor of 1.97)
Boneless Wings $10.29 (factor of 2.90)
Salad $3.99 (factor of 1.19)

Ordering online from Ruby Tuesday in Wrentham, MA:
Sampler Trio $12.49 (factor of 2.15)
Fire Wings $10.99 (factor of 3.10)
Italian Five-Cheese Skillet ("If you love cheese sticks, try this...") $8.29 (factor of 1.97)
(Ruby's doesn't really have a side salad, as they feature their salad bar...)

Ordering online from Chili's in Chelsea, MA:
Signature Wings (or any other kind of wings) $9.99 (factor of 2.81)
Texas Cheese Fries $8.59 (factor of 3.12, but these are loaded up with a lot of stuff)
Crispy Cheddar Bites $6.59 (that's like Mozzarella sticks, right?) (factor of 1.57)
House Salad $3.99 (again) (factor of 1.19)

And from Somerville, MA Outback:
Kookaburra Wings $10.49 (factor of 2.95)
Cheese Fries $9.99 (factor of 3.63, but possibly less without cheese)
Signature Sampler $9.99 (factor of 1.72)
House Side Salad $3.99 (factor of 1.19)

Again, the salad... yeah, salad is not in high demand, I guess.

So, everything is much more expensive than in our 10-year-old fictional menu, except the salad, which has apparently increased everywhere to $3.99 at almost exactly the inflation rate shown by the CPI for the Boston area.

*******************************

ETA:
Apparently I didn't have my location set in the Applebees Menu, because it didn't ask for it before it gave me the menu prices but assumed I wanted the nearest location. So, the Applebees in Dorchester, MA has different prices:
Sampler [plate] $13.79 (factor of 2.37, oddly this one is less expensive in the Boston area)
Mozzarella Sticks $8.49 (factor of 2.02)
Boneless Wings $10.49 (factor of 2.95)
Salad $5.99 (factor of 1.79, this one increased a lot from here to Boston apparently, but still the lowest percentage gain.)

Oh, and now I'm starving.
I hear velociraptor tastes like chicken.


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: Bing [Bot] and 36 guests