Updates from April, 2025 Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 8:32 am on 11 April 2025 Permalink | Reply
    Tags:   

    Teaser 2557: The legacy 

    From The Sunday Times, 25th September 2011 [link] [link]

    In my will I have set aside a five-digit sum of pounds for charity — a group of four animal charities and a group of seven children’s charities. This five-digit sum consists of five consecutive non-zero digits, not in numerical order. On my death this legacy is to be divided equally between these charities. But I have left it to my executors’ discretion to choose to divide it instead equally among the charities in just one of the groups. Each donation will be a whole number of pounds, whichever course they take.

    What is the five-digit sum?

    [teaser2557]

     
    • Jim Randell's avatar

      Jim Randell 8:32 am on 11 April 2025 Permalink | Reply

      The amount must be divisibly by 4, 7, 11, and LCM(4, 7, 11) = 308.

      So we are looking for a 5-digit number that is a multiple of 308, and is composed from a set of 5 different non-zero consecutive digits, but not in numerical order.

      This Python program looks at 5-digit multiples of 308. It has a runtime of 63ms, and an internal runtime of 1.7ms.

      from enigma import (irange, mlcm, nsplit, is_consecutive, printf)

# look for 5-digit multiples of 4, 7, 11
k = mlcm(4, 7, 11)
for n in irange.round(10000, 99999, step=k, rnd='I'):
  # split into digits
  ds = nsplit(n)
  # look for consecutive non-zero digits
  if (0 in ds) or is_consecutive(ds) or not is_consecutive(sorted(ds)): continue
  # output solution
  printf("amount = {n}")

      But it is slightly faster (but also slightly longer) to start with the possible non-zero consecutive digits, and then consider rearrangements of those digits.

      This Python program also runs in 63ms, but has an internal runtime of 784µs.

      from enigma import (irange, mlcm, tuples, subsets, nconcat, is_consecutive, printf)

# amount must be divisible by 4, 7, 11
k = mlcm(4, 7, 11)

# choose 5 consecutive digits
for ds in tuples(irange(1, 9), 5):
  # consider possible numbers formed from these digits
  for ds in subsets(ds, size=len, select='P'):
    n = nconcat(ds)
    # check divisibility
    if not (n % k == 0): continue
    # check the digits are not consecutive
    if is_consecutive(ds): continue
    # output solution
    printf("amount = {n}")

      Solution: The amount is: £ 74536.

      £ 74536 = 4× £ 18634
      £ 74536 = 7× £ 10648
      £ 74536 = 11× £ 6776

      If a 0 digit is permitted there is a second solution of £ 43120.

      Like

    • Frits's avatar

      Frits 4:59 pm on 11 April 2025 Permalink | Reply

      Using divisibility rules.

      from itertools import permutations

# suppose d1 + d3 + d5 = d2 + d4 + k   
# then k % 11 = 0 as legacy is divisible by 11 (alternating sum)
# t = sum(d1...d5) = 2 * (d2 + d4) + k

for i, t in enumerate(range(15, 36, 5), 1):
  # it t odd then k = 11, it t even then k = 0
  k = 11 if t % 2 else 0
  d2d4 = (t - k) // 2
  if d2d4 < 2 * i + 1 or d2d4 > 2 * i + 7: continue
  for d2 in range(i, i + 5):
    d4 = d2d4 - d2
    if d4 == d2 or d4 not in range(i, i + 5): continue
    for d1, d3, d5 in permutations(set(range(i, i + 5)) - {d2, d4}):
      if d5 % 2: continue
      n45 = 10 * d4 + d5
      # divisibility by 4
      if n45 % 4: continue
      # divisibility by 7 rule (alternating sum of blocks of three)
      if (100 * d3 + n45 - 10 * d1 - d2) % 7: continue 

      print("answer:", ''.join(str(x) for x in (d1, d2, d3, d4, d5)))

      Like

  • Unknown's avatar

    Jim Randell 8:27 am on 8 April 2025 Permalink | Reply
    Tags:   

    Teaser 2547: Multiple celebration 

    From The Sunday Times, 17th July 2011 [link] [link]

    Today is my birthday and the birthday of my granddaughter Imogen. My age today is a whole-number multiple of hers, and this has been true on one third of our joint anniversaries.

    If we both live until I am six times her current age, then my age will be a multiple of hers on two more birthdays.

    How old are we today?

    [teaser2547]

     
    • Jim Randell's avatar

      Jim Randell 8:27 am on 8 April 2025 Permalink | Reply

      This Python program runs in 63ms. (Internal runtime is 139µs).

      from enigma import (irange, is_divisor, printf)

# find multiple anniversaries for [a, b] and [a+d, b+d]
def multiples(d, a, b):
  for x in irange(a, b):
    y = x + d
    if is_divisor(y, x):
      yield (x, y)

# consider possible ages for the granddaughter (must be a multiple of 3)
for g in irange(3, 20, step=3):
  # consider the setters age (a multiple of g, less than 6g)
  for k in [2, 3, 4, 5]:
    s = k * g

    # calculate earlier multiples
    d = s - g
    ms = list(multiples(d, 1, g))
    # exactly 1/3 of the joint anniversaries so far are multiples
    if not (len(ms) * 3 == g): continue

    # and in there future there will be 2 more multiple anniversaries
    ms_ = list(multiples(d, g + 1, 6 * g - d))
    if not (len(ms_) == 2): continue

    # output solution
    printf("g={g} s={s} [k={k} d={d}] -> {ms} {ms_}")

      Solution: The setter is 72. The granddaughter is 18.

      So the age difference is 54 years.

      The multiples in the past are:

      1 year old & 55 years old (multiple = 55)
      2 years old & 56 years old (multiple = 28)
      3 years old & 57 years old (multiple = 19)
      6 years old & 60 years old (multiple = 10)
      9 years old & 63 years old (multiple = 7)
      18 years old & 72 years old (multiple = 4)

      Which is 6 anniversaries out of 18, so one third of them are multiples.

      In the future (with the setters age up to 6 × 18 = 108) we can have the following multiples:

      27 years old & 81 years old (multiple = 3)
      54 years old & 108 years old (multiple = 2)

      Like

  • Unknown's avatar

    Jim Randell 7:13 am on 6 April 2025 Permalink | Reply
    Tags:   

    Teaser 3263: Snakes and ladders 

    From The Sunday Times, 6th April 2025 [link] [link]

    My “Snakes and Ladders” board has numbers from 1 to 100 — you throw a die repeatedly and work your way up. There are three “snakes”, each taking you down from one perfect square to another, and three “ladders”, each taking you up from one prime to another. The twelve ends of the snakes and ladders are different two-digit numbers. You must go down a snake if you land on its top-end, and up a ladder if you land on its bottom-end.

    For any number from 1 to 6, if I throw that same number repeatedly then I eventually land on 100. The number of throws of 4 needed (with first stops 4, 8, …) is one more than when throwing 5s, which is more than when throwing 3s.

    What are the three ladders (in the form “p to q“)?

    [teaser3263]

     
    • Jim Randell's avatar

      Jim Randell 7:47 am on 6 April 2025 Permalink | Reply

      Here is my first go at a solution.

      It constructs all possible arrangements of snakes and ladders, and then checks to see if valid sequences of moves can be made. This is quite slow, as although there are only a few possible arrangements for the snakes, there are a lots of possible ladder arrangements to consider.

      It runs in 22.8s (using PyPy).

      from enigma import (irange, primes, subsets, partitions, update, printf)

# play the game, constantly throwing <d>
# return: <sequence-of-positions> or None
def play(d, m, p=0):
  ps = list()
  while True:
    # move d spaces
    p += d
    # have we hit a special position?
    p = m.get(p, p)
    # have we hit a loop?
    if p in ps: return
    ps.append(p)
    # are we done?
    if p >= 100: return ps

# check map <m> of special positions for a solution
def check(m):
  n = dict()
  for d in [4, 5, 3, 6, 2, 1]:
    # each play eventually gets to 100
    ps = play(d, m)
    if ps is None or ps[-1] != 100: return
    n[d] = ps
    # check n4 = n5 + 1
    if d == 5 and not (len(n[4]) == len(n[5]) + 1): return
    # check n3 < n5
    if d == 3 and not (len(n[3]) < len(n[5])): return
  # return the moves for each die value
  return n

# collect 2-digit squares and primes
sqs = list(i * i for i in irange(4, 9))
prs = list(primes.between(10, 99))

# choose k special positions
def special(ss, k, r, m):
  # choose k positions
  for xs in subsets(ss, size=k):
    # pair them up
    for ps in partitions(xs, 2, distinct=1):
      # add them to the map
      yield update(m, (sorted(pair, reverse=r) for pair in ps))

# choose 6 ends for the snakes (squares) and ladders (primes)
for m0 in special(sqs, 6, 1, dict()):
  for m in special(prs, 6, 0, m0):
    # check for solution
    n = check(m)
    if n:
      # output solution
      for (x, y) in m.items():
        printf("{x} -> {y} {z}", z=("ladder" if x < y else "snake"))
      printf()
      for d in sorted(n.keys()):
        printf("{d} -> {k} throws {v}", k=len(n[d]), v=n[d])
      printf()

      Solution: The ladders are: 19 → 97, 29 → 73, 31 → 43.

      And the snakes are: 36 → 25, 49 → 16, 81 → 64.

      The number of throws for each die value are as follows:

      1 = 22 throws
      2 = 42 throws
      3 = 18 throws
      4 = 21 throws
      5 = 20 throws
      6 = 22 throws

      With a standard board layout it looks like this:

      (Snakes in red; Ladders in green).

      Like

      • Jim Randell's avatar

        Jim Randell 2:41 pm on 8 April 2025 Permalink | Reply

        Here is a faster approach:

        This Python 3 program starts by repeatedly throwing a die value and travelling along the board. When it hits a potential “special” square it either allocates a snake/ladder or does nothing, until it completes a sequence that ends on 100. Once this is achieved it takes the partially completed board and then tries another die value, until all values have achieved valid sequences. The completed board (and sequences) are then returned.

        It runs in 115ms. (Internal runtime is 40ms).

        from enigma import (irange, primes, update, remove, printf)

# collect 2-digit squares and primes
sqs = list(i * i for i in irange(4, 9))
prs = list(primes.between(10, 99))

# play the game, repeatedly throwing <d>
# m = behaviour of positions (src -> tgt)
# p = current position
# ps = previous positions
# sps = positions for snakes
# lps = positions for ladders
# ns = remaining snakes
# nl = remaining ladders
# return updated (m, ps, sps, lps, ns, nl) values
def play(d, m, p, ps, sps, lps, ns, nl):
  # are we done?
  if p >= 100:
    yield (m, ps, sps, lps, ns, nl)
  else:
    # move <d> spaces
    p += d
    x = m.get(p)
    if x is not None:
      # behaviour of position is already allocated
      if x not in ps:
        yield from play(d, m, x, ps + [x], sps, lps, ns, nl)
    else:
      # decide the behaviour of this position, either:

      # -> p is not a special square
      if p not in ps:
        yield from play(d, update(m, [(p, p)]), p, ps + [p], sps, lps, ns, nl)

      # -> p is the bottom of a ladder
      if nl > 0 and p in lps:
        # move to a higher ladder position
        for x in lps:
          if not (x > p): continue
          if x not in ps:
            yield from play(d, update(m, [(p, x)]), x, ps + [x], sps, remove(lps, p, x), ns, nl - 1)

      # -> p is the top of a snake
      if ns > 0 and p in sps:
        # move to a lower snake position
        for x in sps:
          if not (x < p): break
          if x not in ps:
            yield from play(d, update(m, [(p, x)]), x, ps + [x], remove(sps, p, x), lps, ns - 1, nl)

# solve the puzzle for repeated throws in <ds>
# m = behaviour of positions (src -> tgt)
# sps = positions for snakes
# lps = positions for ladders
# ns = remaining snakes
# nl = remaining ladders
# ss = sequences recorded
# return (m, ss)
def solve(ds, m, sps, lps, ns, nl, ss=dict()):
  # are we done?
  if not ds:
    yield (m, ss)
  else:
    # try the next sequence
    d = ds[0]
    for (m_, ps_, sps_, lps_, ns_, nl_) in play(d, m, 0, [], sps, lps, ns, nl):
      # check the sequence ends on 100
      if not (ps_[-1] == 100): continue
      ss_ = update(ss, [(d, ps_)])
      # check n4 = n5 + 1
      if d == 4 or d == 5:
        (ss4, ss5) = (ss_.get(4), ss_.get(5))
        if ss4 and ss5 and not (len(ss4) == len(ss5) + 1): continue
      # check n3 < n5
      if d == 3 or d == 5:
        (ss3, ss5) = (ss_.get(3), ss_.get(5))
        if ss3 and ss5 and not (len(ss3) < len(ss5)): continue
      # solve for the remaining sequences
      yield from solve(ds[1:], m_, sps_, lps_, ns_, nl_, ss_)

# solve for repeated throws 1 - 6, with 3 snakes on squares, 3 ladders on primes
for (m, ss) in solve([6, 5, 4, 3, 2, 1], dict(), sqs, prs, 3, 3):
  # output layout
  for s in sorted(m.keys()):
    t = m[s]
    if s < t: printf("{s} -> {t} ladder")
    if s > t: printf("{s} -> {t} snake")
  printf()
  # output sequences
  for d in sorted(ss.keys()):
    ts = ss[d]
    printf("{d} -> {n} throws {ts}", n=len(ts))
  printf()

        Like

    • Frits's avatar

      Frits 6:25 pm on 7 April 2025 Permalink | Reply

      Similar to Jim’s program.

      It runs under 10 seconds (using PyPy).

      # -------------------------------- start Jim Randell ------------------------
# play the game starting with list <lst>, constantly throwing <d>
# return: <sequence-of-positions> or None
def play(d, m, lst):
  ps = list(lst)
  p = lst[-1]
  while True:
    # move d spaces
    p += d
    # have we hit a special position?
    p = m.get(p, p)
    # have we hit a loop?
    if p in ps: return
    ps.append(p)
    # are we done?
    if p >= 100: return ps    

