S2T2 | Solving Sunday Times Teasers

Recent Updates Page 8 Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 10:08 am on 17 April 2025 Permalink | Reply
Tags: by: Andrew Skidmore ( 87 )
Teaser 2535: Eastertide
From The Sunday Times, 24th April 2011 [link] [link]

In the following division sum I have consistently replaced digits with letters, with different letters used for different digits. All three numbers featured are even:

EASTER ÷ TIDE = EGG

What is the numerical value of my TEASER?

[teaser2535]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 10:08 am on 17 April 2025 Permalink | Reply
  We can solve this puzzle using the [[ SubstitutedExpression ]] solver from the enigma.py library:
  
  The following command line executes in 83ms. (Internal runtime of the generated code is 5.6ms).
```
% python3 -m enigma SubstitutedExpression "EGG * TIDE = EASTER" --answer="TEASER"
(EGG * TIDE = EASTER) (TEASER)
(244 * 1062 = 259128) (125928) / A=5 D=6 E=2 G=4 I=0 R=8 S=9 T=1
TEASER = 125928 [1 solution]
```
  Solution: TEASER = 125928.
  
  LikeLike
Reply Cancel reply
Required fields are marked *

Name *

Email *

Website

Notify me of new comments via email.
Notify me of new posts via email.
Δ

Jim Randell 9:06 am on 15 April 2025 Permalink | Reply
Tags: by: W A Thatcher ( 13 )

Brain-Teaser 380: [Feeler gauges]

From The Sunday Times, 18th August 1968 [link]

“Feeler gauges”, says Bell at the pub, “are remarkably interesting things. You’ve all seen garage men use them — fingers of steel fastened together at one end and you can fan them out if you want. When you measure a space you find out which lot of fingers fits in. The thicknesses are marked in thous, that’s thousandths of an inch”.

“I’ve got a set of five gauges here which will measure any number up to 13 thous, always using either a single gauge or a touching set of them. You don’t need to use gauges which aren’t touching for a measurement like you do with the usual gauges. So mine’s better. I might patent it and make a packet”.

Clark examined it for few minutes and said “Not bad at all. I notice you could add an extra gauge in front and then your set would give all measurements up to 18 thous”.

How would the six gauges then read starting at the top?

This puzzle was originally published with no title.

[teaser380]

Jim Randell 9:08 am on 15 April 2025 Permalink | Reply

See also: Teaser 119, Teaser 560, Teaser 777, BrainTwister #61.

I reused the code to generate sparse rulers that I wrote for Teaser 119.

This Python 3 program runs in 81ms. (Internal runtime is 4.1ms).

from enigma import (irange, diff, append, tuples, csum, subsets, printf)

# generate sparse rulers
# L = length
# M = number of marks
# ms = existing marks (set)
# k = number of remaining marks
# xs = distances not yet satisfied (ordered list)
# zl = left zone
# zr = right zone
def rulers(L, M, ms, k, xs, zl, zr):
  if k == 0:
    if not xs:
      yield sorted(ms)
  else:
    # perform some early termination checks:
    # are there too many unsatisfied differences remaining?
    if xs and len(xs) > (k * (k - 1)) // 2 + k * (M - k): return
    # is max distance too big?
    if xs and xs[-1] > max(zr, L - zl): return
    # can we fit k marks in the gaps?
    if zr - zl + 1 < k: return

    # extend left zone?
    if not (zl > L - zr):
      # try with mark at zl
      ds = set(abs(m - zl) for m in ms)
      yield from rulers(L, M, append(ms, zl), k - 1, diff(xs, ds), zl + 1, zr)
      # try without mark at zl
      yield from rulers(L, M, ms, k, xs, zl + 1, zr)
    else:
      # try without mark at zr
      yield from rulers(L, M, ms, k, xs, zl, zr - 1)
      # try with mark at zr
      ds = set(abs(m - zr) for m in ms)
      yield from rulers(L, M, append(ms, zr), k - 1, diff(xs, ds), zl, zr - 1)

# generate rulers that can measure 1..N
sparse_rulers = lambda L, M, N: rulers(L, M, {0, L}, M - 2, diff(irange(1, N), [L]), 1, L - 1)

