Dice_Coding_Challenge_Icon_245x140_ScreenRes.jpg
Thank you to everybody who entered our first Coding Challenge: Prove Your Factorial Fluency. We received a total of 61 entries, from 58 individuals -- three players submitted extra entries in different languages, and I treated each one as a separate entry. Dice Coding Challenge Winner BadgeC++ proved to be the fastest language, with eight of the nine fastest programs written in it. The author of one of them, Rick Matter, proved that Java could be fast as well: His Java entry took 0.00000007706 of a second, not much longer than the 0.000000068845 of a second that it took his C++ version. The one exception to the top nine programs: The one with second fastest time, which was written in C. C wasn't the only unusual programming language: Tom Gauthier provided a VBA Module, which ran in an Excel spreadsheet and tracked all the numbers in the series. It took 0.00001139 of a second, making it the 37th fastest. The fastest time was zero, i.e., too small to measure. And no, it wasn't a statement like:
cout << 752184639 << endl;
Three entrants got a zero time: Thierry Seegers used Template metaprogramming to work out the answer while it compiled. The other two zero-time entrants (Karl Anderson and Steven Heithoff) both figured out an extremely quick method to solve it, which I'll attempt to explain: There are 9! nine-digit numbers. 9! is mathematical notation for 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2. The factorial of a whole number is itself multiplied by itself -1 * itself -2 ... all the way down to x 2. We don't worry about multiplying by 1. Putting it slightly differently, there are 8! unique nine-digit numbers that use each digit only once and start with any given number. So, there are 8! of them that start with 1, 8! that start with 2, 8! that start with 3, etc. The value of 8! is 40,320. So starting at the largest possible number, we can forget the first 40,320 numbers that start with 9 and likewise the next with 8, because 80,640 is still less than 100,000. 120,960 (40,320 * 3) is not less than 100,000, so we know that the 100,000th number must start with a 7. There are 7! (which equals 5,040) of those that have a 1 next, 7! that have a 2 next, etc. After skipping the first 80,640 numbers in the sequence (those that started with an 8 or 9), there are 20,960 numbers that start with 7 before the one we want. So the first 7! (5,040) of these numbers start with a 71, the next 5,040 start 72 and you can see that we can skip the 73s and 74s as well. The number must start with 75. Now repeat this for each successive digit. For the third place there are 6! (or 720) numbers that start with 751, 720 with 752, etc. Eliminating the numbers that start with 71, 72, 73, and 74 eliminates 20,160 more numbers (4 x 5,040 = 20,160). That means there are 800 that start with 75 before the one we want (20,960 – 20,160 = 800). The first 720 numbers after that start with 751, so the 100,000th number must start with 752. You can repeat this reduction very rapidly to find the answer: 752,184,639. Fifty eight of the 61 entries got that answer. Both Karl and Steven used this method to get the answer is no time. The next fastest time was Robert Rodriguez's C program, which did it in 1.241 nanoseconds, and then John Sandberg's C++ in 1.270 nanoseconds. A nano second is a thousand millionth of a second, so these two differed by 310 thousand millionths of a second -- a very small time indeed! Karl's program is actually one of the most lovely, if not cryptic, so I'm showing part of it here:
		F(1), F(2), F(3), F(4), F(5), F(6), F(7), F(8), F(9);
		A(1,2), A(1,3), A(1,4), A(1,5), A(1,6), A(1,7), A(1,8), A(1,9);
		A(2,3), A(2,4), A(2,5), A(2,6), A(2,7), A(2,8), A(2,9);
		A(3,4), A(3,5), A(3,6), A(3,7), A(3,8), A(3,9);
		A(4,5), A(4,6), A(4,7), A(4,8), A(4,9);
		A(5,6), A(5,7), A(5,8), A(5,9);
		A(6,7), A(6,8), A(6,9);
		A(7,8), A(7,9);
		A(8,9);
		D(9), D(8), D(7), D(6), D(5), D(4), D(3), D(2), D(1);
