1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
from collections import defaultdict # generate sequences of nine holes from Ian's perspective # summing his losses and his costs from sequential losses # (since sequences are reversible, we always start with a # a win for John and then reverse the sequence for Ken) # # number of holes: nh # hole value: v (0 = loss, 1 = win) # hole cost: cs # sequence of results: seq def round(nh=9, v=1, ls=0, cs=0, seq=()): # have we finished? if not nh: yield ls, cs else: # the length of the next sequence of wins or losses for ln in range(1, nh + 1): yield from round(nh - ln, 1 - v, # count the losses and their cost ls + (0 if v else ln), cs + (0 if v else ln * (ln + 1) // 2), seq + (v,) * ln) # map costs to losses c2l = defaultdict(set) for ls, cs in round(): c2l[cs].add(ls) # consider possible costs for cost in c2l.keys(): # look for 13 losses in total (5 wins) for loss in c2l[cost]: if 13 - loss in c2l[cost] and 2 * loss < 13: print(f"It cost Uncle Ian £{2 * cost} in total.") |

This version is slower but outputs the results of the rounds of crazy golf involved.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
def round(nh=9, v=1, ls=0, cs=0, seq=()): # have we finished? if not nh: yield ls, cs, seq else: # the length of the next sequence of wins or losses for ln in range(1, nh + 1): yield from round(nh - ln, 1 - v, # count the losses and their cost ls + (0 if v else ln), cs + (0 if v else ln * (ln + 1) // 2), seq + (v,) * ln) rounds = list(round()) pseq = lambda s: ''.join('wl'[i] for i in s) ct = 0 # John's possible sequence of holes starting with a win for l2j, p2j, s2j in rounds: # Ian's possible sequence of holes ending with a # win (the sequences are reversible) for l2k, p2k, s2k in rounds: # look for 13 total losses and equal boys income if l2j + l2k == 13 and p2j == p2k: ct += 1 print(f"{ct:2} John {pseq(s2j)} -> £{p2j} Ken {pseq(s2k[::-1])} -> £{p2k}") |

Here is my first attempt which runs in 25 milliseconds.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
from itertools import combinations # the possible ages (digits 1 and 9 lead to out of range ages) nbrs = [10 * x + y for x in range(2, 9) for y in range(2, 9)] # consider the ages for the first of the two groups of three for f3 in combinations(nbrs, 3): # put the youngest in this group and make the sums of the ages in the # groups equal by equating the sums of the units and the tens digits if sum(x // 10 - x % 10 for x in f3): continue # form the second group with reversed ages s3 = tuple(sorted(10 * (x % 10) + x // 10 for x in f3)) # ensure that the group sums of ages squared are equal if min(f3) >= min(s3) or sum(x * x for x in f3) != sum(x * x for x in s3): continue # form the whole group in age order a6 = tuple(sorted(f3 + s3)) # check that ages differ by at least 9 years if any(x - a6[i] < 9 for i, x in enumerate(a6[1:])): continue # there is an age in both groups that is twice an age # in the other group if len(set(f3).intersection(2 * x for x in s3)) != 1: continue if len(set(s3).intersection(2 * x for x in f3)) != 1: continue print(f"{a6} [{f3}, {s3}]") |

It soon occurred to me that there can be only one age in each decade and this led to this solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
from itertools import combinations, permutations # digits 0, 1 and 9 give invalid ages and this, with age # differences of at least 9, means that no two ages are # in the same decade; hence we have seven decades (2..8) # and six ages so one decade is missing digits = set(range(2, 9)) # the missing decade for md in digits: # the tens digits of the six ages ... t6 = sorted(digits - {md}) # ... and the units digits ... for u6 in permutations(t6): # form the six ages a6 = tuple(10 * t + u for t, u in zip(t6, u6) if u != t) gsum, r = divmod(sum(a6), 2) # there must be six ages with an even sum if len(a6) != 6 or r: continue # consider the possible subgroups of three ages by # picking two ages and checking for a third that # gives the correct group sum for f2 in combinations(a6, 2): t = gsum - sum(f2) if t < f2[1] or t not in a6: continue f3 = tuple(sorted(f2 + (t,))) s3 = tuple(a for a in a6 if a not in f3) # ensure that the sums of ages squared are equal if (f3[0] > s3[0] or sum(x * x for x in f3) != sum(x * x for x in s3)): continue # there is an age in both groups that is twice an age # in the other group if len(set(f3).intersection(2 * x for x in s3)) != 1: continue if len(set(s3).intersection(2 * x for x in f3)) != 1: continue print(f"{a6} [{f3}, {s3}]") |

