Contest: fastest program to solve a christmas puzzle

[engkin]

I did not code it yet, but I believe it should be faster. Let's see.

[VTwin]

I did not code it yet, but I believe it should be faster. Let's see.

I'd be tempted to jump in, but I think I've already been smoked.

[engkin]

I did not code it yet, but I believe it should be faster. Let's see.

I'd be tempted to jump in, but I think I've already been smoked.

I am pretty sure you'd beat us all.

[engkin]

I switched to using CPU ticks for timing. The results after disabling output to console:

My first solution takes:
1763 CPU ticks.

The nearest solution is the one presented by avk. It takes:
1486348 CPU ticks.

Ratio 1486348/1763 ~ 800 times slower.

@Bart, can you please update the first post with the results on your side so far.

[Bart]

@Bart, can you please update the first post with the results on your side so far.

I'll do so once my testing is complete.
(Testing requires altering source code by hand (not the algoritm, but inserting timing code and an outer loop around the algorithm, and disabling console output. All this because you are too fast, and I did not expect you to use Goto to jump out of the loop.)
How do I count CPU ticks (on Windows that is)?

Bart

[avk]

@Thaddy: yes, set is about 15% faster.
@Bart: I use

Code: Pascal  [Select][+][-]

1. {$ASMMODE INTEL}
2. function CPUClocks: QWord; assembler; nostackframe;
3. asm
4.   rdtscp
5. {$IFDEF CPUAMD64}
6.   shl rdx, 32
7.   or  rax, rdx
8. {$ENDIF}
9. end;
10.  

I also have another solution 

Code: Pascal  [Select][+][-]

1. program pazzle;
2.  
3. {$mode objfpc}{$B-}
4.  
5. uses
6.   SysUtils;
7.  
8. type
9.   TDigit = 0..9;
10.  
11. procedure Solve;
12. var
13.   State: set of TDigit;
14.   E, I, K, L, M, N, R, S, T, Count: TDigit;
15.   EN, ET, ST, RS, TERS, ENEN, METTIEN, ERST, KENEN, TTERS, KERST: Integer;
16.   REKENLES1, REKENLES2: Int64;
17.  
18.   function TrueMod10: Boolean;
19.   begin
20.     Result := (10 - Integer(S) + Integer(N) * Succ(Integer(T))) mod 10 = T;
21.   end;
22.   function TrueMod100: Boolean;
23.   begin
24.     RS := Integer(R) * 10 + S;
25.     EN := Integer(E) * 10 + N;
26.     ST := Integer(S) * 10 + T;
27.     ET := Integer(E) * 10 + T;
28.     Result := (100 - RS + EN + EN * ET) mod 100 = ST;
29.   end;
30.   function TrueMod10000: Boolean;
31.   begin
32.     TERS := Integer(T) * 1000 + Integer(E) * 100 + RS;
33.     ENEN := EN * 100 + EN;
34.     METTIEN := (Integer(M) * 100 + ET) * (Integer(T) * 1000 + Integer(I) * 100 + EN);
35.     ERST := Integer(E) * 1000 + Integer(R) * 100 + ST;
36.     Result := (10000 - TERS + ENEN + METTIEN) mod 10000 = ERST;
37.   end;
38.   function TrueMod100000: Boolean;
39.   begin
40.     TTERS := T * 10000 + TERS;
41.     KENEN := Integer(K) * 10000 + ENEN;
42.     KERST := Integer(K) * 10000 + ERST;
43.     Result := (100000 - TTERS + KENEN + METTIEN) mod 100000 = KERST;
44.   end;
45.   function IsSolution: Boolean;
46.   begin
47.     Result := R * 1000000 + E * 100000 + KENEN + METTIEN - (L * 1000000 + E * 100000 + TTERS) = KERST;
48.   end;
49.   function CalcREKENLES: Int64;
50.   begin
51.     Result := Int64(S) + Int64(E) * 10 + Int64(L) * 100 + Int64(N) * 1000 + Int64(E) * 10000 +
52.               Int64(K) * 100000 + Int64(E) * 1000000 + Int64(R) * 10000000;
53.   end;
54. begin
55.   State := [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
56.   Count := 0;
57.   REKENLES1 := 0;
58.   REKENLES2 := 0;
59.   for N := 0 to 9 do
60.     begin
61.       Exclude(State, N);
62.       for S := 0 to 9 do
63.         if S in State then
64.           begin
65.             Exclude(State, S);
66.             for T := 0 to 9 do
67.               if (T in State) and TrueMod10 then
68.                 begin
69.                   Exclude(State, T);
70.                   for E := 0 to 9 do
71.                     if E in State then
72.                       begin
73.                         Exclude(State, E);
74.                         for R := 0 to 9 do
75.                           if (R in State) and TrueMod100 then
76.                             begin
77.                               Exclude(State, R);
78.                               for I := 0 to 9 do
79.                                 if I in State then
80.                                   begin
81.                                     Exclude(State, I);
82.                                     for M := 0 to 9 do
83.                                       if (M in State) and TrueMod10000 then
84.                                         begin
85.                                           Exclude(State, M);
86.                                           for K := 0 to 9 do
87.                                             if (K in State) and TrueMod100000 then
88.                                               begin
89.                                                 Exclude(State, K);
90.                                                 for L := 0 to 9 do
91.                                                   if (L in State) and IsSolution then
92.                                                     begin
93.                                                       Inc(Count);
94.                                                       Write('K=',K);
95.                                                       Write(', E=',E);
96.                                                       Write(', R=',R);
97.                                                       Write(', S=',S);
98.                                                       Write(', T=',T);
99.                                                       Write(', N=',N);
100.                                                       Write(', M=',M);
101.                                                       Write(', I=',I);
102.                                                       Write(', L=',L);
103.                                                       Write('  MINSTREEL=',M,I,N,S,T,R,E,E,L,', ');
104.                                                       WriteLn('REKENLES=',R,E,K,E,N,L,E,S);
105.                                                       if Count = 1 then
106.                                                         REKENLES1 := CalcREKENLES;
107.                                                       if Count = 2 then
108.                                                         begin
109.                                                           REKENLES2 := CalcREKENLES;
110.                                                           WriteLn(REKENLES1,' * ', REKENLES2,' = ',
111.                                                                   REKENLES1 * REKENLES2);
112.                                                           exit;
113.                                                         end;
114.                                                     end;
115.                                                   Include(State, K);
116.                                                 end;
117.                                             Include(State, M);
118.                                           end;
119.                                       Include(State, I);
120.                                     end;
121.                                 Include(State, R);
122.                               end;
123.                           Include(State, E);
124.                         end;
125.                     Include(State, T);
126.                   end;
127.               Include(State, S);
128.             end;
129.       Include(State, N);
130.     end;
131. end;
132.  
133. var
134.   Ticks: QWord;
135.  
136. begin
137.   Ticks := GetTickCount64;
138.   Solve;
139.   Ticks := GetTickCount64 - Ticks;
140.   WriteLn('tick count = ', Ticks);
141.   ReadLn;
142. end.
143.  

[Thaddy]

Nice to see sets have such a big improvement. I suspect engkin's solution 2 also uses sets.

[Bart]

My first solution used sets instead of (T<>K) and (T<>E) and (T<>R).
Now it seems that not (T in [K,E,R]) is faster?
Never new that.

Bart

[Thaddy]

Yes. Set operations are very fast. If you can use them, use them over anything else. (Note: only goes for true sets, they are masked bit operations)
I won't participate, because I have seen too much code and I don't want to steal and improve. The hint was enough.

[Bart]

I updated the scores.

Bart

[Martin_fr]

I wondered how avk archived such a good time.... And I found it (nothing to do with sets, I use an "array [0..9] of bytebool" and its faster (than the same code with sets).

The reason is some really big bit of luck about the order in which the loops where added...

In avk's code, loops that could be ordered in any way... eg the loops for n, s and t, are ordered so they match the expected result.
- N is known to be 0 in the final result. And avk runs that loop first. That means it has a hit in its very first iteration.
- S is known to be 2. And the loop comes 2nd, and again has a hit very early
- t needs to run to 8, and in that set of loops it is last.
 The code would be much faster by doing "for t := 9 downto 0 do"

The next set of loops (before a condition can be tested) is e and r. E(4) then r(3)
Had the code run r before e, it might be yet a bit faster.

Then i(1) and m(7). In that order. Again in the lucky order.

---
If those orders are changed, timing changes drastically.


I think, in order to get a comparison of the actual algorithm, rather than how lucky you where which variable you picked for your first loop, the code should be forbidden to abort on finding the result. It should be required to run the remaining iterations, as if to check that there is no further result.


---
I submitted a modified version of my code to Bart. In this I have enforced the above luck, by changing the order of the loop, and also running some loops from 9 to 0.

I submitted this to Bart to see how fast my code is, with this approach. I do not want that version of mine to be considered for competing. After all I used knowledge about the result, in order to get the result.


---
There are also suggestions here, that one may assume that none of the words can start with a 0. And therefore certain letters can not be 0.
This also should be clarified. If allowed, then all should know and use this.

[Bart]

There are also suggestions here, that one may assume that none of the words can start with a 0. And therefore certain letters can not be 0.
This also should be clarified. If allowed, then all should know and use this.

This is quite alright.
You can assume anything at forehand, and given the kind of the puzzle (which did not originate from a programmers forum or something the like), it is reasonable.

Bart

[Blaazen]

Damn, Avk is 10000*faster than me!!! 

I got the third version. But this one is based on engkin's ideas, I only added a few optimalizations.

Code: Pascal  [Select][+][-]

1. KERST = REKENEN + MET * TIEN - LETTERS }
2.  
3.   RST = R000NEN + MET * TIEN - L0TTERS
4.  
5. L>R, L>0

1) L must be >0 (saves one loop), and is probably high, so is better to do 9 downto loop.
2) R is always <L (saves a few loops)
3) K is calculated after the main formula

