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.

C++ 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.

- Steven Heithoff (C++) Time = 0
- Karl Anderson (C++) Time = 0
- Thierry Seegers (C++) Time = 0
- Robert Rodriguez (C) Time = 0.00000000124107
- John Sandberg (C++) Time = 0.00000000127
- Sandeep Desai (C++) Time = 0.000000002477237
- Richard Vasquez (C++) Time = 0.00000005
- Anil Guchait (C++) Time = 0.0000000535787
- Rick Matter (C++) Time = 0.0000000688453
- Rick Matter (Java) Time = 0.00000007706
- Krassimir Emilov (C) Time = 0.0000001
- Yuriy Kachanov (C++) Time = 0.000000125388
- Rob Polocz (Java) Time = 0.00000014
- Heithoff (Java) Time = 0.00000016044
- Aliaksei Sanko (C++) Time = 0.000000192072
- Jozsef Hollosi (C) Time = 0.00000025
- Richard Kendall Wolf (C++) Time = 0.00000026
- Volodmyr Tkachyshyn (C++) Time = 0.000000266516
- Michael Gould (Java) Time = 3.04346625164339E-07
- Majid Darabi (Java) Time = 0.000000343
- Tim Wiant (C++) Time = 0.0000003949
- Dean Giles (C++) Time = 0.00000045
- Vasan (Java) Time = 0.000000474
- Matthew Yin (C++) Time = 0.000000474994
- J G (C#) Time = 0.000000485653
- Brendan van der Es (Java) Time = 5.48781395760869E-07
- Richard Lerner (C#) Time = 8.13491166786633E-07
- Dave Giusto (C#) Time = 0.00000088662909
- Jay Nagel (Java) Time = 0.000001
- Xueyang Han (Java) Time = 1.00571428571428E-06
- Brent Hauble (C#) Time = 0.0000012385
- Robert Linden (Java) Time = 2.01819687026102E-06
- Andreas Falkenberg (Java) Time = 0.000003614
- Marina Stolyar (C#) Time = 7.0316440696649E-06
- Joseph Brown (C#) Time = 0.0000078
- Deepak Kejrwal (Java) Time = 0.0000102
- Tom Gauthier (VBA) Time = 1.13900405485444E-05
- Satiesh Kumar (Java) Time = 0.0000241473456
- Teresa Carrigan (Java) Time = 0.000051
- David Lotts (Java) Time = 0.000291
- Punith Kumar (C) Time = 0.001
- John Yurina (C++) Time = 0.00101641
- Farjad-H (Java) Time = 0.001259688
- Janusz Szpilewski (C++) Time = 0.00159618
- Hussain Rangwala (Java) Time = 0.0030335
- Namit Swaroop (C#) Time = 0.00400002
- Ian Heneway (C++) Time = 0.0250957
- Ryan B Fore (C) Time = 0.18829
- John Lujan (Java) Time = 1.197
- Vignesh Kumar (Java) Time = 1.491
- Bill Waugh (C#) Time = 1.958796
- Bill Waugh (C++) Time = 2.21507
- Allesandro Rossi (Java) Time = 3
- Ramesh Kapa (Java) Time = 5.738
- Benjamin Thompson (Java) Time = 8.794173
- 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.

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.

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. 🙂

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?

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.”

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.

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.

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.

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).

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?

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.

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.

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.

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!

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. 🙂

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.

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!!

Martin,

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

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.