Comics

462 readers

1 users here now

A community for sharing comics related to programming

Icon base by Delapouite under CC BY 3.0 with modifications to add a gradient

founded 11 months ago

MODERATORS

LinearArray

[xkcd] NP-Complete (9 Jul 2007) (programming.dev)

submitted 11 months ago* (last edited 11 months ago) by mac to c/comics

2 comments fedilink hide all child comments

source under CC BY-NC 2.5 Deed
explainxkcd/287

Hover Text:

General solutions get you a 50% tip.

:::spoiler Transcript

My Hobby:
Embedding NP-Complete problems in restaurant orders
[A menu is shown.]
Chotchkies Restaurant
Appetizers

Mixed Fruit 2.15

French Fries 2.75

Side Salad 3.35

Hot Wings 3.55

Mozzarella Sticks 4.20

Sampler Plate 5.80

Sandwiches

Barbecue 6.55

[Megan, another person, and Cueball are sitting at a table. Cueball is holding the menu as well as a thick book and is ordering from a waiter. Megan is facepalming.]
Cueball: We'd like exactly $15.05 worth of appetizers, please.
Waiter: ...Exactly? Uhh...
Cueball: Here, these papers on the knapsack problem might help you out.
Waiter: Listen, I have six other tables to get to—
Cueball: —As fast as possible, of course. Want something on traveling salesman?

you are viewing a single comment's thread
view the rest of the comments

[–] [email protected] 5 points 11 months ago (1 children)

Thanks for sharing the xkcd explained link. That was interesting!

SPOILER:

!1. A combination of two orders of hot wings, one order of mixed fruit, and one sampler plate

Seven mixed fruit orders (this solution was not intended - see trivia section in OP's link)!<

[–] [email protected] 2 points 9 months ago

You missed the greatest part:
Randall explains [...] that this was due to him using a Perl script with a bug ("You can't compare IEEE floats for equality").