I though that this would be quite a bit faster but it only beat my first attempt by 20%, running in 20 milliseconds.

A third option is to use a constraint programming approach using MiniZinc accessed using Jim Randell’s >minizinc wrapper:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
from minizinc import MiniZinc mz = MiniZinc(""" include "globals.mzn"; % digits 0, 1 and 9 produce invalid ages var 2..8:A; var 2..8:B; var 2..8:C; var 2..8:D; var 2..8:E; var 2..8:F; % variables for the first group ... var 21..89: AB = 10 * A + B; var 21..89: CD = 10 * C + D; var 21..89: EF = 10 * E + F; array[1..3] of var 21..89: FG = [AB, CD, EF]; array[1..3] of var 42..178: FGD = [2 * AB, 2 * CD, 2 * EF]; % ... and for the second group (first group ages reversed) var 21..89: BA = 10 * B + A; var 21..89: DC = 10 * D + C; var 21..89: FE = 10 * F + E; array[1..3] of var 21..89: SG = [BA, DC, FE]; array[1..3] of var 42..178: SGD = [2 * BA, 2 * DC, 2 * FE]; % order the first group ages and order the two groups constraint AB < CD /\ CD < EF /\ AB < BA; % the sums of the ages in the two groups of three are equal constraint AB + CD + EF == BA + DC + FE; % the sums of the squares of the ages in the two groups of three are equal constraint AB * AB + CD * CD + EF * EF == BA * BA + DC * DC + FE * FE; % the group of all six ages (unordered) array[1..6] of var 21..89: AG = [AB, CD, EF, BA, DC, FE]; array[1..6] of var 1..6: SI; % the group of all six ages (ordered) array[1..6] of var 21..89: AGS; % any two of the ages differ by at least 9 constraint arg_sort(AG, SI); constraint forall (i in 1..5) (AG[SI[i + 1]] - AG[SI[i]] >= 9); constraint forall (i in 1..6) (AGS[i] = AG[SI[i]]); % for each group of three there is one age that is twice % that of an age in the other group constraint sum(i, j in 1..3) (bool2int(FG[i] == SGD[j])) == 1; constraint sum(i, j in 1..3) (bool2int(SG[i] == FGD[j])) == 1; solve satisfy; """) fs = ('AB', 'CD', 'EF') for s in mz.solve(): f3 = tuple(10 * s[ab[0]] + s[ab[1]] for ab in fs) s3 = tuple(10 * s[ab[1]] + s[ab[0]] for ab in fs) a6 = tuple(sorted(f3 + s3)) print(f"{a6} [{f3}, {s3}]") |