# consider possible sparse rulers with length L, to measure 1 - 13
for L in irange(13, 19):
  for ss in sparse_rulers(L, 6, 13):
    # calculate gauge thicknesses
    ts = list(b - a for (a, b) in tuples(ss, 2))

    # look for an additional gauge to make all thicknesses up to 18
    for x in irange(max(18 - L, 1), 17):
      ts_ = [x] + ts
      # calculate all measures
      ms_ = set(y - x for (x, y) in subsets(csum(ts_, empty=1), size=2))
      if ms_.issuperset(irange(1, 18)):
        # output solution
        printf("[1..13] = {ts} -> [1..18] = {ts_}")

Solution: The six gauges are: 14, 1, 3, 6, 2, 5.

Gauges [1, 3, 6, 2, 5] can be use to measure 1..13 (as well as 16, 17). It corresponds to a sparse ruler of length 17 with 6 marks.

Adding a gauge of 14 we get the set [14, 1, 3, 6, 2, 5], which can measure 1..18 (as well as 24, 26, 31). Which corresponds to a sparse ruler of length 31 with 7 marks.

Each of the gauges in the original 5-set has a different thickness, and there is another 5-set that would also work:

[1, 7, 3, 2, 4], which can measure 1..13 (as well as 16, 17).

But it cannot be extended to a 6-set that measures 1..18.

LikeLike

Frits 12:19 pm on 17 April 2025 Permalink | Reply

@Jim, you are allowing negative gauges in line 48.

LikeLike
- Jim Randell 2:39 pm on 17 April 2025 Permalink | Reply
  
  @Frits: Thanks. Fixed now.
  
  LikeLike

Frits 12:08 pm on 17 April 2025 Permalink | Reply

Assuming that the first five gauges are single digit.
Instead of “SubstitutedExpression” also “decompose” could have been used to find five numbers that add up to “L”.

from enigma import SubstitutedExpression
from itertools import combinations, accumulate

# can we make numbers 1 - <n> with sequence <s> using "touching" sets 
def check(s, n):
  # calculate all measures
  s_ = set(y - x for (x, y) in combinations(accumulate([0] + s), 2))
  return s_.issuperset(range(1, n + 1))

# the alphametic puzzle
p = SubstitutedExpression(
  [ # we have to make numbers 1 - 13 with a touching set of gauges A, B, C, D, E
    "A + B + C + D < 19",
    "12 < A + B + C + D + E < 20",  # Jim: 13 <= L <= 19
    "check([A, B, C, D, E], 13)",
    
    # we have to make numbers 1 - 18 with a touching set of gauges XY, A, B, C, D, E
    "XY < 18",                  # Jim: 18 - L <= XY <= 17
    "check([XY, A, B, C, D, E], 18)"
  ],
  answer="[XY, A, B, C, D, E]",
  d2i=dict([(0, "ABCDE")] +
           [(k, "X") for k in range(2, 10)]),
  distinct="",
  env=dict(check=check),
  reorder=0,
  verbose=0,    # use 256 to see the generated code
)

# print answers
for ans in p.answers():
  print(f"{ans}")

LikeLike

Frits 12:41 pm on 17 April 2025 Permalink | Reply

The decomposition version (without assuming single digits).

from itertools import combinations, accumulate

# can we make numbers 1 - <n> with sequence <s> using "touching" sets 
def check(s, n):
  # calculate all measures
  s_ = set(y - x for (x, y) in combinations(accumulate([0] + s), 2))
  return s_.issuperset(range(1, n + 1))
  
# decompose <t> into <k> numbers from <ns> so that sum(numbers) equals <t>
def decompose(t, k, ns, s=[]):
  if k == 1:
    if t in ns:
      yield s + [t]
  else:
    for n in ns:
      # <ns> must be a sorted list
      if n > t - (k - 1) * ns[0]: break
      yield from decompose(t - n, k - 1, ns, s + [n])

# consider possible sparse rulers with length L, to measure 1 - 13
for L in range(13, 20):
  # find five numbers that up to <L>
  for s in decompose(L, 5, range(1, L - 3)):
    # can we make numbers 1 - 13 with sequence <s> using "touching" sets
    if not check(s, 13): continue
    # look for an additional gauge to make all thicknesses up to 18
    for x in range(max(1, 18 - L), 18):
      # can we make numbers 1 - 18 using "touching" sets 
      if not check([x] + s, 18): continue
      # output solution
      print(f"[1..13] = {s} -> [1..18] = {[x] + s}")

