Contest: fastest program to solve a christmas puzzle lazarus / 62-General ---------------------------------------------------------------------- Bart · 2018-12-18 22:00 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: SysUtilsMathStandard library used to enable threads on your current OSYou 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): Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   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): Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   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: Code: [Select]?? * ?? = 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 ticksEngkin: 0.5342 ticksBlaazen (second entry): 38 ticksUser137: 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 ---------------------------------------------------------------------- Blaazen · 2018-12-19 01:41 I got solution. 640 ticks on my old Core2Duo at 2GHz, single thread, no optimizations. I'll try harder tomorrow. EDIT: I'm on 270 ticks, with ± your settings, still single thread. What CPU do you have? ---------------------------------------------------------------------- User137 · 2018-12-19 02:42 We can use TMemo from Lazarus to display results? I'm not fond of console apps. No algorithm yet but: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   timing:=gettickcount64;   memo1.Lines.BeginUpdate;  memo1.Lines.Add(... the result lines...   timing:=gettickcount64-timing;  memo1.Lines.Add(format('Elapsed time: %d',[timing]));  memo1.Lines.EndUpdate;Sometimes 0 ms, sometimes 15 or 16. Just so you know it's a bit inaccurate. edit: Begin and EndUpdate helps, it's now always 0 ms with just the displaying. You never said if combined number can start with 0? I assume not. For example MET with M=0, E=1, T=2 would be 012 or 12. If all numbers are 0's it would be a valid result, making the multiplication of both results 0. ---------------------------------------------------------------------- Blaazen · 2018-12-19 04:04 All numbers can't be 0. Mathematically, this puzzle is: http://www.emathematics.net/combinavordinarias.php ---------------------------------------------------------------------- engkin · 2018-12-19 04:31 Around 100 ticks here. Edit: GetTickCount is not fast enough anymore here. I am getting 0 ticks. ---------------------------------------------------------------------- User137 · 2018-12-19 05:19 Solutions found, 594 563 ticks best so far (no optimization). Actually that's 359 ticks with -O3 and single thread. 110 ticks after multithreading done. Using Core i5 6400 2.7GHz quadcore. ---------------------------------------------------------------------- Bart · 2018-12-19 08:45 Quote from: Blaazen on December 19, 2018, 02:41:09 amI got solution. 640 ticks on my old Core2Duo at 2GHz, single thread, no optimizations. I'll try harder tomorrow. EDIT: I'm on 270 ticks, with ± your settings, still single thread. What CPU do you have? Just PM your solution (if you want it to be secret), or post is here, and I'll compare it to mine. Ticks on your machine will probably be very different on mine. I have an Intel Core i5-7200 CPU@2.5 GHz and 8GB of RAM. Bart ---------------------------------------------------------------------- Bart · 2018-12-19 08:49 Quote from: User137 on December 19, 2018, 03:42:18 amWe can use TMemo from Lazarus to display results? I'm not fond of console apps. Yes, you can. It will be slower though (the displaying is inside the timing period). Console apps are not more difficult than GUI apps. Use Lazarus to create them, so you have all the goodies of CodeTools available. Quote from: User137 on December 19, 2018, 03:42:18 amYou never said if combined number can start with 0? I assume not. For example MET with M=0, E=1, T=2 would be 012 or 12. Starting with 0 is allowed. Quote from: User137 on December 19, 2018, 03:42:18 amIf all numbers are 0's it would be a valid result, making the multiplication of both results 0. Read the puzzle. Each letter identifies a unique single digit. Bart ---------------------------------------------------------------------- Bart · 2018-12-19 08:52 Quote from: engkin on December 19, 2018, 05:31:36 amGetTickCount is not fast enough anymore here. I am getting 0 ticks. Wow! I'ld love to see that code. OK, when we get in the range of ticks < 10: repeat the entire solution 1000 times and then divide ticks by 1000 (so you can have fractional ticks). Bart ---------------------------------------------------------------------- Bart · 2018-12-19 08:59 Quote from: Blaazen on December 19, 2018, 05:04:07 amAll numbers can't be 0. Mathematically, this puzzle is: http://www.emathematics.net/combinavordinarias.php Since (n-m) equals 1, the total will be 10!. But do you really need to investigate all possible combinations? I was able to half my time simply by not investigating combinations I could reason to be wrong in the first place. Bart ---------------------------------------------------------------------- engkin · 2018-12-19 12:47 Quote from: Bart on December 19, 2018, 09:52:25 amOK, when we get in the range of ticks < 10: repeat the entire solution 1000 times and then divide ticks by 1000 (so you can have fractional ticks). 2~3 ticks if I switch manually (ALT+TAB) back to the IDE and wait for the CPU activity to go down to avoid scrolling the console penalty. Otherwise, it is ~ 13 ticks. Edit: As for the solution, nothing fancy. KERST = REKENEN + MET * TIEN - LETTERS or KERST + LETTERS = REKENEN + MET * TIEN or Ones digit (KERST + LETTERS) = Ones digit (REKENEN + MET * TIEN) or (KERST + LETTERS) mod 10 = (REKENEN + MET * TIEN) mod 10 or (T+S) mod 10 = (N+T*N) mod 10 Means I don't have to loop through all variables. I can start with T, S and N: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   for N :=0 to 9 do    for S := 0 to 9 do    begin      if S = N then continue;    for T := 0 to 9 do      begin        if (T = N) or (T = S) then continue;        if (T+S) mod 10 = (N+T*N) mod 10 then        begin  Only then I need to loop through the rest. The whole code: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program puz; {$mode objfpc}{$H-} uses  {$IFDEF UNIX}{$IFDEF UseCThreads}  cthreads,  {$ENDIF}{$ENDIF}  Classes, sysutils  { you can add units after this }; var  K,E,R,S,T,N,M,I,L: integer;  VarForFirst_REKENLES, VarForSecond_REKENLES: Integer;  YourValueForTheProduct: int64;  first: boolean = true; function Check(): boolean;var  KERST, REKENEN , MET , TIEN , LETTERS: Integer;  REKEN: Integer;begin  KERST   := K*10000+E*1000+R*100+S*10+T ;  REKEN   := R*1000000+E*100000+K*10000+E*1000+N*100;  //REKENEN := R*1000000+E*100000+K*10000+E*1000+N*100+E*10+N ;  REKENEN := REKEN+E*10+N;  MET     := M*100+E*10+T ;  TIEN    := T*1000+I*100+E*10+N ;  LETTERS := L*1000000+E*100000+T*10000+T*1000+E*100+R*10+S ;   Result  := KERST = REKENEN + MET * TIEN - LETTERS;  //Result  := KERST + LETTERS = REKENEN + MET * TIEN;   if Result then  begin    if first then    begin      WriteLn('1-REKEN: ',REKEN);      VarForFirst_REKENLES := REKEN*10+L*100+E*10+S;      first:= false;    end    else    begin    WriteLn('2-REKEN: ',REKEN);      VarForSecond_REKENLES := REKEN*10+L*100+E*10+S;    end;  end;end; var  counter: integer;  ticks: Int64;  rpt: integer; label  OutOfLoops; begin  //KERST = REKENEN + MET * TIEN - LETTERS  //KERST + LETTERS = REKENEN + MET * TIEN  //U(T+S) = U(N+T*N);   ticks := GetTickCount;  for rpt := 1 to 1000 do begin  counter := 0;   for N :=0 to 9 do    for S := 0 to 9 do    begin      if S = N then continue;      for T := 0 to 9 do      begin        if (T = N) or (T = S) then continue;        if (T+S) mod 10 = (N+T*N) mod 10 then        begin          for K := 0 to 9 do        begin            if (K=T) or (K=S) or (K=N) then continue;          for E := 0 to 9 do            begin              if (E=T) or (E=S) or (E=N) or (E=K) then continue;              for R := 0 to 9 do            begin                if (R=T) or (R=S) or (R=N) or (R=K) or (R=E) then continue;                for M := 0 to 9 do                begin                  if (M=T) or (M=S) or (M=N) or (M=K) or (M=E) or (M=R) then continue;                  for I := 0 to 9 do                begin                    if (I=T) or (I=S) or (I=N) or (I=K) or (I=E) or (I=R) or (I=M) then continue;                    for L := 0 to 9 do                    begin                      if (L=T) or (L=S) or (L=N) or (L=K) or (L=E) or (L=R) or (L=M) or (L=I) then continue;                      if Check() then                      begin                        inc(counter);                        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);                        if counter=2 then goto OutOfLoops;                      end;                   end;                  end;                end;              end;            end;          end;        end;      end;    end; OutOfLoops:   YourValueForTheProduct := int64(VarForFirst_REKENLES)*int64(VarForSecond_REKENLES);  writeln(VarForFirst_REKENLES,' * ',VarForSecond_REKENLES,' = ',YourValueForTheProduct);  end;   WriteLn('Ticks: ',(GetTickCount- ticks) div 1000);end. ---------------------------------------------------------------------- Martin_fr · 2018-12-19 13:16 that needs to define, if the writeln in each repeat are measured... ---------------------------------------------------------------------- engkin · 2018-12-19 13:50 The switch is only of the 1000 times ---------------------------------------------------------------------- Blaazen · 2018-12-19 14:00 Of some reason, when I used two threads it was even slower, so here my single thread solution. Classic approach, I go thru all possible variations. The ony optimalization is in computing "klr:=.."  (line 48), like REKENEN-LETTERS, where E at position 100000 doesn't need to be computed etc. Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program project1;{$R *.res} uses {$IFDEF UNIX} cthreads, {$ENDIF} SysUtils, Math; var  Used: array[0..9] of Boolean;  Res: array[0..8] of Integer;  {e i k l m n r s t}  REKENLES: array[0..1] of Integer;  ResIndex: SmallInt;   procedure Output;  begin  { KERST = REKENEN + MET * TIEN - LETTERS }    REKENLES[ResIndex]:=      10000000*Res[6]+1000000*Res[0]+100000*Res[2]+10000*Res[0]+      1000*Res[5]+100*Res[3]+10*Res[0]+Res[7];    write(  'K=', Res[2]);    write(', E=', Res[0]);    write(', R=', Res[6]);    write(', S=', Res[7]);    write(', T=', Res[8]);    write(', N=', Res[5]);    write(', M=', Res[4]);    write(', I=', Res[1]);    write(', L=', Res[3]);    write('  MINSTREEL=', Res[4], Res[1], Res[5], Res[7], Res[8],      Res[6], Res[0], Res[0], Res[3],', ');    writeln('REKENLES=', Res[6], Res[0], Res[2], Res[0], Res[5], Res[3],    Res[0], Res[7]);    inc(ResIndex);  end;   procedure Variace(j: Byte);  var i, krl, m, ti: Integer;  begin    if j<=8 then      begin        for i:=0 to 9 do          if not Used[i] then            begin            Res[j]:=i;              Used[i]:=True;              Variace(j+1);              Used[i]:=False;            end;      end else      begin        krl:=1000000*(Res[6]-Res[3])-11000*Res[8]+100*(Res[5]-Res[0]-Res[6])        +10*(Res[0]-Res[6]-Res[7])+Res[5]-Res[7]-Res[8];        m:=100*Res[4]+10*Res[0]+Res[8];        ti:=1000*Res[8]+100*Res[1]+10*Res[0]+Res[5];        if (krl+m*ti)=0 then Output;      end;  end; var i, j: Integer;    q: QWord;begin  q:=GetTickCount64;  ResIndex:=0;  for i:=0 to 9 do    Used[i]:=False;  Variace(0);  writeln(REKENLES[0], ' * ', REKENLES[1], ' = ', REKENLES[0]*REKENLES[1]);  writeln('q: ', GetTickCount64-q);end. ---------------------------------------------------------------------- VTwin · 2018-12-19 15:22 Quote from: engkin on December 19, 2018, 01:47:08 pmAs for the solution, nothing fancy. Nice! ---------------------------------------------------------------------- Blaazen · 2018-12-19 16:05 I attach my second version, where is one optimalization. In this puzzle really does not matter on the K, so I omitted it from loops. Now it is ~100 ticks instead of ~270 with the same output. Still far from engkin's solution although.  Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program project1;{$R *.res} uses {$IFDEF UNIX} cthreads, {$ENDIF} SysUtils, Math; var  Used: array[0..9] of Boolean;  Res: array[0..7] of Integer;  REKENLES: array[0..1] of Integer;  ResIndex: SmallInt;   procedure Output;  var i, j, k: Integer;  begin  { KERST = REKENEN + MET * TIEN - LETTERS }    for i:=0 to 7 do      if not Used[i] then      begin          k:=i;          REKENLES[ResIndex]:=            10000000*Res[5]+1000000*Res[0]+100000*k+10000*Res[0]+            1000*Res[4]+100*Res[2]+10*Res[0]+Res[6];          write(  'K=', k);        write(', E=', Res[0]);          write(', R=', Res[5]);          write(', S=', Res[6]);          write(', T=', Res[7]);          write(', N=', Res[4]);          write(', M=', Res[3]);          write(', I=', Res[1]);          write(', L=', Res[2]);          write('  MINSTREEL=', Res[3], Res[1], Res[4], Res[6], Res[7],          Res[6], Res[0], Res[0], Res[2],', ');          writeln('REKENLES=', Res[5], Res[0], k, Res[0], Res[4], Res[2],            Res[0], Res[6]);          inc(ResIndex);        end;  end;   procedure Variace(j: Byte);  var i, krl, m, ti: Integer;  begin    if j<=7 then      begin        for i:=0 to 9 do          if not Used[i] then          begin              Res[j]:=i;              Used[i]:=True;            Variace(j+1);              Used[i]:=False;            end;      end else      begin        krl:=1000000*(Res[5]-Res[2])-11000*Res[7]+100*(Res[4]-Res[0]-Res[5])        +10*(Res[0]-Res[5]-Res[6])+Res[4]-Res[6]-Res[7];        m:=100*Res[3]+10*Res[0]+Res[7];        ti:=1000*Res[7]+100*Res[1]+10*Res[0]+Res[4];        if (krl+m*ti)=0 then Output;      end;  end; var i, j: Integer;    q: QWord;begin  q:=GetTickCount64;  ResIndex:=0;  for i:=0 to 8 do    Used[i]:=False;  Variace(0);  writeln(REKENLES[0], ' * ', REKENLES[1], ' = ', REKENLES[0]*REKENLES[1]);  writeln('q: ', GetTickCount64-q);end. ---------------------------------------------------------------------- damieiro · 2018-12-19 17:22 Brute force only or is allowed analitics? Because if one starts analizing like engkin (good eye ), some values can be known If i did correctly the math (at daring glaze) the expresion is like this 1000000*(R-L)+100000*MT+10000*(MI+ET-T)+1000*(ME+EI+TT- T)+100*(2N+IT+EE-E-R)+10*(E-R+EN+ET-S)+N-S+NT-T=0; ---------------------------------------------------------------------- User137 · 2018-12-19 19:10 My solution was quite different from the others, i guess just less optimal brute force. But i don't calculate the whole formula on every iteration, only when the character in that word changes and only the last change. It's using 10 threads. edit: It came to my attention that last multiplication needs to be typed to int64. It wasn't a problem for me with 64-bit compiler where integer is 64-bit. ---------------------------------------------------------------------- engkin · 2018-12-19 20:45 I forgot to say that when I read: Quote from: Bart on December 18, 2018, 11:00:30 pm.. And the code to display the product of the 2 values for REKENLES should be (executed only once): .. ?? * ?? = 1196530768447364 I knew that S either has one value 2 (2*2=4), or two possible values 1 and 4 (1*4=4). But we were not supposed to use this information to find the solution. ---------------------------------------------------------------------- Blaazen · 2018-12-19 20:55 Similar with "K". The only two occurences of "K" in formula are KERST = REKENEN+... on the position 10000, therefore it does not depend on value of "K" . I used this info for optimalization of the second version. ---------------------------------------------------------------------- Bart · 2018-12-19 21:55 Quote from: engkin on December 19, 2018, 01:47:08 pm KERST = REKENEN + MET * TIEN - LETTERS or KERST + LETTERS = REKENEN + MET * TIEN or Ones digit (KERST + LETTERS) = Ones digit (REKENEN + MET * TIEN) or (KERST + LETTERS) mod 10 = (REKENEN + MET * TIEN) mod 10 or (T+S) mod 10 = (N+T*N) mod 10 Means I don't have to loop through all variables. I can start with T, S and N: Clever thinking! Bart ---------------------------------------------------------------------- Bart · 2018-12-19 22:01 Quote from: damieiro on December 19, 2018, 06:22:55 pmBrute force only or is allowed analitics? You need to eliminate as much permutations beforehand as possible. While not absolutely certain, from the way the puzzle is written, one could infer that the starting letters of the given words will probably NOT be zero. Just applying that halved my calculation time. Bart ---------------------------------------------------------------------- avk · 2018-12-20 09:58 if it's not too late, then here is my solution: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program pazzle; {$mode objfpc}{$H+} uses  SysUtils; type  TPermState = record    case Boolean of    False: (Dw: DWord);    True:  (Bits: bitpacked array[0..9] of Boolean);  end; procedure Solve;var  State: TPermState;  E, I, K, L, M, N, R, S, T, Count: Integer;  function IsSolution: Boolean;  begin    Result := (N + E * 10 + N * 100 + E * 1000 + K * 10000 + E * 100000 + R * 1000000) +              (T + E * 10 + M * 100) * (N + E * 10 + I * 100 + T * 1000) -              (S + R * 10 + E * 100 + T * 1000 + T * 10000 + E * 100000 + L * 1000000) =               T + S * 10 + R * 100 + E * 1000 + K * 10000;  end;  function CalcREKENLES: Int64;  begin    Result := Int64(S) + Int64(E) * 10 + Int64(L) * 100 + Int64(N) * 1000 + Int64(E) * 10000 +            Int64(K) * 100000 + Int64(E) * 1000000 + Int64(R) * 10000000;  end;var  REKENLES1, REKENLES2: Int64;begin  State.Dw := 1023;  Count := 0;  REKENLES1 := 0;  REKENLES2 := 0;  for N := 0 to 9 do    begin    State.Bits[N] := False;      for S := 0 to 9 do        if State.Bits[S] then          begin            State.Bits[S] := False;          for T := 0 to 9 do              if State.Bits[T] then              begin                  if (10 - S + N * Succ(T)) mod 10 <> T then                    continue;                  State.Bits[T] := False;                  for E := 0 to 9 do                    if State.Bits[E] then                      begin                        State.Bits[E] := False;                        for I := 0 to 9 do                        if State.Bits[I] then                            begin                              State.Bits[I] := False;                            for K := 0 to 9 do                                if State.Bits[K] then                                  begin                                  State.Bits[K] := False;                                  for L := 0 to 9 do                                      if State.Bits[L] then                                        begin                                        State.Bits[L] := False;                                        for M := 0 to 9 do                                          if State.Bits[M] then                                            begin                                                State.Bits[M] := False;                                              for R := 0 to 9 do                                                  if State.Bits[R] then                                                    if IsSolution then                                                    begin                                                        Inc(Count);                                                        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);                                                      if Count = 1 then                                                        REKENLES1 := CalcREKENLES;                                                      if Count = 2 then                                                        begin                                                          REKENLES2 := CalcREKENLES;                                                          WriteLn(REKENLES1,' * ', REKENLES2,' = ',                                                                  REKENLES1 * REKENLES2);                                                          exit;                                                        end;                                                    end;                                                State.Bits[M] := True;                                              end;                                          State.Bits[L] := True;                                      end;                                  State.Bits[K] := True;                                  end;                            State.Bits[I] := True;                          end;                        State.Bits[E] := True;                    end;                  State.Bits[T] := True;                end;            State.Bits[S] := True;          end;      State.Bits[N] := True;    end;end; var  Ticks: QWord; begin  Ticks := GetTickCount64;  Solve;  Ticks := GetTickCount64 - Ticks;  WriteLn('tick count = ', Ticks);  ReadLn;end. ---------------------------------------------------------------------- Thaddy · 2018-12-20 10:00 I wonder if it would be faster to handle the state bits as a set. with include/exclude. Set operations are notoriously fast. Faster than array access? ---------------------------------------------------------------------- Bart · 2018-12-20 13:55 Quote from: avk on December 20, 2018, 10:58:40 amif it's not too late, then here is my solution: It's not too late. I'll test at home when I have time. Bart ---------------------------------------------------------------------- engkin · 2018-12-20 19:24 I think I have another solution. ---------------------------------------------------------------------- Thaddy · 2018-12-20 20:45 Let me guess.. ---------------------------------------------------------------------- Bart · 2018-12-20 21:39 Final entries at december 26th 23:59 CET... Bart ---------------------------------------------------------------------- engkin · 2018-12-20 21:51 Quote from: Thaddy on December 20, 2018, 09:45:33 pmLet me guess.. Can you? ---------------------------------------------------------------------- Bart · 2018-12-20 22:02 For fast solutions that need multiple cycles to even be able to get some kind of acurate tick count, I'll measure those with all writing to console commented out. @engkin: you've got an even faster solution???? Bart ---------------------------------------------------------------------- engkin · 2018-12-20 22:13 I did not code it yet, but I believe it should be faster. Let's see. ---------------------------------------------------------------------- VTwin · 2018-12-20 23:06 Quote from: engkin on December 20, 2018, 11:13:08 pmI 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 · 2018-12-21 01:11 Quote from: VTwin on December 21, 2018, 12:06:46 amQuote from: engkin on December 20, 2018, 11:13:08 pmI 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 · 2018-12-21 02:00 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 · 2018-12-21 09:05 Quote from: engkin on December 21, 2018, 03:00:40 am@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 · 2018-12-21 12:42 @Thaddy: yes, set is about 15% faster. @Bart: I use Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i {$ASMMODE INTEL}function CPUClocks: QWord; assembler; nostackframe;asm  rdtscp{$IFDEF CPUAMD64}  shl rdx, 32  or  rax, rdx{$ENDIF}end;  I also have another solution  Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program pazzle; {$mode objfpc}{$B-} uses  SysUtils; type  TDigit = 0..9; procedure Solve;var  State: set of TDigit;  E, I, K, L, M, N, R, S, T, Count: TDigit;  EN, ET, ST, RS, TERS, ENEN, METTIEN, ERST, KENEN, TTERS, KERST: Integer;  REKENLES1, REKENLES2: Int64;   function TrueMod10: Boolean;  begin    Result := (10 - Integer(S) + Integer(N) * Succ(Integer(T))) mod 10 = T;  end;  function TrueMod100: Boolean;  begin    RS := Integer(R) * 10 + S;    EN := Integer(E) * 10 + N;    ST := Integer(S) * 10 + T;    ET := Integer(E) * 10 + T;    Result := (100 - RS + EN + EN * ET) mod 100 = ST;  end;  function TrueMod10000: Boolean;  begin    TERS := Integer(T) * 1000 + Integer(E) * 100 + RS;    ENEN := EN * 100 + EN;    METTIEN := (Integer(M) * 100 + ET) * (Integer(T) * 1000 + Integer(I) * 100 + EN);    ERST := Integer(E) * 1000 + Integer(R) * 100 + ST;    Result := (10000 - TERS + ENEN + METTIEN) mod 10000 = ERST;  end;  function TrueMod100000: Boolean;  begin    TTERS := T * 10000 + TERS;    KENEN := Integer(K) * 10000 + ENEN;    KERST := Integer(K) * 10000 + ERST;    Result := (100000 - TTERS + KENEN + METTIEN) mod 100000 = KERST;  end;  function IsSolution: Boolean;  begin    Result := R * 1000000 + E * 100000 + KENEN + METTIEN - (L * 1000000 + E * 100000 + TTERS) = KERST;  end;  function CalcREKENLES: Int64;  begin    Result := Int64(S) + Int64(E) * 10 + Int64(L) * 100 + Int64(N) * 1000 + Int64(E) * 10000 +            Int64(K) * 100000 + Int64(E) * 1000000 + Int64(R) * 10000000;  end;begin  State := [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];  Count := 0;  REKENLES1 := 0;  REKENLES2 := 0;  for N := 0 to 9 do    begin      Exclude(State, N);      for S := 0 to 9 do        if S in State then        begin            Exclude(State, S);            for T := 0 to 9 do              if (T in State) and TrueMod10 then                begin                  Exclude(State, T);                  for E := 0 to 9 do                    if E in State then                      begin                        Exclude(State, E);                      for R := 0 to 9 do                          if (R in State) and TrueMod100 then                            begin                            Exclude(State, R);                              for I := 0 to 9 do                                if I in State then                                begin                                    Exclude(State, I);                                    for M := 0 to 9 do                                    if (M in State) and TrueMod10000 then                                      begin                                        Exclude(State, M);                                          for K := 0 to 9 do                                            if (K in State) and TrueMod100000 then                                            begin                                                Exclude(State, K);                                                for L := 0 to 9 do                                                  if (L in State) and IsSolution then                                                  begin                                                      Inc(Count);                                                      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);                                                    if Count = 1 then                                                      REKENLES1 := CalcREKENLES;                                                      if Count = 2 then                                                        begin                                                          REKENLES2 := CalcREKENLES;                                                        WriteLn(REKENLES1,' * ', REKENLES2,' = ',                                                                REKENLES1 * REKENLES2);                                                          exit;                                                        end;                                                  end;                                                Include(State, K);                                              end;                                          Include(State, M);                                          end;                                    Include(State, I);                                  end;                                Include(State, R);                              end;                          Include(State, E);                        end;                    Include(State, T);                  end;              Include(State, S);            end;      Include(State, N);    end;end; var  Ticks: QWord; begin  Ticks := GetTickCount64;  Solve;  Ticks := GetTickCount64 - Ticks;  WriteLn('tick count = ', Ticks);  ReadLn;end. ---------------------------------------------------------------------- Thaddy · 2018-12-21 13:05 Nice to see sets have such a big improvement. I suspect engkin's solution 2 also uses sets. ---------------------------------------------------------------------- Bart · 2018-12-21 13:54 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 · 2018-12-21 15:57 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 · 2018-12-21 18:03 I updated the scores. Bart ---------------------------------------------------------------------- Martin_fr · 2018-12-21 22:05 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 · 2018-12-21 22:35 Quote from: Martin_fr on December 21, 2018, 11:05:27 pmThere 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 · 2018-12-21 22:45 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i KERST = REKENEN + MET * TIEN - LETTERS }   RST = R000NEN + MET * TIEN - L0TTERS L>R, L>01) L must be >0 (saves one loop), and is probably high, so is better to do 9 downto loop. 2) R is always n then          for t:=0 to 9 do            if (t<>n) and (t<>s) and (((n*t+n-s-t) mod 10)=0) then              for l:=9 downto 1 do              if (l<>n) and (l<>s) and (l<>t) then                  for r:=0 to l-1 do                    if (r<>n) and (r<>s) and (r<>t) then                      for e:=0 to 9 do                        if (e<>l) and (e<>n) and (e<>r) and (e<>s) and (e<>t) then                        for i:=0 to 9 do                            if (i<>e) and (i<>l) and (i<>n) and (i<>r) and (i<>s) and (i<>t) then                            for m:=0 to 9 do                                if (m<>e) and (m<>i) and (m<>l) and (m<>n) and (m<>r) and (m<>s)                                and (m<>t) and ((100*m+10*e+t)*(1000*t+100*i+10*e+n)                                +(1000000*(r-l)-11001*t+100*(n-e-r)+10*(e-r-s)+n-s)=0) then                                for k:=0 to 9 do                                  if (k<>e) and (k<>i) and (k<>l) and (k<>m) and (k<>n)                                    and (k<>r) and (k<>s) and (k<>t) then                                    begin                                      REKENLES[Res]:=10000000*r+1010010*e+100000*k+1000*n+100*l+s;                                      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);                                      inc(Res);                                      if Res>=2 then exit;                                      end;    end; var q: QWord;begin  q:=GetTickCount64;  Run;  writeln(REKENLES[0], ' * ', REKENLES[1], ' = ', REKENLES[0]*REKENLES[1]);  writeln('Ticks: ', GetTickCount64-q);end.  Looks almost 2000 faster than my second version (with disabled output). ---------------------------------------------------------------------- Bart · 2018-12-21 22:45 Quote from: Martin_fr on December 21, 2018, 11:05:27 pmI 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 · 2018-12-21 22:48 Quote from: Blaazen on December 21, 2018, 11:45:10 pmDamn, 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 ---------------------------------------------------------------------- Blaazen · 2018-12-21 22:54 I also used N as first but it's a coincidence. N,S,T must be looped first to get order of 1 (mod 10). Then I loop L and R because it is obvious from formula that L>R and that L can't be 0 and will be rather high. Therefore L:= 9 downto 1 and R:=0 to L-1. The rest is alphabetically and the K is last. QuoteSubmitted for the contest, or just for the fun of it (since it's derived from engkin)? Rather out of contest but I'd like to know result, please, if you can. ---------------------------------------------------------------------- Bart · 2018-12-21 23:01 Quote from: Blaazen on December 21, 2018, 11:54:06 pmQuoteSubmitted for the contest, or just for the fun of it (since it's derived from engkin)? Rather out of contest but I'd like to know result, please, if you can. See my previous post (which I edited while you were typing yours). Bart ---------------------------------------------------------------------- Blaazen · 2018-12-21 23:05 I see. Res is global so it needs no init for just one run, but you measure it many loops so it matters. ---------------------------------------------------------------------- Martin_fr · 2018-12-21 23:06 Quote from: Bart on December 21, 2018, 11:45:48 pm@avk: did you reorder your loops after you got an initial result for all of the letters? It does not actually matter. And actually, if he did, that might even be the better answer, because then at least the comparison is based on skill (rather than luck). But the point is: - in many solutions the order of some of the loops is coincidence - probably any good program aborts after finding the result (both of them) The amount of iteration is not based on the algorithm or  programmers skill. It is based on the coincidence. So currently the scores are based on luck. Therefore I wrote: QuoteI 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. And that should be required independent of any "ordering" being done by intend or coincidence. ---------------------------------------------------------------------- SymbolicFrank · 2018-12-22 00:22 The fastest way to do it is by using constants, and having the compiler calculate them. But that is forbidden. The fastest way to implement such an algorithm is by using BCD, as that is a native data type of your (i386) CPU, and you get the multiplications and conversion from char to int for free. But unfortunately, there is no native BCD code generated by fpc. It is all converted to integers. The fastest way to execute such an algorithm is by simply calculating every possible value at the same time, preferably on a GPU. Rewrite it like such: 0 = (MET * TIEN) + REKENEN - LETTERS - KERST, upload and calculate all possibilities and select the one that has the right result. The complexity doesn't matter as long as your GPU has at least the same amount of processing units as there are possibilities. Within those bounds, it will always finish in the same time (upload, process, download selected result) But that isn't allowed, either. So, generic methods won't be fastest, analyzing this specific case will make you win. Which isn't really allowed by the rules, either. Right? Does it have to solve only this puzzle, any puzzle like this, or something in between? And how much can you have the compiler do for you? ---------------------------------------------------------------------- avk · 2018-12-22 07:14 Quote from: Bart on December 21, 2018, 11:45:48 pm@avk: did you reorder your loops after you got an initial result for all of the letters? No. The logic of my solver is defined by the pruning rules(source equation and elementary modular arithmetic). I believe the better solution is the better pruning rules. If we begin to reorder the loops, because we know the solution, it is easier to directly print this solution, it will be the fastest option. As for luck or coincidence, it certainly lies in the fact that both solutions are located at the very beginning of the search. But we can “forget” that there are only two solutions(that is, not to exit after receiving the second). It would be interesting to see how long a search will take. ---------------------------------------------------------------------- Thaddy · 2018-12-22 07:34 I think AVK can be even faster like so, because state is only once a full set 0..9, so in should be faster than looping 0..9, and eliminates superfluous comparisons: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i {$mode objfpc}{$B-}{$inline on} uses  SysUtils; type  TDigit = 0..9; procedure Solve;var  State: set of TDigit;  E, I, K, L, M, N, R, S, T, Count: TDigit;  EN, ET, ST, RS, TERS, ENEN, METTIEN, ERST, KENEN, TTERS, KERST: Integer;  REKENLES1, REKENLES2: Int64;   function TrueMod10: Boolean;  begin    Result := (10 - Integer(S) + Integer(N) * Succ(Integer(T))) mod 10 = T;  end;  function TrueMod100: Boolean;  begin    RS := Integer(R) * 10 + S;    EN := Integer(E) * 10 + N;    ST := Integer(S) * 10 + T;    ET := Integer(E) * 10 + T;    Result := (100 - RS + EN + EN * ET) mod 100 = ST;  end;  function TrueMod10000: Boolean;  begin    TERS := Integer(T) * 1000 + Integer(E) * 100 + RS;    ENEN := EN * 100 + EN;    METTIEN := (Integer(M) * 100 + ET) * (Integer(T) * 1000 + Integer(I) * 100 + EN);    ERST := Integer(E) * 1000 + Integer(R) * 100 + ST;    Result := (10000 - TERS + ENEN + METTIEN) mod 10000 = ERST;  end;  function TrueMod100000: Boolean;  begin    TTERS := T * 10000 + TERS;    KENEN := Integer(K) * 10000 + ENEN;    KERST := Integer(K) * 10000 + ERST;    Result := (100000 - TTERS + KENEN + METTIEN) mod 100000 = KERST;  end;  function IsSolution: Boolean;  begin    Result := R * 1000000 + E * 100000 + KENEN + METTIEN - (L * 1000000 + E * 100000 + TTERS) = KERST;  end;  function CalcREKENLES: Int64;  begin    Result := Int64(S) + Int64(E) * 10 + Int64(L) * 100 + Int64(N) * 1000 + Int64(E) * 10000 +            Int64(K) * 100000 + Int64(E) * 1000000 + Int64(R) * 10000000;  end;begin  State := [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];  Count := 0;  REKENLES1 := 0;  REKENLES2 := 0;  for N in state do    begin      Exclude(State, N);      for S in state do          begin            Exclude(State, S);            for T in state do if TrueMod10 then               begin                  Exclude(State, T);                   for E in state do                       begin                        Exclude(State, E);                           for R in state do  if TrueMod100 then                            begin                            Exclude(State, R);                               for I in state do                                  begin                                  Exclude(State, I);                                      for M in state do if TrueMod10000 then                                        begin                                          Exclude(State, M);                                          for K in state do if TrueMod100000 then                                              begin                                                Exclude(State, K);                                                For L in state do if IsSolution then                                                    begin                                                      Inc(Count);                                                      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);                                                    if Count = 1 then                                                      REKENLES1 := CalcREKENLES;                                                      if Count = 2 then                                                        begin                                                          REKENLES2 := CalcREKENLES;                                                        WriteLn(REKENLES1,' * ', REKENLES2,' = ',                                                                REKENLES1 * REKENLES2);                                                          exit;                                                        end;                                                  end;                                                Include(State, K);                                              end;                                          Include(State, M);                                          end;                                    Include(State, I);                                  end;                                Include(State, R);                              end;                          Include(State, E);                        end;                    Include(State, T);                  end;              Include(State, S);            end;      Include(State, N);    end;end; var  Ticks: QWord; begin  Ticks := GetTickCount64;  Solve;  Ticks := GetTickCount64 - Ticks;  WriteLn('tick count = ', Ticks);  ReadLn;end. What does that give Bart? ---------------------------------------------------------------------- avk · 2018-12-22 07:50 No, Thaddy, it is 1.5 times slower, at least on my machine. And this was the reason why I initially preferred the array of bits. ---------------------------------------------------------------------- Thaddy · 2018-12-22 08:02 That is unexpected: there are less loops this way... I will look into it. What if you bitpack the set and inline the functions? On my Raspberry Pi this seems faster than your original code. The assembler output seems to support that: very neat. Can't test on a meaningful Intel (win10 crashed on auto-update last night). It should be faster as you can test by inserting popcnt(dword(state)); given state as a bitpacked set. You can see it has *a lot* less cycles than the for 0 to 9 approach: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i {$mode objfpc}{$B-}{$I-}{$inline on} uses  SysUtils; type  TDigit = 0..9; procedure Solve;var  State: bitpacked set of TDigit;  E, I, K, L, M, N, R, S, T, Count: TDigit;  EN, ET, ST, RS, TERS, ENEN, METTIEN, ERST, KENEN, TTERS, KERST: Integer;  REKENLES1, REKENLES2: Int64;   function TrueMod10: Boolean;inline;  begin    Result := (10 - Integer(S) + Integer(N) * Succ(Integer(T))) mod 10 = T;  end;  function TrueMod100: Boolean;inline;  begin    RS := Integer(R) * 10 + S;    EN := Integer(E) * 10 + N;    ST := Integer(S) * 10 + T;    ET := Integer(E) * 10 + T;    Result := (100 - RS + EN + EN * ET) mod 100 = ST;  end;  function TrueMod10000: Boolean;inline;  begin    TERS := Integer(T) * 1000 + Integer(E) * 100 + RS;    ENEN := EN * 100 + EN;  METTIEN := (Integer(M) * 100 + ET) * (Integer(T) * 1000 + Integer(I) * 100 + EN);    ERST := Integer(E) * 1000 + Integer(R) * 100 + ST;    Result := (10000 - TERS + ENEN + METTIEN) mod 10000 = ERST;  end;  function TrueMod100000: Boolean;inline;  begin    TTERS := T * 10000 + TERS;    KENEN := Integer(K) * 10000 + ENEN;    KERST := Integer(K) * 10000 + ERST;    Result := (100000 - TTERS + KENEN + METTIEN) mod 100000 = KERST;  end;  function IsSolution: Boolean;inline;  begin    Result := R * 1000000 + E * 100000 + KENEN + METTIEN - (L * 1000000 + E * 100000 + TTERS) = KERST;  end;  function CalcREKENLES: Int64;inline;  begin    Result := Int64(S) + Int64(E) * 10 + Int64(L) * 100 + Int64(N) * 1000 + Int64(E) * 10000 +              Int64(K) * 100000 + Int64(E) * 1000000 + Int64(R) * 10000000;  end;begin  State := [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];  Count := 0;  REKENLES1 := 0;  REKENLES2 := 0;  for N in state do    begin      Exclude(State, N);    for S in state do          begin            Exclude(State, S);          for T in state do if TrueMod10 then                 begin                Exclude(State, T);                   for E in state do                     begin                           Exclude(State, E);                         for R in state do  if TrueMod100 then                          begin                              Exclude(State, R);                             for I in state do                                begin                                    Exclude(State, I);                                    for M in state do if TrueMod10000 then                                        begin                                        Exclude(State, M);                                          for K in state do if TrueMod100000 then                                            begin                                              Exclude(State, K);                                                For L in state do if IsSolution then                                                  begin                                                    Inc(Count);                                                    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);                                                    if Count = 1 then                                                      REKENLES1 := CalcREKENLES;                                                      if Count = 2 then                                                        begin                                                          REKENLES2 := CalcREKENLES;                                                        WriteLn(REKENLES1,' * ', REKENLES2,' = ',                                                                REKENLES1 * REKENLES2);                                                          exit;                                                        end;                                                  end;                                                Include(State, K);                                              end;                                          Include(State, M);                                          end;                                    Include(State, I);                                  end;                                Include(State, R);                              end;                          Include(State, E);                        end;                    Include(State, T);                  end;              Include(State, S);            end;      Include(State, N);    end;end; var  Ticks: QWord; begin  Ticks := GetTickCount64;  Solve;  Ticks := GetTickCount64 - Ticks;  WriteLn('tick count = ', Ticks);  ReadLn;end.  At least on arm this is faster. Can you test on intel? This loops 9,8,7,6,5,4,3,2 (optimal permutation) instead of 9,9,9,9,9,9,9 ---------------------------------------------------------------------- avk · 2018-12-22 10:38 Quote from: Thaddy on December 22, 2018, 09:02:34 amCan you test on intel? Of course, about 1.6% faster than previous one(i3-4150) ---------------------------------------------------------------------- Thaddy · 2018-12-22 11:05 So at least armv7 seems more efficient on sets. On arm this code is faster than yours, so there is a processor instruction set dependency too. Strange since it is basically just a mask and test.  Algorithmic it should be faster on intel too. What can be the cause? Anyway it is basically your code and I won't submit it. (Compiled fpc -CX -XXs -O4 ) ---------------------------------------------------------------------- avk · 2018-12-22 12:01 optimizer quirks, code Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   for I := 1 to 10000 do    for J in MySet do; runs during 110316 clock, but Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   for I := 1 to 10000 do    for J := 0 to 9 do      if J in MySet then; during 70104. UPD, looked at the assembler listing, the compiler in both cases unrolls the entire inner loop, but in the first case one step is Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   test  eax, 4  je    @@j13  mov ecx, 2 and in the second one just Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   test  eax, 4 so everything looks logical ---------------------------------------------------------------------- Thaddy · 2018-12-22 15:41 It does explain the difference. The  second example simply does the test 9 times. So 9 times a test is cheaper than just the test until satisfied, at least on intel. ---------------------------------------------------------------------- avk · 2018-12-22 15:52 I meant that it's clear why the first code is slower. And if the set becomes greater, the situation is likely to change. ---------------------------------------------------------------------- Thaddy · 2018-12-22 16:05 Yes, I understood. My version can bail out as soon as condition is met and is not linear time. Depending on which bit it may eventually have better results. Your version is linear time. That may explain the performance on arm: better instruction set for such cases. (and test is fast on intel, I knew that). Still, I feel the Intel optimizer could do a better job.(possibly with a and mask). ---------------------------------------------------------------------- avk · 2018-12-23 09:09 Merry Christmas! I added a pruning rule and slightly changed the order of initialization of local variables, it seems to run a little faster. Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program pazzle; {$mode objfpc}{$B-} uses  SysUtils; type  TDigit = 0..9; procedure Solve;var  State: set of TDigit;  N, S, T, E, R, I, K, M, L, Count: TDigit;  EN, ET, ST, TERS, ENEN, TIEN, METTIEN, ERST, KENEN, TTERS, KERST: Integer;  REKENLES1, REKENLES2: Int64;   function TrueMod100: Boolean;  begin    Result := (100 - (Integer(R) * 10 + S) + EN + EN * ET) mod 100 = ST;  end;  function TrueMod1000: Boolean;  begin    TIEN := Integer(T) * 1000 + Integer(I) * 100 + EN;    if EN * ET < 1000 then      exit(True);    Result := (20000 - TERS - ERST + ENEN + ET * TIEN) mod 1000 = 0;  end;    function TrueMod10000: Boolean;  begin    METTIEN := (Integer(M) * 100 + ET) * TIEN;    Result := (10000 - TERS + ENEN + METTIEN) mod 10000 = ERST;  end;  function TrueMod100000: Boolean;  begin    KENEN := Integer(K) * 10000 + ENEN + METTIEN;    KERST := Integer(K) * 10000 + ERST;    Result := (100000 - TTERS + KENEN) mod 100000 = KERST;  end;  function IsSolution: Boolean;  begin    Result := R * 1000000 + E * 100000 + KENEN - (L * 1000000 + E * 100000 + TTERS) = KERST;  end;  function CalcREKENLES: Int64;  begin    Result := Int64(S) + Int64(E) * 10 + Int64(L) * 100 + Int64(N) * 1000 + Int64(E) * 10000 +              Int64(K) * 100000 + Int64(E) * 1000000 + Int64(R) * 10000000;  end;begin  State := [0..9];  Count := 0;  REKENLES1 := 0;  REKENLES2 := 0;  for N := 0 to 9 do    begin      Exclude(State, N);      for S := 0 to 9 do        if S in State then          begin            Exclude(State, S);            for T := 0 to 9 do              if T in State then                begin                  if (10 - Integer(S) + Integer(N) * Succ(Integer(T))) mod 10 <> T then                    continue;                  Exclude(State, T);                  ST := Integer(S) * 10 + T;                  for E := 0 to 9 do                  if E in State then                      begin                      Exclude(State, E);                        EN := Integer(E) * 10 + N;                        ET := Integer(E) * 10 + T;                      ENEN := EN * 100 + EN;                        for R := 0 to 9 do                          if (R in State) and TrueMod100 then                          begin                              Exclude(State, R);                              TERS := Integer(T) * 1000 + Integer(E) * 100 + Integer(R) * 10 + S;                              ERST := Integer(E) * 1000 + Integer(R) * 100 + ST;                            TTERS := Integer(T) * 10000 + TERS;                              for I := 0 to 9 do                                if (I in State) and TrueMod1000 then                                  begin                                  Exclude(State, I);                                  for M := 0 to 9 do                                      if (M in State) and TrueMod10000 then                                        begin                                          Exclude(State, M);                                        for K := 0 to 9 do                                          if (K in State) and TrueMod100000 then                                            begin                                              Exclude(State, K);                                              for L := 0 to 9 do                                                if (L in State) and IsSolution then                                                  begin                                                    Inc(Count);                                                    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);                                                    case Count of                                                      1: REKENLES1 := CalcREKENLES;                                                      else                                                        REKENLES2 := CalcREKENLES;                                                      WriteLn(REKENLES1,' * ', REKENLES2,' = ',                                                               REKENLES1 * REKENLES2);                                                      exit;                                                    end;                                                   end;                                                Include(State, K);                                                end;                                            Include(State, M);                                        end;                                    Include(State, I);                                    end;                              Include(State, R);                            end;                          Include(State, E);                      end;                    Include(State, T);                  end;              Include(State, S);            end;      Include(State, N);    end;end; var  Ticks: QWord; begin  Ticks := GetTickCount64;  Solve;  WriteLn('tick count = ', GetTickCount64 - Ticks);  ReadLn;end.     Best wishes to all. ---------------------------------------------------------------------- Bart · 2018-12-23 11:59 @avk: 0.014 ticks. I updated the scores. Bart ---------------------------------------------------------------------- Thaddy · 2018-12-23 12:09 @Bart Can you add that all tests are done on Intel CPU's? My adapted AVK (2) code compiled for arm is still faster than the second and third version on a Raspberry Pi. So it should be clear that the instruction set and the platform compiler can have a speed influence, even with a sub-optimal algorithm, as I explained. @AVK I suspect that your code also has better pipelining behavior than my set based version of your code on Intel and family: if it can run in a cache line, of course 0..9 will probably be faster than the set based approach. ---------------------------------------------------------------------- avk · 2018-12-23 12:11 @Bart Thank you very much. ---------------------------------------------------------------------- Martin_fr · 2018-12-23 13:27 I did some experiments. It seems some of the extra checks cost more time, than running the next loop. So I submit a new entry. (I tried various versions, and submit the fastest one) Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program minstreel2; {$mode objfpc}{$H+} uses  Classes, sysutils; {$DEFINE LOOP}  label lbl; var  rekenles1, rekenles2: QWord;  vminstreel, met, aa, en, er, et, x, cnt: Integer;   digits: packed array[0..9] of bytebool;  tc: LongWord;  i, k, l, t, n, s, e, r, m: integer; begin  tc:= GetTickCount;  {$IFDEF LOOP}  for aa := 0 to 100000 do begin  {$ENDIF}  FillByte(digits[0], 10*sizeof(digits[0]), 0);   cnt := 0;   for n := 0 to 9 do  if not digits[n] then  begin    digits[n] := true;     for i := 0 to 9 do    if not digits[i] then    begin      digits[i] := true;       for s := 0 to 9 do      if not digits[s] then      begin        digits[s] := true;         for r := 1 to 9 do      if not digits[r] then        begin          digits[r] := true;         for e := 0 to 9 do          if not digits[e] then          begin            digits[e] := true;            x := 10 *e;            er := x+r;             for k := 1 to 9 do            if not digits[k] then            begin              digits[k] := true;               for m := 1 to 9 do              if not digits[m] then              begin                digits[m] := true;                 for t := 1 to 9 do                if not digits[t] then                begin                digits[t] := true;                   for l := 1 to 9 do                if not digits[l] then                  begin                  digits[l] := true;                      en := x+n;                  et := x+t;                    if                    (K*10000+      er*100+S*10+T) =                       (R*1000000+     (x+K)*10000+    en*100+    en) +                                                       (M*100+    et) *                                                (T*1000+I*100+    en) -                       (L*1000000+        et*10000+T*1000+     er*10+S)                    then                  begin                      cnt := cnt + 1;                      {$IFnDEF LOOP}                      writeln('vminstreel ', m,i,n,s,t,r,e,e,l);                      writeln('rekenles  ', r,e,k,e,n,l,e,s);                      Write('K=',K);                    Write(', E=',E);                      Write(', R=',R);                    Write(', S=',S);                      Write(', T=',T);                    Write(', N=',N);                      Write(', M=',M);                    Write(', I=',I);                      Writeln(', L=',L);                      if cnt = 1 then begin                      rekenles1 := r*10000000+e*1000000+k*100000+e*10000+n*1000+l*100+e*10+s;                    end                      else begin                        rekenles2 := r*10000000+e*1000000+k*100000+e*10000+n*1000+l*100+e*10+s;                    end;                      {$ENDIF}                      if cnt = 2 then                        goto lbl;                    end;                      digits[l] := false;                  end;                digits[t] := false;                end;                digits[m] := false;              end;              digits[k] := false;            end;            digits[e] := false;          end;        digits[r] := false;        end;        digits[s] := false;      end;      digits[i] := false;    end;    digits[n] := false;  end;lbl:   {$IFnDEF LOOP}  writeln('product ', rekenles1 * rekenles2);  {$ENDIF}  {$IFDEF LOOP}  end;  {$ENDIF}  writeln(GetTickCount-tc);  readln;end. ---------------------------------------------------------------------- Bart · 2018-12-23 14:36 @Martin: 0.0006 ticks. Bart ---------------------------------------------------------------------- Blaazen · 2018-12-23 17:46 @ Martin IMO the first check Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   if not digits[n] then  on line 31 is not necessary. But it will not affect time, I guess. ---------------------------------------------------------------------- avk · 2018-12-23 18:13 removed ---------------------------------------------------------------------- Martin_fr · 2018-12-23 18:54 Quote from: Bart on December 23, 2018, 03:36:18 pm@Martin: 0.0006 ticks. Great, waiting for the next update of the scores. ---------------------------------------------------------------------- Bart · 2018-12-23 21:25 Quote from: Martin_fr on December 23, 2018, 07:54:17 pmQuote from: Bart on December 23, 2018, 03:36:18 pm@Martin: 0.0006 ticks. Great, waiting for the next update of the scores. Sorry, did not realize this was a submission (sine some others of your were'nt). I updated the score list. You're number 1 now. Bart ---------------------------------------------------------------------- avk · 2018-12-24 06:10 Quote from: Martin_fr on December 21, 2018, 11:05:27 pm... one may assume that none of the words can start with a 0. Thank you, completely overlooked this fact. I also added one more pruning rule. Nevertheless, I think that this all will not have a significant impact. Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program pazzle; {$mode objfpc}{$B-} uses  SysUtils; type  TDigit = 0..9; procedure Solve;var  State: set of TDigit;  N, S, T, E, R, I, K, M, L, Count: TDigit;  EN, ET, ST, TERS, ENEN, TIEN, METTIEN, ERST, KENEN, TTERS, KERST: Integer;  REKENLES1, REKENLES2: Int64;   function TrueMod100: Boolean;  begin    Result := (100 - (Integer(R) * 10 + S) + EN + EN * ET) mod 100 = ST;  end;  function TrueMod1000: Boolean;  begin    TIEN := Integer(T) * 1000 + Integer(I) * 100 + EN;    if EN * ET < 1000 then      exit(True);    Result := (20000 - TERS - ERST + ENEN + ET * TIEN) mod 1000 = 0;  end;  function TrueMod10000: Boolean;  begin    METTIEN := (Integer(M) * 100 + ET) * TIEN;    Result := (10000 - TERS + ENEN + METTIEN) mod 10000 = ERST;  end;  function TrueMod100000: Boolean;  begin    KENEN := Integer(K) * 10000 + ENEN + METTIEN;    KERST := Integer(K) * 10000 + ERST;    Result := (100000 - TTERS + KENEN) mod 100000 = KERST;  end;  function IsSolution: Boolean;  begin    Result := R * 1000000 + E * 100000 + KENEN - (L * 1000000 + E * 100000 + TTERS) = KERST;  end;  function CalcREKENLES: Int64;  begin    Result := Int64(S) + Int64(E) * 10 + Int64(L) * 100 + Int64(N) * 1000 + Int64(E) * 10000 +              Int64(K) * 100000 + Int64(E) * 1000000 + Int64(R) * 10000000;  end;begin  State := [0..9];  Count := 0;  REKENLES1 := 0;  REKENLES2 := 0;  for N := 0 to 9 do    begin      Exclude(State, N);      for S := 0 to 9 do        if S in State then          begin            Exclude(State, S);            for T := 1 to 9 do              if T in State then                begin                  if (Odd(T) xor (Odd(N) xor Odd(S))) or                     ((10 - Integer(S) + Integer(N) * Succ(Integer(T))) mod 10 <> T) then                    continue;                  Exclude(State, T);                  ST := Integer(S) * 10 + T;                  for E := 0 to 9 do                  if E in State then                      begin                      Exclude(State, E);                        EN := Integer(E) * 10 + N;                        ET := Integer(E) * 10 + T;                      ENEN := EN * 100 + EN;                        for R := 1 to 9 do                          if (R in State) and TrueMod100 then                          begin                              Exclude(State, R);                              TERS := Integer(T) * 1000 + Integer(E) * 100 + Integer(R) * 10 + S;                              ERST := Integer(E) * 1000 + Integer(R) * 100 + ST;                            TTERS := Integer(T) * 10000 + TERS;                              for I := 0 to 9 do                                if (I in State) and TrueMod1000 then                                  begin                                  Exclude(State, I);                                  for M := 1 to 9 do                                      if (M in State) and TrueMod10000 then                                        begin                                          Exclude(State, M);                                        for K := 1 to 9 do                                          if (K in State) and TrueMod100000 then                                            begin                                              Exclude(State, K);                                              for L := 1 to 9 do                                                if (L in State) and IsSolution then                                                  begin                                                    Inc(Count);                                                    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);                                                    case Count of                                                      1: REKENLES1 := CalcREKENLES;                                                      else                                                        REKENLES2 := CalcREKENLES;                                                      WriteLn(REKENLES1,' * ', REKENLES2,' = ',                                                               REKENLES1 * REKENLES2);                                                      exit;                                                    end;                                                  end;                                                Include(State, K);                                                end;                                            Include(State, M);                                        end;                                    Include(State, I);                                    end;                              Include(State, R);                            end;                          Include(State, E);                      end;                    Include(State, T);                  end;              Include(State, S);            end;      Include(State, N);    end;end; var  Ticks: QWord; begin  Ticks := GetTickCount64;  Solve;  WriteLn('tick count = ', GetTickCount64 - Ticks);  ReadLn;end. ---------------------------------------------------------------------- Bart · 2018-12-24 21:06 @avk: 0.00156 ticks (so it's slower on my machine than your previous). A thought: since we can infer that for both solutions of REKENLES it is highly unlikely that there the letter E will be the one that differs, can we take advantage of this in the order of the loop variables? Bart ---------------------------------------------------------------------- Martin_fr · 2018-12-26 13:06 Just thought I post the version of my code that I had submitted by mail. (timing iirc 0.06...) There are some digits that can be calculated, rather than looped. Also, once you have the first solution, only certain letters can change for the 2nd solution. IIRC - taking into account that calculated letters can only change when the letters they derive from change - only k can change. So the code could start a loop "for k2 := k+1 to 9". But since the below code has k already as one of the inner loops it does not benefit. Also such an extra loop is only beneficial, if the code is allowed to abort looping. If all loops must be finished, then the 2nd result will be encountered anyway. What could still be added is: By looking at the formula Code: [Select]KERST = REKENEN + MET * TIEN - LETTERS 54321   7654321   321   4321   7654321 "Kerst" has zero millions (pos 7). So the difference between "REKENEN + MET * TIEN" and "LETTTERS" must have 0 millions too. Even assuming the product to be as small as possible, when subtracting LETTERS, there can be a max carry on of 1. So it must be true that: R <= L+1 And if T < K (pos 5, no carry on) then R= 0) and (l <= 9) and         not digits[l] and         (l * 1000000 = x)      then      begin        {$IFnDEF LOOP}        writeln('vminstreel ', m,i,n,s,t,r,e,e,l);        writeln('rekenles  ', r,e,k,e,n,l,e,s);      Write('K=',K);        Write(', E=',E);        Write(', R=',R);      Write(', S=',S);        Write(', T=',T);        Write(', N=',N);      Write(', M=',M);        Write(', I=',I);        Writeln(', L=',L);        //writeln('KERST = REKENEN + MET * TIEN - LETTERS ',  K,E,R,S,T,' = ',R,E,K,E,N,E,N,' + ',M,E,T,' * ',T,I,E,N,' - ',L,E,T,T,E,R,S);        {$ENDIF}        if rekenles1 = 0 then begin        //vminstreel := m*100000000+i*10000000+n*1000000+s*100000+t*100 00+r*1000+e*100+e*10+l;          rekenles1 := r*10000000+e*1000000+k*100000+e*10000+n*1000+l*100+e*10+s;          // Only letters that can change for rekenles are          // s (but it is fixed due to t and n), k, r (r is fixed to)          // k already is the most inner loop        end        else begin          rekenles2 := r*10000000+e*1000000+k*100000+e*10000+n*1000+l*100+e*10+s;          exit;//goto lbl;        end;         end;        digits[k] := false;    end;    digits[i] := false;  end;  end;end;  begin  tc:= GetTickCount;  {$IFDEF LOOP}  for aa := 0 to 10000 do begin  {$ENDIF}  FillByte(digits[0], 10*sizeof(digits[0]), 0);   rekenles1 := 0;  rekenles2 := 0;   for n := 0 to 9 do  if not digits[n] then  begin    digits[n] := true;      {$IFDEF NoZeroWordStart}    for t := 9 downto 1 do begin    {$ELSE}    for t := 9 downto 0 do begin    {$ENDIF}    digits[t] := true;       //// t = (n + t*n - s ) mod 10      //// last_digit_of( t - (n + t*n) ) = -s      s := (-t + n + t*n+10) mod 10; // +10 do not go negative       if not digits[s] then      begin      digits[s] := true;        for e := 0 to 9 do        if not digits[e] then        begin          // st = en + et*en - rs          // rs = -st +  en + et*en          x := e * 10;          en := x+n;        et := x+t;          st := s*10+t;          rs  := -st + en + et*en;          if (rs < 0) or ((rs mod 10) <> s) then continue;        r := (rs div 10) mod 10;          {$IFDEF NoZeroWordStart}        if r = 0 then continue;          {$ENDIF}           digits[e] := true;           if not digits[r] then          begin            digits[r] := true;            rs := rs mod 100;            rst := rs*10+t;            neners := (rst - ((n*100+en) - (e*100+rs)))  ;          if neners < 0 then neners := neners + 1000;             {$IFDEF NoZeroWordStart}            for m := 9 downto 1 do            {$ELSE}            for m := 9 downto 0 do            {$ENDIF}            if not digits[m] then            begin              digits[m] := true;            met := m*100+et;              innerloops;if rekenles2<>0 then goto lbl;              digits[m] := false;            end;            digits[r] := false;          end;          digits[e] := false;        end;        digits[s] := false;      end;      digits[t] := false;    end;    digits[n] := false;  end;lbl:  {$IFDEF LOOP}//    if aa = 0 then writeln('product ', rekenles1 * rekenles2);  {$ENDIF}   {$IFnDEF LOOP}  writeln('product ', rekenles1 * rekenles2);  {$ENDIF}  {$IFDEF LOOP}  end;  {$ENDIF}  writeln(GetTickCount-tc);  readln;end. ---------------------------------------------------------------------- Kays · 2018-12-27 00:37 I can't beat none of you. Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i (**        \brief contest submission to a christmas puzzle                \version @5C244448        \author Kai Burghardt *)program xmas(input, output, stderr); {$mode FPC} uses        // sysUtils for getTickCount64        sysUtils; //                                                                    //// M A I N                                                              ////                                                                    // var        // sub-range types are, as far as I understand the programmer's manual,        // stored in the smallest possible integer type        // => explicitely use nativeInt        E: nativeInt;      I: nativeInt;        K: nativeInt;        L: nativeInt;        M: nativeInt;        N: nativeInt;        R: nativeInt;        S: nativeInt;        T: nativeInt;        /// D = E - 1           D: nativeInt;        /// U = T + 1        U: nativeInt;        /// temporary variable        X: nativeInt;        /// accumulator        Y: nativeInt;        /// stores two REKENLES results        rekenles: array[0..1] of nativeInt;        /// for speed measurement        tick: qWord; // printResult {{{(**        \brief prints the result MINSTREEL*)// _inline_ procedure, so no frame's created// but the whole procedure's definition is copied// // [according to problem definition is "expected to be executed twice"]procedure printResult; inline;begin        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);end;// }}} function f(): nativeInt;begin        D := E - 1;        U := T + 1;                Y := -S - T;                X := R - L;      if X <> 0 then        begin                inc(Y, trunc(fPower10(X, 6)));        end;                X := M * T;        if X <> 0 then      begin                inc(Y, trunc(fPower10(X, 5)));        end;              X := T * D + I * M;        if X <> 0 then        begin              inc(Y, trunc(fPower10(X, 4)));        end;                X := T * (T - 1) + E * (I + M);        if X <> 0 then        begin              inc(Y, trunc(fPower10(X, 3)));        end;                X := E * D + N * (M + 1) + I * T - R;        if X <> 0 then        begin                inc(Y, trunc(fPower10(X, 2)));        end;              X := 10 * (E * (U + N) - R - S);        inc(Y, X);              inc(Y, N * U);                f := Y;end; // separated from the rest of code,// so exit leaves the frameprocedure p;const        allDigits = [0..9];var        digits: set of 0..9;begin        // produce OEIS sequence A010784        for E in allDigits do        begin                digits := [E];                for T in allDigits - digits do                begin                        include(digits, T);                        for R in allDigits - digits do                        begin                                include(digits, R);                                for N in allDigits - digits do                                begin                                      include(digits, N);                                      for S in allDigits - digits do                                      begin                                                include(digits, S);                                                for L in allDigits - digits  do                                              begin                                                        include(digits, L);                                                      for I in allDigits - digits do                                                      begin                                                              include(digits, I);                                                              for M in allDigits - digits do                                                              begin                                                                      include(digits, M);                                                                      for K in allDigits - digits do                                                                      begin                                                                              if f() = 0 then                                                                              begin                                                                                      printResult;                                                                                                                                                                          rekenles[1] := trunc(                                                                                                    fPower10(R, 7)                                                                                                      + fPower10(E, 6)                                                                                                    + fPower10(K, 5)                                                                                                    + fPower10(E, 4)                                                                                                      + fPower10(N, 3)                                                                                                      + fPower10(L, 2)                                                                                                    + fPower10(E, 1)                                                                                                      + S                                                                                            );                                                                                      if rekenles[0] < 0 then                                                                                    begin                                                                                              rekenles[0] := rekenles[1];                                                                                            rekenles[1] := 0;                                                                                      end                                                                                      else                                                                                      begin                                                                                              exit;                                                                                    end;                                                                              end;                                                                      end;                                                                      exclude(digits, M);                                                              end;                                                              exclude(digits, I);                                                      end;                                                      exclude(digits, L);                                              end;                                              exclude(digits, S);                                        end;                                      exclude(digits, N);                              end;                                exclude(digits, R);                        end;                        exclude(digits, T);                end;        end;end; begin        tick := getTickCount64();                E := 0;        I := 0;        K := 0;        L := 0;        M := 0;        N := 0;        R := 0;        S := 0;        T := 0;        rekenles[0] := -1;        rekenles[1] := 0;                p;                writeLn(rekenles[0], ' * ', rekenles[1],' = ', rekenles[0] * rekenles[1]);                tick := getTickCount64() - tick;        writeLn(tick);// end of xmasend.// vim: set fdm=marker ts=2:It took me some time to come up with a neat algorithm producing numbers with distinct decimal digits. I have no idea yet, though, how I arrange the loop variables smartest. And trial and error, changing them by hand is quite bothersome. I chose fPower10 because it says it's being fast. I'm probably a tick faster if I stay in the ALU, though. ---------------------------------------------------------------------- engkin · 2018-12-27 02:42 Congratulations to Martin, avk, Blaazen and User137. Amazing ideas, and neat code. Thank you Bart for this puzzle, but you still did not share your solution. Quote from: SymbolicFrank on December 22, 2018, 01:22:46 amThe fastest way to do it is by using constants, and having the compiler calculate them. But that is forbidden. Why forbidden? That was one of the ideas I planned to try. I abandoned it after you mentioned it. But then I got busy and could not try anything. Quote from: Bart on December 21, 2018, 10:05:45 amHow do I count CPU ticks (on Windows that is)? Since FPC 3.0.4 does not recognize rdtscp in avk's code, I thought to mention the code I use: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i {$AsmMode intel}function GetTickCount64: Int64; assembler; asm DW 0310FH end; @Kays, the important thing that you tried. The puzzle itself is for fun. Happy holidays everyone! ---------------------------------------------------------------------- Bart · 2018-12-27 17:18 Quote from: engkin on December 27, 2018, 03:42:53 amThank you Bart for this puzzle, but you still did not share your solution. Here's my original, rather embarrassing solution: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program aivd3; {  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?} uses  sysutils;var  K,E,R,S,T,N,M,I,L,Res,KERST,REKENEN,MET,TIEN,LETTERS: integer;  Digits: set of byte;  REKENLES: array[1..2] of Integer;  T0, Ticks: LongWord; begin  T0 := GetTickCount;    REKENLES[1] := -1;  REKENLES[2] := -1;  for k:=0 to 9 do  begin    Digits := [K];    for E := 0 to 9 do if not (E in Digits) then    begin      Digits := Digits + [E];      for R := 0 to 9 do if not (R in Digits) then      begin      Digits := Digits + [R];        for S := 0 to 9 do if not (S in Digits) then        begin          Digits := Digits + [S];          for T := 0 to 9 do if not (t in Digits) then          begin          Digits := Digits + [T];            for N := 0 to 9 do if not (N in Digits) then            begin              Digits := Digits + [n];            for M :=0 to 9 do if not (M in Digits) then              begin                Digits := Digits + [M];                for I := 0 to 9 do if not (I in Digits) then                begin                Digits := Digits + [I];                  for L := 0 to 9 do if not (L in Digits) then                  begin                    //writeln(k,e,r,s,t,n,m,i,l);                     MET := 100*M+10*E+T;      //MET                     TIEN :=  (1000*T+100*I+10*E+N);  //MET * TIEN                     REKENEN := (1000000*R+100000*E+10000*K+1000*E+100*N+10*E+N);                     LETTERS := (1000000*L+100000*E+10000*T+1000*T+100*E+10*R+S);                   RES := REKENEN + (MET*TIEN) - LETTERS;                     KERST := (10000*K+1000*E+100*R+10*S+T);                     if (Res = KERST) then                     begin                      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);                      if REKENLES[1] = -1 then                        REKENLES[1] := 10000000*R+1000000*E+100000*K+10000*E+1000*N+100*L+10*E+S                    else                      begin                        REKENLES[2] := 10000000*R+1000000*E+100000*K+10000*E+1000*N+100*L+10*E+S;                      writeln(REKENLES[1],' * ',REKENLES[2],' = ',Int64(REKENLES[1])*Int64(REKENLES[2]));                        Ticks := GetTickCount - T0;                        writeln('Ticks: ',Ticks);                        Exit; //We know there are only 2 solutions                      end;                     end;                end;                  Digits := Digits - [I];                end;                Digits := Digits - [M];              end;            Digits := Digits - [N];            end;            Digits := Digits - [T];          end;          Digits := Digits - [S];        end;        Digits := Digits - [R];      end;      Digits := Digits - [E];    end;  end;  //Ticks: 344end. Just brute forcing the thing. Interestingly a collegue of mine told me that a relative of her had solved the puzzle in Python in a single line. I'm still waiting for the sourcecode for that one. Bart ---------------------------------------------------------------------- Bart · 2018-12-27 17:35 Quote from: Kays on December 27, 2018, 01:37:09 am I can't beat none of you. 150 ticks. At least your faster than me  But: your end calculation is wrong: 34540942 * 34640942 = 124422020. You need to cast your operands to Int64 before doing the multiplication. Bart ---------------------------------------------------------------------- Bart · 2018-12-27 17:55 OK, I got the Python solution I mentioned above. It's not a one-liner. Code: Python  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i # KERST = REKENEN + MET*TIEN - LETTERS# a) MINSTREEL# b) REKENLES  2x from itertools import permutationsimport copy reference = 'KERSTNMIL'result = []perms = [''.join(p) for p in permutations('1234567890')]#perms = perms[1583749:]print("controleer {} varianten".format(len(perms)))KERST = 'KERST'REKENEN = 'REKENEN'MET = 'MET'TIEN = 'TIEN'LETTERS = 'LETTERS'MINSTREEL = 'MINSTREEL'word_list = [list(KERST),list(REKENEN),list(MET),list(TIEN),list(LETTERS)]for item in perms:    words = copy.deepcopy(word_list)    for word in words:        for i, c in enumerate(word):            pos = reference.index(c)            word[i] = item[pos]    kerst = int(''.join(map(str,words[0])))    rekenen = int(''.join(map(str,words[1])))    met = int(''.join(map(str,words[2])))    tien = int(''.join(map(str,words[3])))    letters = int(''.join(map(str,words[4])))    if rekenen + met*tien - letters == kerst:        result.append(item)        print("{}= {} + {} * {} - {}".format(kerst,rekenen,met,tien,letters))        if(len(result)==2):            breakprint(result)# antwoord 3aminstreel = list(MINSTREEL)for i, c in enumerate(minstreel):    pos = reference.index(c)    minstreel[i] = result[0][pos]print("\n3a "+MIN STREEL+"="+''.join(map(str,minstreel))) REKENLES='REKENLES'rekenles1 = list(REKENLES)for i, c in enumerate(rekenles1):    pos = reference.index(c)    rekenles1[i] = result[0][pos]ans1 = int(''.join(map(str,rekenles1)))rekenles2 = list(REKENLES)for i, c in enumerate(rekenles2):    pos = reference.index(c)    rekenles2[i] = result[1][pos]ans2 = int(''.join(map(str,rekenles2)))print("\n3b")prin t(REKENLES+"={}".format(ans1))print(REKENLES+"={}".format(ans2))print( "REKENLES*REKENLES={}".format(ans1*ans2)) Can sombody who has Python time this against the winning code (or my original, a few posts above this)? Bart ---------------------------------------------------------------------- bytebites · 2018-12-27 18:22 Python: real   2m49.760s user   2m49.602s sys   0m0.088s Bart's code real   0m0.028s user   0m0.028s sys   0m0.001s ---------------------------------------------------------------------- Kays · 2018-12-27 18:50 Quote from: Bart on December 27, 2018, 06:35:30 pmBut: your end calculation is wrong: 34540942 * 34640942 = 124422020. You need to cast your operands to Int64 before doing the multiplication.Huh. I wouldn't have submitted it, if it didn't produce the right result. On my x86_64 machine it works fine. Quote from: Bart on December 27, 2018, 06:35:30 pmQuote from: Kays on December 27, 2018, 01:37:09 am I can't beat none of you. 150 ticks. At least your faster than me  “You are faster […]” Oh, huh.  My laptop needs at least 320 ticks, more like 350. ---------------------------------------------------------------------- Bart · 2018-12-27 22:17 Quote from: Kays on December 27, 2018, 07:50:48 pmQuote from: Bart on December 27, 2018, 06:35:30 pmBut: your end calculation is wrong: 34540942 * 34640942 = 124422020. You need to cast your operands to Int64 before doing the multiplication.Huh. I wouldn't have submitted it, if it didn't produce the right result. On my x86_64 machine it works fine. My fpc is 32-bit, so there you go. NativeInt = PtrInt = Logint on 32-bit, whereas it maps to Int64 on 64-bit CPU's. Quote from: Kays on December 27, 2018, 07:50:48 pm“You are faster […]” No, your code really is faster than mine: Code: [Select]C:\Users\Bart\LazarusProjecten\ConsoleProjecten\fun\aivd>aivd3 K=5, E=4, R=3, S=2, T=8, N=0, M=7, I=1, L=9  MINSTREEL=710283449, REKENLES=34540942 K=6, E=4, R=3, S=2, T=8, N=0, M=7, I=1, L=9  MINSTREEL=710283449, REKENLES=34640942 34540942 * 34640942 = 1196530768447364 Ticks: 375 C:\Users\Bart\LazarusProjecten\ConsoleProjecten\fun\aivd>kai\aivd3 K=5, E=4, R=3, S=2, T=8, N=0, M=7, I=1, L=9  MINSTREEL=710283449, REKENLES=34540942 K=6, E=4, R=3, S=2, T=8, N=0, M=7, I=1, L=9  MINSTREEL=710283449, REKENLES=34640942 34540942 * 34640942 = 1196530768447364 Ticks: 156 Bart ---------------------------------------------------------------------- Bart · 2018-12-27 22:19 Quote from: bytebites on December 27, 2018, 07:22:32 pmPython: real   2m49.760s user   2m49.602s sys   0m0.088s That is: 2 minutes and 49 seconds for the python solution????? Bart ---------------------------------------------------------------------- Kays · 2018-12-28 16:26 Quote from: Bart on December 27, 2018, 11:17:19 pm[…] My fpc is 32-bit, so there you go. NativeInt = PtrInt = Logint on 32-bit, whereas it maps to Int64 on 64-bit CPU's […]Alright, I see. Quote from: Bart on December 27, 2018, 11:17:19 pm[…]Quote from: Kays on December 27, 2018, 07:50:48 pm“You are faster […]” No, your code really is faster than mine: […] I was correcting your English. ---------------------------------------------------------------------- Bart · 2018-12-28 16:54 Quote from: Kays on December 28, 2018, 05:26:46 pmI was correcting your English. Feel a bit embarrassed now  Bart ---------------------------------------------------------------------- Thaddy · 2018-12-28 17:05 Have to look into that Python code, though. That is unbelievably slow. (Why call enumerate so many times, that is really not necessary) ---------------------------------------------------------------------- avk · 2018-12-29 06:30 Congratulations to Martin_fr. Many thanks to Bart for this puzzle and time spent. Thanks to everyone who participated in the contest. HAPPY NEW YEAR! ---------------------------------------------------------------------- Bart · 2018-12-29 09:36 Quote from: avk on December 29, 2018, 07:30:34 amMany thanks to Bart for this puzzle and time spent. The puzzle is care of the AIVD (Dutch intelligence agency). And time flies when you're having fun  Quote from: avk on December 29, 2018, 07:30:34 amHAPPY NEW YEAR!  Code: C  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i +=1; Bart ---------------------------------------------------------------------- bytebites · 2018-12-31 13:17 Python-code with similar approach gives: Prints only final product. Code: Python  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i class ready(Exception):  pass try:  digits=[False]*10  cnt=0  for n in range(10):    print(n)    if not digits[n]:      digits[n]=True      for i in range(10):        if not digits[i]:          digits[i]=True        for s in range(10):            if not digits[s]:              digits[s]=True              for r in range(10):                if not digits[r]:                  digits[r]=True                  for e in range(10):                    if not digits[e]:                      digits[e]=True                      x=10*e                      er=x+r                      for k in range(10):                      if not digits[k]:                          digits[k]=True                        for m in range(10):                            if not digits[m]:                              digits[m]=True                            for t in range(10):                                if not digits[t]:                                  digits[t]=True                                for l in range(10):                                  if not digits[l]:                                       en=x+n                                    et=x+t                                    if (k*10000+ er*100+s*10+t ==                                     r*1000000+ (x+k)*10000+en*100+en+                                     (m*100+et)*                                       (t*1000+i*100+en)-                                       (l*1000000+et*10000+t*1000+er*10+s)):                                        cnt+=1                                          if cnt == 1:                                              rekenles1 = r*10000000+e*1000000+k*100000+e*10000+n*1000+l*100+e*10+s                                        else:                                            rekenles2 = r*10000000+e*1000000+k*100000+e*10000+n*1000+l*100+e*10+s                                        if cnt ==2:                                             raise ready                                   digits[t] = False;                              digits[m] = False;                        digits[k] = False;                      digits[e] = False;                  digits[r] = False;              digits[s] = False;        digits[i] = False;      digits[n] = False;except ready:  print('product ', rekenles1 * rekenles2)  real   0m0.029s user   0m0.025s sys   0m0.000s ---------------------------------------------------------------------- Bart · 2018-12-31 13:42 Thank you for investigating that! Bart