Son Of Darts

Another thing I’ve been very busy with lately is AZsPCs (Al Zimmermanns Programming Competition). The current contest is called Son of Darts.

The idea behind these contests are that they are easy to grasp, but very hard to master.

Lets take three darts. You have to throw them to a dartboard which is divided into 4 regions. For example, the values on these regions are: 1,2,4,6.
The first question is: What is the lowest value you can’t throw with these three darts?

This is easy to calculate:
Can we throw one? Yes: 1 dart in the 1
Can we throw two? Yes: 1 dart in the 2, or 2 darts in the 1
etc etc
Can we throw nine? Yes: 6,2,1
Can we throw ten? Yes: 6,4
Can we throw eleven? Yes: 6,4,1
Can we throw twelve? Yes: 6,6
Can we throw thirteen? Yes: 6,6,1
Can we throw fourteen? Yes: 6,6,2
Can we throw fifteen? Err… no, sorry…

So the score is: 15 points.

The main question: Can you think of better values for the regions of the dartboard to get a higher topscore??

This is what the competition is about. But not only for a dartboard consisting of 4 regions, but up to 40 regions. And not only for three darts, but also 4, 5 and even 6 darts.

If you can create a good solver its pretty easy to bruteforce up to a certain point, but the problem is, you quickly get more and more options for which you have to check the scores… It is an exponential function…!

Actually, this is not a new puzzle. Its been around of quite a long time. But its more commenly known as the local postage stamp problem (LPSP). Formulated just a little bit different, instead of a dartboard with regions you have a postcard with room for H stamps. What is the lowest value you can’t create with stamps Nh? Also check out Wolfram’s description of the problem.

This problem has been proven to be NP-hard, so bruteforcing won’t be an option, you’ll need to use something different. Put on your thinking-caps and create some good innovative heuristics.