Darts Contest

Final Report

If you aren’t familiar with the Darts Contest, you can find a description of it here.

Acknowledgments

I would like to thank two people for helping to make the Darts Contest a success. Dr. Michael W. Ecker allowed the contest to be publicized in REC (his publication of Recreational and Educational Computing) and on REC’s website. John Knoderer allowed MSOWorld’s Programming Contests discussion site to be used for discussion of the Darts Contest.

Results

Congratulations to Mathijs Vogelzang of The Netherlands for having the winning entry, and to Eric Bainville of France for coming in a very close second. Mathijs and Eric swapped positions a few times during the last two weeks of the contest and it ended with Mathijs on top.
Here are the entire contest rankings. I’ve listed only those scores that were needed to determine each person’s position.

  Rank Name Scores
  1. Mathijs Vogelzang 4 8 16 25 37 53 71 94 122 155 187 226 272 324 368 426
  2. Eric Bainville 4 8 16 25 37 53 71 94 122 155 187 226 272 324 368 421
  3. Michael Strauch 4 8 16 25 37 53 71 94 122 155 187 226 272 320 386 431
  4. Ben Glasson 4 8 16 25 37 53 71 94 122 155 187 226 272 320 386 423
  5. Stephen Montgomery-Smith 4 8 16 25 37 53 71 94 122 155 187 226 272 320 380
  6. Ionel Santa 4 8 16 25 37 53 71 94 122 155 187 226 272 319
  7. Frédéric van der Plancke 4 8 16 25 37 53 71 94 122 155 187 226 272 316 372
  8. Greg Galperin 4 8 16 25 37 53 71 94 122 155 187 226 272 316 362
  9. Miroslav Rudisin 4 8 16 25 37 53 71 94 122 155 187 226 272 312
  10. William J. Little 4 8 16 25 37 53 71 94 122 155 187 226 271 320
  11. Alexander B. Alexandrov 4 8 16 25 37 53 71 94 122 155 187 226 271 307
  12. Fred W. Helenius 4 8 16 25 37 53 71 94 122 155 187 226 270 319
  13. Karl Grill 4 8 16 25 37 53 71 94 122 155 187 226 270 318
  14. R.Thirunadha Rao 4 8 16 25 37 53 71 94 122 155 187 226 270 316
  15. Bill Wade 4 8 16 25 37 53 71 94 122 155 187 226 270 312
  16. Myron P. Souris 4 8 16 25 37 53 71 94 122 155 187 226 270 311
  17. Jurgen van Dijk 4 8 16 25 37 53 71 94 122 155 187 226 265 307
  18. Harry J. Smith 4 8 16 25 37 53 71 94 122 155 187 226 265 295
  19. Andrey Nikolaev 4 8 16 25 37 53 71 94 122 155 187 226 264
  20. Spiros Mourgoyiannis 4 8 16 25 37 53 71 94 122 155 187 226 263
  21. Marko Savic 4 8 16 25 37 53 71 94 122 155 187 226 261
  22. Mark Mammel 4 8 16 25 37 53 71 94 122 155 187 226 259
  23. Kálmán Barnabás 4 8 16 25 37 53 71 94 122 155 187 226 257 299
  24. Rob Pratt 4 8 16 25 37 53 71 94 122 155 187 226 257 288 367
  25. Rob Suykerbuyk 4 8 16 25 37 53 71 94 122 155 187 226 257 288 001
  26. Jim Nastos 4 8 16 25 37 53 71 94 122 155 187 226 250
  27. David Pritchard 4 8 16 25 37 53 71 94 122 155 187 225
  28. Kyle Corbin 4 8 16 25 37 53 71 94 122 155 187 223
  29. Tomek Czajka 4 8 16 25 37 53 71 94 122 155 187 222
  30. Daniel Prusa 4 8 16 25 37 53 71 94 122 155 187 221
  31. Max Alekseyev 4 8 16 25 37 53 71 94 122 155 187 219
  32. Yen Nam Thien 4 8 16 25 37 53 71 94 122 155 187 218 257
  33. Alin Sinpalean 4 8 16 25 37 53 71 94 122 155 187 218 253
  34. Vitaly Demyanets 4 8 16 25 37 53 71 94 122 155 187
  35. Stephan Schwebel 4 8 16 25 37 53 71 94 122 155 186 218 252
  36. Jan Stola 4 8 16 25 37 53 71 94 122 155 186 218 244
  37. Alexey Smirnov 4 8 16 25 37 53 71 94 122 155 182
  38. Ravindranath Chowdary J 4 8 16 25 37 53 71 94 122 155 044
  39. kanav 4 8 16 25 37 53 71 94 122 150
  40. Jean-Christophe Filliatre 4 8 16 25 37 53 71 94 122 149 186
  41. Vladimir Namkhoev 4 8 16 25 37 53 71 94 122 149 178
  42. Caetano Arnasalon 4 8 16 25 37 53 71 94 122 148
  43. Tien Nguyen 4 8 16 25 37 53 71 94 122 145
  44. Kevin Burfitt 4 8 16 25 37 53 71 94 122 143
  45. Bob Lodge 4 8 16 25 37 53 71 94 122 127
  46. Alex Cvetkov 4 8 16 25 37 53 71 94 122 124
  47. Oren Hollander 4 8 16 25 37 53 71 94 122 031
  48. Mikhail Gambarian 4 8 16 25 37 53 71 94 118
  49. Richard Malaschitz 4 8 16 25 37 53 71 94 117 155
  50. Tom Yee 4 8 16 25 37 53 71 94 117 150
  51. Wolfram Hinderer 4 8 16 25 37 53 71 94 117 146
  52. Rajgopal Nayak 4 8 16 25 37 53 71 94 115
  53. Derrick Coetzee 4 8 16 25 37 53 71 94 101
  54. Mohamed Saad El Dawy 4 8 16 25 37 53 71 93
  55. Prunescu Remus Mihail 4 8 16 25 37 53 71 91
  56. Robert Newmark 4 8 16 25 37 53 67
  57. Neil Bloomfield 4 8 16 25 37 52
  58. Steve Wentworth 4 8 16 25 37 46
  59. Howard H. Yeager 4 8 15
  60. Sam vanGool 4 8 13
  61. Lukin Evgeni 4 7
  62. Randy Shedden 1
  63. Antonios G. Danalis (Submitted only syntactically incorrect entries)