Code: Pascal  [Select][+][-]

1. program project1;
2. {$R *.res}
3.  
4. uses SysUtils;
5.  
6. var REKENLES: array[0..1] of Integer;
7.     Res: Integer;
8.  
9.   procedure Run;
10.   var e, i, k, l, m, n, r, s, t: Integer;
11.   begin
12.     for n:=0 to 9 do
13.       for s:=0 to 9 do
14.         if s<>n then
15.           for t:=0 to 9 do
16.             if (t<>n) and (t<>s) and (((n*t+n-s-t) mod 10)=0) then
17.               for l:=9 downto 1 do
18.                 if (l<>n) and (l<>s) and (l<>t) then
19.                   for r:=0 to l-1 do
20.                     if (r<>n) and (r<>s) and (r<>t) then
21.                       for e:=0 to 9 do
22.                         if (e<>l) and (e<>n) and (e<>r) and (e<>s) and (e<>t) then
23.                           for i:=0 to 9 do
24.                             if (i<>e) and (i<>l) and (i<>n) and (i<>r) and (i<>s) and (i<>t) then
25.                               for m:=0 to 9 do
26.                                 if (m<>e) and (m<>i) and (m<>l) and (m<>n) and (m<>r) and (m<>s)
27.                                   and (m<>t) and ((100*m+10*e+t)*(1000*t+100*i+10*e+n)
28.                                   +(1000000*(r-l)-11001*t+100*(n-e-r)+10*(e-r-s)+n-s)=0) then
29.                                   for k:=0 to 9 do
30.                                     if (k<>e) and (k<>i) and (k<>l) and (k<>m) and (k<>n)
31.                                       and (k<>r) and (k<>s) and (k<>t) then
32.                                       begin
33.                                         REKENLES[Res]:=10000000*r+1010010*e+100000*k+1000*n+100*l+s;
34.                                         write(  'K=', k);
35.                                         write(', E=', e);
36.                                         write(', R=', r);
37.                                         write(', S=', s);
38.                                         write(', T=', t);
39.                                         write(', N=', n);
40.                                         write(', M=', m);
41.                                         write(', I=', i);
42.                                         write(', L=', l);
43.                                         write('  MINSTREEL=', m, i, n, s, t, r, e, e, l,', ');
44.                                         writeln('REKENLES=', r, e, k, e, n, l, e, s);
45.                                         inc(Res);
46.                                         if Res>=2 then exit;
47.                                       end;
48.     end;
49.  
50. var q: QWord;
51. begin
52.   q:=GetTickCount64;
53.   Run;
54.   writeln(REKENLES[0], ' * ', REKENLES[1], ' = ', REKENLES[0]*REKENLES[1]);
55.   writeln('Ticks: ', GetTickCount64-q);
56. end.
57.  

Looks almost 2000 faster than my second version (with disabled output).

[Bart]

I submitted a modified version of my code to Bart. In this I have enforced the above luck, by changing the order of the loop, and also running some loops from 9 to 0.

I submitted this to Bart to see how fast my code is, with this approach. I do not want that version of mine to be considered for competing. After all I used knowledge about the result, in order to get the result.

0.00152 ticks on average...

Bart

@avk: did you reorder your loops after you got an initial result for all of the letters?

Bart

[Bart]

Damn, Avk is 10000*faster than me!!! 

I got the third version. But this one is based on engkin's ideas, I only added a few optimalizations.

Submitted for the contest, or just for the fun of it (since it's derived from engkin)?

B.t.w: it averages at 3.688 ticks.
(You did not initialize Res inside Run, so when I ran that in a loop I immediately got a range check error on the second loop (Res being 3)).

Bart