LikeLike

Jim Randell 6:53 am on 13 April 2025 Permalink | Reply
Tags: by: Mark Valentine ( 17 )
Teaser 3264: Saving rum
From The Sunday Times, 13th April 2025 [link] [link]

Captain Noah was tired of spilling his rum at sea. His glass (twice the density of the rum) is a hollow cylinder with a solid flat base. The outer diameter is 72 mm. The glass thickness and base height are both 4 mm. After testing the stability of the upright glass, he instructed the steward to keep his glass topped up to one-third full, where it has the lowest centre of mass.

What is the overall height of the glass (including the base)?

[teaser3264]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 8:03 am on 13 April 2025 Permalink | Reply
  Here is a numerical solution, using the [[ find_min() ]] function from the enigma.py library.
  
  I treat the glass and rum system as 3 separate components:
  
  a hollow cylinder of glass, with external diameter 72 mm (external radius = 36 mm) and 4 mm thick walls (internal radius = 32 mm), and height h.
  
  a solid disc of glass, with diameter 72 mm (radius = 36 mm) and height 4 mm, that sits underneath the cylinder, on a flat table.
  
  a cylinder of rum with radius 32 mm, and height x (between 0 and h), that sits on the disc, inside the cylinder. The density of the rum is 1/2 that of the glass.
  
  The individual centres of mass of the three components are then combined to give the combined centre of mass. Each of them is somewhere on the central line of the cylinder, so we only need to worry about their heights above the table.
  
  For a given value of h we can calculate the value of x that gives the minimum height for the combined centre of mass, and then look for a value of h where h = 3x.
  
  This Python program runs in 69ms. (Internal runtime is 2.3ms).
```
from enigma import (sq, fdiv, find_min, find_value, printf)

# given height h find height of rum that gives the minimal centre of mass
def fn(h):

  # calculate centre of mass for rum height x
  def f(x):
    # mass of cylinder, base, rum (half the density)
    mc = (sq(36) - sq(32)) * h * 2
    mb = sq(36) * 4 * 2
    mr = x * sq(32)
    # heights of their respective centres of mass
    hc = 4 + h * 0.5
    hb = 2
    hr = 4 + x * 0.5
    # calculate height of combined centre of mass
    return fdiv(mc * hc + mb * hb + mr * hr, mc + mb + mr)

  # find minimal centre of mass = x
  r = find_min(f, 0, h)
  x = r.v
  # return h/x
  return fdiv(h, x)

# find when h/x = 3 (i.e. the minimal centre of mass is when the glass is 1/3 full)
r = find_value(fn, 3, 20, 200)
# output overall glass height (including base = 4 mm)
h = r.v + 4
printf("height = {h:.2f} mm")
```
  Solution: The glass is 112 mm high.
  
  So the internal height is 108 mm, and the lowest centre of mass occurs with 36 mm of rum in the glass.
  
  We can get an exact answer to the puzzle using analysis.
  
  LikeLike
  - Jim Randell 1:14 pm on 15 April 2025 Permalink | Reply
    Here is my analytical solution:
    
    The CoM of the cylinder is in the centre of the cylinder, and adding the base will bring the CoM down a little.
    
    Suppose we then start adding rum to the glass:
    
    We start by adding a little rum. This forms a layer of rum below the current CoM of the glass, so the combined CoM moves down a bit. And this continues until the combined CoM is level with the top of the rum. At this point, when we add additional rum, it forms a layer above the current CoM, and so the combined CoM starts to move upwards.
    
    Hence the combined CoM is at a minimum when it is level with the top of the rum.
    
    So we are interested in when:
    
    ∑(m[i] . h[i]) / ∑(m[i]) = x + 4
    ⇒
    ∑(m[i] . h[i]) = (x + 4) ∑(m[i])
    
    And we want to find solutions when h = 3x, which we can do manually, or use a program.