Yes, that is code. It uses #define macros.

Results

Note, positions 1-3 are joint winners.
  1. Steven Heithoff (C++) Time = 0
  2. Karl Anderson (C++) Time = 0
  3. Thierry Seegers (C++) Time = 0
  4. Robert Rodriguez (C) Time = 0.00000000124107
  5. John Sandberg (C++) Time = 0.00000000127
  6. Sandeep Desai (C++) Time = 0.000000002477237
  7. Richard Vasquez (C++) Time = 0.00000005
  8. Anil Guchait (C++) Time = 0.0000000535787
  9. Rick Matter (C++) Time = 0.0000000688453
  10. Rick Matter (Java) Time = 0.00000007706
  11. Krassimir Emilov (C) Time = 0.0000001
  12. Yuriy Kachanov (C++) Time = 0.000000125388
  13. Rob Polocz (Java) Time = 0.00000014
  14. Heithoff (Java) Time = 0.00000016044
  15. Aliaksei Sanko (C++) Time = 0.000000192072
  16. Jozsef Hollosi (C) Time = 0.00000025
  17. Richard Kendall Wolf (C++) Time = 0.00000026
  18. Volodmyr Tkachyshyn (C++) Time = 0.000000266516
  19. Michael Gould (Java) Time = 3.04346625164339E-07
  20. Majid Darabi (Java) Time = 0.000000343
  21. Tim Wiant (C++) Time = 0.0000003949
  22. Dean Giles (C++) Time = 0.00000045
  23. Vasan (Java) Time = 0.000000474
  24. Matthew Yin (C++) Time = 0.000000474994
  25. J G (C#) Time = 0.000000485653
  26. Brendan van der Es (Java) Time = 5.48781395760869E-07
  27. Richard Lerner (C#) Time = 8.13491166786633E-07
  28. Dave Giusto (C#) Time = 0.00000088662909
  29. Jay Nagel (Java) Time = 0.000001
  30. Xueyang Han (Java) Time = 1.00571428571428E-06
  31. Brent Hauble (C#) Time = 0.0000012385
  32. Robert Linden (Java) Time = 2.01819687026102E-06
  33. Andreas Falkenberg (Java) Time = 0.000003614
  34. Marina Stolyar (C#) Time = 7.0316440696649E-06
  35. Joseph Brown (C#) Time = 0.0000078
  36. Deepak Kejrwal (Java) Time = 0.0000102
  37. Tom Gauthier (VBA) Time = 1.13900405485444E-05
  38. Satiesh Kumar (Java) Time = 0.0000241473456
  39. Teresa Carrigan (Java) Time = 0.000051
  40. David Lotts (Java) Time = 0.000291
  41. Punith Kumar (C) Time = 0.001
  42. John Yurina (C++) Time = 0.00101641
  43. Farjad-H (Java) Time = 0.001259688
  44. Janusz Szpilewski (C++) Time = 0.00159618
  45. Hussain Rangwala (Java) Time = 0.0030335
  46. Namit Swaroop (C#) Time = 0.00400002
  47. Ian Heneway (C++) Time = 0.0250957
  48. Ryan B Fore (C) Time = 0.18829
  49. John Lujan (Java) Time = 1.197
  50. Vignesh Kumar (Java) Time = 1.491
  51. Bill Waugh (C#) Time = 1.958796
  52. Bill Waugh (C++) Time = 2.21507
  53. Allesandro Rossi (Java) Time = 3
  54. Ramesh Kapa (Java) Time = 5.738
  55. Benjamin Thompson (Java) Time = 8.794173
  56. Joel Harvell (C#) Time = 23.0840523
I'll put the source code with the correct results on SourceForge over the weekend. Thanks once again to everyone that entered and commiserations to these five who didn’t get the correct answer: Michael Tingey, Tom Jill, Nathan Pfluger, Don Taylor and John Philip Britt.