Teaser 2705: In the pub
From The Sunday Times, 27th July 2014 [link] [link]
George and Martha are in the pub. He has ordered a glass of lager for her and some ale for himself. He has written three numbers in increasing order, none involving a zero, then consistently replaced digits by letters to give:
DRANK
GLASS
LAGERGeorge explains this to Martha and tells her that the third number is in fact the sum of the previous two. From this information she is able to work out the value of each letter.
What is the number of George’s ALE?
[teaser2705]
John Crabtree, 
GeoffR, and 1 other are discussing. 
Frits are discussing. 
Robert Brown, and 1 other are discussing. 
Dilwyn Jones, and 1 other are discussing. 
S2T2 
Jim Randell 5:43 pm on 13 August 2020 Permalink |
We can solve this straightforwardly using the [[
SubstitutedExpression()]] solver from the enigma.py library.The following run file executes in 270ms.
Run: [ @replit ]
Solution: ALE = 392.
For a faster execution time, we can use the [[
SubstitutedSum()]] solver to solve the alphametic sum, and then check the solutions it finds to ensure D < G.from enigma import (SubstitutedSum, irange, printf) # all digits are non-zero p = SubstitutedSum(['DRANK', 'GLASS'], 'LAGER', digits=irange(1, 9)) for s in p.solve(check=(lambda s: s['D'] < s['G']), verbose=1): printf("ALE={ALE}", ALE=p.substitute(s, 'ALE'))By itself the alphametic sum has 3 solutions (when 0 digits are disallowed), but only one of these has D < G.
LikeLike
Frits 11:26 am on 14 August 2020 Permalink |
@Jim
You might also add “D + G == L or D + G + 1 == L” to speed things up.
LikeLike
Jim Randell 2:53 pm on 14 August 2020 Permalink |
Yes. If we break down the sum into individual columns, with carries of 0 or 1 between them we can use the following run file to solve the problem:
#! python -m enigma -rr SubstitutedExpression --answer="{ALE}" --distinct="ADEGKLNRS" --invalid="0,ADEGKLNRS" --invalid="2-9,abcd" # breaking the sum out into individual columns "{D} + {G} + {a} = {L}" "{R} + {L} + {b} = {aA}" "{A} + {A} + {c} = {bG}" "{N} + {S} + {d} = {cE}" "{K} + {S} = {dR}" # and G > D "{G} > {D}" --template="(DRANK + GLASS = LAGER) (G > D)"If we specify the [[
--verbose=32]] to measure the internal run-time of the generated code, we find that it runs in 170µs. (The total execution time for the process (which is what I normally report) is 97ms).The question is whether the fraction of a second saved in run time is paid off by the amount of additional time (and effort) taken to write the longer run file.
LikeLike
Frits 8:18 pm on 15 August 2020 Permalink |
@Jim,
If I use [[ –verbose=32 ]] on your code (with pypy) the internal run-time is 20% of the total execution time (15ms / 75ms). A lot more than you reported.
I rewrote the generated code.
It runs approx 3 times faster (elapsed time).
PS Currently I am more interested in efficient Python code than the easiest/shortest way of programming.
# breaking the sum out into individual columns # "{D} + {G} + {a} = {L}" # "{R} + {L} + {b} = {aA}" # "{A} + {A} + {c} = {bG}" # "{N} + {S} + {d} = {cE}" # "{K} + {S} = {dR}" notIn = lambda w: [x for x in range(1,10) if x not in w] for A in [1, 2, 3, 4, 5, 6, 7, 8, 9]: for c in [0, 1]: x = 2*A + c; G = x % 10 if G != A and G in {2,3,4,5,6,7,8}: b = x // 10 for D in [1, 2, 3, 4, 5, 6, 7]: if D != A and G > D: for a in [0, 1]: L = D + G + a if L != A and L < 10: for R in notIn({D,G,L,A}): x = R + L + b if x % 10 == A and x // 10 == a: for K in notIn({D,G,L,A,R}): for S in notIn({D,G,L,A,R,K}): x = K + S if x % 10 == R: d = x // 10 for N in notIn({D,G,L,A,R,K,S}): x = N + S + d E = x % 10 if E not in {D,G,L,A,R,K,S,N,0}: if x // 10 == c: print(" ALE DRANK GLASS LAGER\n", " ---------------------\n", A*100+L*10+E, D*10000+R*1000+A*100+N*10+K, G*10000+L*1000+A*100+S*11, L*10000+A*1000+G*100+E*10+R)LikeLike
Jim Randell 10:00 am on 24 March 2021 Permalink |
I’ve added the [[
SubstitutedExpression.split_sum()]] method to enigma.py, so you don’t have to split out the columns manually:from enigma import SubstitutedExpression # split the sum into columns args = SubstitutedExpression.split_sum("DRANK + GLASS = LAGER") # none of the symbols in the original sum can be zero args.d2i.update((0, x) for x in args.symbols) # solve the sum, with additional condition: (G > D) SubstitutedExpression( args.exprs + ["{G} > {D}"], distinct=args.symbols, d2i=args.d2i, answer="{ALE}", template=args.template + " ({G} > {D}) ({ALE})", solution=args.symbols, ).run()LikeLike
Jim Randell 2:55 pm on 22 October 2022 Permalink |
We can now call the [[
SubstitutedExpression.split_sum]] solver directly from a run file. Giving us a solution that is both short and fast.The following run file executes in 68ms, and the internal runtime of the generated program is just 139µs.
Run: [ @replit ]
#! python3 -m enigma -rr SubstitutedExpression.split_sum --invalid="0,ADEGKLNRS" # none of the digits are 0 --answer="ALE" "{DRANK} + {GLASS} = {LAGER}" --extra="{G} > {D}"LikeLike
Frits 11:28 am on 14 August 2020 Permalink |
from enigma import join print("ALE DRANK GLASS LAGER") print("---------------------") for G in range(1,10): for D in range(1,10): if D in {G}: continue if G <= D: continue for L in range(1,10): if L in {G,D}: continue if D + G != L and D + G + 1 != L: continue for A in range(1,10): if A in {G,D,L}: continue if A + A != 10 + G and A + A != G and A + A != 9 + G and A + A + 1 != G: continue for S in range(1,10): if S in {G,D,L,A}: continue GLASS = G*10000+L*1000+A*100+S*10+S for K in range(1,10): if K in {G,D,L,A,S}: continue for R in range(1,10): if R in {G,D,L,A,S,K}: continue if K + S != 10 + R and K + S != R: continue for N in range(1,10): if N in {G,D,L,A,S,K,R}: continue DRANK = D*10000+R*1000+A*100+N*10+K for E in range(1,10): if E in {G,D,L,A,S,K,R,N}: continue LAGER = L*10000+A*1000+G*100+E*10+R if DRANK + GLASS != LAGER: continue print(join([A,L,E]),join([D,R,A,N,K]),join([G,L,A,S,S]),join([L,A,G,E,R]))LikeLike
Frits 12:52 pm on 14 August 2020 Permalink |
Fastest solution so far and more concise:
# range 1,2,..,9 without elements in set w notIn = lambda w: [x for x in range(1,10) if x not in w] print("ALE DRANK GLASS LAGER") print("---------------------") for D in range(1,10): for G in notIn({D}): if G < D: continue for L in notIn({D,G}): if D + G != L and D + G + 1 != L: continue for A in notIn({D,G,L}): if A + A != 10 + G and A + A != G and \ A + A != 9 + G and A + A + 1 != G: continue for S in notIn({D,G,L,A}): GLASS = G*10000+L*1000+A*100+S*10+S for K in notIn({D,G,L,A,S}): for R in notIn({D,G,L,A,S,K}): if K + S != 10 + R and K + S != R: continue for N in notIn({D,G,L,A,S,K,R}): DRANK = D*10000+R*1000+A*100+N*10+K for E in notIn({D,G,L,A,S,K,R,N}): LAGER = L*10000+A*1000+G*100+E*10+R if DRANK + GLASS != LAGER: continue print(A*100+L*10+E, DRANK, GLASS, LAGER) # ALE DRANK GLASS LAGER # --------------------- # 392 14358 79366 93724LikeLike
Jim Randell 1:12 pm on 14 August 2020 Permalink |
@Frits: You should be able to do without the loop for E.
Once you have determined the other letters there is only one possible value for E determined by the fact: DRANK + GLASS = LAGER.
This is one of the things the [[
SubstitutedExpression()]] solver does to improve its performance. (See: Solving Alphametics with Python, Part 2.Not a huge win in this case (as there is only a single value left to be E), but generally quite useful technique.
LikeLike
Jim Randell 3:31 pm on 14 August 2020 Permalink |
… and if we use this technique on the equivalent expression:
We only need to consider the 6 symbols on the left, which gives a much more respectable execution time of 164ms for the following short run file:
LikeLike
GeoffR 3:56 pm on 14 August 2020 Permalink |
The following link is an alphametic solver :
http://www.tkcs-collins.com/truman/alphamet/alpha_solve.shtml
(Enter DRANK and GLASS in the left hand box and LAGER in the right hand box)
It outputs eight solutions, five of whch contain zeroes, which are invalid for this teaser.
It also outputs three non-zero solutions, only one of which has GLASS > DRANK, which is the answer:
i.e. 14358 + 79366 = 93724, from which ALE = 392
LikeLike
GeoffR 4:42 pm on 14 August 2020 Permalink |
import time start = time.time() from itertools import permutations for Q in permutations('123456789'): d,r,a,n,k,l,s,g,e = Q drank = int(d+r+a+n+k) glass = int(g+l+a+s+s) if glass > drank: lager = int(l+a+g+e+r) if drank + glass == lager: ale = int(a+l+e) print(f"ALE = {ale}") t1 = time.time() - start print(t1, "sec") print(f"Sum is {drank} + {glass} = {lager}") # ALE = 392 # 0.0311 sec # Sum is 14358 + 79366 = 93724LikeLike
GeoffR 10:06 pm on 18 August 2020 Permalink |
LikeLike
John Crabtree 7:32 pm on 20 August 2020 Permalink |
I solved this by hand. Looking at the first three columns, if NK + SS < 100, by digital roots, D + R + A = 0 mod 9. If NK + SS > 100, D + R + A = 8 mod 9.
For each condition and each A, G is fixed. Then for each possible D (<G and G + D < 10), R is fixed, and then so is L. I only found four sets of (A, G, D, R and L), ie (3, 6, 1, 5 8), (3, 6, 2, 4, 9), (1, 3, 2, 5, 6) and (3, 7, 1, 4, 9) for which it was necessary to evaluate the other letters.
Could this be the basis for a programmed solution?
LikeLike