Final Report
If you aren’t familiar with the Darts Contest, you can find a description of it here.
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.
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) |
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 |
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.
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