However, this does not compete on speed, running in 250 milliseconds.

]]>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
from itertools import combinations from collections import defaultdict # the notes J..P will be represented by the integers 0..6 # the starting/ending chord jnp = (0, 4, 6) # map chords to the chords that can follow them ch2chs = defaultdict(set) for ch in combinations(range(7), 3): # consider the three possible next chords for p in range(3): # create the next chord nch = set(((x - 2) if i == p else (x + 1)) % 7 for i, x in enumerate(ch)) # check that it has three different notes if len(nch) == 3: nch = tuple(sorted(nch)) if nch != ch: ch2chs[ch].add(nch) # generate chord sequences starting and ending with chord <sc> def chord_seq1(sc, ch_seq=()): if ch_seq and ch_seq[-1] == ch_seq[0]: yield ch_seq else: if not ch_seq: ch_seq = (sc,) for ch in ch2chs[ch_seq[-1]]: if ch_seq.count(ch) < 2: yield from chord_seq1(ch, ch_seq + (ch,)) # collect all chord changes in sequences starting with jnp cc = set() for s in chord_seq1(jnp): for i, c in enumerate(s[1:]): cc.add((s[i], c)) # generate chord sequences starting with chord <sc> # that use all chord changes in <cc> def chord_seq2(sc, cc, ch_seq=()): if not cc: yield ch_seq else: for nc in ch2chs[sc]: t = (sc, nc) if t in cc: yield from chord_seq2(nc, cc.difference([t]), ch_seq + (nc,)) min_diff, min_seq = None, None # consider all chord sequences that use all chord changes for s in chord_seq2(jnp, cc): # find the positions of jnp chords ps = tuple(i for i, c in enumerate(s) if c == jnp) # the first gap between jnp chords is smaller than the last if len(ps) > 1 and ps[0] > ps[-1] - ps[-2]: if min_diff is None or ps[0] < min_diff: min_diff, min_seq = ps[0], s s = [''.join('JKLMNOP'[n] for n in x) for x in min_seq] print(f"{s[6]} ({' '.join(s)})") |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
from number_theory import tau # generate <nd>-digit integers with digit sums of <nd> def gen(nd, dsum, nbr=0): if not nd: if not dsum: yield nbr else: for d in range(0 if nbr else 1, min(10, dsum + 1)): yield from gen(nd - 1, dsum - d, 10 * nbr + d) nd, cnt = 0, 0 while True: nd += 1 # consider integers with both digit sums and ... for nbr in gen(nd, nd): # ... numbers of divisors equal to their length if tau(nbr) == nd: cnt += 1 sfx = f"(Answer = {nd})" if cnt == 6 else "" print(f"D[{cnt}] = {nbr} {sfx}") if cnt == 6: exit() |