# check map <m> of special positions for a solution
def check_sol(m):
  n = dict()
  for d in [4, 5, 3, 6, 2, 1]:
    # each play eventually gets to 100
    ps = play(d, m, f_lst[d])
    if ps is None or ps[-1] != 100: return
    n[d] = ps
    # check n4 = n5 + 1
    if d == 5 and not (len(n[4]) == len(n[5]) + 1): return
    # check n3 < n5
    if d == 3 and not (len(n[3]) < len(n[5])): return
  # return the moves for each die value
  return n
# -------------------------------- end Jim Randell --------------------------
  
prms = [x for x in range(11, 100, 2) if all(x % p for p in [3, 5, 7])]
sqs = [i * i for i in range(4, 10)]  # 2-digit squares
spec = prms + sqs

# mandatory first numbers 
f_lst = {n: list(range(n, next(x for x in range(n, 100, n) if x in spec and 
                  x not in {sqs[0], prms[-1]}), n)) for n in range(1, 7)}

# generate all possible combinations of 3 ladders
ladders = []
inds = {x: i for i, x in enumerate(prms)}
for P in prms[:-3]:
  for Q in prms[inds[P] + 1:]:
   
    for R in prms[inds[P] + 1:-2]:
      if R == Q: continue
      for S in prms[inds[R] + 1:]:
        if S == Q: continue
        
        for T in prms[inds[R] + 1:-1]:
          if T in {Q, S}: continue
          for U in prms[inds[T] + 1:]:
            if U in {Q, S}: continue
            ladders.append((P, Q, R, S, T, U))
        
# generate all possible combinations of 3 snakes
for a in range(5, 9):
  A = a * a
  for b in range(4, a):
    B = b * b
    for c in range(a + 1, 9):
      C = c * c
      for d in range(4, c):
        if d in {a, b}: continue
        D = d * d
        e = 9
        E = e * e
        f = 39 - a - b - c - d - e
        if f in {a, b, c, d}: continue
        F = f * f
        # create snake dictionary
        d = {A: B, C: D, E: F}
        for lddr in ladders:
          d_ = d.copy()
          # add ladder data to dictionary
          d_.update({lddr[i]: lddr[i + 1] for i in range(0, 6, 2)})
          # check for solution 
          if (n := check_sol(d_)) is None: continue
          print("answer:", *[lddr[i:i+2] for i in range(0, 6, 2)])

      Like

    • Frits's avatar

      Frits 7:13 pm on 8 April 2025 Permalink | Reply

      New approach, again without using analysis.
      The main line can probably done with recursion but I didn’t feel like doing that.

      It run in approx. 18ms (using Cpython).

      prms = [x for x in range(11, 100, 2) if all(x % p for p in [3, 5, 7])]
sqs = [i * i for i in range(4, 10)]  # 2-digit squares
spec = prms + sqs

# dictionary of mandatory last numbers 
dlast = {n: tuple(range(next(x for x in range(100 - n, 0, -n) if x in spec and 
            x not in {sqs[-1], prms[0]}), 100 + n, n)) for n in range(1, 7)}

# dictionary of mandatory first numbers
dfirst = {n: tuple(range(n, next(x for x in range(n, 100, n) if x in spec and 
                   x not in {sqs[0], prms[-1]}), n)) for n in range(1, 7)}

# go from number <a> to <b> by adding a maximum of <k> board numbers
# between <a> and <b> with standard throws <m> and <kn> = known snakes/ladders
def solve(m, a, b, k, ns=0, nl=0, kn=set(), ss=[], new=set()):
  tst = (11, 83) in kn | new
  # <k> fields cause <k + 1> moves
  if k == -1 or a == b:
    if a == b:
      yield len(ss) - 1, kn | new, ns, nl
  else:
    # new number may not have been seen before
    if (n := a + m) in ss or n > 100: return
    # try standard throw if not on a kn snake of ladder 
    if n not in {x for x, y in kn}:
      yield from solve(m, n, b, k - 1, ns, nl, kn, ss + [n], new)
    
    # try to add a snake  
    if n in sqs:
      for s in sqs:
        if s == n: break 
        # do checks for new snake
        if (n, s) not in kn:
          if ns > 2 or not set(sum(kn | new, ())).isdisjoint({n, s}):
            continue
          ns_ = ns + 1
        else:
          ns_ = ns
        yield from solve(m, s, b, k - 1, ns_, nl, kn, ss + [s], new | {(n, s)})
    # try to add a ladder
    if n in prms:
      for p in prms[::-1]:
        if p == n: break 
        # do checks for new ladder
        if (n, p) not in kn:
          if nl > 2 or not set(sum(kn | new, ())).isdisjoint({n, p}):
            continue
          nl_ = nl + 1
        else:
          nl_ = nl  
        yield from solve(m, p, b, k - 1, ns, nl_, kn, ss + [p], new | {(n, p)})

def six_throws(seq, ln5=0, ns=0, nl=0, kn=set(), ss=[]):
  if not seq:
    if len(kn) == 6:
      yield kn
  else:
    m = seq[0]
    mx = (107 if m not in {3, 4} else
          ln5 + (2 * m - 7) - len(dfirst[m]) - len(dlast[m]))
    
    for ln, kn_, ns_, nl_ in solve(m, dfirst[m][-1], dlast[m][0], 
                                   mx, ns, nl, kn):
      if m == 4: # check requirement
        if len(dfirst[m]) + len(dlast[m]) + ln != ln5 + 1: continue
        
      if m == 5: # save number of throws of 5 needed
        ln5 = len(dfirst[m]) + len(dlast[m]) + ln
      
      yield from six_throws(seq[1:], ln5 , ns_, nl_, kn_, ss)
        
# perform 2 passes as some ordr's generate incorrect solutions
ordr = (5, 4, 3, 6, 2, 1)  # one of the most efficient orders
# 1st pass: start with no known snakes and ladders
for p1 in six_throws(ordr):
  # 2nd pass: check again with a full set of snakes and ladders
  sols = []
  for p2 in six_throws(ordr, 0, 3, 3, p1):
    if p2 not in sols:
      if p1 != p2: 
        print("ERROR")
        exit(0)
      sols.append(p2) 
      
for s in sols:
  print("answer:", *[(x, y) for x, y in sorted(s) if x not in sqs])

      Like

  • Unknown's avatar

    Jim Randell 10:30 am on 4 April 2025 Permalink | Reply
    Tags: ,   

    Teaser 2558: Round table 

    From The Sunday Times, 2nd October 2011 [link] [link]

    Pat likes to demonstrate his favourite trick shot on the pub pool table, which is 90 inches long and 48 inches wide. Pat hits the ball so that it strikes the long side of the table first, then (after a perfect bounce) it hits the short side, then the other long side, and then finally the other short side, from which it returns to the starting point, making its path the perimeter of a quadrilateral.

    What is the length of the perimeter of that quadrilateral?

    [teaser2558]

     
    • Jim Randell's avatar

      Jim Randell 10:31 am on 4 April 2025 Permalink | Reply

      (See also: Teaser 3184, Teaser 3073, Teaser 1917).

      Wherever the ball starts tracing out the quadrilateral, we can consider its movement in the x and y directions.

      In the x direction it travels to the cushion on one end, back to the other cushion, and then returns to its original position.

      i.e. the total distance travelled in the x direction is twice the length of the table (= 2 × 90 in = 180 in).

      Similarly the distance travelled in the y direction is twice the width of the table (= 2 × 48 in = 96 in).

      Hence the total distance travelled by the ball is: hypot(180, 96):

      >>> hypot(180, 96)
204.0

      Solution: The length of the perimeter of the quadrilateral is 204 in.

      Like

  • Unknown's avatar

    Jim Randell 8:59 am on 2 April 2025 Permalink | Reply
    Tags:   

    Teaser 2561: Winning the double 

    From The Sunday Times, 23rd October 2011 [link] [link]

    Four teams, A, B, C and D, played each other once in a league, then played a knockout competition. They scored a total of 54 goals in the nine games, with a different score in each game; no team scored more than five goals in any game. For each team the average number of goals per game was a different whole number. Team B beat D by a margin of more than one goal in the knockout competition, but team A took the double, winning all their games.

    What was the score in the match CvD?

    [teaser2561]

     
    • Jim Randell's avatar

      Jim Randell 9:00 am on 2 April 2025 Permalink | Reply

      In the tournament the 6 matches are:

      AvB, AvC, AvD, BvC, BvD, CvD

      In the knockout there is a BvD match (which B won), but A won the knockout. So the matches in the knockout must be:

      1st round: AvC (A wins); BvD (B wins)
      Final: AvB (A wins)

      So A and B have played 5 matches, and C and D have played 4.

      A won all their matches, so their goal average must be at least 3.

      B won at least one match, so their goal average must be at least 1.

      The following run file finds possible scorelines in each match. It isn’t very fast though, but it does run in 10.3s under PyPy.

      #! python3 -m enigma -rr

SubstitutedExpression

# tournament:
#
#     A B C D
#  A: - H I J  (A wins all matches)
#  B: K - L M
#  C: N P - Q
#  D: R S T -
#
# knockout:
#
#  round 1: A v C = U - V (A wins); B v D = W - X (B wins)
#  final: A v B = Y - Z (A wins)
#
# no team scored more than 5 goals, so goals (and goal averages = A, B, C, D) are all 0-5
--base=6  # allows digits 0-5
--distinct="ABCD"  # goal averages are all different

# total goals scored by each team
--macro="@goalsA = (H + I + J + U + Y)"
--macro="@goalsB = (K + L + M + W + Z)"
--macro="@goalsC = (N + P + Q + V)"
--macro="@goalsD = (R + S + T + X)"

# total of all the goals scored is 54
"@goalsA + @goalsB + @goalsC + @goalsD == 54"

# each game has a different score line
"seq_all_different(ordered(x, y) for (x, y) in zip([H, I, J, L, M, Q, U, W, Y], [K, N, R, P, S, T, V, X, Z]))"

# goal averages (are all different by --distinct)
"A * 5 == @goalsA"
"B * 5 == @goalsB"
"C * 4 == @goalsC"
"D * 4 == @goalsD"
"A > 2"  # A won all their matches
"B > 0"  # B won at least one match
# and the total of all goals scored is 54
"5 * (A + B) + 4 * (C + D) == 54"

# B beat D by more than 1 goal in the knockout
"W > X + 1"

# A won all their games
"H > K" "I > N" "J > R" "U > V" "Y > Z"

--template="(H-K I-N J-R L-P M-S Q-T) (U-V W-X; Y-Z) (A B C D)"
--header="(AvB AvC AvD BvC BvD CvD) (AvC BvD; AvB) (A B C D)"
--solution=""
--answer="(Q, T)"  # answer is the score in C vs D match
--denest=-1  # CPython workaround

      Solution: The score in the C vs D match was 5 – 5.

      The program finds 48 ways to assign the scores in each match.

      For example, one of the assignments is:

      Tournament:
      A vs B = 5-1
      A vs C = 5-3
      A vs D = 5-0
      B vs C = 0-4
      B vs D = 0-3
      C vs D = 5-5

      Knockout:
      A vs C = 5-4
      B vs D = 2-0
      A vs B = 5-2

      A wins all their matches by scoring 5 goals, so their goal average is 5. And the goal averages for B, C, D are B = 1 (from 5 goals), C = 4 (from 16 goals), D = 2 (from 8 goals).

      Like

      • Frits's avatar

        Frits 1:20 pm on 2 April 2025 Permalink | Reply

        @Jim, typo in line 48: “J > R”.
        It makes the program slower (and 48 ways to assign the scores in each match)

        Like

      • Frits's avatar

        Frits 2:17 pm on 2 April 2025 Permalink | Reply

        Easy performance enhancement (from Brian’s analysis):

        --invalid="5,BCD"  # teams other than A cannot score 5 goals in all their games

        Like

        • Jim Randell's avatar

          Jim Randell 2:27 pm on 2 April 2025 Permalink | Reply

          Yes. With a little analysis there are some easy additional restrictions we can deduce.

          These bring the run time down to a much more reasonable 196ms.

          # more restrictions we can deduce
--invalid="0,ABHIJUWY"
--invalid="1,AW"
--invalid="2,A"
--invalid="4,X"
--invalid="5,BCDKNRVXZ"

          And with more analysis we can go further. But I prefer to let the computer do the majority of the work.

          Like

    • Frits's avatar

      Frits 1:15 pm on 3 April 2025 Permalink | Reply

      The program loops over the requested score so we can early return as soon as a solution is found (and not report 47 similar solutions).

      The runtime approaches the 10 ms with CPython (as is feasible for most teasers).

      from itertools import product

# Analysis: (credit B. Gladman)

# If the average goals per game for A, B, C, D are a, b, c and d we then have
#
#     54 == 5.(a + b) + 4.(c + d) 
#
# (since A and B play five games whereas C and D play four). Here the possible
# solutions (a + b, c + d) = (10, 1), (6, 6) or (2, 11).
 
# Since the maximum goals a team can score in any game is 5, all the averages
# are five or less. And, since the averages are all different, a + b and c + d
# are both less than 10 which means that a + b == c + d == 6. Moreover, since
# A wins all their games, other teams cannot score 5 goals in all their games
# and must have goals per match averages of less than five.
#
# Hence the possibilities are:
#
#      (a, b) = (5, 1), (4, 2), (2, 4)
#      (c, d) = (4, 2), (2, 4)
#
# And since the values are all different 
#
#      (a, b, c, d) =  (5, 1, 4, 2) or (5, 1, 2, 4)
#
#
# Hence in goal totals (A, B, C, D) = (25, 5, 16, 8) or (25, 5, 8, 16)

(H, I, J, U, Y, A, B) = (5, 5, 5, 5, 5, 5, 1)

# tournament:
#
#     A B C D
#  A: - H I J  (A wins all matches)
#  B: K - L M
#  C: N P - Q
#  D: R S T -
#
# knockout:
#
#  round 1: A v C = U - V (A wins); B v D = W - X (B wins)
#  final: A v B = Y - Z (A wins)
#

