smert.net

There is very popular web comic called XKCD. The site seems to have been around since January of 2006 and I’m sure that anyone that reads Digg or Reddit will be familiar with them. I visit there from time to time and even have a couple of their comics taped to my desk at work.

A few weeks ago Jordan brought up one in particular because of a job listing for a “consulting and software development firm”. The comic is a bit old and is from earlier this year in July. In the job listing they had a programming exercise referring to that comic and wanted it to work on multiple data sets read from a file. The problem in the comic is np-complete. If you aren’t familiar with that term than you might want to read up. Quoting the article on nist.gov below.

Note: A trivial example of NP, but (presumably) not NP-complete is finding the bitwise AND of two strings of N boolean bits. The problem is NP, since one can quickly (in time ?(N)) verify that the answer is correct, but knowing how to AND two bit strings doesn’t help one quickly find, say, a Hamiltonian cycle or tour of a graph. So bitwise AND is not NP-complete (as far as we know).

Confused yet? Because I am. I thought I had an understanding or what NP-complete meant before I started reading that. Anyways I thought it would be easy to program and it was. I started writing mine in Bash which is definitely NOT the right tool for the job. Adding numbers in Bash is slow, the optimized version takes 20 seconds for the first 6 menu items (37 seconds to display each combination, during debugging). The most simple solution to the problem is to try all of the possibilities. As the number of items grows so does the number of combinations exponentially. Also, having an item that is small in comparison to the total increases the combinations as well.

I started thinking of the optimized way of doing it. That was much more complicated plus the exercise stated that it had to work with multiple data sets (so the loop needed to be dynamic). It didn’t take me long to realize what I wanted to do but doing it was another matter. I had a really hard time trying to make my loop dynamic and to properly count in a optimized fashion. I eventually gave up since it took longer than I thought I should spend on it. I just thought there wasn’t any point of taking so long since even with a larger data set the PHP solution only took 4 seconds. Yet once I started talking to Jordan about why I gave up I got interested again (it also irritated me that I didn’t have a solution anyways). I asked him to make a truth table for me with all the combinations and the values for the first 4 items. Using this helped me out a lot be cause I could see how it should look and then I could visualize it better. You can find the bash solution here. You will also need the text file with the list of items.

The solution relies on sorting the items from smallest to largest. Then the maxes are computed for each item. The first column contains the smallest item so the max would be the number of them equal or less than the total. The next column would be the next highest price item. The max for that column is calculated by having one of the items from that column plus the max number of the smallest items equal or less than the total. Once the maxes are computed it begins by starting with the smallest item adding one to the item count and testing it against the total. At anytime does a combination equal the total it will print it. Once that column goes over the total or the max number of items for that column it adds one to the next highest priced item’s column. When this happens for the first time the max number of items column is shifted to reflect that items computed max.

We are now dealing with two columns. Say we have 3 items in the least priced column and 2 in the next highest price column. The max for my example is 7 items. When we add 1 of the lowest priced item making it 4 the price of all the items goes over the total. So now the least priced item’s column is set to 0 and the next highest priced item is set to 3. This time the same thing happens and the price of the items goes over the total. Since we know that adding anything to those two columns will still go over the total we must increase the 3rd highest priced item to 1 and set the other two back to 0. This jump is what cuts out a large number of possibilities. For each consecutive zero starting with the least priced item is set to that columns max and one more column farther is changed as well. Then on the next count it will increment correctly.

There you have it. I will be creating the optimized version in PHP sometime soon. Jordan has already created the brute force version and I will eventually provide links. I need to test and put limits in place to prevent abuse. The links to the source will be unmodified versions for you to run on your own machines. I computed from the example that there are 45360 combinations and I only had to check 359 of them. All of the other combinations were over the item max or the total price.