Here is a variation that allows “diddums” with a range of lengths to be output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
from sys import argv from number_theory import factor, tau # generate <nd>-digit integers with digit sums of <nd> def gen1(nd, dsum, nbr=0): if not nd: if not dsum: yield nbr else: for d in range(0 if nbr else 1, min(10, dsum + 1)): yield from gen1(nd - 1, dsum - d, 10 * nbr + d) # generate integers of length <nd> with both digit sums # and numbers of divisors equal to their length gen2 = lambda nd: (nbr for nbr in gen1(nd, nd) if tau(nbr) == nd) # allow 'diddums' to be output if there are input parameters # giving the minimum and maximum number of digits to output min_nd, max_nd, cnt_max = 1, 8, 6 if (ln:= len(argv)) >= 2: cnt_max = 0 min_nd, *r = (int(x) for x in argv[1:]) max_nd = min_nd if not r else r[0] cnt = 0 for nd in range(min_nd, max_nd + 1): for nbr in gen2(nd): cnt += 1 sfx = f" -> Answer = {nd}" if cnt == cnt_max else "" fct = '.'.join(f"{p}" if e == 1 else f"{p}^{e}" for p, e in factor(nbr)) print(f"D[{cnt:3}] = {nbr} = {fct} {sfx}") if cnt_max and cnt == cnt_max: break else: continue break |

]]>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
from itertools import permutations #pass rate for first four years pr = (30, 32, 35, 36) #list of numbers successful candidates sc = [0, 0, 0, 0, 0] #consider different permutations of number of candidates first 4 years for c in permutations(range(475, 526), 4): # do pass rates result in integer number of successful candidates for i in range(4): sc[i], r = divmod(c[i] * pr[i], 100) if r != 0: break # skip to next permutation else: # if pass rates give integer number of candidates that pass for 4 years # consider number of cadidates for last year for c4 in set(tuple(range(475, 526))) - set(c): for j in (31, 33, 34): # possible pass rates for year 2022 sc[4], r = divmod(c4 * j, 100) # successful candidates for 2022: integer and different over 5 years if r == 0 and len(set(sc)) == 5: #possible perfect square pps = sum(sc) if int(pps ** 0.5) ** 2 == pps: print(c + (c4,), "X =", j, pps, pps ** 0.5) print(sc) |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
from itertools import permutations #pass rate for first four years pr = (30, 32, 35, 36) #list of successful candidates sc = [0, 0, 0, 0, 0] #consider different permutations of number of candidates for c in permutations(range(475, 526), 5): # do pass rates result in integer number of successful candidates for i in range(4): sc[i], r = divmod(c[i] * pr[i], 100) if r != 0: break # skip to next permutation else: # if pass rates give integer number of candidates that pass for 4 years for j in (31, 33, 34): # possible pass rates for year 2022 sc[4], r = divmod(c[4] * j, 100) # succesful candidates for 2022 are integer and different over five years if r == 0 and len(set(sc)) == 5: #possible perfect square pps = sum(sc) if int(pps ** 0.5) ** 2 == pps: print(c, "X =", j, pps, pps ** 0.5) print(sc) |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
# sc18 = successful candidates for 2018 # Y18 = entrants for 2018 # Lower bound for passes = 0.3 * 475 = 142 # Upper bound for passes = 0.36 * 525 = 189 # Year 2018 for Y18 in range(475, 526): for sc18 in range(142, 190): if 100 * sc18 != 30 * Y18: continue # Year 2019 for Y19 in range(475, 526): if Y19 == Y18: continue for sc19 in range(142, 190): if 100 * sc19 != 32 * Y19: continue if sc19 == sc18: continue # Year 2020 for Y20 in range(475, 526): if Y20 in (Y18, Y19): continue for sc20 in range(142, 190): if sc20 in (sc18, sc19): continue if 100 * sc20 != 35 * Y20: continue # Year 2021 for Y21 in range(475, 526): if Y21 in (Y18, Y19, Y20): continue for sc21 in range(142, 190): if sc21 in (sc18, sc19, sc20): continue if 100 * sc21 != 36 * Y21: continue # Year 2022 for Y22 in range(475, 526): if Y22 in (Y18, Y19, Y20, Y21): continue for sc22 in range(142, 190): if sc22 in (sc18, sc19, sc20, sc21): continue for pr in range(30, 36): # check pass rate for 2022 is different # to years 2018, 2019, 2020 and 2021 if pr in (30, 32, 35, 36): continue if 100 * sc22 == pr * Y22: # find total of passes from 2018 to 2022 total = sc18 + sc19 + sc20 + sc21 + sc22 if round(total ** 0.5) ** 2 == total: print(f"Passes for 2022 = {sc22}") print(f"Entrants for 2022 = {Y22}") |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
# find the number of candidates and the number who pass # for a given sequence of annual percentage pass rates def solve(pc, ns=(), ss=()): if not pc: yield ns, ss else: # 500 +/- 5% for n in range(475, 526): s, r = divmod(pc[0] * n, 100) # all numbers of candidates and all numbers of # successes are different if not r and n not in ns and s not in ss: yield from solve(pc[1:], ns + (n,), ss + (s,)) # the given percentages pc = (30, 32, 35, 36) # X is within the above range but different for x in (31, 33, 34): for n, s in solve(pc + (x,)): # the sum of the successful candidates over # the five years is a perfect square sm = sum(s) sr = round(sm ** 0.5) if sr ** 2 == sm: print(f"N={n}, S={s}, X={x}, sum(S)={sr}^2") |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
from itertools import combinations # all fifteen cards (since there are eight cards with 'E's and seven # without, the 'E' cards must be in even positions to avoid snaps) wrds = ('ACE', 'TWO', 'THREE', 'FOUR', 'FIVE', 'SIX', 'SEVEN', 'EIGHT', 'NINE', 'TEN', 'JACK', 'QUEEN', 'KING', 'SHOUT', 'SNAP') # the four odd cards that occur in order odds = ('THREE', 'FIVE', 'SEVEN', 'NINE') # the three court cards ccrd = {'JACK', 'QUEEN', 'KING'} # record all card pairs that can be adjacent ok = set() for a, b in combinations(wrds, 2): if not set(a).intersection(b): ok.update([(a, b), (b, a)]) # generate card sequences without snaps, with # court cards equally spaced and the designated # odd cards apppearing in order def ns_seq(cards, ix_cc=(), nodd=0, seq=()): if not cards: yield seq else: pos_even = not (len(seq) & 1) # try to add another card to the sequence for i, c in enumerate(cards): if not seq or (c, seq[-1]) in ok: # ensure all 'E' cards are in even positions if pos_even and 'E' not in c: continue # ensure the equal spacing of the Jack, Queen and King nix_cc = ix_cc if c in ccrd: nix_cc += (len(seq),) # if we have seen all of them, check for equal spacing if len(nix_cc) == 3 and nix_cc[0] + nix_cc[2] != 2 * nix_cc[1]: continue # ensure that THREE, FIVE, SEVEN and NINE are seen in order if c in odds and odds.index(c) != nodd: continue # add further cards yield from ns_seq(cards[:i] + cards[i + 1:], nix_cc, nodd + (c in odds), seq + (c,)) sol = set() for s in ns_seq(wrds): print(f"{' '.join(s[:6])} [{' '.join(s[6:])}]") |