def inner(Q, T):
  for C in [2, 4]:
    D = 6 - C
    # A wins all their games with 5 goals  
    if 5 in {Q, T} and (Q, T) != (5, 5): continue
    for X in range(3):                        # X != 3 as W < 5
      for W in range(X + 2, 5):               # B beat D by more than one goal
        for R in range(5):
          S = D * 4 - (R + T + X)             # team D
          if not (0 <= S <= 4): continue      # S != 5 as M <= 3
          for V in range(5):                  # as W >= 2 then K,L,M,Z <= 3
            if V == R: continue
            for N in range(5):
              if N in {V, R}: continue
              P = C * 4 - (N + Q + V)         # team C
              if not (0 <= P <= 4): continue  # P != 5 als L <= 3
              # as W >= 2 then K,L,M,Z <= 3
              for L, M in product(range(4), repeat=2): 
                # different games
                if (len(set(s := list(zip([L, M, Q, W], [P, S, T, X])))) !=
                    len(s)): continue
                for Z in range(4):            # as W >= 2 then K,L,M,Z <= 3
                  if Z in {V, R, N}: continue
                  K = B * 5 - (L + M + W + Z) # team B
                  if not (0 <= K <= 3) or K in {V, R, N, Z}: continue
                  if H+I+J+K+L+M+N+P+Q+R+S+T+U+V+W+X+Y+Z != 54: continue
                  return str((Q, T))

sols = []
# Process scores CvD  (Q, T)
for C, D in product(range(6), repeat=2):
  if (s := inner(C, D)):
    sols.append(s)

print("answer(s):", ' or '.join(sols))

      Like

    • Frits's avatar

      Frits 6:20 pm on 3 April 2025 Permalink | Reply

      Another one using more analysis. Internal runtime 22 microseconds (under PyPy).

      from itertools import product, permutations

stup = lambda x, y: (x, y) if x < y else (y, x)
  
def diffgames(a, b):
  return len(set(s := list(stup(x, y) for x, y in zip(a, b)))) == len(s)
  
# Analysis: (credit B. Gladman)

# If the average goals per game for A, B, C, D are a, b, c and d we then have
#
#     54 == 5.(a + b) + 4.(c + d) 
#
# (since A and B play five games whereas C and D play four). Here the possible
# solutions (a + b, c + d) = (10, 1), (6, 6) or (2, 11).
 
# Since the maximum goals a team can score in any game is 5, all the averages
# are five or less. And, since the averages are all different, a + b and c + d
# are both less than 10 which means that a + b == c + d == 6. Moreover, since
# A wins all their games, other teams cannot score 5 goals in all their games
# and must have goals per match averages of less thsn five.
#
# Hence the possibilities are:
#
#      (a, b) = (5, 1), (4, 2), (2, 4)
#      (c, d) = (4, 2), (2, 4)
#
# And since the values are all different 
#
#      (a, b, c, d) =  (5, 1, 4, 2) or (5, 1, 2, 4)
#
#
# Hence in goal totals (A, B, C, D) = (25, 5, 16, 8) or (25, 5, 8, 16)
#
#
# In the knockout 1st round game BvD team B can score a maximum of 4 goals
# and we have B - D >= 2. Team D can only score a maximum of 2 goals in this 
# knockout round.
# This means the average of team D cannot be 4 (as it would require at least 
# 2 wins with 5 goals). So the averages of team C and D are 2 resp. 4.
# In all games of team C they score at least 3 goals.

(H, I, J, U, Y, A, B, C, D) = (5, 5, 5, 5, 5, 5, 1, 4, 2)
(B5, C4, D4) = (5 * B, 4 * C, 4 * D)

# tournament:
#
#     A B C D
#  A: - H I J  (A wins all matches)
#  B: K - L M
#  C: N P - Q
#  D: R S T -
#
# knockout:
#
#  round 1: A v C = U - V (A wins); B v D = W - X (B wins)
#  final: A v B = Y - Z (A wins)
#

# inner loops
def inner(Q, T):
  # team A wins all their games scoring 5 goals in each game
  if 5 in {Q, T} and (Q, T) != (5, 5): return
  for X in range(3):                      # X != 3 as W < 5
    for R in range(3):                    # as N and V (team C) use 3 and 4
      S = D4 - (R + T + X)             # team D
      if not (0 <= S <= 4): continue      # S != 5 as M <= 3
      for N, V in permutations(range(3, 5), 2): # team C goals
        P = C4 - (N + Q + V)           # team C
        if not (3 <= P <= 4): continue    # P != 5 als L <= 3
        for W in range(X + 2, 5):         # B beat D by more than one goal
          # K + N + R + V + Z = 10  and  K + L + M + W + Z = 5
          for L in range((LM := (V + N + R) - W - 5) + 1):       
            M = LM - L
            
            # different games
            if not diffgames([L, M, Q, W], [P, S, T, X]): continue

            for Z in range(6 - W - L - M):  # K,L,M,Z <= 3 as W >= 2
              if Z in {V, R, N}: continue
              K = B5 - (L + M + W + Z) # team B
              if not (0 <= K <= 3) or K in {V, R, N, Z}: continue

              if H+I+J+K+L+M+N+P+Q+R+S+T+U+V+W+X+Y+Z != 54: continue
              return str((Q, T))

sols = []
# process scores CvD, team C scores at least 3 goals in each game
for Q, T in product(range(3, 6), range(6)):
  if (s := inner(Q, T)):
    sols.append(s)

print("answer(s):", ' or '.join(sols))

      Like

  • Unknown's avatar

    Jim Randell 2:42 am on 30 March 2025 Permalink | Reply
    Tags:   

    Teaser 3262: Log cabins 

    From The Sunday Times, 30th March 2025 [link] [link]

    Ann, Bert, Chloe and Dave own log cabins on the shore of a circular lake. Ann often rows across the lake (in a straight line) to visit Bert, and vice-versa. Chloe and Dave also visit each other in the same way.

    The two routes cross in the lake at point X. Interestingly, the four distances from the log cabins to X are all whole numbers of metres (greater than 20m), but the list of distances contains no digit more than once. Chloe’s distance from her log cabin to X is twice Ann’s, while Bert’s distance is three times Ann’s.

    In ascending order, what are the four distances from the log cabins to X?

    [teaser3262]

     
    • Jim Randell's avatar

      Jim Randell 3:10 am on 30 March 2025 Permalink | Reply

      The cabins form a cyclic quadrilateral [ @wikipedia ].

      And if we denote the distances AX = a, BX = b, CX = c, DX = d. Then we have:

      a . b = c . d

      This is the intersecting chords theorem [ @wikipedia ].

      So:

      b = 3a
      c = 2a
      ⇒
      d = 3a/2

      Hence a must be even.

      The following Python program runs in 67ms. (Internal runtime is 106µs).

      from enigma import (irange, inf, ediv, ordered, join, printf)

# consider distance AX = a (must be even)
for a in irange(22, inf, step=2):
  # BX = b = 3a, CX = c = 2a, DX = d = 3a/2
  (b, c, d) = (3 * a, 2 * a, ediv(3 * a, 2))
  ds = ordered(a, b, c, d)
  s = join(ds)
  # between them they use no digit more than once
  if len(s) > 10: break
  if len(s) != len(set(s)): continue
  # output solution
  printf("{ds} [a={a} b={b} c={c} d={d}]")

      Solution: The distances are: 36, 54, 72, 108 metres.

      a = 36
      b = 108
      c = 72
      d = 54
      and:
      a . b = c . d = 3888

      Manually we can follow a similar approach, considering even values for a starting at 22, until a solution is found:

      a = 22; repeated digits
      a = 24; b = 72; repeated digits
      a = 26; b = 78; c = 52; repeated digits
      a = 28; b = 84; repeated digits
      a = 30; b = 90; repeated digits
      a = 32; b = 96; c = 64; repeated digits
      a = 34; b = 102; c = 68; d = 51; repeated digits
      a = 36; b = 108; c = 72; d = 54; solution found

      For an exhaustive solution it is sufficient to check a ≤ 66 beyond which the distances use more than 10 digits, so there will always be duplication of digits. But there are no further solutions.

      Like

  • Unknown's avatar

    Jim Randell 3:50 pm on 28 March 2025 Permalink | Reply
    Tags:   

    Teaser 2563: Prime time 

    From The Sunday Times, 6th November 2011 [link] [link]

    In this addition sum I have consistently replaced digits by letters, with different letters for different digits, and I have ended up with another correct addition sum.

    What is the prime number NOW?

    [teaser2563]

     
    • Jim Randell's avatar

      Jim Randell 3:51 pm on 28 March 2025 Permalink | Reply

      We can use the [[ SubstitutedExpression.split_sum ]] solver from the enigma.py library to solve this puzzle.

      The following run file executes in 77ms. (Internal runtime of the generated code is 110µs).

      #! python3 -m enigma -rr

SubstitutedExpression.split_sum

"ONE + TWO + FIVE = EIGHT"

--extra="is_prime(NOW)"
--answer="NOW"

      Solution: NOW = 467.

      Like

    • Ruud's avatar

      Ruud 9:17 am on 29 March 2025 Permalink | Reply 

      import istr


for o, n, e, t, w, f, i, v, g, h in istr.permutations(range(10)):
    if (o | n | e) + (t | w | o) + (f | i | v | e) == (e | i | g | h | t) and (n | o | w).is_prime():
        print("now =", n | o | w)

      Like

    • GeoffR's avatar

      GeoffR 10:12 am on 29 March 2025 Permalink | Reply 

      
% A Solution in MiniZinc
include "globals.mzn";

%      O N E
%      T W O
%    F I V E
%  ---------
%  E I G H T
%  ---------
%     c3c2c1
 
var 1..9:O; var 1..9:N; var 1..9:E; var 1..9:T; var 0..9:W; 
var 1..9:F; var 0..9:I; var 0..9:V; var 0..9:G; var 0..9:H;
var 0..2:c1; var 0..2:c2; var 0..2:c3;
var 100..999:NOW = 100*N + 10*O + W;

constraint E == 1;

constraint all_different([O, N, E, T, W, F, I, V, G, H]);

predicate is_prime(var int: x) = 
x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
((i < x) -> (x mod i > 0));

constraint (E + O + E ) mod 10 == T 
/\ (E + O + E) div 10 == c1;

constraint (N + W + V + c1) mod 10 == H 
/\ (N + W + V + c1) div 10 == c2;

constraint (O + T + I + c2) mod 10 == G 
/\ (O + T + I + c2) div 10 == c3;

constraint (F + c3) mod 10 == I /\ (F + c3) div 10 == E; 

constraint is_prime(NOW);

solve satisfy;
output[ "NOW = " ++ show(NOW)];

% NOW = 467
% ----------
% ==========

      Like

  • Unknown's avatar

    Jim Randell 8:39 am on 25 March 2025 Permalink | Reply
    Tags:   

    Teaser 2559: Inconsequential 

    From The Sunday Times, 9th October 2011 [link] [link]

    Most whole numbers can be expressed as the sum of two or more consecutive whole numbers. For example:

    35 = 17 + 18
    36 = 11 + 12 + 13
    40 = 6 + 7 + 8 + 9 + 10

    I have written down two whole numbers. Between them they use each of the digits 0 to 9 exactly once. But neither of the numbers can be expressed as the sum of two or more consecutive whole numbers.

    What are my two numbers?

    [teaser2559]

     
    • Jim Randell's avatar

      Jim Randell 8:39 am on 25 March 2025 Permalink | Reply

      I am assuming that by “whole numbers” the setter means the positive integers.

      We have encountered the polite numbers [@wikipedia] before, see: BrainTwister #43, Enigma 776, Teaser 2994, Enigma 914, Enigma 1231, Enigma 1.

      The “impolite” numbers are the powers of 2, so we need to find two powers of 2 that between them use each of the 10 digits exactly once.

      This Python program runs in 62ms. (Internal runtime is 134µs).

      from enigma import (distinct_chars, printf)

# record powers of 2 (as strings)
ps = list()
n = 1
while True:
  s = str(n)
  if len(s) > 9: break
  # look for a pair that use all 10 digits between them
  for x in ps:
    if distinct_chars(x, s) == 10:
      printf("{x}, {n}")
  ps.append(s)
  n *= 2

      Solution: The numbers are: 4, 536870912.

      Where:

      2^2 = 4
      2^29 = 536870912

      Like

  • Unknown's avatar

    Jim Randell 1:43 am on 23 March 2025 Permalink | Reply
    Tags:   

    Teaser 3261: The evidence of weight 

    From The Sunday Times, 23rd March 2025 [link] [link]

    The sunbathing pontoon’s four identical, cubic, sealed floats had widths a whole number of centimetres (less than 100). Arkim, Edie’s son, knew that the pontoon’s labelled weight of 20,000 grams would equal the combined submerged volume of the floats in cubic centimetres, if the pool water’s density was one gram per cubic centimetre.

    Later, with Edie alone on the pontoon (once again level in still water), the floats were a whole number of centimetres further partially submerged. Assuming the above, Arkim calculated Edie’s weight to be a whole number of kilograms (under her 90 kg peak, but above her 50 kg “wedding” weight).

    If I were a cad and revealed Edie’s weight, you would be unsure of a float’s width.

    Give Edie’s weight in kilograms.

    [teaser3261]

     
    • Jim Randell's avatar

      Jim Randell 2:12 am on 23 March 2025 Permalink | Reply

      If the floats are cubes with dimension f (cm), and have submerged depth d (cm), then the total submerged volume is: 4.f^2.d (cm^3). And this is equal to the total weight (in grams) supported by the floats.

      The following Python program runs in 76ms. (Internal runtime is 1.9ms).

      from enigma import (Rational, irange, group, unpack, printf)

Q = Rational()