```
from enigma import (Polynomial, rdiv, sq, printf)

x = Polynomial('x')
h = 3 * x
half = rdiv(1, 2)

# mass of cylinder, base, rum (half the density)
mc = (sq(36) - sq(32)) * h * 2
mb = sq(36) * 4 * 2
mr = x * sq(32)
# heights of their respective centres of mass
hc = 4 + h * half
hb = 2
hr = 4 + x * half

# polynomial to solve: sum(m[i] * h[i]) = (x + 4) * sum(m[i])
p = (mc * hc + mb * hb + mr * hr) - (x + 4) * (mc + mb + mr)
p = p.scale()
printf("[p = {p}]")

# find real, positive solutions for p(x) = 0
for x in p.roots(domain='F', include='+'):
  h = 3 * x
  height = h + 4
  printf("height = {height} mm [x={x} h={h}]")
```
    Manually we find the resulting polynomial p(x) factorises as follows:
    
    p(x) = 19x^2 − 648x − 1296
    p(x) = (19x + 36)(x − 36)
    
    From which we see there is a single positive real root that is an integer, and this provides an integer answer to the puzzle.
    
    Or we can use calculus to determine when the minimum height centre of mass occurs:
    
    For a glass with an internal height h and a depth of rum x we can calculate the centre of mass as:
    
    f(x) = (544h(4 + h/2) + 10368 . 2 + 1024x(4 + x/2)) / (544h + 10368 + 1024x)
    f(x) = (17h^2 + 136h + 32x^2 + 256x + 1296) / (34h + 64x + 648)
    
    And we can calculate when the derivative of this function with respect to x is 0, using the quotient rule:
    
    f(x) = p(x) / q(x)
    ⇒
    f'(x) = (p'(x) q(x) − p(x) q'(x)) / q(x)^2
    
    So the minimum value occurs when p’ q = p q’.
    
    In this case:
    
    p(x) = (17h^2 + 136h + 32x^2 + 256x + 1296)
    p'(x) = 64x + 256
    
    q(x) = (34h + 64x + 648)
    q'(x) = 64
    
    (64x + 256)(34h + 64x + 648) = (17h^2 + 136h + 32x^2 + 256x + 1296)(64)
    ⇒
    32x^2 + (648 + 34h)x + (1296 − 17h^2) = 0
    
    And we want to find the minimum value when h = 3x:
    
    32x^2 + (648 + 34 . 3x)x + (1296 − 17 . (3x)^2) = 0
    ⇒
    19x^2 − 648x − 1296 = 0
    (19x + 36)(x − 36) = 0
    ⇒
    x = 36
    h = 108
    
    And the answer to the puzzle follows directly.
    
    LikeLike
Jim Randell 8:32 am on 11 April 2025 Permalink | Reply
Tags: by: Graham Smithers ( 83 )
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]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Frits and Jim Randell are discussing. Toggle Comments
- 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.
  
  LikeLike
- 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)))
```
  LikeLike
Jim Randell 8:27 am on 8 April 2025 Permalink | Reply
Tags: by: Robin Nayler ( 16 )
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]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- 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)
  
  LikeLike

Jim Randell 7:13 am on 6 April 2025 Permalink | Reply
Tags: by: Victor Bryant ( 143 )

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 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).

LikeLike

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()

LikeLike

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

LikeLike

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

LikeLike

Jim Randell 10:30 am on 4 April 2025 Permalink | Reply
Tags: by: C Higgins ( 37 ), by: H Bradley ( 37 )
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]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- 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.
  
  LikeLike

Jim Randell 8:59 am on 2 April 2025 Permalink | Reply
Tags: by: Nick MacKinnon ( 54 )

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 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).

LikeLike
- 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)
  
  LikeLike
  - Jim Randell 1:35 pm on 2 April 2025 Permalink | Reply
    
    @Frits: Thanks. Fixed now.
    
    LikeLike
- 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
```
  LikeLike
  - 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.
    
    LikeLike

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))

LikeLike

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))

LikeLike

Jim Randell 2:42 am on 30 March 2025 Permalink | Reply
Tags: by: John Owen ( 33 )
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]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- 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.
  
  LikeLike

Jim Randell 3:50 pm on 28 March 2025 Permalink | Reply
Tags: by: Andrew Skidmore ( 87 )

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

LikeLike

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)

LikeLike

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
% ----------
% ==========

LikeLike

