Programming Puzzle #3 Solutions

It's in that spirit that I am presenting Python code submitted by David Farrell.

1. import random
2. data = [-50,-21,13,171,14,-42,-58,109,4,7,-23,-44,-98,-121,101,
3. 33,87,-121,-40,-65,43,54,-45,-12,-12,38,25,3,7,8]
4. subdata = [-1]
5. while sum(subdata) != 0:
6. subdata = random.sample(data, 9)
7. print subdata
8. View this file Here (Right Click and save As)

The next solution I received was from Josh, and was in complete contrast to the above, in that it was C++ and generated a solution in less than a milisecond. View Joshs C++ solution. Immediately after came the first of the Java offerings from Reinier, who stated correctly that the problem was obviously NP Hard (we'll come back to that later). View Reineirs Java solution.

The first of the "truly alternative" solutions was a Scheme solution from Bendick, which uses memoization, and returns pretty quickly. You can view Bendicks Scheme solution here.

Comments broke for a short while, due to the Akismet Spam Protector going on holiday, and in this gap I recieved 4 more solutions. Cameron offered this well written and well commented ML solution, Dmitry followed that up with a Perl solution, Taylor chimed in with with a less random Python solution than Davids, and finally I received an Erlang solution from Jason. Now, about that P or NP issue...

The most common misconceptions about P and NP

I am including this mainly the majority of the programming world illustrate fragile knowledge about P and NP, in that they think they understand, and are usually incorrect. It's far better off to know you don't understand P and NP, than to merely think you do.

1. NP does not mean Not Possible

2. NP does not mean that the solution is Non Polynomial

3. Proving a problem is NP does not mean that code doesn't exist to solve it. I've seen a lot of people realise that a problem is NP, and then back away thinking there is no practical solution to the problem.

Informally NP problems are ones where you can check if a solution is correct, in polynomial time, but the best known solutions are not significantly faster than a brute force approach. For example, it's much much easier to verify a solution to the Subset Sum problem, than it is to find one. It's much easier to check that a given traversal of a graph sums up to X, than it is to find that traversal. It's far easier to verify that a given ordering of tasks will finish in X amount of time, than it is to find that particular ordering. Thats why the Subset Problem, the Travelling Salesman problem, and Scheduling are said to be NP. Whether P = NP or not is a different problem, one so famous it was once featured on the Simpsons.

Thanks to everyone for their solutions, I think I'll let Steve take a break now and move onto a new character and genre of programming problems. Keep reading

Related Links

• Subset Sum The problem featured in this entry.
• NP if you program, you should learn it.
• Dmitrys post about Steve and his gambling.
• Learn about P and NP and win yourself $1,000,000