# generate candidate solutions
def generate():
  # consider possible dimensions of the floats (f: cm)
  for f in irange(1, 99):
    # calculate initial displacement (d: cm)
    A = 4 * f * f
    d = Q(20000, A)  # platform weight = 20 kg
    # consider possible additional displacement (x: cm)
    for x in irange(1, int(f - d)):
      # calculate E's weight (E: kg)
      E = Q(A * x, 1000)
      if E.denominator == 1 and 50 < E < 90:
        printf("[f={f} d={d:.2f}, x={x} -> E={E}]", d=float(d))
        yield (f, d, x, int(E))

# group candidate solutions by E
g = group(generate(), by=unpack(lambda f, d, x, E: E))

# look for solution with multiple float widths
for (E, vs) in g.items():
  fs = set(f for (f, d, x, E) in vs)
  if len(fs) > 1:
    printf("E={E} -> fs={fs}", fs=sorted(fs))

      Solution: Edie weighs 72 kg.

      Without further information we cannot determine if the floats are 30 cm cubes (and the additional displacement was 20 cm), or they are 60 cm cubes (and the additional displacement was 5 cm).

      There are 8 candidate solutions. Of these there are 6 weights which do give a unique solution, and 1 that has multiple solutions:

      54 kg → 30 cm cubes; 15 cm additional displacement
      60 kg → 50 cm cubes; 6 cm additional displacement
      64 kg → 40 cm cubes; 10 cm additional displacement
      70 kg → 50 cm cubes; 7 cm additional displacement
      80 kg → 50 cm cubes; 8 cm additional displacement
      81 kg → 45 cm cubes; 10 cm additional displacement

      72 kg → 30 cm cubes; 20 cm additional displacement
      72 kg → 60 cm cubes; 5 cm additional displacement

      Eureka!

      Like

    • Frits's avatar

      Frits 3:40 am on 23 March 2025 Permalink | Reply 

      # the floats should support at least Edie (>= 51kg) and the pontoon (20 kg)

seen = set()

# Edie weighs <wght> kilograms or 
# <wght>.8.5^3 grams = 4.h.w^2 so w must be a multiple of 5
min_w = next(w for w in range(5, 100, 5) if w > (71000 / 4)**(1 / 3))

# cubic width of a float 
for w in range(min_w, 100, 5):
  # make sure <v> will be a multiple of 1000
  mult = 1 + (w % 2)
  # check if h must also be a multiple of 5
  min_h, step = (5 * mult, 5 * mult) if w % 25 else (mult, mult) 
  # extra submersion in centimeters with Edie on the pontoon
  for h in range(min_h, w, step):
    # extra volume submersed 
    if (v := 4 * h * w**2) > 89000: break
    if v < 51000: continue  
    if v in seen:
      print(f"answer: {v // 1000} kilograms")
    seen.add(v)

      Like

    • Frits's avatar

      Frits 5:36 am on 24 March 2025 Permalink | Reply

      A different approach.

      from collections import defaultdict

# the floats should support at least Edie (>= 51kg) and the pontoon (20 kg)

# Edie weighs <wght> kilograms or 
# <wght>.8.5^3 grams = 4.h.w^2 so w must be a multiple of 5
min_w = next(w for w in range(5, 100, 5) if w >= (71000 / 4)**(1 / 3))

# if there is a solution with w1, v and h1 and h1 is a multiple of a
# square (h2 * a^2) there might be another solution v = 4 * h2 * w2^2
# where w2 = a * w1 and w2 within boundaries

# collect multiples of squares (except 1^2)
multsq = defaultdict(list)
for i in range(2, 9):
  for j in range(1, 25):
    if (m := j * i * i) > 99 - min_w: break
    multsq[m] += [i]

