Hi,
Here's the puzzle (translated from Dutch):
Given that:
KERST = REKENEN + MET * TIEN - LETTERS
Each letter represents a single unique digit (0..9)
- What is the value of MINSTREEL
- REKENLES can be 2 different numbers: what is the product of these two?
(The first sentence translates to: Christmas = Calculating + With * Ten - Characters)
Can you come up with the fastest algorithm to solve this problem?
Rules:- You can use the following standard libraries:
- SysUtils
- Math
- Standard library used to enable threads on your current OS
- You may also use any library you want to visually enhance your program if you wish to do so.
- The program must be cross-platform and compilable with fpc 3.0.4. I must be able to test the program on my Win10 machine.
- The use of (inline) assembly is not allowed.
- The use of compiler directives other than {$mode }, {$H} or conditional defines to use standard threading libraries is not allowed.
The code displaying the result should be (expected to be executed twice):
write('K=',K);
write(', E=',E);
write(', R=',R);
write(', S=',S);
write(', T=',T);
write(', N=',N);
write(', M=',M);
write(', I=',I);
write(', L=',L);
write(' MINSTREEL=',M,I,N,S,T,R,E,E,L,', ');
writeln('REKENLES=',R,E,K,E,N,L,E,S);
And the code to display the product of the 2 values for REKENLES should be (executed only once):
writeln(VarForFirst_REKENLES,' * ',VarForSecond_REKENLES,' = ',YourValueForTheProduct);
Reason: the displaying is part of the timing.
As a proof that I have actually solved this puzzle I give you the expected output for the final calculation:
?? * ?? = 1196530768447364
My current solution uses 203 ticks (measured with GetTickCount from start of program to writing down the last calculation).
Speed comparison will be done on my machine, with the exact same compiler options for each program
(this happens to be: -MObjFPC -Scghi -O3 -OoREGVAR -Xs -XX -l -vewnhibq -Filib\i386-win32 -Fu. -FUlib\i386-win32 -FE.), using fpc 3.0.4 32-bit on Win10-64.
Trying several approaches I found that elegant code is not necessarily faster than ugly, seemingly clumsy, code.
Note: a program simply outputting the correct results (after another program calculated it) will not do.
The algorithm for solving the puzzle must be a part of the program (and this part
must executed).
I'll keep track of the 5 fastest solutions here.
Ticks are in GetTickCount units.
Note: very fast algorithms are timed over 1000 or 10000 iterations. In that case all writing to console is commented out.
Scores (2018-12-21 19:00 CET):- Martin_fr: 0.0006 ticks (a whooping 573000 times faster than my original code)
- Avk (avk's third entry): 0.0014 ticks
- Engkin: 0.5342 ticks
- Blaazen (second entry): 38 ticks
- User137: 159 ticks
Prizes:The first and only price will be: eternal fame.
As I am not supposed (nor expected) to win: please beat me...
Eternal fame goes to Martin_fr!(No more submissions are excepted for the contest as of 20018-12-26 23:59 CET.)Bart