Statistics

I received a total of 299 entries from 63 participants. Twenty-two countries were represented:

  Australia Israel
  Austria Netherlands
  Belgium Poland
  Canada Romania
  Czech Republic Russia
  Egypt Slovak Republic
  France Ukraine
  Germany United Kingdom
  Greece United States
  Hungary Vietnam
  India Yugoslavia

Below are the best solutions that were received for each N. Prior to this contest the optimal solutions for N = 1 through 12 were available on the web. The solution below for N = 13 is optimal.

N Score Solution First Sent By
1 4 1  
2 8 1, 3  
3 16 1, 4, 5  
4 25 1, 4, 7, 8  
5 37 1, 4, 6, 14, 15  
6 53 1, 3, 7, 9, 19, 24 and 1, 4, 6, 14, 17, 29  
7 71 1, 4, 5, 15, 18, 27, 34  
8 94 1, 3, 6, 10, 24, 26, 39, 41  
9 122 1, 3, 8, 9, 14, 32, 36, 51, 53  
10 155 1, 2, 6, 8, 19, 28, 40, 43, 91, 103  
11 187 1, 2, 3, 8, 11, 26, 38, 56, 69, 85, 89 and
1, 4, 6, 13, 16, 27, 44, 49, 73, 81, 91		  
12 226 1, 3, 8, 13, 15, 16, 49, 53, 84, 88, 108, 114  
13 272 1, 4, 6, 14, 16, 20, 39, 56, 79, 100, 113, 122, 131 Stephen Montgomery-Smith
14 324 1, 2, 4, 9, 15, 27, 38, 43, 46, 97, 107, 127, 147, 157 Eric Bainville
15 386 1, 3, 8, 12, 19, 25, 34, 36, 57, 98, 118, 128, 168, 178, 198 Michael Strauch
16 451 1, 3, 4, 8, 12, 17, 26, 39, 45, 60, 110, 130, 180, 190, 210, 220 Stephen Montgomery-Smith
17 505 1, 2, 6, 8, 19, 24, 27, 33, 45, 75, 105, 135, 145, 155, 320, 330, 340 Stephen Montgomery-Smith
18 595 1, 2, 6, 8, 19, 24, 27, 33, 45, 75, 105, 135, 165, 175, 185, 380, 390, 400 Stephen Montgomery-Smith
19 685 1, 2, 6, 8, 19, 24, 27, 33, 45, 75, 105, 135, 165, 195, 205, 215, 440, 450, 460 Stephen Montgomery-Smith
20 775 1, 2, 6, 8, 19, 24, 27, 33, 45, 75, 105, 135, 165, 195, 225, 235, 245, 500, 510, 520 Stephen Montgomery-Smith
21 865 1, 2, 6, 8, 19, 24, 27, 33, 45, 75, 105, 135, 165, 195, 225, 255, 265, 275, 560, 570, 580 Stephen Montgomery-Smith
22 955 1, 2, 6, 8, 19, 24, 27, 33, 45, 75, 105, 135, 165, 195, 225, 255, 285, 295, 305, 620, 630, 640 Stephen Montgomery-Smith
23 1045 1, 2, 6, 8, 19, 24, 27, 33, 45, 75, 105, 135, 165, 195, 225, 255, 285, 315, 325, 335, 680, 690, 700 Stephen Montgomery-Smith
24 1135 1, 2, 6, 8, 19, 24, 27, 33, 45, 75, 105, 135, 165, 195, 225, 255, 285, 315, 345, 355, 365, 740, 750, 760 Stephen Montgomery-Smith
25 1225 1, 2, 6, 8, 19, 24, 27, 33, 45, 75, 105, 135, 165, 195, 225, 255, 285, 315, 345, 375, 385, 395, 800, 810, 820 Stephen Montgomery-Smith
Origins of the Darts Problem

The Darts Problem has been around for at least 30 years. The earliest reference I’ve personally seen was a 1969 research paper in which the problem was expressed in terms of postage stamp denominations rather than dart board regions. That paper had references to even earlier papers. The notion of using dart board regions comes from Tim Edmond’s excellent Primrose Puzzles site.

What’s Next?

Even though the contest has ended, some of you may wish to continue working on the problem. Some of you may want to contact others to ask them about their algorithms or computing power. To satisfy such interests, I've set up a discussion site where interested parties can keep in touch.

Regards to all,
Al Zimmermann

Darts Contest Description — Al Zimmermann's Programming Contests