sols = set()
# cubic width of the smaller float 
for w in range(min_w, 50, 5):
  w25 = w % 25
  # extra submersion in centimeters with Edie on the pontoon
  for h, vs in multsq.items():
    # we need enough factors of 5
    if w25 and h % 5: continue
    # extra volume submerged 
    if (v := 4 * h * w**2) > 89000: break
    if v < 51000: continue  
    if v % 1000: continue
    
    # check if there is a solution with same volume but a larger cubic width
    for i in vs:
      if i * w < 100:
        sols.add(str(v // 1000))

print(f"answer: {' or '.join(sols)} kilograms")

      Like

    • GeoffR's avatar

      GeoffR 10:38 am on 26 March 2025 Permalink | Reply

      Multiple output solutions gives two solutions for one particular weight, which is the answer. Other solutions are single solutions for different weights.

      
% A Solution in MiniZinc
include "globals.mzn";

var 5..100: w;      % Float width of four floats
var 0.1..99.9: d1;  % Submerged depth due to self weight
var 1..99: d2;      % Submerged depth due to Edie's weight
var 51..89: E;      % Edie's weight in kilograms

% Re-use d2 is a multiple of 5
constraint d2 mod 5 == 0;

% Find d1
constraint 4.0 * int2float(w) * int2float(w) * d1 == 20000.0;

% Ensure some freeboard on floats  with Edie's weight
constraint int2float(d2) < int2float(w) - d1;

% Find d2
constraint 4 * w * w * d2 / 1000 == E;

solve satisfy;

output ["[ w, d1, d2, E] = " ++ show([w, d1, d2, E])];

      Like

      • Jim Randell's avatar

        Jim Randell 1:10 pm on 29 March 2025 Permalink | Reply

        @Geoff: This doesn’t find the candidate solutions where the floats are 50 cm cubes. This seems to be due to the constraint at line 10, which can be removed.

        However, it then finds an additional candidate where the floats are 100 cm, and this gives a second solution to the puzzle.

        But we can reduce the range at line 4, as the float dimension has to be less than 100 cm. Then we find all 8 candidate solutions, and there is only one case of a duplicate weight for Edie.

        Like

    • GeoffR's avatar

      GeoffR 5:19 pm on 29 March 2025 Permalink | Reply

      @Jim: Yes, fair comment to upgrade ny code.

      Like

    • GeoffR's avatar

      GeoffR 12:10 pm on 30 July 2025 Permalink | Reply

      Here is my updated solution.

      
% A Solution in MiniZinc
include "globals.mzn";
 
var 5..99: w;       % Float width of four floats
var 0.1..99.9: d1;  % Submerged depth due to self weight
var 1..99: d2;      % Submerged depth due to Edie's weight
var 51..89: E;      % Edie's weight in kilograms
 
% Find d1
constraint 4.0 * int2float(w) * int2float(w) * d1 == 20000.0;
 
% Ensure some freeboard on floats  with Edie's weight
constraint int2float(d2) < int2float(w) - d1;
 
% Find d2
constraint 4 * w * w * d2 / 1000 == E;
 
solve satisfy;
 
output ["[ w, d1, d2, E] = " ++ show([w, d1, d2, E])];

% [ w, d1, d2, E] = [30.0, 5.55555555555556, 15.0, 54.0]
% ----------
% [ w, d1, d2, E] = [30.0, 5.55555555555556, 20.0, 72.0]
% ----------
% [ w, d1, d2, E] = [40.0, 3.125, 10.0, 64.0]
% ----------
% [ w, d1, d2, E] = [45.0, 2.46913580246914, 10.0, 81.0]
% ----------
% [ w, d1, d2, E] = [60.0, 1.38888888888889, 5.0, 72.0]
% ----------
% [ w, d1, d2, E] = [50.0, 2.0, 6.0, 60.0]
% ----------
% [ w, d1, d2, E] = [50.0, 2.0, 7.0, 70.0]
% ----------
% [ w, d1, d2, E] = [50.0, 2.0, 8.0, 80.0]
% ----------
% ==========
%  Edie = 72 kg is the only weight with multiple solutions (2 No.)

      Like

  • Unknown's avatar

    Jim Randell 7:44 am on 21 March 2025 Permalink | Reply
    Tags:   

    Teaser 2564: 11/11/11 

    From The Sunday Times, 13th November 2011 [link] [link]

    As it was 11/11/11 last Friday, I have been looking at numbers that are divisible by 11.

    I have written down an eight-figure number using the digits 2, 3, 4, 5, 6, 7, 8 and 9 in some order. For any two adjacent digits in the number, either: one is a multiple of the other; or: the two digits differ by one.

    My number is divisible by its first digit, its last digit, and (of course) by 11.

    What is the eight-figure number?

    [teaser2564]

     
    • Jim Randell's avatar

      Jim Randell 7:44 am on 21 March 2025 Permalink | Reply

      The following run file executes in the 79ms. (Internal runtime of the generated code is 897µs).

      #! python3 -m enigma -rr

SubstitutedExpression

# suppose the 8-digit number is: ABCDEFGH
--digits="2-9"

# for any adjacent digits, either:
# - one is a multiple of the other; or:
# - the two digits differ by 1
--code="f = lambda a, b: a % b == 0 or b % a == 0 or abs(a - b) == 1"
"f(A, B)" "f(B, C)" "f(C, D)" "f(D, E)" "f(E, F)" "f(F, G)" "f(G, H)"

# the number is divisible by A, H and 11
"ABCDEFGH % A = 0"
"ABCDEFGH % H = 0"
"ABCDEFGH % 11 = 0"

--answer="ABCDEFGH"
--verbose="A"

      Solution: The number is: 76398245.

      Like

    • Frits's avatar

      Frits 3:33 am on 22 March 2025 Permalink | Reply 

      from functools import reduce

# convert digit list to number
d2n = lambda s: reduce(lambda x,  y: 10 * x + y, s) 

# check if digit <n> can be adjacent to digit <a> 
chk = lambda n, a: n % a == 0 or a % n == 0 or abs(a - n) == 1

# dictionary of possible neighbours
adj = {i: [j for j in range(2, 10) if j != i and 
           chk(i, j)] for i in range(2, 10)}

# generate valid sequences a, b, c, d, e, f, g, h
def solve(dgts, k, ss):
  # do we know a, b, c, d, e, f?
  if k == 2:
    # N = sum(2..9), remaining even sum: e = N - (o := (a + c + e + g))
    # divisibility by 11 rule: (o - e) % 11 = 0 or (2.o - 44) % 11 = 0
    g = 22 - ss[0] - ss[2] - ss[4]
    if not (g in adj[ss[-1]] and g in dgts): return
    h = dgts.difference([g]).pop()
    # divisibility by 3 rule (as sum(2..9) = 44)
    if h in {3, 6, 9} or not h in adj[g]: return
    yield ss + [g, h]
  else:  
    for n in adj[ss[-1]]:
      if n not in ss:
        yield from solve(dgts - {n}, k - 1, ss + [n])

# the solution has to start or end with 5 or 7
# (if both are in the middle then either 3 or 9 is at an end)      
for f in (5, 7):
  for s in solve(set(range(2, 10)) - {f}, 7, [f]):
    # add reverse if necessary
    rng = (s, s[::-1]) if s[-1] not in {5, 7} else (s, )
    for s_ in rng:
      abcdefgh = d2n(s_)
      if abcdefgh % s_[0]: continue
      if abcdefgh % s_[-1]: continue
      print("answer:", abcdefgh)

      Like

  • Unknown's avatar

    Jim Randell 7:57 am on 18 March 2025 Permalink | Reply
    Tags:   

    Teaser 2528: [Football league] 

    From The Sunday Times, 6th March 2011 [link] [link]

    Some teams, A, B, C and so on, play each other once in a football league, earning three points for a win and one for a draw. So far, each team has played two games and scored the same total number of goals. At the moment, they stand in alphabetical order, with each team having a different number of points. The result of the game B v E was 3-2, and indeed all the wins so far have been by a one-goal margin.

    If you knew how many teams there were in the league, then it would be possible to work out all the results so far.

    What are those results?

    This puzzle was originally published with no title.

    [teaser2528]

     
    • Jim Randell's avatar

      Jim Randell 7:57 am on 18 March 2025 Permalink | Reply

      Each team has played 2 matches, so the possible outcomes are:

      w+w = 6 points
      w+d = 4 points
      w+l = 3 points
      d+d = 2 points
      d+l = 1 point
      l+l = 0 points

      So, if each of the teams has a different number of points, there can be no more than 6 teams in the league. And we are told there are at least 5 teams.

      There were quite a lot of conditions to keep track of, so I opted to use a MiniZinc model, and then look for a unique solution given the number of teams in the league (using the minizinc.py wrapper).

      The following Python/MiniZinc program runs in 649ms.

      from enigma import (irange, subsets, str_upper, sprintf, printf)
from minizinc import MiniZinc

# find solutions for <n> teams
def solve(n):
  model = sprintf(r"""

  include "globals.mzn";

  set of int: Teams = 1..{n};

  % record goals scored in the matches
  % 0 = unplayed
  % >0 = goals scored + 1
  array [Teams, Teams] of var 0..10: x;

  % no team plays itself
  constraint forall (i in Teams) (x[i, i] = 0);

  % unplayed games are unplayed by both sides
  constraint forall (i, j in Teams where i < j) (x[i, j] = 0 <-> x[j, i] = 0);

  % each team has played exactly 2 games (= positive values)
  constraint forall (i in Teams) (sum (j in Teams) (x[i, j] > 0) = 2);

  % each team has scored the same number of goals (over both games)
  function var int: goal(var int: X) = if X > 0 then X - 1 else 0 endif;
  function var int: goals(var Teams: i) = sum (j in Teams) (goal(x[i, j]));
  constraint all_equal([goals(i) | i in Teams]);

  % points are in alphabetical order
  function var int: pt(var int: X, var int: Y) = if X > 0 /\ Y > 0 then 3 * (X > Y) + (X = Y) else 0 endif;
  function var int: pts(var Teams: i) = sum (j in Teams where j != i) (pt(x[i, j], x[j, i]));
  constraint forall (i in Teams where i > 1) (pts(i) < pts(i - 1));

  % score in B vs E match was 3-2 (so values are 4, 3)
  constraint x[2, 5] = 4 /\ x[5, 2] = 3;

  % all winning goal margins are 1
  constraint forall (i, j in Teams where i != j) (x[i, j] > x[j, i] -> x[i, j] = x[j, i] + 1);

  solve satisfy;
  """)

  m = MiniZinc(model, solver="minizinc -a --solver chuffed")
  for s in m.solve():
    yield s['x']

# output matches for <n> teams, solution <x>
def output(n, x):
  for i in irange(0, n - 1):
    for j in irange(i + 1, n - 1):
      (a, b) = (x[i][j] - 1, x[j][i] - 1)
      if a == b == -1: continue
      printf("{i} vs {j} = {a} - {b}", i=str_upper[i], j=str_upper[j])
  printf()

# find possible points totals for 2 matches scoring 0, 1, 3.
tots = set(x + y for (x, y) in subsets([0, 1, 3], size=2, select='R'))
printf("tots = {tots}")

# consider leagues with at least 5 teams
for n in irange(5, len(tots)):
  ss = list(solve(n))
  k = len(ss)
  printf("[{n} teams -> {k} solutions]")
  if k == 1:
    for x in ss:
      output(n, x)

      Solution: The results are: A vs C = 2-1; A vs F = 3-2; B vs D = 2-2; B vs E = 3-2; C vs F = 4-3; D vs E = 3-3.

      The points are:

      A = 6 points (2 wins)
      B = 4 points (1 win + 1 draw)
      C = 3 points (1 win)
      D = 2 points (2 draws)
      E = 1 point (1 draw)
      F = 0 points

      With 5 teams there are 3 possible sets of matches, so this does not provide a solution:

      A vs C = 1-0; A vs E = 3-2; B vs D = 1-1; B vs E = 3-2; C vs D = 4-3;
      A vs C = 2-1; A vs D = 4-3; B vs D = 3-3; B vs E = 3-2; C vs E = 5-4
      A vs D = 1-0; A vs E = 2-1; B vs C = 0-0; B vs E = 3-2; C vs D = 3-3

      Like

  • Unknown's avatar

    Jim Randell 6:36 am on 16 March 2025 Permalink | Reply
    Tags:   

    Teaser 3260: Alphabet soup 

    From The Sunday Times, 16th March 2025 [link] [link]

    Clark had four dice with each of the 24 faces containing a different letter of the alphabet. Up to four could be rotated then placed side by side to spell out words on the topmost faces. Clark could spell out any of the words in just one of the following sayings:

    “Don’t rock the boat”
    “Easy come, easy go”
    “Give a dog a bad name”
    “If the cap fits wear it”
    “Life is what you make it”
    “Make love not war”
    “You reap what you sow”
    “If you can’t beat them join them”
    “Don’t bury your head in the sand”
    “Time and tide wait for no man”

    It was impossible to have any arrangement of 24 letters that could spell the words in this saying but also spell the words in one of the others.

    Which saying was Clark able to spell out?

    [teaser3260]

     
    • Jim Randell's avatar

      Jim Randell 7:07 am on 16 March 2025 Permalink | Reply

      See also: Enigma 687, Teaser 2780, Enigma 1605.

      I adapted the code I wrote for Enigma 687 to solve this puzzle. (Allowing words of different lengths, but not allowing symbols to appear on more than one die).

      I have removed repeated words from the phrases, and also words that are included in other words. Note that each phrase consists of valid words (no repeated letters, no more than 4 letters), and also each phrase has at least one maximal length word.

      This Python 3 program runs in 146ms. (Internal runtime is 72ms).

      from enigma import (
  irange, subsets, seq_ordered as ordered, peek, uniq, append, remove, join, printf
)

# phrases to check
phrases = list(set(x.split()) for x in [
  "DONT ROCK THE BOAT",
  "EASY COME GO",  # "EASY COME EASY GO",
  "GIVE DOG BAD NAME",  # "GIVE A DOG A BAD NAME"
  "THE CAP FITS WEAR",  # "IF THE CAP FITS WEAR IT"
  "LIFE IS WHAT YOU MAKE IT",
  "MAKE LOVE NOT WAR",
  "YOU REAP WHAT SOW",  # "YOU REAP WHAT YOU SOW"
  "IF YOU CANT BEAT THEM JOIN",  # "IF YOU CANT BEAT THEM JOIN THEM"
  "DONT BURY YOUR HEAD IN THE SAND",
  "TIME AND TIDE WAIT FOR NO MAN",
])

# merge symbols <ss> into dice <ds>; max <k> symbols per die
def merge(ds, ss, k):
  rs = list(ds)
  for (i, (d, s)) in enumerate(zip(ds, ss)):
    if s in d or s == '?':
      pass
    elif len(d) < k and not any(s in r for r in rs):
      rs[i] = append(d, s)
    else:
      return
  return rs

# construct dice <ds> for words <ws>; max <k> symbols per die
def construct(ws, ds, n, k):
  # are we done?
  if not ws:
    yield ordered(ordered(d) for d in ds)
  else:
    # choose the next word, and pad to required length
    w = peek(ws)
    w_ = w + '?' * (n - len(w))
    # consider all anagrams of the word
    for ss in subsets(w_, size=len, select='mP'):
      ds_ = merge(ds, ss, k)
      if ds_:
        yield from construct(remove(ws, w), ds_, n, k)

# find sets of <n> <k>-sided dice to display <words>
def solve(words, n, k):
  ds = list(set() for _ in irange(n))
  # start with a maximal word
  w = peek(w for w in words if len(w) == n)
  for (i, x) in enumerate(w):
    ds[i].add(x)
  # solve for the remaining words
  return uniq(construct(remove(words, w), ds, n, k))

pfmt = lambda ws: join(ws, sep=' ', enc='"')  # format a phrase
dfmt = lambda ds: join(map(join, ds), sep=', ', enc="[]")  # format a set of dice

# check phrase <ph> can only be made with a non-extendable set of dice
def check(ph, n=4, k=6):
  ds = None
  # make a set of <n> dice (<k> sided) for this phrase
  for ds in solve(ph, n, k):
    # can we extend the set to make any of the other phrases?
    ds1 = None
    for ph1 in phrases:
      if ph1 == ph: continue
      ds1 = peek(construct(ph1, ds, n, k), default=None)
      if ds1: break
    # can this set of dice be extended?
    if ds1:
      # output an extendable set
      printf("{ph} -> {ds}", ph=pfmt(ph), ds=dfmt(ds))
      printf("+ {ph1} -> {ds1}", ph1=pfmt(ph1), ds1=dfmt(ds1))
      printf()
      return
  # return a non-extendable set
  return ds

# choose one of the phrases
for ph in phrases:
  # check there are only non-extendable sets for this phrase
  ds = check(ph)
  if ds:
    printf("SOLUTION: {ph} -> {ds}", ph=pfmt(ph), ds=dfmt(ds))
    printf()

      Solution: The saying is: “Time and tide wait for no man”.

      For example the following set of dice can make the phrase (_ can be any letter):

      AEO___
      DFMW__
      INR___
      T_____

      But there is no way to fill out the unspecified letters such that any of the other phrases can be made. And this is true for all sets of 4 dice that can be used to spell out the phrase.

      We can see this in the example set because A and E and O are on the same die, which means we cannot make any of the following words:

      BEAT (AE)
      BOAT (AO)
      EASY (AE)
      HEAD (AE)
      MAKE (AE)
      NAME (AE)
      REAP (AE)
      WEAR (AE)

      And one of these words is included in each of the remaining phrases.

      In fact, there are 36 possible sets of partial dice that can be used to make “TIME AND TIDE WAIT FOR NO MAN“.

      All of them have A and E on the same die, so this eliminates all the other phrases apart from “DONT ROCK THE BOAT“.

      Of these 36 sets, 12 of them also have O on same die as A and E, so those eliminate BOAT also (as above).

      And the remaining 24 sets each have at least 2 letters of DONT on the same die, so these are not possible either.

      Like

      • Frits's avatar

        Frits 3:04 pm on 16 March 2025 Permalink | Reply

        @Jim, your latest code (with seq_ordered ) also has the runtime unpredicability issue with CPython. If you solve this please let me know how you did this.

        Like

        • Jim Randell's avatar

          Jim Randell 4:30 pm on 16 March 2025 Permalink | Reply

          In CPython3 if you ask for elements of a set() (for example) they could come out in any order. So the execution path the program takes may be different each time it is run. Sometimes it might hit upon a faster execution path, and sometimes a slower one.

          For a more reproducible execution path you can use PyPy (or in this case PyPy3).

          % repeat 5 python3.14 -c "from enigma import *; print(peek(set(str_upper)))"
G
T
I
Y
G
 
% repeat 5 python2.7 -c "from enigma import *; print(peek(set(str_upper)))"
A
A
A
A
A
 
% repeat 5 pypy -c "from enigma import *; print(peek(set(str_upper)))"
A
A
A
A
A

% repeat 5 pypy3 -c "from enigma import *; print(peek(set(str_upper)))"
A
A
A
A
A

          But if you set the environment variable PYTHONHASHSEED to a fixed integer value, then CPython3 will behave in a repeatable fashion:

          % repeat 5 PYTHONHASHSEED=42 python3.14 -c "from enigma import *; print(peek(set(str_upper)))"  
J
J
J
J
J

          Like

      • Jim Randell's avatar

        Jim Randell 11:15 am on 19 March 2025 Permalink | Reply

        Here is a faster solution that collects the dice as a map (instead of a collection of sequences), as each symbol can only appear on one die.

        It has an internal runtime of 4.8ms.

        from enigma import (irange, multiset, fail, intersect, subsets, peek, group, remove, update, join, printf)

# phrases to check
phrases = [
  "DONT ROCK THE BOAT",
  "EASY COME EASY GO",
  "GIVE A DOG A BAD NAME",
  "IF THE CAP FITS WEAR IT",
  "LIFE IS WHAT YOU MAKE IT",
  "MAKE LOVE NOT WAR",
  "YOU REAP WHAT YOU SOW",
  "IF YOU CANT BEAT THEM JOIN THEM",
  "DONT BURY YOUR HEAD IN THE SAND",
  "TIME AND TIDE WAIT FOR NO MAN",
]

# analyse the phrases
words = list()
for ph in phrases:
  ws = list()
  for w in sorted(ph.split(), key=len, reverse=1):
    w = join(w, sort=1)
    s = set(w)
    fail(len(s) != len(w), "repeated letters found")
    if any(s.issubset(x) for x in ws): continue
    ws.append(w)
  words.append(ws)

# complete dice (<d>, <r>) for words <ws>
# d = map of symbols to die index
# r = remaining count of symbols per die
def construct(ws, d, r):
  # are we done?
  if not ws:
    yield (d, r)
  else:
    # choose the next word (maximal intersection)
    w = max(ws, key=lambda w: len(intersect([w, d.keys()])))
    # find used dice, and unused symbols
    (ds, us) = (list(), list())
    for x in w:
      i = d.get(x)
      if i is None:
        us.append(x)
      else:
        ds.append(i)
    # no die can be used more than once
    if len(ds) != len(set(ds)): return
    # assign unused symbols to the remaining dice
    rs = list(i for (i, x) in r.items() if i not in ds)
    if len(rs) < len(us): return
    for ss in subsets(rs, size=len(us), select='P'):
      d_ = update(d, us, ss)
      r_ = r.difference(ss)
      # and solve for the remaining words
      yield from construct(remove(ws, w), d_, r_)

# find sets of <n> dice (<k>-sided) to display <ws>
def dice(ws, n, k):
  (d, r) = (dict(), multiset.from_seq(irange(n), count=k))
  # start with the first word
  w = ws[0]
  for (i, x) in enumerate(w):
    d[x] = i
    r.remove(i)
  # and add in the remaining words
  yield from construct(ws[1:], d, r)

# format a set of dice
def fmt(d):
  g = group(d.keys(), by=d.get)
  return join((join(g[k], sort=1) for k in sorted(g.keys())), sep=", ", enc="[]")

# collect phrases that can be extended
multiple = set()

# examine all sets for phrase <i>
def solve(i, n=4, k=6):
  if i in multiple: return

  # make a set of 4 dice (6-sided) for this phrase
  d = None
  for (d, r) in dice(words[i], n, k):
    # can we extend the dice to make any of the other phrases?
    for (j, ws1) in enumerate(words):
      if j == i: continue
      (d1, _) = peek(construct(ws1, d, r), default=(None, None))
      if d1:
        multiple.update((i, j))
        # output an extendable set
        printf("\"{ph}\" -> {d}", ph=phrases[i], d=fmt(d))
        printf("+ \"{ph}\" -> {d1}", ph=phrases[j], d1=fmt(d1))
        printf()
        return
  # return an example non-extendable set
  return d

# consider each phrase
for (i, ph) in enumerate(phrases):
  d = solve(i)
  if d:
    printf("SOLUTION = \"{ph}\" -> {d}", d=fmt(d))
    printf()

        Like

    • Frits's avatar

      Frits 2:40 pm on 16 March 2025 Permalink | Reply

      The runtime of this program varies. Normally this is caused by using sets but removing sets as much as possible hasn’t removed the unpredictability of run times.

      [program removed]

      Like

      • Frits's avatar

        Frits 4:36 pm on 16 March 2025 Permalink | Reply

        Luckily no word contains duplicate letters otherwise a fix is needed.

        Like

        • Jim Randell's avatar

          Jim Randell 4:38 pm on 16 March 2025 Permalink | Reply

          @Frits: A letter can only appear on one die, so it wouldn’t be possible to make a word with repeated letters.

          Like

    • Frits's avatar

      Frits 5:28 pm on 16 March 2025 Permalink | Reply

      Thanks. I may try it.

      I found the cause of the unpredictable behaviour in my code. If during the first sort (line 19) the data is sorted on both length and value then the behaviour is predictable again. I’ll send a new version tomorrow.

      Like

    • Frits's avatar

      Frits 8:48 am on 19 March 2025 Permalink | Reply 

      from itertools import combinations, permutations

sayings_orig = ["Don't rock the boat",
                "Easy come, easy go",
                "Give a dog a bad name",
                "If the cap fits wear it",
                "Life is what you make it",
                "Make love not war",
                "You reap what you sow",
                "If you can't beat them join them",
                "Don't bury your head in the sand",
                "Time and tide wait for no man"]
           
# convert to lowercase and remove non alphabetics
sayings = [[''.join(c for c in w if c.isalpha()) for w in s.lower().split()]
            for s in sayings_orig]
                                         
# remove words that are subsets of other words and
# sort sayings on length and preserve original index                 
sayings = list(enumerate(sorted([w1 for i, w1 in enumerate(s) 
    if all(not set(w1).issubset(set(w2)) or (set(w1) == set(w2) and i < j) 
          for j, w2 in enumerate(s) if i != j)], key=len, reverse=True) 
          for s in sayings)) 

# sort by number of 4-character words (descending)                                                            
sayings.sort(key = lambda x: -len([1 for y in x[1] if len(y) == 4]))                                 
ln = len(sayings)
      
# try to place all letters on the dice in <ss> for all words in <ws>
def solve(ws, ss=[]):
  if not ws:
    yield ss
  else:
    # try to add each letter of <w> to one of the 4 dice in <ss>
    if not ss: 
      ss = ["" for _ in range(4)]
      fn = combinations
      w = ws[0]    
      free_dice = range(4)  
    else:  
      fn = permutations 
      w = list(ws[0])
      free_dice = [n for n in range(4) if len(ss[n]) < 6] 
      removed = set()
      for ltr in ws[0]:
        for n in range(4):
          # letter <ltr> already on a die?
          if ltr in ss[n]:
            if n in removed: return # two letters of current word on same die
            if n in free_dice:
              # credit: B. Gladman
              free_dice.remove(n)
              removed.add(n)
            w.remove(ltr)
            break
     
    # assign all unassigned letters to the available dice 
    for p in fn(free_dice, len(w)):
      ss_ = ss.copy()
      for i, n in enumerate(p):
        ss_[n] += w[i]
      yield from solve(ws[1:], ss_)
        
sols, processed = set(range(ln)), set()     
  
# for all sayings    
for i in range(ln):    
  # skip if this saying is not the solution
  if (i_o := sayings[i][0]) not in sols: continue
  processed.add(i)
  for dice1 in solve(sayings[i][1]):
    # try to combine other sayings with these dice
    for j in range(ln):
      if j == i: continue
      # skip if saying <j> has been fully processed
      if (j_o := sayings[j][0]) in sols and j in processed: continue
      # skip if both sayings are not the solution
      if i_o not in sols and j_o not in sols: continue
      
      for dice2 in solve(sayings[j][1], dice1):
        print(f"with dice {[''.join(sorted(x)) for x in dice2]} "
              f"the following sayings can be constructed:")
        print("--", sayings_orig[i_o])
        print("--", sayings_orig[j_o], "\n")
        sols -= {i_o, j_o}
        break # finding one example is enough to remove <j_o> from <sols>
      else: # no break
        continue
      break  
    else: # no break
      continue
    break    
          
print(f"answer(s): '{' or '.join(sayings_orig[s] for s in sols)}'")

      Like

  • Unknown's avatar

    Jim Randell 7:29 am on 14 March 2025 Permalink | Reply
    Tags:   

    Teaser 2568: Ending 2011 

    From The Sunday Times, 11th December 2011 [link] [link]

    I have written down three positive whole numbers consisting of two primes and a perfect square. Between them they use nine digits and no digit is repeated.

    If you form an addition sum with the three numbers, then what do you end up with as the total? Appropriately enough you end up with 2011.

    What, in increasing order, are the three numbers?

    [teaser2568]

     
    • Jim Randell's avatar

      Jim Randell 7:30 am on 14 March 2025 Permalink | Reply

      This Python program looks at possible squares (without repeated digits), and then checks to see if the remainder can be made from the sum of two primes.

      The year to be made can be specified on the command line.

      It runs in 62ms. (Internal runtime is 3.4ms).

      from enigma import (powers, inf, primes, distinct_chars, arg, printf)

# total to find
N = arg(2011, 0, int)

# consider possible squares
for s in powers(1, inf, 2):
  r = N - s
  if r < 5: break
  if distinct_chars(s) is None: continue

  # look for pairs of primes that sum to r
  for p in primes.between(2, r // 2):
    q = r - p
    # q is also a prime
    if q not in primes: continue
    # check for 9 different digits
    if distinct_chars(p, q, s) != 9: continue
    # output solution
    printf("{ns} -> {N} [primes = {p}, {q}; square = {s}]", ns=sorted([p, q, s]))

      Solution: The numbers are: 263, 841, 907.

      263 and 907 are prime, and 841 = 29^2.

      We could be a bit cleverer with finding pairs of primes that sum to r. For instance, if r is odd, then one of the primes would have to be 2. But it makes the code a bit longer, and the version above is already fast enough, so I haven’t included it.

      Like

    • Frits's avatar

      Frits 5:05 am on 15 March 2025 Permalink | Reply

      Designed for a low internal run time.

      from itertools import compress

# total to find
N = 2011

# 2 < primes < n 
def primesbelow(n):
  # rwh_primes1v2(n):
  """ Returns a list of 2 < primes < n for n > 2 """
  sieve = bytearray([True]) * (n // 2 + 1)
  for i in range(1, int(n ** 0.5) // 2 + 1):
    if sieve[i]:
      sieve[2 * i * (i + 1)::2 * i + 1] = \
      bytearray((n // 2 - 2 * i * (i + 1)) // (2 * i + 1) + 1)
  return {*compress(range(3, n, 2), sieve[1:])}

P = primesbelow(1885)  # max prime is 2011 - 23 - 104

# split number <n> in two different odd prime endings, unequal to <o>
split = lambda n, o: [(i, i2) for i in range(1, 11, 2) 
                     if (i2 := (10 + n - i) % 10) > i and
                     {i, i2}.isdisjoint([5, o])]

# odd prime number endings per odd square number ending
pes = {se: split(11 - se, se) for se in [1, 5, 9] for i in range(1, 10, 2)}
pes = {k: {x for v in vs for x in v} for k, vs in pes.items()}

# all three numbers must be odd as 2 + abcd + efgh > 4000

# consider odd possible squares (with at least 2 digits)
for n in range(5, 45, 2):
  r = N - (sq := n * n)
  # square ending must allow for valid prime endings
  if not (se := pes[sq % 10]): continue
  if len(set(s := str(sq))) != len(s): continue
  
  # look for pairs of odd primes that sum to r 
  for p in sorted(P):
    # a 2-digit square requires a prime of 1xxx
    if '1' in s and len(s) == 2: break
    if p > r // 2: break
    # valid prime number ending
    if (p % 10) not in se: continue

    q = r - p
    # q is also a prime, no repeated digits
    if q not in P: continue
    if len(set(s1 := s + str(p) + str(q))) == len(s1) == 9: 
      # output solution
      print("answer:", sorted([sq, p, q]))

      Like

    • ruudvanderham's avatar

      ruudvanderham 11:31 am on 15 March 2025 Permalink | Reply 

      import istr

primes = [n for n in istr(range(100, 1000)) if n.is_prime() and n.all_distinct()]
squares = [n * n for n in istr(range(10, 32)) if (n * n).all_distinct()]

for (n1, n2), n3 in istr.product(istr.combinations(primes, r=2), squares):
    if (n1 | n2 | n3).all_distinct() and n1 + n2 + n3 == 2011:
        print(sorted((n1, n2, n3)))

      Like

      • Jim Randell's avatar

        Jim Randell 5:01 pm on 15 March 2025 Permalink | Reply

        @Ruud: Note that it is not specified that the three numbers are all 3-digit numbers (although it turns out that the numbers in the solution are).

        But if the puzzle had been set in 1990, the solution would not be three 3-digit numbers:

        % python3 teaser2568.py 1990
[59, 324, 1607] -> 1990 [primes = 59, 1607; square = 324]

        Like

        • Ruud's avatar

          Ruud 5:13 pm on 15 March 2025 Permalink | Reply

          @Jim
          You are right. I had misread the problem description.
          The code below does not assume that the numbers have three digits.

          import istr

primes = [n for n in istr(range(1, 2011)) if n.is_prime() and n.all_distinct()]
squares = [n * n for n in istr(range(1, 45)) if (n * n).all_distinct()]

for (n1, n2), n3 in istr.product(istr.combinations(primes, r=2), squares):
    if (n1 | n2 | n3).all_distinct() and n1 + n2 + n3 == 2011:
        print(sorted((n1, n2, n3)))

          Like

          • Frits's avatar

            Frits 2:53 am on 16 March 2025 Permalink | Reply

            @Ruud, you would have reported three solutions for year 1990 .

            “Between them they use nine digits” means exactly nine digits.

            Like

    • Frits's avatar

      Frits 4:21 am on 16 March 2025 Permalink | Reply

      712 is the first year that there is a solution.
      Up to year 2011 there are 454 solutions.
      The program runs in 163ms but is not valid for years a little higher than 2011.

      from itertools import compress

# 2 < primes < n 
def primesbelow(n):
  # rwh_primes1v2(n):
  """ Returns a list of 2 < primes < n for n > 2 """
  sieve = bytearray([True]) * (n // 2 + 1)
  for i in range(1, int(n ** 0.5) // 2 + 1):
    if sieve[i]:
      sieve[2 * i * (i + 1)::2 * i + 1] = \
      bytearray((n // 2 - 2 * i * (i + 1)) // (2 * i + 1) + 1)
  return {*compress(range(3, n, 2), sieve[1:])}

M = 2011
# max prime is N - 23 - 104
P = {p for p in primesbelow(M - 126) if len(set(s := str(p))) == len(s)}
P2 = sorted(p for p in P if p < 100)
P3 = sorted(p for p in P if 100 <= p < 1000)

c = 0
for N in range(1, M + 1):
  # consider possible squares (with at least 2 digits)
  for n in range(4 + (N % 2), int(N**.5) + 1, 2):
    r = N - (sq := n * n)
    if r < 120: break # at least a 2-digit and a 3-digit prime 
    if len(set(s := str(sq))) != (ln := len(s)): continue
    
    # determine which primes to use
    # consider the number of digits in the square number
    # 2 : p + q = 7 so 3 and 4
    # 3 : p + q = 6 so 2 and 4  or  3 and 3
    # 4 : p + q = 5 so 2 and 3
    plst = []
    if ln != 2:
      # add list of 2-digit primes
      plst.append([] if '1' in s and ln == 3 else P2)
    if ln != 4:    
      # add list of 3-digit primes
      plst.append([p for p in P3 if r - p < 1000] if ln == 3 else 
                  [] if '1' in s else P3)
    
    for prms in plst:   
      # look for pairs of primes that sum to r
      for p in prms: 
        q = r - p
        if q < p: break
        # q is also a prime, no repeated digits
        if q not in P: continue
        # between them they use nine digits
        if len(set(s1 := s + str(p) + str(q))) == len(s1) == 9: 
          c += 1
          # output solution
          print(c, f"{N = }", "answer:", sorted([sq, p, q]))

      Like

  • Unknown's avatar

    Jim Randell 10:23 am on 11 March 2025 Permalink | Reply
    Tags:   

    Teaser 2556: Dotty squares 

    From The Sunday Times, 18th September 2011 [link] [link]

    On a piece of paper I have drawn a neat, evenly spaced square array of 36 dots, namely six rows of six.

    If I were to ask you how many squares are formed, you might say just 25, for the array seems to consist of 25 little squares. However, lots of sets of four of the dots form the vertices of a square.

    How many ways are there of choosing four of the dots so that they form the vertices of a square?

    [teaser2556]

     
    • Jim Randell's avatar

      Jim Randell 10:25 am on 11 March 2025 Permalink | Reply

      See: Enigma 1723.

      The number of possible squares on an n × n grid of dots is given by:

      S(n) = n²(n² − 1)/12

      See: OEIS A002415.

      So, with a 6×6 grid of dots:

      S(6) = 36 × 35 / 12 = 105

      Solution: There are 105 sets of 4 points that will make a square.

      Here is a constructive program using some routines from the enigma.py library.

      It runs the N=6 case in 74ms. (Internal runtime is 5.6ms).

      from enigma import (irange, subsets, line_bisect, rdiv, arg, printf)

# number of dots on each side of the square
N = arg(6, 0, int)

# co-ordinates of the dots [0 .. N-1]
dots = sorted(subsets(irange(N), size=2, select='M'))

# choose 2 of the dots (will be ordered)
n = 0
for (a, b) in subsets(dots, size=2):
  # find the vertices of the other diagonal
  (c, d) = sorted(line_bisect(a, b, div=rdiv))
  if not (c in dots and d in dots): continue
  # eliminate duplicates (otherwise each square will appear twice)
  if (c, d) < (a, b): continue
  # output square
  n += 1
  printf("[{n}: ({a}, {b}) -> ({c}, {d})]")

# output total
printf("N={N}: {n} squares")

      Like

  • Unknown's avatar

    Jim Randell 6:20 am on 9 March 2025 Permalink | Reply
    Tags:   

    Teaser 3259: Something to get your teeth into 

    From The Sunday Times, 9th March 2025 [link] [link]

    My bicycle has a set of three toothed rings (“chainrings”) attached to the pedal mechanism; I’d chosen these, with different numbers of teeth, from offered values of 30, 41, 45, 47, 58. Correspondingly, the rear wheel mechanism is attached to a set of five toothed rings (“sprockets”), each with no more than 20 teeth. A chain passes over one ring from each set, as selected by the gear controls; at any time the gear ratio is the number of teeth on the selected chainring divided by the number of teeth on the selected sprocket.

    There are exactly three pairs of chainring/sprocket combinations that give gear ratios whose difference equals one divided by a whole number more than 100.

    What are the numbers of teeth on the sprockets, in ascending order?

    [teaser3259]

     
    • Jim Randell's avatar

      Jim Randell 6:31 am on 9 March 2025 Permalink | Reply

      Here is a brute force solution.

      It runs in 1.7s.

      from enigma import (Rational, irange, subsets, cproduct, first, printf)

Q = Rational()

# check a collection of chainrings and sprockets
# for differences in ratios of 1/N where N > 100
def check(xs, ys):
  # find the gear ratios
  rs = list(Q(x, y) for (x, y) in cproduct([xs, ys]))
  # find differences that are 1/N
  for (a, b) in subsets(rs, size=2):
    d = abs(a - b)
    if d.numerator == 1 and d.denominator > 100:
      yield (a, b)

# check possible chainrings and sprockets
xss = subsets((30, 41, 45, 47, 58), size=3)  # 3 chainrings
yss = subsets(irange(5, 20), size=5)  # 5 sprockets
for (xs, ys) in cproduct([xss, yss]):
  # look for exactly 3 1/N differences
  ds = first(check(xs, ys), count=4)
  if len(ds) == 3:
    printf("chainrings = {xs}, sprockets = {ys}")

      Solution: The teeth on the sprockets are: 12, 13, 14, 16, 17.

      And the teeth on the chainring are: 41, 47, 58.

      And the three gear combinations are:

      58/16 − 47/13 = 1/104
      47/16 − 41/14 = 1/112
      41/12 − 58/17 = 1/204

      There are 6 pairs of gear ratios that give the required 1/N values (and they all give different values for N):

      58/16 − 47/13 = 1/104
      41/10 − 45/11 = 1/110
      47/16 − 41/14 = 1/112
      58/18 − 45/14 = 1/126
      41/15 − 30/11 = 1/165
      41/12 − 58/17 = 1/204

      But the only set of 3 N values that gives ≤ 3 numerators and ≤ 5 denominators is: 104, 112, 204, and this set gives exactly 3 numerators and exactly 5 denominators, so the set of cogs is fully determined.

      Like

      • Jim Randell's avatar

        Jim Randell 9:25 am on 9 March 2025 Permalink | Reply

        Here is a much faster approach. It looks for possible 1/N differences (with N > 100), and then assembles possible collections of chainrings and sprockets from 3 of the differences. This gives candidate sets of cogs, and fortunately there is only one that does not exceed the required numbers of chainrings and sprockets).

        It runs in 68ms. (Internal runtime is 4.7ms).

        from enigma import (
  irange, cproduct, subsets, fraction, ordered, flatten, unzip, diff, printf
)

# possible cogs
ns = [30, 41, 45, 47, 58]
ds = list(irange(5, 20))

# find pairs with a difference that is 1/N, N > 100
pairs = list()
for ((a, b), (c, d)) in subsets(cproduct([ns, ds]), size=2):
  (p, q) = fraction(abs(a * d - b * c), b * d)
  if p == 1 and q > 100:
    pairs.append(ordered((a, b), (c, d)))
    printf("[abs({a}/{b} - {c}/{d}) -> {p}/{q}]")

# check if pair <p> can be formed from <ns> and <ds>
check = lambda p, ns, ds: all(n in ns and d in ds for (n, d) in p)

# now choose 3 pairs
for ps in subsets(pairs, size=3):
  # collect the numerators (chainrings) and denominators (sprockets)
  (cs, ss) = (sorted(set(s)) for s in unzip(flatten(ps)))
  # there are only 3 different chainrings, and 5 different sprockets
  if len(cs) > 3 or len(ss) > 5: continue

  # check no additional pairs can be formed
  if any(check(p, cs, ss) for p in diff(pairs, ps)): continue

  # output candidate solutions
  printf("chainrings = {cs}, sprockets = {ss}")
  printf("-> pairs = {ps}")

        Potentially the program could produce incomplete candidate sets of cogs. However, it turns out that only a single candidate solution is produced, and it is complete, so it doesn’t seem worth adding the code that completes set of cogs (which would be added at line 26), as it wouldn’t get called.

        Like

  • Unknown's avatar

    Jim Randell 9:35 am on 4 March 2025 Permalink | Reply
    Tags:   

    Teaser 2446: [Shuffling cards] 

    From The Sunday Times, 9th August 2009 [link]

    Old Professor Shufflebottom buys a fresh pack of 52 standard playing cards. He has studied various shuffles and knows that, for any shuffle or rearrangement, if he repeatedly performs it, the cards will eventually be returned to their original order. Of the astronomical number of different shuffles possible (1, 2, 3, …, 52), he chooses one requiring the greatest number of repeated shuffles to return the cards to their original order.

    How many times must that shuffle be done before the cards are returned to their original order?

    This puzzle was originally published with no title.

    [teaser2446]

     
    • Jim Randell's avatar

      Jim Randell 9:36 am on 4 March 2025 Permalink | Reply

      By “shuffle” I think we are meant to assume a mathematical permutation of the sequence of 52 cards. (i.e. each time a shuffle is applied to a deck of 52 cards, the top card always ends up in the same position in the shuffled deck, as does the second card, and so on). (See: [ @wikipedia ]

      Maybe it could have read:

      Professor Shufflebottom has devised a machine that shuffles a standard pack of 52 playing cards.

      The machine is configured by setting 52 dials. Each is set with a different number from 1 to 52. The first dial controls the position that the top card in the starting pack will appear in the shuffled pack. The second dial dial controls the position the second card will appear in the shuffled pack, and so on, until all 52 dials are set.

      Professor Shufflebottom sets the dials such that the number of repeated shuffles to return the cards to their original order is as large as possible.

      What is that number of repeated shuffles?

      So the shuffle can be described as a permutation on 52-sequences.

      Any permutation can be broken down into a combination of disjoint cycles, and then the order of the permutation (which is the number of times it needs to be applied for all elements to return to their original positions) is the lowest common multiple of the lengths of the cycles.

      So we need a number of cycles, with a total length of 52, from which we can calculate the order of a permutation consisting of cycles of those lengths. And we are looking for the cycle lengths which give a maximal order.

      The following Python program runs in 631ms (using PyPy).

      from enigma import (Accumulator, irange, decompose, mlcm, arg, printf)

N = arg(52, 0, int)
printf("[N = {N}]")

# find maximal orders
r = Accumulator(fn=max, collect=1)

# consider decompositions into 1 .. N tuples
for k in irange(1, N):
  for ns in decompose(N, k, increasing=1, sep=0, min_v=1):
    # calculate the order
    m = mlcm(*ns)
    r.accumulate_data(m, ns)

printf("max order = {r.value} [from {r.count} decompositions]")
for ns in r.data:
  printf("  cycles = {ns}")

      Solution: The shuffle must be done 180180 times.

      Possible cycle lengths are:

      (3, 4, 5, 7, 9, 11, 13) → sum = 52; lcm = 180180
      (1, 2, 4, 5, 7, 9, 11, 13) → sum = 52; lcm = 180180
      (1, 1, 1, 4, 5, 7, 9, 11, 13) → sum = 52; lcm = 180180

      See also: OEIS A000793.

      Like

      • Jim Randell's avatar

        Jim Randell 9:28 am on 7 March 2025 Permalink | Reply

        Here is a solution that finds the maximal order, without examining all possible decompositions, and allows much larger numbers to be determined.

        It is based on the code given in the OEIS entry, and uses the fact that a maximal decomposition can be constructed that consists of powers of primes, or 1.

        It has an internal runtime of 138µs.

        from enigma import (primes, irange, arg, printf)

N = arg(52, 0, int)
printf("[N = {N}]")

# compute terms 0 .. n of the landau function
def landau(n):
  n += 1
  g = [1] * (n + 1)
  for p in primes.between(2, n):
    for j in irange(n, p, step=-1):
      (v, pp) = (g[j], p)
      while pp < j:
        v = max((pp if j == pp else g[j - pp] * pp), v)
        pp *= p
      g[j] = v
  g.pop(0)
  return g

g = landau(N)
#printf("g[0..{N}] = {g}")
printf("max order = {r}", r=g[N])

        Like

  • Unknown's avatar

    Jim Randell 1:03 am on 2 March 2025 Permalink | Reply
    Tags:   

    Teaser 3258: On grid 

    From The Sunday Times, 2nd March 2025 [link] [link]

    Using all the digits 1 to 9 in a 3 by 3 grid, I have devised a game. In this grid, if each of the three rows, three columns and two diagonals are read both forwards and backwards, there are 16 three-digit numbers.

    Points are awarded to each of these three-digit numbers; with 1 point awarded if it’s a prime number, 3 points if it’s a perfect square, 6 points if a perfect cube; with the points being cumulative if more than one applies.

    What is the highest number of points that can be awarded?

    [teaser3258]

     
    • Jim Randell's avatar

      Jim Randell 1:27 am on 2 March 2025 Permalink | Reply

      Here’s a brute force solution.

      It runs in 177ms (using PyPy).

      from enigma import (
  defaultdict, Accumulator, primes, powers, nsplit, irange, subsets, rev, printf
)

# points for 3-digit primes, squares, cubes
cats = [
  (primes.between(100, 999), 1),  # prime -> +1
  (powers(10, 31, 2), 3),  # square -> +3
  (powers(5, 9, 3), 6),  # cube -> +6
]
# collect points for 3-digit sequences, in both directions
pts = defaultdict(int)
for (ns, p) in cats:
  for n in ns:
    ds = nsplit(n)
    if len(set(ds)) < len(ds): continue
    pts[ds] += p
    pts[rev(ds)] += p

# find maximal grids
r = Accumulator(fn=max, collect=1)
for ss in subsets(irange(1, 9), size=len, select='P'):
  (A, B, C, D, E, F, G, H, I) = ss
  # eliminate repeated solutions
  if not (A < C and A < G and A < I and B < D): continue
  # score this grid
  p = sum(pts.get(k, 0) for k in [
    (A, B, C), (D, E, F), (G, H, I),  # rows
    (A, D, G), (B, E, H), (C, F, I),  # columns
    (A, E, I), (C, E, G),  # diagonals
  ])
  r.accumulate_data(p, ss)

# output solution(s)
printf("max points = {r.value} [from {r.count} grids]")
for (A, B, C, D, E, F, G, H, I) in r.data:
  printf("-> [ {A} {B} {C} | {D} {E} {F} | {G} {H} {I} ]")

      Solution: The maximum possible points total is: 27.

      Here is a grid that scores 27:

      The scoring numbers are:

      137 is prime → +1
      169 = 13^2 → +3
      961 = 31^2 → +3
      324 = 18^2 → +3
      587 is prime → +1
      125 = 5^3 → +6
      521 is prime → +1
      729 = 27^2 = 9^3 → +9
      total = 27

      As the numbers are read in both directions this grid can be rotated and reflected to give 7 additional grids using the same numbers.

      These can be seen by removing the check at line 25 from the program.

      Like

    • Frits's avatar

      Frits 1:22 pm on 2 March 2025 Permalink | Reply 

      from enigma import SubstitutedExpression
from itertools import permutations

# determine valid primes 123 - 987
P = {3, 5, 7}
P |= {n for n in range(11, 100, 2) if all(n % p for p in P)}
P = {n for n in range(123, 988, 2) if all(n % p for p in P) and
     len(set(str(n))) == 3}
     
sqs = {sq for n in range(10, 32) if len(set(str(sq := n * n))) == 3}
cbs = {cb for n in range(5, 10) if len(set(str(cb := n * n * n))) == 3}

# make dictionary of points per number
d = {(n := int(''.join(p))): 1 
     if n in P else 3 if n in sqs else 6 if n in cbs else 0 
     for p in permutations("123456789", 3)}
     
# check numbers both square and cube        
for c in cbs:
  if c in sqs:
    d[c] = 9  

# return points for number <n>
pts = lambda n: d[n]
    
rows = "ABC DEF GHI".split()
cols = list(''.join(x) for x in zip(*rows))
diags = ["AEI", "CEG"]
vars = rows + cols + diags
vars += [v[::-1] for v in vars]
ans = ' + '.join(f"pts({v})" for v in vars)

exprs = []
# avoid rotations, reflections etc
exprs.append("A < C")  
exprs.append("A < G")   
exprs.append("A < I")  
exprs.append("B < D") 
# calculate one of the variables
exprs.append("45 - (A + B + C + D + E + F + G + I) = H") 
  
# the alphametic puzzle
p = SubstitutedExpression(
  exprs,
  answer="@ans, (ABC, DEF, GHI)",
  macro=dict([("ans", ans)]),
  d2i=dict([(1, "CDGI")] +
           [(k, "A") for k in range(7, 9)] +
           [(9, "AB")]),
  env=dict(pts=pts),
  digits=range(1, 10),
  verbose=0,    # use 256 to see the generated code
) 

mx, sols = 0, []
# collect answers
for t, m in sorted(p.answers(), reverse=True):
  if mx and t != mx: break
  sols.append(m)
  mx = t
  
print("answer:", mx)
print()
print("Example(s):")
# print examples
for s in sols:
  print()
  print('\n'.join(str(x) for x in s))

      Like

    • Ruud's avatar

      Ruud 7:41 pm on 2 March 2025 Permalink | Reply

      Even more brute force:

      import istr


def is_square(n):
    square_root = int(n) ** (1.0 / 2.0)
    return round(square_root) ** 2 == n


def is_cube(n):
    cube_root = int(n) ** (1.0 / 3.0)
    return round(cube_root) ** 3 == n


max_score = 0

for a, b, c, d, e, f, g, h, i in istr.permutations(istr.digits("1-9")):
    total = 0
    for n in (a | b | c, d | e | f, g | h | i, a | d | g, b | e | h, c | f | i, a | e | i, c | e | g):
        for m in n, n[::-1]:
            total += m.is_prime() + 3 * is_square(m) + 6 * is_cube(m)
    max_score = max(max_score, total)

print(max_score)

      Liked by 1 person

    • Frits's avatar

      Frits 6:11 am on 4 March 2025 Permalink | Reply

      Using Jim’s trick of also storing the points of the reversed entry.

      from itertools import permutations

# determine valid primes 123 - 987
P = {3, 5, 7}
P |= {n for n in range(11, 100, 2) if all(n % p for p in P)}
P = {str(n) for n in range(123, 988, 2) if all(n % p for p in P)}
     
sqs = {str(n * n) for n in range(10, 32)}
cbs = {str(n * n * n) for n in range(5, 10)}

# make dictionary of points per three-digits tuple
d = {tuple(int(x) for x in p): 1 
     if (s := ''.join(p)) in P else 3 if s in sqs else 6 if s in cbs else 0 
     for p in permutations("123456789", 3)}
          
# check numbers both square and cube        
for c in cbs:
  if c in sqs:
    d[tuple(int(x) for x in c)] =  9  
    
# let every entry also contain the points of the reversed entry 
d = {k: v + d[k[::-1]] for k, v in d.items()}

# return points for sequence of three digits <s>
pts = lambda s: d[s]

alldgts = set(range(1, 10))
sols, mx = [], 0

# A B C
# D E F
# G H I
    
for A in range(1, 7):
  # eliminate repeated solutions
  for C, G, I in permutations(range(A + 1, 10), 3):
    r5 = alldgts - {A, C, G, I}
    for B in r5 - {9}:  # B < D
      r4 = r5 - {B}
      p4 = pts((A, B, C))
      for D in [x for x in r4 if x > B]:
        p3 = p4 + pts((A, D, G))
        for E, F, H in permutations(r4 - {D}):
          p0 = (p3 + pts((D, E, F)) + pts((G, H, I)) + pts((B, E, H)) + 
                     pts((C, F, I)) + pts((A, E, I)) + pts((C, E, G))) 
          if p0 >= mx:
            if p0 > mx:
              sols = []
              mx = p0
            sols.append([(A, B, C), (D, E, F), (G, H, I)])
          
print("answer:", mx)
print()
print("Example(s):")
# print examples
for s in sols:
  print()
  print('\n'.join(str(x) for x in s))

      Like

  • Unknown's avatar

    Jim Randell 5:07 pm on 26 February 2025 Permalink | Reply
    Tags:   

    Teaser 2548: Planetary line 

    From The Sunday Times, 24th July 2011 [link] [link]

    George and Martha are studying a far-off galaxy consisting of 10 planets circling a sun clockwise, all in the same plane. The planets are Unimus (taking one year to circle the sun), Dubious (two years), Tertius (three years), and so on up to Decimus (10 years).

    At one instant today the sun and all 10 planets were in one straight line. Martha said it will be ages before that happens again. “Don’t let’s be greedy,” said George. “How long must we wait until at least nine planets and the sun are in a straight line?”

    How long must they wait?

    In honour of the current planetary parade.

    [teaser2548]

     
    • Jim Randell's avatar

      Jim Randell 5:08 pm on 26 February 2025 Permalink | Reply

      Assuming the planets are in circular orbits, and they can be aligned on opposite sides of the sun.

      If we have a faster planet that makes a half orbit in period x, and a slower planet that makes a half orbit in period y, then, if they are initially in alignment, the time t taken for the fast planet to get one half orbit ahead of the slow planet is given by:

      t/x = t/y + 1
      ⇒
      t = x.y / |x − y|

      For for any collection of planets we can choose one of the planets, calculate the time taken for it to align with each of the other planets separately, and then calculate the LCM of these values to find the earliest time when they all align.

      This Python program runs in 68ms. (Internal runtime is 211µs).

      from enigma import (Rational, Accumulator, mlcm, mgcd, subsets, call, arg, printf)

Q = Rational()

# orbital periods of the planets
orbits = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

k = arg(9, 0, int)

# find the earliest (half-orbit) alignment of the planets <ss>
def align(ss):
  x = ss[0]
  qs = list(Q(x * y, 2 * abs(x - y)) for y in ss[1:])
  # calculate the LCM of the fractions
  n = call(mlcm, (q.numerator for q in qs))
  d = call(mgcd, (q.denominator for q in qs))
  return Q(n, d)

# find minimal times
r = Accumulator(fn=min, collect=1)

# consider k sized subsets
for ss in subsets(orbits, size=k):
  # calculate the alignment times for this set
  t = align(ss)
  printf("[{ss} -> {t} ({f})]", f=float(t))
  r.accumulate_data(t, ss)

# output solution
printf("min time = {r.value} ({f}) years", f=float(r.value))
for ss in r.data:
  printf("-> {ss}")

      Solution: 9 planets and the sun will align after 180 years.

      If all the planets start at an angle of 0°, then in 180 years we have the following alignment:

      Planet 1: 0°
      Planet 2: 0°
      Planet 3: 0°
      Planet 4: 0°
      Planet 5: 0°
      Planet 6: 0°
      Planet 7: 257.14°
      Planet 8: 180°
      Planet 9: 0°
      Planet 10: 0°

      We see that planets 1, 2, 3, 4, 5, 6, 9, 10 are in their original positions, and planet 8 is on the opposite side of the sun (but still in a straight line with the other planets). Planet 7 is the only one that is off the line.

      After 1260 years all the planets will have completed a whole number of half-orbits (all except 8 have returned to their original positions, but 8 is on the opposite side of the sun), and after 2520 years (= LCM of 1 .. 10) all the planets have returned to their original positions and the cycle will start again. The cycle of alignments is as follows:

      0, 2520 years = all planets at 0°
      180, 540, 900, 1620, 1980, 2340 years = planets 1, 2, 3, 4, 5, 6, 9, 10 at 0°; planet 8 at 180°; planet 7 out of alignment
      360, 720, 1080, 1440, 1800, 2160 years = planets 1, 2, 3, 4, 5, 6, 8, 9, 10 at 0°; planet 7 out of alignment
      420, 2100 years = planets 1, 2, 3, 4, 5, 6, 7, 10 at 0°; planet 8 at 180°; planet 9 out of alignment
      630, 1890 years = planets 1, 2, 3, 5, 6, 7, 9, 10 at 0°; planet 4 at 180°; planet 8 out of alignment
      840, 1680 years = planets 1, 2, 3, 4, 5, 6, 7, 8, 10 at 0°; planet 9 out of alignment

      But we can have alignments other than at 0°/180°:

      For example the earliest alignment of the 5 planets 1, 3, 5, 7, 9 is after 78.75 years:

      They are aligned along 90°/270°.

      Like

  • Unknown's avatar

    Jim Randell 9:49 am on 25 February 2025 Permalink | Reply
    Tags:   

    Teaser 2504: [Hidden crosses] 

    From The Sunday Times, 19th September 2010 [link] [link]

    Here are 18 black cards and there is a cross on the back of some of them.

    The clue in any gap indicates how many crosses there are on cards that are adjacent to that gap.

    How many black cards have a cross on them?

    This puzzle was originally published with no title.

    [teaser2504]

     
    • Jim Randell's avatar

      Jim Randell 9:50 am on 25 February 2025 Permalink | Reply

      Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      It runs in 80ms. (And the internal runtime of the generated program is just 53µs).

      #! python3 -m enigma -rr

SubstitutedExpression

#  +---+---+---+---+---+---+
#  | A |   | B |   | C |!=0|
#  +---+---+---+---+---+---+
#  | 1 | D | >2| E | <2| F |
#  +---+---+---+---+---+---+
#  | G |   | H |!=1| I |   |
#  +---+---+---+---+---+---+
#  |   | J |   | K | >1| L |
#  +---+---+---+---+---+---+
#  | M | >2| N |!=3| P |   |
#  +---+---+---+---+---+---+
#  |!=2| Q |   | R | =1| S |
#  +---+---+---+---+---+---+

--distinct=""
--digits="0,1"

# the clues
"C + F != 0"
"A + D + G = 1"
"B + D + E + H > 2"
"C + E + F + I < 2"
"E + H + I + K != 1"
"I + K + L + P > 1"
"J + M + N + Q > 2"
"K + N + P + R != 3"
"M + Q != 2"
"P + R + S = 1"

--answer="sum([A, B, C, D, E, F, G, H, I, J, K, L, M, N, P, Q, R, S])"
--template=""

      Solution: 10 of the black cards have a cross on them.

      There are 4 possible arrangements, that can be summarised as follows:

      8 of the crosses are marked X, and the remaining 2 crosses appear in squares marked a and b.

      Like

    • ruudvanderham's avatar

      ruudvanderham 12:26 pm on 1 March 2025 Permalink | Reply 

      import itertools


def s(*args):
    return sum(a[arg] for arg in args)


for a in itertools.product((0, 1), repeat=18):
    if (
        s(2, 5) != 0
        and s(0, 3, 6) == 1
        and s(1, 3, 4, 7) > 2
        and s(2, 4, 5, 8) < 2
        and s(4, 7, 8, 10) != 1
        and s(8, 10, 11, 14) > 1
        and s(9, 12, 13, 15) > 2
        and s(10, 13, 14, 16) != 3
        and s(12, 15) != 2
        and s(14, 16, 17) == 1
    ):
        print(a, sum(a))

      Like

  • Unknown's avatar

    Jim Randell 6:42 am on 23 February 2025 Permalink | Reply
    Tags:   

    Teaser 3257: Powers of deduction 

    From The Sunday Times, 23rd February 2025 [link] [link]

    One evening, Sherlock Holmes challenges Watson and Mycroft to a game of Cluedo.

    He places one each of the six “person” cards, six “weapon” cards and nine “room” cards into the murder bag, shuffles the rest and deals them out equally.

    Mycroft sees his cards and says, “If I guessed what was in the murder bag now, my chance of being correct is one in an integer that is a power greater than two”.

    “I’m saying nothing”. Watson replies. “I’d only give something away”.

    “Commendably prudent”, Sherlock says, “but the same is true for you”.

    Watson studies his cards, then looks agitated. “How could you know that?”

    “Sherlock isn’t cheating”. Mycroft reassures him. “He didn’t even know how many person cards you’re holding”.

    How many room cards is Mycroft holding?

    [teaser3257]

     
    • Jim Randell's avatar

      Jim Randell 8:14 am on 23 February 2025 Permalink | Reply

      After the culprit is selected there are 5 person, 5 weapon and 8 room cards remaining, and these are distributed among the 3 players (so, 6 cards each).

      If a player is holding p person cards, w weapon cards, and r room cards, then the probability of making a correct accusation from the cards he is not holding is:

      P = (1/(6 − p)) × (1/(6 − w)) × (1/(9 − r))
      1/P = (6 − p) × (6 − w) × (9 − r)

      This Python program finds possible (p, w, r) hands that have a 1/(n^k) chance of giving a correct guess, where k > 2.

      from enigma import (decompose, irange, inf, powers, first, lt, printf)

# there are only a few higher powers than squares to consider
(M, pows) = (6 * 6 * 9, set())
for k in irange(3, inf):
  ps = first(powers(2, inf, k), count=lt(M))
  if not ps: break
  pows.update(ps)

# find hands of 6 cards, with a 1/power chance of a correct guess
for (p, w, r) in decompose(6, 3, increasing=0, sep=0, min_v=0):
  if p > 5 or w > 5: continue
  N = (6 - p) * (6 - w) * (9 - r)
  if N not in pows: continue
  # output possible hands
  printf("p={p} w={w} r={r} -> N={N}")

      The only cards that give a required 1/power chance are:

      (p w r) = (3 3 0) = 1/81 (81 = 3^4)
      (p w r) = (1 1 4) = 1/125 (125 = 5^3)

      Mycroft declares he has one of these hands, and Sherlock declares Watson has one of these hands. It is not possible for there to be more than one (3 3 0) hand, but if there are a (3 3 0) and a (1 1 4) then the remaining hand is also a (1 1 4), and if there are two (1 1 4) hands then the remaining hand is a (3 3 0), and so Sherlock also has one of these hands.

      Hence the three hands are (1 1 4) (1 1 4) (3 3 0) (in some order). So when Mycroft declares he has one of these, Sherlock can see that he (Sherlock) also has one, and so Sherlock can declare that Watson must too have one of these hands.

      Which means Mycroft and Sherlock both know that each of them has one of these three hands, and if either of them has (3 3 0) they know the other two must both have (1 1 4).

      So Sherlock must be holding (1 1 4) (as Mycroft states that he does not know which of the possible hands Watson is holding), and the only way Mycroft can be certain that Sherlock has (1 1 4) is if he (Mycroft) is holding (3 3 0).

      And so: Mycroft = (3 3 0), Watson = (1 1 4), Sherlock = (1 1 4).

      Solution: Mycroft is holding no room cards.

      Like

      • Jim Randell's avatar

        Jim Randell 9:44 pm on 23 February 2025 Permalink | Reply

        I’ve not seen another solution to this puzzle yet, so here is a complete solution.

        The following Python program runs in 60ms. (Internal runtime is 476µs).

        from enigma import (
  namedtuple, decompose, irange, inf, powers, first, lt,
  subsets, filter_unique, unpack, intersect, seq2str, printf
)

# there are only a few higher powers than squares to consider
(M, pows) = (6 * 6 * 9, set())
for k in irange(3, inf):
  ps = first(powers(2, inf, k), count=lt(M))
  if not ps: break
  pows.update(ps)

# find hands of 6 cards, with a 1/power chance of a correct guess
Hand = namedtuple('Hand', 'p w r')
hs = list()
for (p, w, r) in decompose(6, 3, increasing=0, sep=0, min_v=0):
  if p > 5 or w > 5: continue
  N = (6 - p) * (6 - w) * (9 - r)
  if N not in pows: continue
  # output possible hands
  printf("[({p}, {w}, {r}) -> N={N}]")
  hs.append(Hand(p, w, r))

# collect possible scenarios
ss = list()
# M and W each have one of these hands
for (M, W) in subsets(hs, size=2, select='M'):
  # and S has the remaining cards
  S = Hand(5 - M.p - W.p, 5 - M.w - W.w, 8 - M.r - W.r)
  if S.p < 0 or S.w < 0 or S.r < 0: continue
  ss.append((M, W, S))

# find situations where S _cannot_ determine W.p
ss1 = filter_unique(ss, unpack(lambda M, W, S: S), unpack(lambda M, W, S: W.p)).non_unique

# find situations where M _can_ fully determine S's hand
ss2 = filter_unique(ss, unpack(lambda M, W, S: M), unpack(lambda M, W, S: S)).unique

# look for common situations
for (M, W, S) in intersect([ss1, ss2]):
  printf("M={M} W={W} S={S}", M=seq2str(M), W=seq2str(W), S=seq2str(S))

        Like

← Older posts

Newer posts →

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
Design a site like this with WordPress.com
Get started