Contest: fastest program to solve a christmas puzzle

[Bart]

Thank you Bart for this puzzle, but you still did not share your solution.

Here's my original, rather embarrassing solution:

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

1. program aivd3;
2.  
3. {
4.   Given that:
5.     KERST = REKENEN + MET * TIEN - LETTERS
6.     Each letter represents a single unique digit (0..9)
7.  
8.   - What is the value of MINSTREEL
9.   - REKENLES can be 2 different numbers: what is the product of these two?
10. }
11.  
12. uses
13.   sysutils;
14. var
15.   K,E,R,S,T,N,M,I,L,Res,KERST,REKENEN,MET,TIEN,LETTERS: integer;
16.   Digits: set of byte;
17.   REKENLES: array[1..2] of Integer;
18.   T0, Ticks: LongWord;
19.  
20. begin
21.   T0 := GetTickCount;
22.  
23.  
24.   REKENLES[1] := -1;
25.   REKENLES[2] := -1;
26.   for k:=0 to 9 do
27.   begin
28.     Digits := [K];
29.     for E := 0 to 9 do if not (E in Digits) then
30.     begin
31.       Digits := Digits + [E];
32.       for R := 0 to 9 do if not (R in Digits) then
33.       begin
34.         Digits := Digits + [R];
35.         for S := 0 to 9 do if not (S in Digits) then
36.         begin
37.           Digits := Digits + [S];
38.           for T := 0 to 9 do if not (t in Digits) then
39.           begin
40.             Digits := Digits + [T];
41.             for N := 0 to 9 do if not (N in Digits) then
42.             begin
43.               Digits := Digits + [n];
44.               for M :=0 to 9 do if not (M in Digits) then
45.               begin
46.                 Digits := Digits + [M];
47.                 for I := 0 to 9 do if not (I in Digits) then
48.                 begin
49.                   Digits := Digits + [I];
50.                   for L := 0 to 9 do if not (L in Digits) then
51.                   begin
52.                     //writeln(k,e,r,s,t,n,m,i,l);
53.                      MET := 100*M+10*E+T;      //MET
54.                      TIEN :=  (1000*T+100*I+10*E+N);  //MET * TIEN
55.                      REKENEN := (1000000*R+100000*E+10000*K+1000*E+100*N+10*E+N);
56.                      LETTERS := (1000000*L+100000*E+10000*T+1000*T+100*E+10*R+S);
57.                      RES := REKENEN + (MET*TIEN) - LETTERS;
58.                      KERST := (10000*K+1000*E+100*R+10*S+T);
59.                      if (Res = KERST) then
60.                      begin
61.                       write('K=',K);
62.                       write(', E=',E);
63.                       write(', R=',R);
64.                       write(', S=',S);
65.                       write(', T=',T);
66.                       write(', N=',N);
67.                       write(', M=',M);
68.                       write(', I=',I);
69.                       write(', L=',L);
70.                       write('  MINSTREEL=',M,I,N,S,T,R,E,E,L,', ');
71.                       writeln('REKENLES=',R,E,K,E,N,L,E,S);
72.                       if REKENLES[1] = -1 then
73.                         REKENLES[1] := 10000000*R+1000000*E+100000*K+10000*E+1000*N+100*L+10*E+S
74.                       else
75.                       begin
76.                         REKENLES[2] := 10000000*R+1000000*E+100000*K+10000*E+1000*N+100*L+10*E+S;
77.                         writeln(REKENLES[1],' * ',REKENLES[2],' = ',Int64(REKENLES[1])*Int64(REKENLES[2]));
78.                         Ticks := GetTickCount - T0;
79.                         writeln('Ticks: ',Ticks);
80.                         Exit; //We know there are only 2 solutions
81.                       end;
82.                      end;
83.                   end;
84.                   Digits := Digits - [I];
85.                 end;
86.                 Digits := Digits - [M];
87.               end;
88.               Digits := Digits - [N];
89.             end;
90.             Digits := Digits - [T];
91.           end;
92.           Digits := Digits - [S];
93.         end;
94.         Digits := Digits - [R];
95.       end;
96.       Digits := Digits - [E];
97.     end;
98.   end;
99.   //Ticks: 344
100. end.

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]

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]

OK, I got the Python solution I mentioned above.
It's not a one-liner.

Code: Python  [Select][+][-]