Jim Randell 8:39 am on 25 March 2025 Permalink | Reply
Tags: by: Victor Bryant ( 143 )
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]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- 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
  
  LikeLike

Jim Randell 1:43 am on 23 March 2025 Permalink | Reply
Tags: by: Stephen Hogg ( 63 )

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 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!

LikeLike

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)

LikeLike

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")

LikeLike

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])];
```
LikeLike
- 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.
  
  LikeLike
GeoffR 5:19 pm on 29 March 2025 Permalink | Reply

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

LikeLike

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.)

LikeLike

Jim Randell 7:44 am on 21 March 2025 Permalink | Reply
Tags: by: Victor Bryant ( 143 )

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

LikeLike

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)

LikeLike

Jim Randell 7:57 am on 18 March 2025 Permalink | Reply
Tags: by: Nick MacKinnon ( 54 )

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

LikeLike

Jim Randell 6:36 am on 16 March 2025 Permalink | Reply
Tags: by: Peter Good ( 28 )

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

LikeLike

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.

LikeLike
- 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
```
  LikeLike

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()

LikeLike

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]

LikeLike
- Frits 4:36 pm on 16 March 2025 Permalink | Reply
  
  Luckily no word contains duplicate letters otherwise a fix is needed.
  
  LikeLike
  - 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.
    
    LikeLike
    - Frits 4:41 pm on 16 March 2025 Permalink | Reply
      
      @Jim, you are right.
      
      LikeLike
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.

LikeLike

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)}'")

LikeLike

Jim Randell 7:29 am on 14 March 2025 Permalink | Reply
Tags: by: Adrian Somerfield ( 13 )

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

LikeLike

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

LikeLike

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)))

LikeLike

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]
```
LikeLike
- 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)))
```
  LikeLike
  - 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.
    
    LikeLike

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

LikeLike

Jim Randell 10:23 am on 11 March 2025 Permalink | Reply
Tags: by: Andrew Skidmore ( 87 )
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]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- 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")
```
  LikeLike
Jim Randell 6:20 am on 9 March 2025 Permalink | Reply
Tags: by: Colin Vout ( 38 )
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]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- 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.
  
  LikeLike
  - 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.
    
    LikeLike
Jim Randell 9:35 am on 4 March 2025 Permalink | Reply
Tags: by: Des MacHale ( 11 )
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]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- 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.
  
  LikeLike
  - 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])
```
    LikeLike

Jim Randell 1:03 am on 2 March 2025 Permalink | Reply
Tags: by: Howard Williams ( 44 )

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

LikeLike

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))

LikeLike

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)

LikeLiked by 1 person

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))

