Coding Challenge Results: The Most Factorially Fluent

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.

Comments

  1. BY John S. says:

    Thanks for the awesome contest and congratulations to the three winners. Alas, I would have had “0″ time if I didn’t over-engineer my timing loop. Live and learn! I hope that Dice.com has future contests like this one. This was a lot of fun.

  2. BY John Garrard says:

    Just as a note, I know my e-mail address’s associated name is just J G, but could I get my full name in there (It should also lead off the comments in the file). While I didn’t win overall I did do the best for my language choice, so I might use that for interview fodder. :)

  3. BY John Munson says:

    That’s a cool algorithm, but it looks like your explanation of it is incorrect and it was just a coincidence that the explanation came up with the correct first three digits. It goes wrong after picking the fourth digit.

    The explanation of the first digit (7) is fine — there are 80,640 ( 100,000) starting with 9, 8, or 7, so the 100,000th number falls in that range of numbers starting with a 7.

    But then things get weird. The explanation says:
    “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.”
    But that’s not correct. It appears that you got 20,960 by counting the *excess* numbers beyond 100,000 up to 120,960 (40,320 * 3). What we need to do is count the *remaining* numbers, from the 80,640 we’ve already used, up to 100,000, which is 19,359 before the one we want.

    The explanation then takes another strange turn by switching from ordering the numbers in *descending* order, as given in the problem, to *ascending* order:
    “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.”
    Actually, we skip…
    - the 5,040 that start with 79
    - the 5,040 that start with 78
    - the 5,040 that start with 76
    … leaving out those that start with 77 since we can’t reuse a digit. Thus, the second digit is 5.

    So, we skipped 80,640 on the first digit and 15,120 (5,040 * 3) on the second digit, leaving another 4,240 to get up to 100,000. We now skip 3,600 of those (6! = 720 for each of 759, 758, 756, 754, and 753), making the third digit 2. And so on.

    How does that sound?

    • BY John Munson says:

      I just noticed that the second paragraph of my comment on November 28 got mangled because I used a less-than sign followed a bit later by a greater-than sign and they apparently got interpreted as tag delimiters, and thus the intervening text got swallowed up. It’d be nice if there was a warning that comments will be interpreted as HTML.

      Anyway, here’s my original text, using “less than” and “greater than” instead:

      “The explanation of the first digit (7) is fine — there are 80,640 (less than 100,000) numbers starting with 9 or 8, but 120,960 (greater than 100,000) starting with 9, 8, or 7, so the 100,000th number falls in that range of numbers starting with a 7.”

  4. BY Lubo Antonov says:

    It seems to me that if a solution uses template metaprogramming then you should include the compile time in the evaluation to make it fair. Otherwise, solutions that simply print out the correct answer should be acceptable.

  5. BY Anonymous says:

    Nothing takes zero time. Just by figuring some clever way to do the computation in the compile phase instead of the execution phase doesn’t mean that you’re computer didn’t spend processing time executing the computation and therefore is essentially:

    String ret = compute() //Only done in compile phase
    long startTime = ‘current time’
    cout << ret << 'current time' – startTime;

    Which is cheating. Regardless, this still takes time even if the resolution is not enough to show it.

  6. BY Richard Vasquez says:

    Hm. This is a tough one. The rules did say “Speed is the criteria for winning, so we’re looking for the fastest correct answer.”, so the letter of the rule was met, but I’d definitely say the spirit was not met. What’s done is done, and it’s time to move on. I wouldn’t have won anyway, being 4th (taking away the top 3), so I hope that doesn’t sound like sour grapes.

    I do have a suggestion though as to how to make this a bit more realistic the next round. Provide the problem, require the program to take an arbitrary legitimate value via stdin, then output the correct answer only, via stdout.

    I’m going to use this original contest as the basis for my example. We need to find element n (index 1 based) in the reverse lexicographic order of numeric representations of 9!. The following are correct examples for various values of n:

    1: 987 654 321
    10: 987 653 214
    100: 987 615 324
    1,000: 986 452 317
    10,000: 971 264 538
    100,000: 752 184 639
    362,880: 123 456 789

    Having provided the correct data, when the programs are submitted, you run them with a set of predetermined inputs (different from the examples provided) from one input file, send stdout to another file, and compare the results with a master “answer” file.

    As it is, I’ll tip my hat to the C++ template metaprogramming, as it’s a powerful tool, and I’ve seen some interesting results from it, but as said above, the computation time involved during compilation is actual time spent. Using a stdin/stdout format would eliminate that time from all entries and result in a measurement of time used to calculate a general problem in all of its legitimate formats.

    • BY John Munson says:

      Richard, I think that’s an excellent suggestion to use stdin/stdout. It takes the problem farther away from the toy-problem world.

      It should be pointed out, though, that your revised problem statement isn’t correct. We’re not looking for “numeric representations of 9!” — there’s only one numeric representation of 9! (okay, in decimal anyway!), and it’s 362,880. We’re looking for numbers that contain exactly one occurrence of each digit from 1 to 9 (inclusive).

      • BY Richard Vasquez says:

        Ok… That was a bit pedantic, but correct. I misstated the problem description while typing in stream of thought mode. I’d assumed that since the contest was done, those of us who had participated would know what I meant based on the actual contest.

        How’s this?

        Given the set of distinct numbers {1, 2, 3, 4, 5, 6, 7, 8, 9}, there exist 9! (362,880) distinct permutations. These permutations can be arranged in reverse lexicographical order with the following example input of n (index 1 based) results in the following value (comma formatted input value, colon, and spaces added for clarity) Actual output should only consist of a single line followed by 9 distinct numbers and a CRLF with no additional spaces.

        [insert my previous list here]

        Is that clearer?

        • BY John Munson says:

          I was merely suggesting replacing “numeric representations of 9!” with “numbers that contain exactly one occurrence of each digit from 1 to 9 (inclusive)” — then you’re all set. :-)

          You’re right that those who had participated would know what you meant. But, pedantic or not, I wanted to avoid confusion among people who might be jumping into this in the middle, because that’s kind of what happened to me. I didn’t know about this contest until I saw this article giving the results, and as I read it, I realized that there was no way to understand it without going to the original article stating the problem. And that’s totally reasonable. But you never know when people are going to run into things out of context, so I didn’t want newcomers to get confused by an incorrect restatement of the problem.

      • BY Richard Vasquez says:

        Or better yet:

        {val[n] | val[n] = [numeric]{res| res = [sigma][n] * {x | x [element of] *N*, x [less than] 10, x[9] [greater than] x[2], …, x[8] [greater than] x[9]}[1] [concatenate] … [concatenate] {x | x [element of] *N*, x [less than] 10, x[9] [greater than] x[2], …, x[8] [greater than] x[9]}[9]} > val[n + 1]}

        Given an n, return val[n].

        I think I have all the braces there, and I had to put braces around symbols/operations to avoid HTML issues.

    • BY Thomas, The Mischievious Optimizer says:

      I knew the fastest program would be made by someone who got the compiler to optimize everything out… and should have submitted the “cout << 752184639 << endl;" solution… XD

    • My solution is the general solution. So I tried with small numbers 1,2,3 etc. and then 100000. Once it worked I did not spend extra time to optimize. So I am happy that the result is correct. I guess there are some of the slower results which do the general calculation.

    • BY Thierry Seegers says:

      I used the very expression “follows the letter but violates the spirit” in my submission e-mail to Mr. Bolton. At best, I was expecting an “honorable mention for a creative approach” and after the update of October 30th listed only run-time computation results, I figured I had been plainly and summarily disqualified! :)

      I agree with you that, in the future, forcing the problems’ variables to be gathered at run-time will prevent entries like mine (if that’s desired) and make things less ambiguous.

      Also, just to make it crystal clear in case anybody is wondering, my solution is not hard-coded to “987654321″ and “100000″. It can take any input. I was just taking advantage of the fact that, as the problem was stated, the inputs were known by the programmer.

      And while I’m at it, I’ll point out that template metaprogramming in C++ for the purpose of compile-time computation may soon be a thing of the past with the upcoming loosening up of the restrictions imposed on the “constexpr” keyword. It is possible that, in the near future, the run-time solutions submitted for this challenge can be turned into both compile-time and run-time code just by adding “constexpr” to their functions’ signature. Pretty cool!

      • BY Richard Vasquez says:

        You said your solution is more open ended, or at least not hard coded. I’m definitely interested in seeing it (and the rest of the competition) when David puts code on Sourceforge. I’m always open to learning something new, although I’ll admit when a buddy of mine showed me how to generate factorials proper using templates, I kind of snapped a synapse or a dozen at the time.

        I’ll admit to not keeping up with C++ beyond the point where I can pull it out when I need to crank up some speed, which I did with this one in my travel from C# to C++ and then reading some papers to drop it to what I thought was bare metal. I doubt I’ll ever be a C++ guru, but it’s nice to know I can pull out the tools and be competent.

        I suppose after I pick up some more Clojure, I’ll take a look at what’s going on with C++ with the new standards, and check out the constexpr keyword you mentioned and what impact it may have. It may be a while, though. Functional programming seems insane in some ways, and the rent’s paid with C#, so time’s not always available.

        Anyway, after rambling a bit (sleep dep does that to me), I don’t want to forget to congratulate you. And I’ll try to get you and your little dog Toto, too, next time. :)

  7. BY Rick Matter says:

    Thanks to David Bolton for running this fun competition! Let’s hope he runs more of these in the future. It could not have been easy to test 60 entries using various languages.

    I will defer to his judgement as to the winning entries. While the first three probably were not zero-time if they had printed out the results, they were probably very close to zero-time.

  8. BY Martin Palmeri says:

    Hey, Everyone who scored in the top 20 on the Java & C++ test send me your resume for a few open jobs I am trying to fill OR I will tell your boss you took the test on company time!!

    • BY F.W. St John says:

      Martin,

      Why is there a purple squirrel on your “Available Candidates” list?

  9. BY Richard Vasquez says:

    So, while we’re waiting for David to post everyone’s entries on SourceForge, I’d like to throw out the idea of us going ahead and showing off on our own.

    I threw out a Gist on GitHub after the results were posted, and it’s at https://gist.github.com/RichardVasquez/7735635

    No laughing allowed. :)

    Maybe others could post a URL of their code as well?

    As for Martin… I’m speechless. Yeah, that covers it, I think.

Post a Comment

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>