This program counts the number of work rosters for which the full levelling-up procedure is both necessary and possible:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
from itertools import combinations_with_replacement as cwr # set to False to output the intended # levelling-up result all = True # perform the six levelling-up steps def do_sixavs(*arg): d = list(arg) for i in range(6): av, r = divmod (sum(d), 3) if r: return None for i, x in enumerate(d): if x < av: d[i] = av return tuple(d) solns = set() # consider the possible days worked by Scrooge, # Marley and Cratchit for s, m, c in cwr(range(1, 367), 3): # check that levelling-up is necessary if not (s == m == c): av, r = divmod(s + m + c, 3) if not r: d = do_sixavs(s, m, c) if d: if all: solns.add((s, m, c)) elif len(set(d).intersection((s, m, c))) == 2: print(f"{(s, m, c)} -> {d}") exit() print(len(solns)) |

It finds 3429 such work rosters (if ‘all’ is set to false it gives the result for the intended solution).

Only one of the 3429 possible work rosters acts on only one of Scrooge, Marley and Cratchit:

1 2 3 4 5 6 7 8 9 |
[ 1, 365, 366] [244, 365, 366] [325, 365, 366] [352, 365, 366] [361, 365, 366] [364, 365, 366] [365, 365, 366] |

which is applied on 26th to 31st December in the year 1836.

Since they all work on the same dates in 1835 (365 days) and 1836 (366 days) except that Scrooge works on Cratchit’s birthday, this identifies the latter’s birthdate as 29th February. We are also told that Cratchit is in his forties and, unusually, the year 1796 is the only leap year between those in 1792 and 1804. We hence now know that Cratchit’s birthdate is 29th February 1796.

Despite the teaser’s flaw, in the process of working out the various dates involved it was easy to notice that the wording identifies the unusual eleven year period between the leap years in 1792 and 1804 in which only one leap year (1796) occurs since the normal ‘new century’ leap year is missing. This allowed many solvers, including myself, to guess that the intended solution was 29th February 1796 without even considering the levelling-up process.

Here is the levelling-up example that I posted here that alerted John Owen to the flawed teaser wording:

1 2 3 4 5 6 7 8 9 |
[138, 334, 347] [273, 334, 347] [318, 334, 347] [333, 334, 347] [338, 338, 347] [341, 341, 347] [343, 343, 347] |