1. # KERST = REKENEN + MET*TIEN - LETTERS
2. # a) MINSTREEL
3. # b) REKENLES  2x
4.  
5. from itertools import permutations
6. import copy
7.  
8. reference = 'KERSTNMIL'
9. result = []
10. perms = [''.join(p) for p in permutations('1234567890')]
11. #perms = perms[1583749:]
12. print("controleer {} varianten".format(len(perms)))
13. KERST = 'KERST'
14. REKENEN = 'REKENEN'
15. MET = 'MET'
16. TIEN = 'TIEN'
17. LETTERS = 'LETTERS'
18. MINSTREEL = 'MINSTREEL'
19. word_list = [list(KERST),list(REKENEN),list(MET),list(TIEN),list(LETTERS)]
20. for item in perms:
21.     words = copy.deepcopy(word_list)
22.     for word in words:
23.         for i, c in enumerate(word):
24.             pos = reference.index(c)
25.             word[i] = item[pos]
26.     kerst = int(''.join(map(str,words[0])))
27.     rekenen = int(''.join(map(str,words[1])))
28.     met = int(''.join(map(str,words[2])))
29.     tien = int(''.join(map(str,words[3])))
30.     letters = int(''.join(map(str,words[4])))
31.     if rekenen + met*tien - letters == kerst:
32.         result.append(item)
33.         print("{}= {} + {} * {} - {}".format(kerst,rekenen,met,tien,letters))
34.         if(len(result)==2):
35.             break
36. print(result)
37. # antwoord 3a
38. minstreel = list(MINSTREEL)
39. for i, c in enumerate(minstreel):
40.     pos = reference.index(c)
41.     minstreel[i] = result[0][pos]
42. print("\n3a "+MINSTREEL+"="+''.join(map(str,minstreel)))
43.  
44. REKENLES='REKENLES'
45. rekenles1 = list(REKENLES)
46. for i, c in enumerate(rekenles1):
47.     pos = reference.index(c)
48.     rekenles1[i] = result[0][pos]
49. ans1 = int(''.join(map(str,rekenles1)))
50. rekenles2 = list(REKENLES)
51. for i, c in enumerate(rekenles2):
52.     pos = reference.index(c)
53.     rekenles2[i] = result[1][pos]
54. ans2 = int(''.join(map(str,rekenles2)))
55. print("\n3b")
56. print(REKENLES+"={}".format(ans1))
57. print(REKENLES+"={}".format(ans2))
58. 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]

Python:
real   2m49.760s
user   2m49.602s
sys   0m0.088s

Bart's code
real   0m0.028s
user   0m0.028s
sys   0m0.001s

[Kays]

But: 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.

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]

But: 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.

“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]

Python:
real   2m49.760s
user   2m49.602s
sys   0m0.088s

That is: 2 minutes and 49 seconds for the python solution?????

Bart

[Kays]

[…] 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.

[…]

“You are faster […]”

No, your code really is faster than mine: […]

I was correcting your English.

[Bart]

I was correcting your English.

Feel a bit embarrassed now 

Bart

[Thaddy]

Have to look into that Python code, though. That is unbelievably slow. (Why call enumerate so many times, that is really not necessary)

[avk]

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]

Many 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 

HAPPY NEW YEAR!   

Code: C  [Select][+][-]

1. +=1;

Bart

[bytebites]

Python-code with similar approach gives:
Prints only final product.

Code: Python  [Select][+][-]

1. class ready(Exception):
2.   pass
3.  
4. try:
5.   digits=[False]*10
6.   cnt=0
7.   for n in range(10):
8.     print(n)
9.     if not digits[n]:
10.       digits[n]=True
11.       for i in range(10):
12.         if not digits[i]:
13.           digits[i]=True
14.           for s in range(10):
15.             if not digits[s]:
16.               digits[s]=True
17.               for r in range(10):
18.                 if not digits[r]:
19.                   digits[r]=True
20.                   for e in range(10):
21.                     if not digits[e]:
22.                       digits[e]=True
23.                       x=10*e
24.                       er=x+r
25.                       for k in range(10):
26.                         if not digits[k]:
27.                           digits[k]=True
28.                           for m in range(10):
29.                             if not digits[m]:
30.                               digits[m]=True
31.                               for t in range(10):
32.                                 if not digits[t]:
33.                                   digits[t]=True
34.                                   for l in range(10):
35.                                     if not digits[l]:
36.  
37.                                       en=x+n
38.                                       et=x+t
39.                                       if (k*10000+ er*100+s*10+t ==
40.                                        r*1000000+ (x+k)*10000+en*100+en+
41.                                        (m*100+et)*
42.                                        (t*1000+i*100+en)-
43.                                        (l*1000000+et*10000+t*1000+er*10+s)):
44.                                           cnt+=1
45.                                           if cnt == 1:
46.                                               rekenles1 = r*10000000+e*1000000+k*100000+e*10000+n*1000+l*100+e*10+s
47.                                           else:
48.                                               rekenles2 = r*10000000+e*1000000+k*100000+e*10000+n*1000+l*100+e*10+s
49.                                           if cnt ==2:
50.                                                raise ready
51.  
52.                                   digits[t] = False;
53.                               digits[m] = False;
54.                           digits[k] = False;
55.                       digits[e] = False;
56.                   digits[r] = False;
57.               digits[s] = False;
58.           digits[i] = False;
59.       digits[n] = False;
60. except ready:
61.   print('product ', rekenles1 * rekenles2)
62.  

real   0m0.029s
user   0m0.025s
sys   0m0.000s

[Bart]

Thank you for investigating that!

Bart