Teaser 3164: Touching base
From The Sunday Times, 14th May 2023 [link] [link]
Liam has a pack of twenty cards; each card has a number printed on it as a word rather than figures.
There are two cards with ONE, two cards with TWO etc., up to two cards with TEN. He has taken four of the cards to construct an addition sum. The largest value card he has used is the sum of the values of the other cards, e.g.:
ONE + ONE + TWO = FOUR.
If I now work in the base equal to that sum (i.e., base 4 in the example), and consistently replace letters with single digits, this gives a correct sum. All of the possible digits in that base are used.
Leaving the answer in the working base, what is the total of my addition sum?
[teaser3164]
Frits and 
S2T2 
Jim Randell 4:50 pm on 12 May 2023 Permalink |
This Python program constructs the viable alphametic sums and then uses the [[
SubstitutedExpression.split_sum()]] solver from the enigma.py library to evaluate them (assuming “standard” alphametic rules, i.e. leading zeros are not allowed, and each letter stands for a different digit).It runs in 73ms. (Internal runtime is 16.8ms).
Run: [ @replit ]
from enigma import ( SubstitutedExpression, irange, multiset, subsets, int2words, union, join, substitute, sprintf as f, printf ) # the cards cards = multiset.from_seq(irange(1, 10), count=2) # choose 3 of the cards for cs in subsets(cards, size=3, select="mC", fn=list): # add in the the sum of the 3 cards t = sum(cs) cs.append(t) # check they make a valid set of 4 cards if not cards.issuperset(cs): continue # construct the corresponding words ws = list(int2words(x).upper() for x in cs) # check there are t different letters if len(union(ws)) != t: continue # construct the alphametic sum expr = f("{terms} = {result}", terms=join(ws[:-1], sep=" + "), result=ws[-1]) p = SubstitutedExpression.split_sum(expr, base=t, verbose=0) # and solve it for s in p.solve(): # output solution ss = substitute(s, expr) printf("{expr} / {ss} [base {t}]")Or a faster (but longer) version [ @replit ]. (Internal runtime is 6.1ms).
Solution: The result of the sum is: 61503 (in base 8).
There are 2 candidate alphametic sums (under “standard” alphametic rules):
Only the one with 8 letters yields solutions in the appropriate base.
So the sum is:
In Python:
LikeLike
Frits 9:21 pm on 12 May 2023 Permalink |
The commented code seems to work but somehow it runs slower than threee separate checks.
from itertools import permutations from math import ceil # convert a string in the specified base to an integer d2n = lambda s, b: int(''.join(str(x) for x in s), b) # the numbers numbers = ('ONE', 'TWO', 'THREE', 'FOUR', 'FIVE', 'SIX', 'SEVEN', 'EIGHT', 'NINE', 'TEN') # choose 3 of the cards (below ten) for a in range(1, 4): # a + 2b <= 10 for b in range(a, ceil((10 - a) / 2) + 1): for c in range(b, 11 - a - b): if a == b == c: continue t = sum([a, b, c]) # get all the letters ltrs = [x for n in (a, b, c, t) for x in numbers[n - 1]] if len(set(ltrs)) != t: continue # get words ws = [numbers[n - 1] for n in (a, b, c, t)] # skip if RHS word is too short if any(len(ws[i]) > len(ws[-1]) for i in range(3)): continue ltrs = list(set(ltrs)) # determine non-zero positions nz_ltrs = set(x[0] for x in ws) nz_pos = [i for i, x in enumerate(ltrs) if x in nz_ltrs] (u_pos, t_pos, h_pos) = ([ltrs.index(x) for x in [x[-i] for x in ws]] for i in range(1, 4)) # check all possible letter values for p in permutations(range(t)): # skip for leading zeroes if any(not p[x] for x in nz_pos): continue ''' sm = 0 # already check unit/ten/hundred sums if any((sm := (sm // t + sum(p[x] for x in chk[:-1]))) % t != p[chk[-1]] for chk in (u_pos, t_pos, h_pos) ): continue ''' # check unit sum if (usum := sum(p[x] for x in u_pos[:-1])) % t != p[u_pos[-1]]: continue # check ten sum if (tsum := (usum // t + sum(p[x] for x in t_pos[:-1]))) % t != \ p[t_pos[-1]]: continue # check hundred sum if (hsum := (tsum // t + sum(p[x] for x in h_pos[:-1]))) % t != \ p[h_pos[-1]]: continue # perform the complete check via dictionary lookup d = {ltr: v for ltr, v in zip(ltrs, p)} # get the terms in base t ns = [[d[x] for x in ws[i]] for i in range(4)] # check the sum in base t if sum(d2n(n, t) for n in ns[:-1]) != d2n(ns[-1], t): continue print(ws) print("answer:", ''.join(str(x) for x in ns[-1]))LikeLike
Frits 11:04 am on 13 May 2023 Permalink |
from enigma import SubstitutedExpression from math import ceil # the numbers numbers = ('ONE', 'TWO', 'THREE', 'FOUR', 'FIVE', 'SIX', 'SEVEN', 'EIGHT', 'NINE', 'TEN') carry_ltrs = "ABCD" # maximum word length is 5 so 4 free letters needed # choose 3 of the cards (below ten) for a in range(1, 4): # a + 2b <= 10 for b in range(a, ceil((10 - a) / 2) + 1): for c in range(b, 11 - a - b): if a == b == c: continue t = sum([a, b, c]) # get string of used letters ltrs = ''.join(set(x for n in (a, b, c, t) for x in numbers[n - 1])) if len(set(ltrs)) != t: continue # get words ws = [numbers[n - 1] for n in (a, b, c, t)] lenRHS = len(ws[-1]) # skip if RHS word is too short if any(len(ws[i]) > lenRHS for i in range(3)): continue # letters per column c_ltrs = [[ws[j][-i] if i <= len(ws[j]) else '0' for j in range(4)] for i in range(1, lenRHS + 1)] carries = ['0'] + list(carry_ltrs[:lenRHS - 1]) + ['0'] # build expressions per column exprs = [] for i, s in enumerate(c_ltrs): exprs.append("(" + '+'.join(s[:-1]) + "+" + carries[i] + ") % " + str(t) + " = " + s[-1]) exprs.append("(" + '+'.join(s[:-1]) + "+" + carries[i] + ") // " + str(t) + " = " + carries[i + 1]) # the alphametic puzzle p = SubstitutedExpression( exprs, base=t, answer='(' + '), ('.join(list(','.join(w) for w in ws)) + ')', d2i=dict([(0, set(w[0] for w in ws))] + [(k, carries[1:-1]) for k in range(3, t)]), distinct=ltrs, verbose=0, ) # print answer for (_, ans) in p.solve(): print(f"{' + '.join(ws[:-1])} = {ws[-1]}") print("answer:", ''.join(str(x) for x in ans[-1]))LikeLike
Frits 1:19 pm on 13 May 2023 Permalink |
Another variation. This program sometimes runs under 10ms.
from itertools import permutations from math import ceil # the numbers numbers = ('ONE', 'TWO', 'THREE', 'FOUR', 'FIVE', 'SIX', 'SEVEN', 'EIGHT', 'NINE', 'TEN') # process sum per column for each column in <cols> def solve_column(base, rng, cols, carry, d=dict()): if not cols: yield d else: col = cols[0] novalue = set(x for x in col if x not in d and x != '0') for p in permutations(rng, len(novalue)): d_ = d.copy() d_['0'] = 0 # for dummy letter i = 0 # assign letters without value for c1 in set(col): if c1 not in d_: d_[c1] = p[i] i += 1 # substitute letters by value lst = [d_[c2] for c2 in col] # check column sum if (csum := (carry + sum(lst[:-1]))) % base == lst[-1]: yield from solve_column(base, set(rng).difference(p), cols[1:], csum // base, d_) # choose 3 of the cards (below ten) for a in range(1, 4): # a + 2b <= 10 for b in range(a, ceil((10 - a) / 2) + 1): for c in range(b, 11 - a - b): if a == b == c: continue t = sum([a, b, c]) # get all the letters ltrs = [x for n in (a, b, c, t) for x in numbers[n - 1]] if len(set(ltrs)) != t: continue # get words ws = [numbers[n - 1] for n in (a, b, c, t)] lenRHS = len(ws[-1]) # skip if RHS word is too short if any(len(ws[i]) > lenRHS for i in range(3)): continue # determine non-zero letters nz_ltrs = set(x[0] for x in ws if len(x) > 1) # letters per column c_ltrs = [[ws[j][-i] if i <= len(ws[j]) else '0' for j in range(4)] for i in range(1, lenRHS + 1)] # solve sums for all columns for d1 in solve_column(t, range(t), c_ltrs, 0): # check for leading zeroes if any(d1[x] == 0 for x in nz_ltrs): continue print("answer:", ''.join(str(d1[x]) for x in ws[-1]))LikeLike
Frits 3:23 pm on 17 May 2023 Permalink |
With range based logic (maybe domain is a better word).
from itertools import permutations from math import ceil # the numbers numbers = ('ONE', 'TWO', 'THREE', 'FOUR', 'FIVE', 'SIX', 'SEVEN', 'EIGHT', 'NINE', 'TEN') # pick one value from each entry of a <ns> # so that all <k> values are different def pickOneFromEach(k, ns, s=[]): if k == 0: yield s else: for n in ns[k - 1]: if n not in s: yield from pickOneFromEach(k - 1, ns, [n] + s) # try to reduce ranges with analysis def reduce_ranges(base, words, cols, rngs): # check first column chars = [x for x in cols[-1][:-1] if x != '0'] # no letters to add? if not chars: # total digit in first column must be 1 rngs = {k: [1] if k == cols[-1][-1] else set(v).difference([1]) for k, v in rngs.items()} # only one letter has to be added more than once elif len(set(chars)) == 1 and len(chars) > 1: mx = (base - 1) // len(chars) rngs[chars[0]] = [x for x in rngs[chars[0]] if x <= mx] mn = rngs[chars[0]][0] # total digit may have a new minimum rngs[cols[-1][-1]] = [x for x in rngs[cols[-1][-1]] if x >= mn * len(chars)] # check last column chars = [x for x in cols[0][:-1] if x != '0'] # only one letter has to be added if len(set(chars)) == 1 and chars[0] != cols[0][-1]: # a multiple of zero is zero rngs[chars[0]] = [x for x in rngs[chars[0]] if x != 0] # stop with the analysis return rngs # process sum per column for each column in <cols> def solve_column(base, used, cols, carry, d={'0': 0}): if not cols: yield d else: col = cols[0] unused_ltrs = sorted(set(x for x in col if x not in d and x != '0')) # get ranges for unused letters (without used values) rs = [[y for y in ranges[x] if y not in used] for x in unused_ltrs] for p in pickOneFromEach(len(unused_ltrs), rs): d_ = d.copy() d_.update(zip(unused_ltrs, p)) # substitute letters by value vs = [d_[c2] for c2 in col] # check column sum if (csum := (carry + sum(vs[:-1]))) % base == vs[-1]: yield from solve_column(base, used | set(p), cols[1:], csum // base, d_) # choose 3 of the cards (below ten) for a in range(1, 4): # a + 2b <= 10 for b in range(a, ceil((10 - a) / 2) + 1): for c in range(b if b > a else b + 1, 11 - a - b): t = sum([a, b, c]) # get all the letters ltrs = [x for n in (a, b, c, t) for x in numbers[n - 1]] if len(set(ltrs)) != t: continue # get words ws = [numbers[n - 1] for n in (a, b, c, t)] lenRHS = len(ws[-1]) # skip if RHS word is too short if any(len(ws[i]) > lenRHS for i in range(3)): continue # determine non-zero letters nz_ltrs = set(x[0] for x in ws if len(x) > 1) # letters per column c_ltrs = [[ws[j][-i] if i <= len(ws[j]) else '0' for j in range(4)] for i in range(1, lenRHS + 1)] # determine initial range per letter ranges = {ltr: range(0 if ltr not in nz_ltrs else 1, t) for ltr in ltrs} ranges = reduce_ranges(t, ws, c_ltrs, ranges) # solve sums for all columns for d1 in solve_column(t, set(), c_ltrs, 0): print("answer:", ''.join(str(d1[x]) for x in ws[-1]))LikeLike