Objective
25 years ago, a British computer magazine had a programming contest and this was one of the puzzles.There are a large number of 9 digit integers in the range 123456789 to 987654321 where each digit only appears once. What is the 100,000th number in this sequence?
Example
The first number is 123456789, the second is 123456798, the third is 123456879 and so on. No digit can repeat so 122345675 is not a valid number in this sequence.The problem was "Write a program in Ansi C, C++ or C# 2.0 (C# 1.0 is allowed) that outputs the 100,000th number as fast as possible. Use any algorithm, except you cannot pre-calculate the answer and then write a program that just prints the result. Your entry must calculate the number!". This ran through June 2007
Results
The correct answer was 358926471. All entrants, ranked by processing speed are listed below and you can download the ten fastest. Apologies if I have upset the code's appearance by adding in timing and looping code. The links below take you to articles on adding high resolution timing.The timing was done by adding the appropriate timing code and running on the same computer which was a three year old twin 3 GHZ Pentium running Windows XP/SP 2 with 1.25 GB of ram.
Name/Country Age Time (Secs)
- 1 Brent Edwards (USA) 0.00000050521
- 2 Neil McCoy (Australia) 0.00000059442
- 3 Dan Moinescu 0.000000735
- 4 Sattar Sattari (Iran) 0.00000076792
- 5 Richard Collins (USA) 0.00000277959
- 6 Domaniç Lavery (England) 20 0.00000362433
- 7 José Ricardo Ziviani 0.00000380989
- 8 Nikhil Dhume (India,28) 0.0000134448
- 9 Mindaugas Mozuras (Lithunia,19) 0.000015481
- 10 Mohammad M. Motieian (Canada,23) 23 0.0000184903
- 11 Ian Wells 0.000284
- 12 Dan Wahl and Lee-kai Wang (USA) 0.000303288
- 13 Yanjiang Qian (China) 0.00044
- 14 Paul Martin (UK,21) 0.0156593
- 15 Çëéáò Ôóéôóéìðçò (Greece) 0.0209068
- 16 Raghuram Duraisamy (India,19) 0.05499
- 17 indra jadab(India) 0.08406
- 18 Renelou Esperanzate (Philippines,22) 3.1475193
- 19 prasanna regunathan (India) 4.36872
- 20 Johannes Dahlström (Finland,23) 4.00
- 21 Rajesh Subramanian (India,23) 47.79557
- 22 Daniel Souza (USA) 60.32082
- 23 Corinna Schmidt (USA,18) 172.56
- 24 Harshil B. Patel (India,23) 600
- 25 Varun Modi* (India,22) N/A
- 26 Avinash Joshi N/A
- 26 Senthil Cholan N/A
- 26 Michel van der Wal (The Netherlands) N/A
- 26 Eddie S.*(Israel) N/A
- 26 long hong* N/A
- 26 Tokhir Dadaev (27) N/A
- 26 Caspar de Haes* N/A
- 26 Gene Romig* (USA) N/A
I've ranked everyone who got the wrong answer or no answer at joint 26th. If there is a * by your name, your code generated the wrong number.
Johannes Dahlström had the potentially fastest version as he provided several, including a template metaprogramming solution which would have solved it at compile time (and a runtime of nearly 0!), only it wouldn't compile with the compilers I used.
If you have a problem with the timing of your entry, please write to me at the usual address cplus.guide@about.com?subject=Programming Challenge 1
Notes
I compiled every C or C++ entry in a project in Microsoft Visual C++ version 6. The C# entries were compiled with Microsoft Visual C# 2005 Express Edition.After running and noting the result, I moved the fast executing code into a loop, added timing code and ran it, and checked that it still produced the correct answer. The loops ran typically a million times for the fastest entries, less for the slower ones.
Thanks once again to everyone that wrote code and submitted it. Life is full of challenges- here are some more!
More Programming Challenges
- Link to Rock, Scissors and Paper Bot Ongoing Programming Challenge - Runs weekly until 2008.
- Link to Programming Challenge 2 - Count the Islands. (Finished)
- Link to Programming Challenge 3 - Manage Elevators. (Finished)
- Link to Programming Challenge 4 - Guess the Mastermind Code - (Deadline September 30 2007)
