XKCD: NP-Complete Problem
I was browsing through the job section on Craigslist one day and one of the job postings caught my attention. I read through their job listing and one of their requirements was to solve a problem programmatically from xkcd. This is a first that I’ve seen for job postings and I think it’s pretty awesome. You are looking for a programmer so why not test out their skills before you hire them.
I decided to give this problem a go. Not that I’m trying to apply for this job or anything. I just want to find a way to solve it. It was really hard to start off because there are so many ways to approach it. One, I can brute force the program to make it go through every possible combinations there are and find out the answer through there. Or second, create an easy algorithm that goes through and provides the answer as quickly as possible.
I decided to go with PHP (because it’s what I know best) and went with the second method. I’ve been working on this on and off for about a day or two and today I’ve got it working (through the help of others of course). If you want to check out my source code, go here.
The answer to the problem above is:
1 mixed fruit, 2 hot wings, 1 sampler plate
7 mixed fruits
One of the things I had to do was multiply the target price and each menu item price by 100 so that I won’t run into calculation errors. The solution of 7 mixed fruits didn’t come up until I did it that way.
hcudtk iqxcnw zgoelix kicao qfigmvkzn kfixvceg ojqbsulf