LikeLike

	Jim Randell on Teaser 2451: [Just one ou…
	Ruud on Teaser 3312: Never ends r…
	Jim Randell on Teaser 3312: Never ends r…
	ruudvanderham on Teaser 2452: [Cubic time]
	ruudvanderham on Teaser 2452: [Cubic time]
	Jim Randell on Teaser 2452: [Cubic time]
	Jim Randell on Teaser 3311: Calling from…
	Ellen Napier on Teaser 3311: Calling from…

Search

Recent Posts

Recent Comments

Archives

Categories

Subscribe

RSS Links

Site Stats

Meta

Recent Updates Page 8 Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 10:08 am on 17 April 2025 Permalink | Reply Tags: by: Andrew Skidmore ( 87 )

Rate this:

Share:

Jim Randell 10:08 am on 17 April 2025 Permalink | Reply

Reply Cancel reply

Jim Randell 9:06 am on 15 April 2025 Permalink | Reply Tags: by: W A Thatcher ( 13 )

Rate this:

Share:

Jim Randell 9:08 am on 15 April 2025 Permalink | Reply

Frits 12:19 pm on 17 April 2025 Permalink | Reply

Jim Randell 2:39 pm on 17 April 2025 Permalink | Reply

Frits 12:08 pm on 17 April 2025 Permalink | Reply

Frits 12:41 pm on 17 April 2025 Permalink | Reply

Jim Randell 6:53 am on 13 April 2025 Permalink | Reply Tags: by: Mark Valentine ( 17 )

Rate this:

Share:

Jim Randell 8:03 am on 13 April 2025 Permalink | Reply

Jim Randell 1:14 pm on 15 April 2025 Permalink | Reply

Jim Randell 8:32 am on 11 April 2025 Permalink | Reply Tags: by: Graham Smithers ( 83 )

Rate this:

Share:

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

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

Jim Randell 8:27 am on 8 April 2025 Permalink | Reply Tags: by: Robin Nayler ( 16 )

Rate this:

Share:

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

Jim Randell 7:13 am on 6 April 2025 Permalink | Reply Tags: by: Victor Bryant ( 143 )

Rate this:

Share:

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

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

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

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

Jim Randell 10:30 am on 4 April 2025 Permalink | Reply Tags: by: C Higgins ( 37 ), by: H Bradley ( 37 )

Rate this:

Share:

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

Jim Randell 8:59 am on 2 April 2025 Permalink | Reply Tags: by: Nick MacKinnon ( 54 )

Rate this:

Share:

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

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

Jim Randell 1:35 pm on 2 April 2025 Permalink | Reply

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

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

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

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

Jim Randell 2:42 am on 30 March 2025 Permalink | Reply Tags: by: John Owen ( 33 )

Rate this:

Share:

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

Jim Randell 3:50 pm on 28 March 2025 Permalink | Reply Tags: by: Andrew Skidmore ( 87 )

Rate this:

Share:

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

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

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

Jim Randell 8:39 am on 25 March 2025 Permalink | Reply Tags: by: Victor Bryant ( 143 )

Rate this:

Share:

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

Jim Randell 1:43 am on 23 March 2025 Permalink | Reply Tags: by: Stephen Hogg ( 63 )

Rate this:

Share:

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

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

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

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

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

Jim Randell 10:08 am on 17 April 2025 Permalink | Reply
Tags: by: Andrew Skidmore ( 87 )

Jim Randell 9:06 am on 15 April 2025 Permalink | Reply
Tags: by: W A Thatcher ( 13 )

Jim Randell 6:53 am on 13 April 2025 Permalink | Reply
Tags: by: Mark Valentine ( 17 )

Jim Randell 8:32 am on 11 April 2025 Permalink | Reply
Tags: by: Graham Smithers ( 83 )

Jim Randell 8:27 am on 8 April 2025 Permalink | Reply
Tags: by: Robin Nayler ( 16 )

Jim Randell 7:13 am on 6 April 2025 Permalink | Reply
Tags: by: Victor Bryant ( 143 )

Jim Randell 10:30 am on 4 April 2025 Permalink | Reply
Tags: by: C Higgins ( 37 ), by: H Bradley ( 37 )

Jim Randell 8:59 am on 2 April 2025 Permalink | Reply
Tags: by: Nick MacKinnon ( 54 )

Jim Randell 2:42 am on 30 March 2025 Permalink | Reply
Tags: by: John Owen ( 33 )

Jim Randell 3:50 pm on 28 March 2025 Permalink | Reply
Tags: by: Andrew Skidmore ( 87 )

Jim Randell 8:39 am on 25 March 2025 Permalink | Reply
Tags: by: Victor Bryant ( 143 )

Jim Randell 1:43 am on 23 March 2025 Permalink | Reply
Tags: by: Stephen Hogg ( 63 )

Jim Randell 7:44 am on 21 March 2025 Permalink | Reply
Tags: by: Victor Bryant ( 143 )

Jim Randell 7:57 am on 18 March 2025 Permalink | Reply
Tags: by: Nick MacKinnon ( 54 )

Jim Randell 6:36 am on 16 March 2025 Permalink | Reply
Tags: by: Peter Good ( 28 )

Jim Randell 7:29 am on 14 March 2025 Permalink | Reply
Tags: by: Adrian Somerfield ( 13 )

Jim Randell 10:23 am on 11 March 2025 Permalink | Reply
Tags: by: Andrew Skidmore ( 87 )

Jim Randell 6:20 am on 9 March 2025 Permalink | Reply
Tags: by: Colin Vout ( 38 )

Jim Randell 9:35 am on 4 March 2025 Permalink | Reply
Tags: by: Des MacHale ( 11 )

Jim Randell 1:03 am on 2 March 2025 Permalink | Reply
Tags: by: Howard Williams ( 44 )