Tagged: by: Peter Good Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 6:32 am on 7 December 2025 Permalink | Reply
    Tags: by: Peter Good   

    Teaser 3298: Bletchley Park 

    From The Sunday Times, 7th December 2025 [link] [link]

    Secret agent Robert Holmes was searching the hotel room of a foreign agent who was downstairs having breakfast.

    Holmes discovered a piece of paper containing the [following] text:

    DKCCVTCSZQRZYTAZXTTX

    And he thought this might be a coded message about the foreign agent’s mission, so he sent it to his code-breaking experts.

    They discovered that it was a message that had been scrambled by consistently replacing each letter of the alphabet with a different letter (no letter being used to replace more than one different letter). They decoded the message as a sentence containing four words, which they sent back to Holmes with spaces inserted between words. Holmes realised that his life was in imminent danger as soon as he read it.

    What was the decoded message?

    [teaser3298]

     
    • Jim Randell's avatar

      Jim Randell 6:33 am on 7 December 2025 Permalink | Reply

      Assuming the foreign agent communicates in English, I had a guess at to what the first two words might be, and this gave me enough letters to fill out a likely candidate for the rest of the message immediately.

      Solution: The message can be decoded as: KILL HOLMES BEFORE NOON.

      But the clear text could just be the less threatening: CALL HOLMES BEFORE NOON.

      Or it could not involve HOLMES at all: PULL MELBA STAGE CAREER.

      In fact there are lots of possible clear text substitutions consisting of four English words (although most of them don’t form a coherent sentence).

      Like

      • Frits's avatar

        Frits 8:27 am on 7 December 2025 Permalink | Reply

        @Jim, I also found the solution but wonder how to make a general program that also runs in a reasonable time.

        Like

      • Jim Randell's avatar

        Jim Randell 9:59 am on 7 December 2025 Permalink | Reply

        The following program assumes that HOLMES appears somewhere in the decoded message. And then tries to split the unused cipher text into three possible words. (Which is how I attacked the puzzle manually).

        Using a list of 61871 fairly common English words, the following program finds many possible ways to decipher the text (including the way I found earlier, which still seems to be the most likely candidate solution).

        It runs in 5.03s (using PyPy).

        from enigma import (irange, group, tuples, translate, readlines, printf)

# enciphered text
code = "DKCCVTCSZQRZYTAZXTTX"

# read words into a dict (indexed by word length)
path = "words.txt"
with open(path, "r") as fh:
  words = group(readlines(fh, fn=str.upper, st=str.isalpha), by=len)

# consistently update dict <d> mapping keys <ks> to values <vs>
def update(d, ks, vs):
  d = dict(d)
  for (k, v) in zip(ks, vs):
    if k == v:
      return
    elif k in d:
      if v != d[k]: return
    elif v in d.values():
      return
    else:
      d[k] = v
  return d

# solve cipher text <ws> = [(<n>, <text>), ...] into <n> words
# using dict <d>
def solve(ws, d):
  # are we done?
  if not ws:
    text = translate(code, d)
    printf("-> {text}")
  else:
    # consider the next chunk of code
    (k, t) = ws[0]
    # look for a single word
    if k == 1:
      for x in words.get(len(t), []):
        d1 = update(d, t, x)
        if d1:
          solve(ws[1:], d1)
    elif k > 1:
      # solve the first word
      for n in irange(1, len(t) + 1 - k):
        for x in words.get(n, []):
          d1 = update(d, t[:n], x)
          if d1:
            solve([(k - 1, t[n:])] + ws[1:], d1)

# look for a run of 6 different letters to be "HOLMES"
for (i, vs) in enumerate(tuples(code, 6)):
  if len(set(vs)) != 6: continue
  d = dict(zip(vs, "HOLMES"))
  # split the text at HOLMES
  (a, b) = (code[:i], code[i + 6:])
  if not a:
    solve([(3, b)], d)
  elif not b:
    solve([(3, a)], d)
  else:
    solve([(1, a), (2, b)], d)
    solve([(2, a), (1, b)], d)

        You will need to provide a list of candidate words in [[ words.txt ]] (or change the definition of path to point to such a list).

        The [[ readlines() ]] function is a recent addition to the enigma.py library.

        Like

  • Unknown's avatar

    Jim Randell 6:08 am on 5 October 2025 Permalink | Reply
    Tags: by: Peter Good   

    Teaser 3289: Spot check 

    From The Sunday Times, 5th October 2025 [link] [link]

    Jack has a set of 28 standard dominoes: each domino has a spot pattern containing 0 to 6 spots at either end and every combination ([0-0], [0-1] and so on up to [6-6]) is represented in the set. He discarded a non-blank domino and arranged the remaining dominoes into six “groups”, each of which contained a positive cube number of spots; a group might comprise a single domino. He then discarded another non-blank domino and rearranged the remaining dominoes into six groups each of which again contained a positive cube number of spots. He managed to do this the maximum possible number of times.

    How many dominoes did Jack discard? And how many spots in total were there on the dominoes that remained at the end?

    [teaser3289]

     
    • Jim Randell's avatar

      Jim Randell 9:26 am on 5 October 2025 Permalink | Reply

      I ignored the [0-0] domino as it doesn’t affect the results (it can’t be one of the discarded dominoes, and it can be added to any of the piles without affecting the total number of pips).

      I assumed the groups are just collections of 1 or more dominoes. (And not that they had to fit together as in a domino game). So we can just keep track of the number of pips on each domino.

      And that a “non-blank” domino is a domino that does not have either half blank.

      My code gets multiple answers for the second part of the puzzle.

      from enigma import (
  Accumulator, irange, inf, multiset, subsets,
  peek, powers, first, lt, group, printf
)

# collect pips on dominoes; all; non-0; total
# (we discard 0-0 as it does not affect the results)
(ds_all, ds_non0, T) = (multiset(), multiset(), 0)
# the complete set of dominoes
for (x, y) in subsets(irange(0, 6), size=2, select='R'):
  if x == y == 0: continue  # skip [0-0]
  t = x + y
  ds_all.add(t)
  if x > 0 and y > 0: ds_non0.add(t)
  T += t

# possible cubes
cubes = list(first(powers(1, inf, 3), count=lt(T)))

# decompositions of numbers that can be expressed as the sum of 6 cubes
g = group(subsets(cubes, size=6, select='R'), by=sum, st=(lambda ns: sum(ns) < T))

# make piles with total in <ts> from dominoes <ds>
def piles(ts, ds, ps=list()):
  # are we done?
  if not ts:
    yield ps
  else:
    t = ts[0]
    for ss in ds.express(t):
      yield from piles(ts[1:], ds.difference(ss), ps + [ss])

# starting with total <t>
# discard a domino from <ds_non0> and form the remaining dominoes in piles
# return [(t1, ps1), ..., (tk, psk)]
def solve(t, ds_all, ds_non0, ss=list()):
  if ss: yield ss
  # look for a non0 domino to discard
  for x in ds_non0.keys():
    # remaining total pips
    t_ = t - x
    if t_ not in g: continue
    ds_all_ = ds_all.difference([x])
    # consider possible decompositions into 6 piles
    for ts in g[t_]:
      # can we make an appropriate set of piles?
      ps = peek(piles(ts, ds_all_), default=None)
      if ps:
        yield from solve(t_, ds_all_, ds_non0.difference([x]), ss + [(t_, ps)])
        break  # we only need one viable decomposition

# find maximal length sequences
r = Accumulator(fn=max, collect=1)
for ss in solve(T, ds_all, ds_non0):
  r.accumulate_data(len(ss), ss)
printf("max discards = {r.value}")

# output example maximal sets
rs = set()
for ss in r.data:
  for (t, ps) in ss:
    printf("{t} -> {ps}", ps=list(list(p.sorted()) for p in ps))
  printf()
  rs.add(t)
printf("remaining dominoes = {rs} pips", rs=sorted(rs))

      Solution: [See below]

      Like

      • Jim Randell's avatar

        Jim Randell 2:45 pm on 5 October 2025 Permalink | Reply

        Taking a “non-blank” domino to mean any domino other than [0-0] (which I excluded anyway) allows me to simplify my code (although we could just change the [[ and ]] on line 14 to an [[ or ]]), and get a single answer to both of the questions in the puzzle. And so may well be what the setter intended.

        If this is the case, I think it would probably have been better to say the [0-0] domino was removed from a standard 28-domino set, and then the puzzle is solved with the remaining 27 dominoes. That way we don’t need mention the “non-blank” condition (we can just discard any of the remaining dominoes).

        from enigma import (
  Accumulator, irange, inf, multiset, subsets,
  peek, powers, first, lt, group, printf
)

# collect pips on dominoes; and total pips
ds = multiset.from_seq(x + y for (x, y) in subsets(irange(0, 6), size=2, select='R'))
ds.remove(0)  # remove [0-0] as it does not affect the results
T = ds.sum()

# possible cubes
cubes = list(first(powers(1, inf, 3), count=lt(T)))

# decompositions of numbers that can be expressed as the sum of 6 cubes
g = group(subsets(cubes, size=6, select='R'), by=sum, st=(lambda ns: sum(ns) < T))

# make piles with total in <ts> from dominoes <ds>
def piles(ts, ds, ps=list()):
  # are we done?
  if not ts:
    yield ps
  else:
    t = ts[0]
    for ss in ds.express(t):
      yield from piles(ts[1:], ds.difference(ss), ps + [ss])

# starting with total <t>
# discard a domino from <ds> and form the remaining dominoes in piles
# return [(t1, ps1), ..., (tk, psk)]
def solve(t, ds, ss=list()):
  if ss: yield ss
  # look for a domino to discard
  for x in ds.keys():
    # remaining total pips
    t_ = t - x
    if t_ not in g: continue
    ds_ = ds.difference([x])
    # consider possible decompositions into 6 piles
    for ts in g[t_]:
      # can we make an appropriate set of piles?
      ps = peek(piles(ts, ds_), default=None)
      if ps:
        yield from solve(t_, ds_, ss + [(t_, ps)])
        break  # we only need one viable decomposition

# find maximal length sequences
r = Accumulator(fn=max, collect=1)
for ss in solve(T, ds):
  r.accumulate_data(len(ss), ss)
printf("max discards = {r.value}")

# output example maximal sets
rs = set()
for ss in r.data:
  for (t, ps) in ss:
    printf("{t} -> {ps}", ps=list(list(p.sorted()) for p in ps))
  printf()
  rs.add(t)
printf("remaining dominoes = {rs} pips", rs=sorted(rs))

        Solution: Jack discarded 11 dominoes. At the end, the total number of spots on the remaining dominoes was 98.

        There are 3 sequences of totals that can be made:

        [165, 162, 160, 158, 153, 143, 136, 124, 116, 105, 98 ]
        [165, 162, 160, 158, 153, 143, 135, 124, 117, 105, 98 ]
        [165, 162, 160, 158, 153, 143, 135, 123, 116, 105, 98 ]

        Like

        • Frits's avatar

          Frits 3:42 am on 10 October 2025 Permalink | Reply

          @Jim, couldn’t you use a break on line 44 after the yield?

          In my opinion as soon as you have found a valid “ps” you don’t need to process another “ts”. It may depend on what you want to display as output.

          Like

          • Jim Randell's avatar

            Jim Randell 8:54 am on 10 October 2025 Permalink | Reply

            @Frits: Yes, we could. There only needs to be one viable decomposition into cubes. (Although for most totals there is only one possible decomposition anyway). I’ll add it in.

            Like

  • Unknown's avatar

    Jim Randell 6:17 am on 3 August 2025 Permalink | Reply
    Tags: by: Peter Good   

    Teaser 3280: No square rolls 

    From The Sunday Times, 3rd August 2025 [link] [link]

    Clark had a set of more than one identical six-sided dice, and each die had a different positive whole number on each face. He would roll the dice and work out the total of all the numbers showing on the top faces. Clark knew that the largest possible total was 69, but it took him much longer to realise that it was impossible to roll a total that was a perfect square. The latter was true no matter how many of the dice were rolled.

    In ascending order, what were the six numbers on each die?

    [teaser3280]

     
    • Jim Randell's avatar

      Jim Randell 6:18 am on 3 August 2025 Permalink | Reply

      If the largest possible total is 69, then there must be 3 dice and the largest number in the set is 23.

      The other numbers must be from 1 to 22, from which we can remove any number that is itself a square, or if a double or treble would give a square. Or where that number with 23 or double 23 would give a square.

      This Python program runs in 66ms. (Internal runtime is 2.6ms).

      from enigma import (irange, sq, subsets, printf)

# squares up to 69
sqs = set(sq(i) for i in irange(1, 8))

# there must be 3 dice, with a largest number of 23
# choose the remaining 5 numbers
ns = list(x for x in irange(1, 22) if sqs.isdisjoint({x, 2*x, 3*x, x + 23, x + 46, 2*x + 23}))
for ds in subsets(ns, size=5, fn=list):
  ds.append(23)
  # check possible throws with 2 and 3 dice
  if any(sum(ss) in sqs for ss in subsets(ds, min_size=2, max_size=3, select='R')): continue
  # output solution
  printf("dice = 3x {ds}")

      Solution: The numbers on each die are: 7, 10, 14, 17, 20, 23.

      And so the possible throws are:

      7, 10, 14, 17, 20, 21, 23, 24, 27, 28, 30, 31, 33, 34, 35, 37, 38, 40,
      41, 42, 43, 44, 45, 46, 47, 48, 50, 51, 53, 54, 56, 57, 60, 63, 66, 69

      Avoiding the square numbers in the range [7 .. 69] = 9, 16, 25, 36, 49, 64 (as well as some non-square numbers in this range).

      Like

      • Jim Randell's avatar

        Jim Randell 11:03 am on 3 August 2025 Permalink | Reply

        Or, with more generic code.

        This Python program has an internal runtime of 3.4ms.

        from enigma import (irange, powers, inf, first, le, subsets, decompose, divisors_pairs, arg, printf)

# consider up to k dice combinations of x with m
combine = lambda x, m, k: (x + i * x + j * m for (i, j) in decompose(irange(0, k - 1), 2, increasing=0, sep=0, min_v=0))

# solve for k dice, with n faces and a max value of m
def solve(k, n, m):
  # squares up to k.m
  sqs = set(first(powers(1, inf, 2), count=le(k * m)))
  if any(i * m in sqs for i in irange(1, k)): return

  # the candidate numbers (other than m)
  ns = list(x for x in irange(1, m - 1) if not any(t in sqs for t in combine(x, m, k)))

  # choose numbers for the remaining faces
  for ds in subsets(ns, size=n - 1, fn=list):
    ds.append(m)
    # check up to k throws
    if not any(sum(ss) in sqs for ss in subsets(ds, min_size=2, max_size=k, select='R')):
      yield ds

# solve the puzzle for a max throw of 69
M = arg(69, 0, int)
for (k, m) in divisors_pairs(M, every=1):
  if not (k > 1 and m > 8): continue
  for ds in solve(k, 6, m):
    printf("dice = {k}x {ds}")

        This program allows us to explore similar problems with other largest totals.

        For a largest total of 87 there are 3 sets of 3 dice. And for a largest total of 99 there are 35 sets of 3 dice.

        The first set of 4 dice appears at a largest total of 120:

        dice = 4× [11, 13, 15, 26, 28, 30]

        Like

    • Frits's avatar

      Frits 11:31 am on 3 August 2025 Permalink | Reply 

      from itertools import combinations, product

# possible square totals
sqs = {i * i for i in range(1, 9)}

# dice that can cause a square total
invalid = {n for n in range(1, 23) for i in range(4) for j in range(4 - i)
          if i * n + j * 23 in sqs}

rng = set(range(1, 23)) - invalid

# dice pairs that can cause a square total
invalid_pairs = {(x, y) for x, y in combinations(rng, 2)
                 if x + y in sqs or x + y + 23 in sqs}

# choose 5 dice (besides 23)
for d5 in combinations(rng, 5):
  # check possible dice pairs from these dice
  if any(d2 in invalid_pairs for d2 in combinations(d5, 2)): continue
  # check rolling of 3 dice (we have already checked combinations with 23)
  if any(sum(d3) in sqs for d3 in product(d5, repeat=3)): continue     
  print("answer:", d5 + (23, ))

      Like

      • Frits's avatar

        Frits 12:14 pm on 3 August 2025 Permalink | Reply

        A little bit more efficient.

        from itertools import combinations

# possible square totals
sqs = {i * i for i in range(1, 9)}

# dice that can cause a square total
invalid = {n for n in range(1, 23) for i in range(4) for j in range(4 - i)
          if i * n + j * 23 in sqs}

rng = set(range(1, 23)) - invalid

# dice pairs that can cause a square total
invalid_pairs = {(x, y) for x, y in combinations(rng, 2)
                 if x + y in sqs or 2 * x + y in sqs or 
                    x + 2 * y in sqs or x + y + 23 in sqs}
                 
# choose 5 dice (besides 23)
for d5 in combinations(rng, 5):
  # check possible dice pairs from these dice
  if any(d2 in invalid_pairs for d2 in combinations(d5, 2)): continue
  # check total of 3 different top faces
  if any(sum(d3) in sqs for d3 in combinations(d5, 3)): continue     
  print("answer:", d5 + (23, ))

        Like

      • Frits's avatar

        Frits 2:02 pm on 3 August 2025 Permalink | Reply

        In my first program itertools.combinations_with_replacement() is more suitable than product() (after reviewing Jim’s code).

        This version is again a bit more efficient (especially with CPython).

        from itertools import combinations

# possible square totals
sqs = {i * i for i in range(1, 9)}

# dice that can cause a square total
invalid = {n for n in range(1, 23) for i in range(4) for j in range(4 - i)
          if i * n + j * 23 in sqs}

rng = set(range(1, 23)) - invalid

# dice pairs that can cause a square total
invalid_pairs = {(x, y) for x, y in combinations(rng, 2)
                 if x + y in sqs or 2 * x + y in sqs or 
                    x + 2 * y in sqs or x + y + 23 in sqs}

# add <k> top face numbers                    
def solve(k, ns, ss=tuple()):
  if k == 0:
    yield ss
  else:
    for i, n in enumerate(ns):
      # check for possible square totals
      if ss and any((s, n) in invalid_pairs for s in ss): continue
      yield from solve(k - 1, ns[i + 1:], ss + (n, ))

# choose 5 other top face numbers (besides 23)
for s in solve(5, sorted(rng)):
  print("answer:", s + (23, ))

        Like

    • Frits's avatar

      Frits 3:44 pm on 4 August 2025 Permalink | Reply

      Another.

      from itertools import combinations
 
# possible square totals
sqs = {i * i for i in range(1, 9)}

# all combinations with x and y
c2 = lambda x, y: [2*x, 3*x, x + y, x + 2*y, 2*x + y]     
c3 = lambda x, y, z: [x + y, x + 2*y, 2*x + y, x + y + z]

rng = [x for x in range(1, 23) if x not in sqs and sqs.isdisjoint(c2(x, 23))]
# dictionary of numbers that may be paired with a number (including itself)                      
d = {x: {y for y in rng if sqs.isdisjoint(c3(x, y, 23))} for x in rng}

# choose 5 other top face numbers (besides 23)
for d5 in combinations(d.keys(), 5):
  # each number must pair with other selected numbers
  if any(not d[n].issuperset(d5) for n in d5): continue
  print("answer:", d5 + (23, ))

      Like

  • Unknown's avatar

    Jim Randell 6:21 am on 1 June 2025 Permalink | Reply
    Tags: by: Peter Good   

    Teaser 3271: Uncut diamonds 

    From The Sunday Times, 1st June 2025 [link] [link]

    Andrew was building a rhombus-shaped patio. He could have paved it with equilateral triangular slabs with 1ft edges, but he wanted a layout with a hexagonal slab in place of six triangular ones at various places. He considered two layouts that were symmetrical in two perpendicular directions:

    Layout 1: every triangular slab touches the perimeter of the patio in at least one point.

    Layout 2: each group of three adjacent hexagonal slabs encloses exactly one triangular one.

    The triangular and hexagonal slabs come in boxes of 12, and Andrew chose layout 1 because he would only need a third as many boxes of triangular slabs as layout 2.

    What length were the sides of the patio and how many slabs in total would be left over?

    [teaser3271]

     
    • Jim Randell's avatar

      Jim Randell 7:13 am on 1 June 2025 Permalink | Reply

      Once you have determined how the two layouts work (isometric graph paper helps), this is a relatively straightforward puzzle.

      Here are the two layouts on a rhombus with sides of size 8:

      (Layout 1 uses 17 hexes and 26 tris. Layout 2 uses 16 hexes and 32 tris. Note that there are tris in Layout 2 that are not surrounded by 3 hexes).

      The following Python program generates increasing sizes for each layout, and determines the (side, hexes, tris) for each case, and then looks for two layouts with the same size where layout 1 requires 1/3 the number of boxes of triangular tiles as layout 2.

      It runs in 60ms. (Internal runtime is 266µs).

      from enigma import (irange, inf, sq, intersect, divc, printf)

# generate (<side>, <hexes>, <tris>) for layout 1
def layout1(M):
  # consider number of hexagons on the long diagonal
  for n in irange(1, inf):
    s = n + 1
    if s > M: break
    h = 2 * sum(irange(n, 1, step=-3)) - n
    t = 2 * sq(s) - 6 * h
    yield (s, h, t)

# generate (<side>, <hexes>, <tris>) for layout 2
def layout2(M):
  # there is a sq(n) array of hexagons
  for n in irange(1, inf):
    s = 2 * n
    if s > M: break
    h = sq(n)
    t = 2 * sq(s) - 6 * h
    yield (s, h, t)

# collect (h, t) by s for each layout
M = 100
(d1, d2) = (dict(), dict())
for (s, h, t) in layout1(M): d1[s] = (h, t)
for (s, h, t) in layout2(M): d2[s] = (h, t)

# calculate boxes and left overs
def boxes(n, k=12):
  b = divc(n, k)
  return (b, k * b - n)

# examine common side lengths
for s in sorted(intersect([d1.keys(), d2.keys()])):
  ((h1, t1), (h2, t2)) = (d1[s], d2[s])
  # check for layout 1 needing 1/3 as many boxes of tris as layout 2
  ((b1, r1), (b2, r2)) = (boxes(t1), boxes(t2))
  if 3 * b1 == b2:
    # output solution
    printf("s={s}: layout 1 = {h1} hex + {t1} tri; layout 2 = {h2} hex + {t2} tri")
    printf("-> tri: layout 1 = {b1} boxes (rem = {r1}); layout 2 = {b2} boxes (rem = {r2})")
    ((b1, r1), (b2, r2)) = (boxes(h1), boxes(h2))
    printf("-> hex: layout 1 = {b1} boxes (rem = {r1}); layout 2 = {b2} boxes (rem = {r2})")
    printf()

      Solution: The sides of the patio were 24 ft. There are 9 slabs left over.

      Layout 1 uses 177 hex slabs (= 15 boxes, with 3 unused), and 90 tri slabs (= 8 boxes, with 6 unused).

      Layout 2 uses 144 hex slabs (= 12 boxes, with 0 unused), and 288 tri slabs (= 24 boxes, with 0 unused).

      Like

      • Jim Randell's avatar

        Jim Randell 9:45 am on 1 June 2025 Permalink | Reply

        Some analysis gives a shorter program:

        For a rhombus with side s, the number of hexagons in each of the layouts is:

        layout 1: h1 = ceil(sq(s − 1)/3), where s ≥ 2
        layout 2: h2 = sq(s/2), where s is even

        The following program considers increasing even length sides of the rhombus, until a solution is found.

        from enigma import (irange, inf, sq, divc, ediv, printf)

# calculate boxes and left overs
def boxes(n, k=12):
  b = divc(n, k)
  return (b, k * b - n)

# consider possible sides of the rhombus
for s in irange(2, inf, step=2):
  n = 2 * sq(s)  # number of triangular cells
  # calculate the number of hex tiles
  (h1, h2) = (divc(sq(s - 1), 3), sq(ediv(s, 2)))
  # calculate the number of tri tiles
  (t1, t2) = (n - 6 * h1, n - 6 * h2)
  # calculate number of boxes of tri tiles
  ((b1, r1), (b2, r2)) = (boxes(t1), boxes(t2))
  if 3 * b1 == b2:
    # output solution
    printf("s={s}: layout 1 = {h1} hex + {t1} tri; layout 2 = {h2} hex + {t2} tri")
    printf("-> tri: layout 1 = {b1} boxes (rem = {r1}); layout 2 = {b2} boxes (rem = {r2})")
    ((b1, r1), (b2, r2)) = (boxes(h1), boxes(h2))
    printf("-> hex: layout 1 = {b1} boxes (rem = {r1}); layout 2 = {b2} boxes (rem = {r2})")
    printf()
    break

        Like

  • Unknown's avatar

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

    Teaser 3260: Alphabet soup 

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

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

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

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

    Which saying was Clark able to spell out?

    [teaser3260]

     
    • Jim Randell's avatar

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

      AEO___
      DFMW__
      INR___
      T_____

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

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

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

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

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

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

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

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

      Like

      • Frits's avatar

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

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

        Like

        • Jim Randell's avatar

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

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

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

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

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

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

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

          Like

      • Jim Randell's avatar

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

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

        It has an internal runtime of 4.8ms.

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

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

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

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

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

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

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

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

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

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

        Like

    • Frits's avatar

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

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

      [program removed]

      Like

      • Frits's avatar

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

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

        Like

        • Jim Randell's avatar

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

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

          Like

    • Frits's avatar

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

      Thanks. I may try it.

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

      Like

    • Frits's avatar

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

      from itertools import combinations, permutations

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

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

      Like

  • Unknown's avatar

    Jim Randell 7:02 am on 2 February 2025 Permalink | Reply
    Tags: by: Peter Good   

    Teaser 3254: Pizza pans 

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

    In a large pan, James baked three identical circular pizzas whose radius was a whole number of cm (less than 75). He laid them on a platter so that one pizza overlapped the other two. The pizza centres formed a right-angled triangle, with sides that were whole numbers of cm. The two lengths of overlap and the gap between the two non-overlapping pizzas (all measured along the lines joining the pizza centres) were all whole numbers of cm and could have formed another right-angled triangle.

    He baked a fourth, smaller, circular pizza and it just fitted inside the triangle formed by the centres of the other three. Even if you knew the radii of the pizzas, you couldn’t work out the size of those right-angled triangles.

    What was the radius of the smallest pizza?

    [teaser3254]

     
    • Jim Randell's avatar

      Jim Randell 7:22 am on 2 February 2025 Permalink | Reply

      The following Python program runs in 69ms. (Internal runtime is 571µs).

      from enigma import (defaultdict, irange, pythagorean_triples, divc, rdiv, printf)

# generate possible dimensions
def generate():
  # consider pythagorean triples (x, y, z)
  for (x, y, z) in pythagorean_triples(225):

    # consider possible radii for the pizza (R)
    for R in irange(divc(y + 1, 2), 74):
      RR = 2 * R
      (X, Y, Z) = (RR - y, RR - x, RR + z)
      if not (X * X + Y * Y == Z * Z): continue

      # calculate inradius of X, Y, Z (r = area / semiperimeter)
      r = rdiv(X * Y, X + Y + Z)

      # return (<radii>, <large triangle>, <small triangle>)
      yield((R, r), (X, Y, Z), (x, y, z))

# collect triangles by radii (R, r)
d = defaultdict(list)
for ((R, r), Ts, ts) in generate():
  printf("[R={R} {Ts} -> {ts} r={r}]")
  d[(R, r)].append((Ts, ts))

# look for non-unique radii pairs
for ((R, r), vs) in d.items():
  if len(vs) < 2: continue
  # output solution
  printf("({R}, {r}) -> {vs}")

      Solution: The smaller pizza has a radius of 30 cm.

      And the larger pizzas have radii of 60cm. (So each pizza is 120cm across! – that’s a big pizza).

      One of the possible arrangements looks like this:

      The overlaps are 10 cm and 24 cm, and the gap is 26 cm.

      And the other possible arrangement looks quite similar, but the overlaps are 15 cm and 20 cm, and the gap is 25 cm.

      Like

    • Frits's avatar

      Frits 6:36 am on 3 February 2025 Permalink | Reply 

      from enigma import pythagorean_triples

# let x, y, z be the lengths of the triangle of the overlaps and gap
# let R be the radius of the 3 identical pizzas
# RR = 2 * R
# (X, Y, Z) = (RR - y, RR - x, RR + z)
# right-angled: 4 * R**2 = 4 * (y * R + x * R + z * R)
#               so R must be equal to y + x + z  

seen = set()
# consider pythagorean triples (X, Y, Z)
for (X, Y, Z) in pythagorean_triples(4 * 75 - 1):
  # small and big radius
  # (x, y, z) = sorted([R2 - X, R2 - Y, Z - R2])
  # x + y + z = 2R - X - Y + Z = 2R - 2r = R --> R = 2r
  R = (X + Y - Z)  # r = R / 2
  
  if (R2 := 2 * R) > 2 * 75: continue
  
  # x, y, z must be positive numbers
  if min(R2 - X, R2 - Y, Z - R2) < 1: continue
  
  if R in seen:
    print(f"answer: {r} cm")
  seen.add(R)

      Like

  • Unknown's avatar

    Jim Randell 7:08 am on 24 November 2024 Permalink | Reply
    Tags: by: Peter Good,   

    Teaser 3244: Borderline case 

    From The Sunday Times, 24th November 2024 [link] [link]

    Jack has a set of 28 standard dominoes: each domino has a spot pattern containing 0 to 6 spots at either end and every combination ([0-0], [0-1] and so on up to [6-6]) is represented in the set. He laid them end-to-end in several strips and arranged each strip so it formed the border of an empty square. Adjacent dominoes in each strip shared the same spot pattern where they were joined and the total number of spots on each strip was the square of the number of dominoes in that strip. More than half of the doublets were in the longest strip and there was a doublet in just one of the two shortest strips. This doublet was the largest possible in a strip of this size.

    Which dominoes were in the shortest strip that doesn’t contain a doublet?

    I think this puzzle is poorly worded. But I give an interpretation of the text that does give a unique answer to the puzzle in the comments below.

    [teaser3244]

     
    • Jim Randell's avatar

      Jim Randell 11:25 am on 24 November 2024 Permalink | Reply

      Initially I thought that the dominoes were formed into a collection of [straight linear] strips, and then these strips were used (as is) to make the border of a (single) square.

      However, after working on the puzzle for some time I was not able to find a solution using this interpretation (or variations thereof).

      You can see my thoughts in the chat page [ here ].

      However, I think I have now found an alternative interpretation that does lead to a unique answer to the puzzle.

      To me the use of the term “strip” implied that a selected set of dominoes were formed into a straight linear arrangement, whereas it seems that they need to be formed into a square loop. So in the following I just used the term “pile”.

      The set of 28 dominoes is formed into a collection of piles, such that for each pile:

      + The total sum of the pips is the square of the number of the dominoes in that pile.

      + The dominoes in each pile can be arranged to form a closed loop that is the outline of a square, and where two dominoes meet the pip values on the adjoining ends are the same.

      Additional requirements for the collection of piles are:

      + There is a single pile that is identifiably the largest pile, and it contains more than half of the double tiles.

      + There are (exactly) two piles that are identifiably the smallest piles. One of these piles contains a double tile, and this double is the largest possible double that can occur in a pile of that size (constructed subject to the conditions above).

      + The other smallest pile does not have a double in it, and the required answer is a list of dominoes that make up this pile.

      I have verified that under this interpretation there is a unique answer to the puzzle, and have posted my code below.

      Solution: [see below]

      Like

      • Rob Bellis's avatar

        Rob Bellis 8:48 am on 26 November 2024 Permalink | Reply

        hello Jim

        Is there any reason why the square cound not be bounded by 2 x 8 tiles and 2 x 6 tiles (to enclose a 6×6 square) ?
        If each side length 6 was constructed of a 2 +4 tile strings then the sum of the squares would = 168 which is the total domino spots .

        Like

        • Jim Randell's avatar

          Jim Randell 8:56 am on 26 November 2024 Permalink | Reply

          In my initial interpretation of the puzzle I did look at attempting to make the outline of a single 14×14 square from a collection of straight strips, but it was not possible using 26 of the dominoes (for example: [7] + [4, 3] + [4, 2] + [4, 2]).

          In the (presumably) intended interpretation, enclosing a 6×6 square would require 14 dominoes, so to form an allowable loop there would have to be 14^2 = 196 pips in the selection. But there are only 168 pips in the entire set of dominoes, so the squares must be smaller than this.

          Like

    • NigelR's avatar

      NigelR 5:38 pm on 24 November 2024 Permalink | Reply

      A single domino doesn’t seem to satisfy being a border of an empty square. However, the wording would seem to allow a single strip being part of more than one square. Perhaps we are looking for a more complex shape than one or more detached squares?

      Like

    • Jim Randell's avatar

      Jim Randell 11:12 am on 25 November 2024 Permalink | Reply

      This Python 3 program solves the interpretation of the puzzle given above in my first comment.

      It assumes the two smallest piles are the same size.

      It runs in 851ms.

      from enigma import (
  defaultdict, irange, inf, first, subsets, sq, express, flatten,
  rev, remove, trim, cproduct, multiset, join, printf
)

# we represent a domino by a tuple (x, y)

# format a collection of dominoes
fmt = lambda ds: join((join(d, sep='-', enc="[]") for d in ds), sep=' ')

# number of pips on a domino
pips = sum

# a complete set of dominoes
ds = set(subsets(irange(0, 6), size=2, select='R'))

# normal form of dominoes
normalise = lambda d: tuple(sorted(d))
normal = lambda *ss: (normalise(d) for d in flatten(ss, fn=iter))

# invalid pips (sorts before all valid pips)
X = -1

# generate loops with <k> dominoes and <t> pips, from dominoes <ds>
# <m> = min starting domino
def loops(k, t, ds, m=(X, X), ss=[]):
  # are we done?
  if k == 0:
    # remove duplicate loops
    if normalise(ss[1]) > normalise(ss[-1]): return
    # check all pips are used, and a loop is formed
    if t == 0 and ss[0][0] == ss[-1][-1]:
      yield (ss, ds)
  elif not (t > 12 * k):
    # choose the next domino
    for d in ds:
      nd = normalise(d)
      if nd < m or (ss and normalise(ss[0]) > nd): continue
      p = pips(d)
      if p > t: continue
      if (not ss) or (d[0] == ss[-1][-1]):
        yield from loops(k - 1, t - p, remove(ds, d, rev(d)), m, ss + [d])

# make a collection of loops with length <ks>, from dominoes <ds>
def piles(ks, ds, rs=[]):
  # are we done?
  if not ks:
    yield (rs, ds)
  else:
    k = ks[0]
    m = (normalise(rs[-1][0]) if rs and k == len(rs[-1]) else (X, X))
    for (ss, ds_) in loops(k, sq(k), ds, m):
      yield from piles(ks[1:], ds_, rs + [ss])

# find the doubles in a set of dominoes
doubles = lambda ds: sorted(x for (x, y) in ds if x == y)

# max or X
max_ = lambda xs: (max(xs) if xs else X)

# total number of pips
tpips = sum(pips(d) for d in ds)
printf("[{n} dominoes, total pips = {tpips}]", n=len(ds))

# piles have an even number of dominoes, minimum 4
ns = first(irange(4, inf, step=2), count=(lambda x: sq(x) < tpips))
printf("[pile sizes = {ns}]")

# initial set of dominoes in either orientation
dss = set(flatten({d, rev(d)} for d in ds))

# collect results
rs = multiset()

# look for possible numbers of piles (at least 3)
for qs in express(tpips, list(sq(n) for n in ns)):
  if sum(qs) < 3: continue
  # form the pile sizes (in order)
  ks = flatten([n] * q for (n, q) in zip(ns, qs) if q > 0)
  # use all the dominoes
  if sum(ks) != 28: continue
  # there should be 2 identifiable smallest piles, and 1 identifiable largest pile
  if not (ks[0] == ks[1] < ks[2] and ks[-2] < ks[-1]): continue
  # the largest pile has 4 doubles -> a loop of at least 8 dominoes
  if ks[-1] < 8: continue
  printf("[checking {ks} = {n} dominoes]", n=sum(ks))

  # start with the smallest piles (size k)
  (k, gs) = (ks[0], defaultdict(list))
  for (ss, _) in loops(k, sq(k), dss):
    gs[max_(doubles(ss))].append(ss)
  # max possible double in a smallest pile
  m = max(gs.keys())
  assert m != X

  # choose the two smallest piles
  for (ss1, ss2) in cproduct([gs[X], gs[m]]):
    # which must contain distinct dominoes
    xs = set(normal(ss1, ss2))
    if len(xs) < 2 * k: continue

    # choose the largest pile (size K)
    (K, dss_) = (ks[-1], dss.difference(xs, (rev(x) for x in xs)))
    for (ssz, dsz) in loops(K, sq(K), dss_):
      # which must have at least 4 doubles
      if len(doubles(ssz)) < 4: continue

      # fill out the remaining piles
      for (ps, _) in piles(trim(ks, head=2, tail=1), dsz):
        ans = tuple(sorted(normal(ss1)))
        # display the collection of piles
        printf("ss1 = {ss1} -> answer", ss1=fmt(ss1))
        printf("ss2 = {ss2}", ss2=fmt(ss2))
        for (i, ss) in enumerate(ps, start=3):
          printf("ss{i} = {ss}", ss=fmt(ss))
        printf("ss{z} = {ssz}", z=len(ps) + 3, ssz=fmt(ssz))
        printf()
        rs.add(ans)

# output solutions
for (ss, n) in rs.most_common():
  printf("dominoes = {ss} [{n} solutions]", ss=fmt(ss))

      Solution: The required dominoes are: [0-1] [0-5] [1-2] [2-5].

      Here are the 28 dominoes split into 5 piles, and each pile laid out as a square loop:

      [1-0] [0-5] [5-2] [2-1]
      [2-0] [0-3] [3-3] [3-2]
      [0-0] [0-4] [4-3] [3-5] [5-6] [6-0]
      [3-1] [1-4] [4-2] [2-2] [2-6] [6-3]
      [1-1] [1-5] [5-5] [5-4] [4-4] [4-6] [6-6] [6-1]

      The dominoes that make up the answer to the puzzle are those in the first (top-left) square, which has 4 dominoes and 16 pips in total.

      The second (top-right) square uses the double [3-3], which is the largest possible double for a loop with 4 dominoes. It also has 16 pips in total.

      Each of the middle squares consists of 6 dominoes, and has 36 pips in total.

      The bottom square consists of 8 dominoes, uses 4 doubles ([1-1] [5-5] [4-4] [6-6]), and has 64 pips in total.

      There is a further layout that also provides a solution:

      [1-0] [0-5] [5-2] [2-1]
      [2-0] [0-3] [3-3] [3-2]
      [0-0] [0-4] [4-5] [5-3] [3-6] [6-0]
      [3-1] [1-6] [6-2] [2-2] [2-4] [4-3]
      [1-1] [1-4] [4-4] [4-6] [6-6] [6-5] [5-5] [5-1]

      The first two loops are the same as the layout above.

      And of course any loop in a solution can be reflected or rotated.

      Like

      • Brian Gladman's avatar

        Brian Gladman 2:56 pm on 29 November 2024 Permalink | Reply

        @Jim. Your optimisation in this code very is impressive. I have a structurally similar solution but it is painfully slow because it finds the same loops many thousands of times and I have not found a technique for preventing this. I can see that you have managed to do this but I am wondering what principle you have based this on?

        Like

        • Jim Randell's avatar

          Jim Randell 3:08 pm on 29 November 2024 Permalink | Reply

          @Brian: Yes, this was a tricky one to program (even after determining the intended interpretation of the text).

          I used several “normal forms” to eliminate duplicate solutions:

          + for a domino (x, y) the normal form is when x ≤ y. (Otherwise we might also consider (y, x)).

          + for a loop, the normal form is to start with smallest domino (as above), and travel round the loop such that the second domino is less than the final domino. (There are at least 4 dominos in a loop, so these are all different). (Otherwise we could start at any domino, and go round the loop in either direction).

          + for a collection of loops of the same size, I require that they are ordered by the first domino. (Otherwise we might find the same loops in a different order).

          Together these bring the number of solutions down to two different collections of dominoes.

          Liked by 1 person

          • Brian Gladman's avatar

            Brian Gladman 5:15 pm on 29 November 2024 Permalink | Reply

            Thanks Jim, It looks like eliminating duplicate solutions is as much, if not more work, than finding solutions in the first place!

            Like

      • Frits's avatar

        Frits 11:53 am on 12 December 2024 Permalink | Reply

        @Jim,

        If you are only interested in the answer then you might split the cproduct for ss1 and ss2 to two separate loops and do some else/continue/break constructs. This will bring down the run time by a factor 3.

        Also using a simpler normalise() is faster.

        normalise = lambda d: d if d[0] <= d[1] else (d[1], d[0])

        Like

    • Frits's avatar

      Frits 10:59 am on 12 December 2024 Permalink | Reply

      This program runs in 35ms (not as fast as Brian’s recursive program).
      A lot of work again.

      from enigma import SubstitutedExpression

mx_dom = 6

# sorted tuple
stup = lambda s: tuple(sorted(s))
# generate circular pairs
circular = lambda s: set(stup([x, y]) for x, y in zip(s, s[1:] + s[:1]))

# including (x, y) and (y, x)
allcombs = lambda s: s | set((y, x) for x, y in s)
tri = lambda n: n * (n + 1) // 2

# decompose <t> into at least <mn> non-decreasing square piles
def decompose(t, mn=4, ns=[], fn=lambda x: x * x, ss = ()):
  unpack = lambda f: (lambda x: f(*x))
  if t == 0 and len(ss) >= mn:
    # also require that the two smallest values in <ss> are
    # equal and that there is only one largest value
    if ss[0] == ss[1] and ss[-1] > ss[-2]:
      yield ss
  else:
    for i, s in enumerate(ns):
      if t >= fn(s):
        yield from decompose(t - fn(s), mn, ns[i:], fn, ss + (s, ))

# run the SubstitutedExpression with specific expressions
def run(exprs, answer, d2i, syms, s2d=dict(), reorder=0, verbose=0):
  # eg for strip 'a-b-c-d-e-f-g-h-i-j' a must be different from c and i
  distinct = set(x + y if x < y else y + x for x, y in zip(syms, syms[2:] + syms[:2]))

  p = SubstitutedExpression(
      exprs,
      symbols=syms,
      answer=answer,
      d2i=d2i,
      distinct=distinct,
      env=dict(stup=stup, allcombs=allcombs),
      base=mx_dom + 1,
      s2d=s2d,
      digits=(range(mx_dom + 1)),
      reorder=reorder,
      verbose=verbose,  # use 256 to see the generated code
    )
  return tuple(p.answers())

# solve remaining strips after 3 strips are known
def solve(k, strips, pairs, ss=tuple()):
  if k == 0:
    yield ss
  else:
    s_size = strips[0]
    syms = allsyms[:s_size]
    vars = ','.join(syms)
    varlist = "[" + vars + "]"
    pairs4 = f"list(zip({varlist}, [{vars[2:]},{syms[0]}]))"
    s2d = dict()

    exprs = []

    # check if remaining strips all have the same size
    if len(set(strips)) == 1:
      # let strip begin with lowest remaining domino
      low = next(x for x in dominoes if x not in pairs)
      s2d[syms[0]], s2d[syms[1]] = low[0], low[1]
      first_domino_set = 1
    else:
      first_domino_set = 0
      # start with lowest number
      for i in range(1, s_size - 1):
        exprs.append(f"{syms[0]} <= {syms[i]}")

    # try to speed up the process
    #for i in range(2, 3):
    #  exprs.append(f"({syms[i - 1]}, {syms[i]}) not in {pairs}")

    # calculate last variable: sum(syms) * 2 = s_size^2
    exprs.append(f"{s_size**2 // 2} - sum([{vars[:-2]}]) = {syms[-1]}")

    if not first_domino_set:
      exprs.append(f"{syms[0]} <= {syms[-1]}")
    # ABCD <= ADCB
    exprs.append(f"{syms[1]} <= {syms[-1]}")

    # use different dominoes than already used
    exprs.append(f"allcombs(set(p4 := {pairs4})).isdisjoint({pairs})")

    # all dominoes must be unique
    exprs.append(f"len(set([stup([x, y]) for x, y in p4])) == {s_size}")

    # avoid rotations if list starts with a doublet
    exprs.append(f"{syms[0]} != {syms[1]} or "
                 f"{varlist} <= [{syms[1]},{syms[0]},{','.join(syms[2:][::-1])}]")

    answer = "tuple(" + varlist + ")"

    # limit variable values
    if first_domino_set:
      # other values in <syms> may not be smaller than first value
      # and for strip 'a-b-c-d-e-f-g-h-i-j' a must be different from c and i
      d2i = dict([(k, vars[2:]) for k in range(s2d[syms[0]])] +
                 [(s2d[syms[0]], syms[2] + syms[-2])])
      d2i[s2d[syms[1]]] = d2i.get(s2d[syms[1]], "") + syms[3] + syms[-1]
    else:
      # calculate highest possible starting domino
      ln = len(dominoes)
      mx = next(i for i in range(6, -1, -1)
                if ln - dominoes.index((i, i)) >= s_size)
      d2i = dict([(k, vars[0]) for k in range(mx + 1, mx_dom + 1)])

    # solve one strip
    for r in run(exprs, answer, d2i, syms, s2d, reorder=0, verbose=0):
      yield from solve(k - 1, strips[1:], pairs | circular(r), ss + (r, ))

allsyms = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

# the 28 dominoes
dominoes = tuple((i, j) for i in range(mx_dom + 1) for j in range(i, mx_dom + 1))
# the total number of spots
n_spots = sum(a + b for a, b in dominoes)
rt_spots = int(n_spots**.5)

mn_pile = 4 # at least 4 sides
# sum of spots of <n> largest dominoes must be >= n^2
mx_pile = next(i for i in range(rt_spots - rt_spots % 2 , 2, -2)
               if i * i <= sum(a + b for a, b in dominoes[-i:]))
sols = set()

# generate valid piles of strips
for pile in decompose(n_spots, mn_pile, range(mn_pile, mx_pile + 1, 2)):
  # ----------------------
  # get shortest strips
  # ----------------------
  min_strip = pile[0]
  syms = allsyms[:min_strip]
  vars = ','.join(syms)
  varlist = "[" + vars + "]"
  exprs = []
  pairs1 = f"[stup([x, y]) for x, y in zip({varlist}, [{vars[2:]},{syms[0]}])]"
  for i in range(1, min_strip - 1):
    exprs.append(f"{syms[0]} <= {syms[i]}")

  # calculate last variable: sum(syms) * 2 = min_strip^2
  exprs.append(f"{min_strip**2 // 2} - sum([{vars[:-2]}]) = {syms[-1]}")

  exprs.append(f"{syms[0]} <= {syms[-1]}")
  exprs.append(f"{syms[1]} <= {syms[-1]}")  # ABCD <= ADCB
  # strip should have 0 or 1 doublets
  exprs.append(f"len({{{vars}}}) >= {min_strip - 1}")

  # all dominoes must be unique
  exprs.append(f"len(set({pairs1})) = {min_strip}")

  answr = f"next((x for x, y in {pairs1} if x == y), -1), "
  answr += "tuple(" + varlist + ")"
  # calculate highest possible starting domino
  ln = len(dominoes)
  mx = next(i for i in range(6, -1, -1)
            if ln - dominoes.index((i, i)) >= min_strip)
  d2i = dict([(k, vars[0]) for k in range(mx + 1, 10)])
  # reverse sort on doublet
  answs = sorted(run(exprs, answr, d2i, syms, s2d=dict(),
                     reorder=0, verbose=0), reverse=True)

  mx_doublet = answs[0][0]
  # find strips with 1 doublet
  for ans1 in answs:
    if ans1[0] != mx_doublet or ans1[0] == -1: break
    pairs1 = circular(ans1[1])

    # find strips without a doublet
    for ans2 in answs:
      if ans2[0] != -1: continue
      # first 2 strips have to use different dominoes
      if len(pairs12 := pairs1 | circular(ans2[1])) != 2 * min_strip: continue

      # store potential answer
      sol = tuple((x, y) for x, y in zip(ans2[1], ans2[1][1:] + (ans2[1][0], )))
      if sol in sols: continue

      # get all possible pairs of both strips
      pairs12all = allcombs(pairs12)

      # ---------------------------------
      # find longest strip
      # ---------------------------------
      max_strip = pile[-1]
      syms = allsyms[:max_strip]
      mn_doublets = mx_dom // 2 + 1   # minimum number of doublets required

      exprs = []

      # all dominoes are doublets?
      if (all_doublets := (max_strip == 2 * mn_doublets)):
        # create <vars> like A,A,C,C,E,E,G,G
        vars = ','.join(x + "," + x for x in allsyms[:max_strip][::2])
        varlist = "[" + vars + "]"
        pairs3 = f"list(zip({varlist}, [{vars[2:]},{syms[0]}]))"
        for i in range(2, max_strip - 2, 2):
          exprs.append(f"{syms[0]} < {syms[i]}")

        # calculate last variable: sum(syms) * 2 = max_strip^2
        exprs.append(f"div({max_strip**2 // 2} - sum([{vars[:-4]}]), 2) = {syms[-2]}")
        exprs.append(f"{syms[0]} < {syms[-2]}")
      else:
        vars = ','.join(syms)
        varlist = "[" + vars + "]"
        pairs3 = f"list(zip({varlist}, [{vars[2:]},{syms[0]}]))"
        # start strip with the smallest doublet
        exprs.append(f"{syms[0]} = {syms[1]}")
        for i in range(2, max_strip - 1):
          exprs.append(f"{syms[i - 1]} != {syms[i]} or {syms[0]} < {syms[i]}")
          exprs.append(f"({syms[i - 1]}, {syms[i]}) not in {pairs12all}")

        # calculate last variable: sum(syms) * 2 = max_strip^2
        exprs.append(f"{max_strip**2 // 2} - sum([{vars[:-2]}]) = {syms[-1]}")
        exprs.append(f"{syms[0]} <= {syms[-1]}")
        exprs.append(f"{syms[1]} <= {syms[-1]}")    # ABCD <= ADCB
        exprs.append(f"({syms[-1]}, {syms[0]}) not in {pairs12all}")
        # more than half doublets
        exprs.append(f"len({{{vars}}}) <= {pile[-1] - mn_doublets}")

      # use different pairs
      exprs.append(f"allcombs(set(p3 := {pairs3})).isdisjoint({pairs12all})")
      # all dominoes must be unique
      exprs.append(f"len(set([stup([x, y]) for x, y in p3])) == {max_strip}")

      # avoid rotations if strip starts with a doublet
      if all_doublets:
        exprs.append(f"{varlist} <= [{vars[:3]},{vars[4:][::-1]}]")
      else:
        exprs.append(f"{syms[0]} != {syms[1]} or "
                     f"{varlist} <= [{syms[1]},{syms[0]},{','.join(syms[2:][::-1])}]")

      # eg. the four doublets (3, 3)...(6, 6) have too many spots
      max_smallest_doublet = next(i for i in range(max_strip - mn_doublets, -1, -1)
                                  if 4 * (i * mn_doublets + tri(mn_doublets - 1))
                                  <= max_strip**2)

      # limit first domino
      d2i = dict([(k, vars[0]) for k in range(max_smallest_doublet + 1, 10)])
      if all_doublets:
        # if (0, 0) is present then it has to be the first doublet
        d2i[0] = syms[::2][1:]
        d2i[ans1[0]] = syms # exclude the doublet used in shortest strip
      answr = f"tuple(" + varlist + ")"

      for ans3 in run(exprs, answr, d2i, syms, s2d=dict(), reorder=0, verbose=0):
        pairs123all = allcombs(pairs12 | circular(ans3))
        # solve remaining strips
        for s in solve(len(pile) - 3, pile[2:-1], pairs123all):
          sols.add(sol)
          break # as <sol> only depends on 2nd strip
        else: # no break
          continue
        break

for s in sols:
  print("answer:", s)

      Like

  • Unknown's avatar

    Jim Randell 12:22 am on 8 September 2024 Permalink | Reply
    Tags: by: Peter Good   

    Teaser 3233: Not Mrs Perkins’ quilt! 

    From The Sunday Times, 8th September 2024 [link] [link]

    Sue was making a quilt in the shape of an equilateral triangle and she sewed a straight line of stitches from each corner of the quilt to its opposite edge, so as to divide each edge in the ratio 1:2 in a clockwise direction. Sue covered the region enclosed by the lines of stitches with a triangular piece of material of exactly the same size. The area of this piece was 2 square feet.

    Including the triangular quilt and the extra triangular piece, what was the total area of material used?

    Mrs. Perkins’s quilt is a puzzle by Henry Ernest Dudeney from his book “Amusements in Mathematics” (1917).

    [teaser3233]

     
    • Jim Randell's avatar

      Jim Randell 12:41 am on 8 September 2024 Permalink | Reply

      See also: Teaser 2865, Enigma 1076, Enigma 320, Enigma 1313.

      We can solve the puzzle directly using Routh’s Theorem [ @wikipedia ], which I have previously made some notes on here [ rouths-theorem.pdf ]

      In this case we have x = y = z = 2, hence:

      XYZ / ABC = (x − 1)^2 / (x^2 + x + 1)
      XYZ / ABC = 1 / 7

      We are given the area XYZ = 2, hence ABC = 14.

      And the total area of the two triangles is easily calculated.

      from enigma import (rdiv, printf)

# ratio XYZ/ABC in Routh's theorem
def routh(x, y, z):
  a = x * y * z - 1
  b = (x * y + y + 1) * (y * z + z + 1) * (z * x + x + 1)
  return rdiv(a * a, b)

# compute the ratio r = XYZ / ABC
r = routh(2, 2, 2)

# calculate the areas of the triangles
XYZ = 2
ABC = rdiv(XYZ, r)

# calculate the total area
T = ABC + XYZ
printf("total area = {T}")

      Solution: The total area of material used is: 16 square feet.

      Note that the result holds even if the triangle is not equilateral.

      Like

    • GeoffR's avatar

      GeoffR 8:07 am on 8 September 2024 Permalink | Reply 

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

int: x == 2;
int: y == 2;
int: z == 2;
 
var 1..35:ABC;
var 1..5:XYZ; 

% Using Routh's theorem
constraint XYZ * (x*x + x + 1) == ABC * (x - 1 ) * (x - 1);
constraint XYZ * 7 == ABC /\ XYZ == 2;

solve satisfy;
output["Total area = " ++ show(ABC + XYZ) ++ " Sq. Ft."];

      Like

  • Unknown's avatar

    Jim Randell 4:32 pm on 28 June 2024 Permalink | Reply
    Tags: by: Peter Good   

    Teaser 3223: Shaping up 

    From The Sunday Times, 30th June 2024 [link] [link]

    Clark wondered how many different shapes he could draw with identical squares joined edge to edge and each shape containing the same number of squares. He only drew five different shapes containing four squares, for example, because he ignored rotations and reflections:

    He drew all of the different shapes containing 1, 2, 3, 4, 5 and 6 squares and wrote down the total number of different shapes in each case. He took the six totals in some order, without reordering the digits within any total, and placed them end to end to form a sequence of digits which could also be formed by placing six prime numbers end to end.

    In ascending order, what were the six prime numbers?

    [teaser3223]

     
    • Jim Randell's avatar

      Jim Randell 4:53 pm on 28 June 2024 Permalink | Reply

      This is fairly straightforward, if you know how many free n-polyominoes there are of the required sizes. [@wikipedia]

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

      Run: [ @replit ]

      from enigma import (irange, primes, subsets, concat, uniq, ordered, printf)

# number of n-polyominoes (n = 1..6) [see: OEIS A000105]
ns = [1, 1, 2, 5, 12, 35]

# can we split a string into k primes?
def solve(s, k, ps=list()):
  if k == 1:
    p = int(s)
    if p in primes:
      yield ps + [p]
  elif k > 0:
    for n in irange(1, len(s) + 1 - k):
      p = int(s[:n])
      if p in primes:
        yield from solve(s[n:], k - 1, ps + [p])

# collect answers (ordered sequence of primes)
ans = set()
# consider possible concatenated sequences
for s in uniq(subsets(ns, size=len, select='P', fn=concat)):
  # can we split it into 6 primes?
  for ps in solve(s, 6):
    ss = ordered(*ps)
    printf("[{s} -> {ps} -> {ss}]")
    ans.add(ss)

# output solution(s)
for ss in sorted(ans):
  printf("answer = {ss}")

      Solution: The 6 prime numbers are: 2, 2, 5, 5, 11, 13.

      (Although note that they are not 6 different prime numbers).

      The number of free n-polyominoes for n = 1..6 is:

      1, 1, 2, 5, 12, 35

      (i.e. there is only 1 free monomino, going up to 35 free hexominoes).

      And we don’t have to worry about polyominoes with holes, as they don’t appear until we reach septominoes (7-ominoes).

      We can order these numbers as follows:

      1, 12, 1, 35, 2, 5 → “11213525”

      and this string of digits can be split into 6 prime numbers as follows:

      “11213525” → 11, 2, 13, 5, 2, 5

      In fact, we can order the numbers into 24 different strings of digits that can be split into primes, but they all yield the same collection of primes.

      Like

  • Unknown's avatar

    Jim Randell 4:37 pm on 26 April 2024 Permalink | Reply
    Tags: by: Peter Good   

    Teaser 3214: Squaring the square 

    From The Sunday Times, 28th April 2024 [link] [link]

    Clark took a sheet of A4 paper (8.27 × 11.69 inches) and cut out a large square with dimensions a whole number of inches. He cut this into an odd number of smaller squares, each with dimensions a whole number of inches. These were of several different sizes and there was a different number of squares of each size; in fact, the number of different sizes was the largest possible, given the above.

    It turns out that there is more than one way that the above dissection can be made, but Clark chose the method that gave the smallest number of smaller squares.

    How many smaller squares were there?

    [teaser3214]

     
    • Jim Randell's avatar

      Jim Randell 5:55 pm on 26 April 2024 Permalink | Reply

      The largest (integral sized) square that can cut from a sheet of A4 is 8 inches × 8 inches. And in order to get multiple different sizes of smaller square we need at least a 3 × 3 square.

      I am assuming that when the puzzle refers to “more than one way that the dissection can be made”, it means there are multiple different possible sets of smaller squares. (Not the same set just assembled in a different way to form the larger square).

      By using the [[ express() ]] function from the enigma.py library to find candidate dissections, and the rectpack.py library to fit the smaller squares into the larger square, I was able to quickly write a program that runs in a reasonable time.

      However, the rectpack.py library wasn’t designed to handle multiple rectangles of the same shape, and was not as efficient as it could be in this case. So I have updated it to cope better with this situation, and the program now runs even faster.

      The following Python program runs in 95ms. (Internal runtime is 28ms).

      Run: [ @replit ]

      from enigma import (Accumulator, irange, express, multiset, seq_all_different, group, item, printf)
import rectpack

# can we pack the squares?
def pack(n, ms):
  rs = list((x, x) for x in ms.elements())
  for ps in rectpack.pack(n, n, rs):
    return ps  # a single packing will do

# find the largest number of different sizes of smaller square [at least 3]
acc = Accumulator(fn=max, value=3, collect=1)

# consider the size of the larger square
for n in irange(8, 3, step=-1):

  # consider the areas of smaller squares
  ss = list(irange(1, n - 1))

  # decompose n^2 into smaller squares
  for qs in express(n * n, (i * i for i in ss)):
    # there was an odd number of smaller squares
    if sum(qs) % 2 != 1: continue
    # and there were "several" sizes
    k = len(qs) - qs.count(0)
    if k < acc.value: continue
    ms = multiset.from_pairs(zip(ss, qs))
    # and a different number of each size
    if not seq_all_different(ms.values()): continue
    # attempt to pack the squares
    ps = pack(n, ms)
    if ps:
      # record (<size of large square>, <number of smaller squares>, <packing>)
      acc.accumulate_data(k, (n, ms.size(), ps))

if acc.data:
  printf("{acc.value} different sizes of smaller squares")

  # consider possible sizes of larger square
  g = group(acc.data, by=item(0))
  for (k, vs) in g.items():
    # we need multiple ways to dissect the square
    if len(vs) < 2: continue
    printf("{k} x {k} square -> {n} dissections", n=len(vs))
    # find the minimal number of smaller squares
    sm = min(s for (n, s, ps) in vs)
    printf("min {sm} smaller squares")
    for (n, s, ps) in vs:
      if s == sm:
        rectpack.output_grid(n, n, ps, end="--")

      Solution: There were 13 smaller squares.

      The maximum number of different sizes of smaller squares is 4. It is possible to dissect 5×5, 6×6, 7×7, 8×8 using 3 different sizes of smaller squares, but only 8×8 can be dissected into 4 different sizes. So this must be the size of square chosen by Clark.

      An 8×8 square can be dissected into 5 different sets of smaller squares of 4 different sizes, and the smallest of these uses 13 smaller squares.

      A minimal dissection is shown below:

      1 @ 4×4 square [red]
      3 @ 3×3 squares [orange]
      4 @ 2×2 squares [green]
      5 @ 1×1 squares [blue]
      = 13 smaller squares

      Had the puzzle allowed Clark to start with a 9×9 square this can also be dissected into 4 different sizes of smaller squares (but not 5), and so this would give a further answer to the puzzle:

      A 9×9 square can be dissected into 23 different sets of smaller squares of 4 different size, and the smallest of these uses 15 smaller squares.

      The program can be used to investigate extensions to the puzzle for squares up to 12 × 12, after which it gets a bit bogged down.

      Like

    • Frits's avatar

      Frits 5:40 pm on 27 April 2024 Permalink | Reply

      Using SubstitutedExpression to fit pieces into a grid.
      The programs runs in 1.25 seconds (8 or 9 times longer than my similar Python-only program on Brian’s site).

      from enigma import SubstitutedExpression

symbols = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
symbols += "ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖØÙÚÛÜÝÞßàáâãäåæçèéêëìíîïð"

# "these were of several different sizes" (let's say more than three)
min_sizes = 4

# decompose <t> into <k> numbers from <ns> so that sum(<k> numbers) equals <t>
def decompose(t, k=1, ns=[], s=[], mn=min_sizes):
  if k == 1:
    if t in ns and t >= s[-1]:
      s_ = s + [t]
      cnts = [s_.count(x) for x in set(s_)]
      # there was a different number of squares of each size
      if len(cnts) >= mn and len(cnts) == len(set(cnts)):
        yield (s_, cnts)
  else:
    for n in ns:
      if k * n > t: break
      if s and n < s[-1]: continue   # sequence is non-decreasing
      yield from decompose(t - n,  k - 1, ns, s + [n])
 
sqs = [i * i for i in range(1, 9)]

# determine sum of <min_sizes> lowest squares
mand = sum(x * x for x in range(1, min_sizes + 1))

max_diff_sizes = 0
sols = []
# process sizes of the large square (at least 5x5)
for sq in sqs[::-1][:-4]:
  X = int(sq**.5)            # width and height of the large square
  sqs_ = [x for x in sqs if x < sq]
  max_pieces = sq - mand
  # start with a high number of pieces
  for np in range(max_pieces - (max_pieces % 2 == 0), 3, -2):
    # break if triangular root of <np> get's too low
    if int(0.5 * ((8 * np + 1)**.5 - 1.0)) < max_diff_sizes: break
    
    # make total <sq> from small squares
    for p, cnts in decompose(sq, np, sqs_):
      # ignore entries with too few different sizes
      if (ln := len(cnts)) >= max_diff_sizes:
        pieces = [int(x**.5) for x in p[::-1]]
        topleft = [symbols[2 * i:2 * i + 2] for i in range(np)]
        sizes = [symbols[2 * np + i] for i in range(np)]
        s2d = dict(zip(sizes, pieces))
       
        answer = ', '.join(str('(({' + x[0] + '}, {' + x[1] + '}), \
                 {' + sizes[i] + '})') \
                 for i, x in enumerate(topleft) if s2d[sizes[i]] > 1)
        answer = f"{answer}"

        # invalid digit / symbol assignments
        d2i = {i: set() for i in range(len(pieces))}
        for i, p in enumerate(pieces):
          # make sure we don't cross the boundaries
          for d in range(X - p + 1, 10):
            vs = set()
            vs.update(topleft[i][0])
            vs.update(topleft[i][1])
            d2i[d] |= vs

        placed = [(topleft[0], sizes[0])]
        # build expressions
        exprs = []
        for i in range(1, np):
          piece = symbols[2 * i:2 * i + 2]
          sz = sizes[i]
          if s2d[sz] == 1: break  # pieces of dimensions 1 always fit
          for tl, s in placed:
            # squares may not overlap
            exprs.append(f"({{{tl[0]}}} + {{{s}}} <= {{{piece[0]}}} or "
                         f"{{{piece[0]}}} <= {{{tl[0]}}} - {{{sz}}}) or "
                         f"({{{tl[1]}}} + {{{s}}} <= {{{piece[1]}}} or "
                         f"{{{piece[1]}}} <= {{{tl[1]}}} - {{{sz}}})")             
          placed.append((piece, sz))  
      
        #for e in exprs: print(e); 
        #print()

        # the alphametic puzzle
        p = SubstitutedExpression(
          exprs,
          base=X,
          answer=answer,
          d2i=d2i,
          s2d=s2d,
          distinct="",
          verbose=0,    # use 256 to see the generated code
        )

        # print answers
        for ans in p.answers():
          if ln > max_diff_sizes:
            sols = []
          # store data, count of smallest piece first
          sols.append((pieces.count(min(pieces)), np, pieces))
          break # we need only one solution
          
        max_diff_sizes = len(cnts)          

if len(sols) < 2:
  print("no multiple dissections have been found")
else: 
  # print the solution with the the smallest number of smaller squares
  for n_smallest, m, pieces in sorted(sols):
    print("answer:", m, "\n")
    print("pieces:", *[(x, x) for x in pieces], "\n")
    break

      Like

      • Jim Randell's avatar

        Jim Randell 10:45 am on 3 May 2024 Permalink | Reply

        @Frits: An inventive use of the [[ SubstitutedExpression ]] solver.

        But I think the puzzle is asking for a dissection that uses the minimum number of pieces in total, rather than a dissection that has the minimum number of smallest pieces. (Although it turns out these are the same for the given constraints).

        Like

        • Frits's avatar

          Frits 8:24 pm on 3 May 2024 Permalink | Reply

          Yes, I got confused with the phrase “smallest number of smaller squares”.

          I also have a Python only version that first performs the express calls for all “n” using the Boecker-Liptak Money Changing [https://enigmaticcode.wordpress.com/2020/09/21/enigma-946-patterns-of-fruit/#comment-9773] and then reorders this list on the number of different pieces and number of pieces before packing.

          The A1 format (n=23) can be done in 165 seconds:

          29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 28 28 28 28 28 28 27 27
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 28 28 28 28 28 28 27 27
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 28 28 28 28 28 28 26 26
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 28 28 28 28 28 28 26 26
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 28 28 28 28 28 28 25 25
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 28 28 28 28 28 28 25 25
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 24 24 24 24 24 23 23 23
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 24 24 24 24 24 23 23 23
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 24 24 24 24 24 23 23 23
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 24 24 24 24 24 22 22 22
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 24 24 24 24 24 22 22 22
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 21 21 21 20 19 22 22 22
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 21 21 21 18 18 18 18 18
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 21 21 21 18 18 18 18 18
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 17 17 17 18 18 18 18 18
16 16 16 16 16 16 15 15 15 15 14 14 14 14 13 17 17 17 18 18 18 18 18
16 16 16 16 16 16 15 15 15 15 14 14 14 14 12 17 17 17 18 18 18 18 18
16 16 16 16 16 16 15 15 15 15 14 14 14 14 11 11 11 11 11 11 10 10 10
16 16 16 16 16 16 15 15 15 15 14 14 14 14 11 11 11 11 11 11 10 10 10
16 16 16 16 16 16  9  9  9  9  8  8  8  8 11 11 11 11 11 11 10 10 10
16 16 16 16 16 16  9  9  9  9  8  8  8  8 11 11 11 11 11 11  7  7  7
 6  6  5  5  4  3  9  9  9  9  8  8  8  8 11 11 11 11 11 11  7  7  7
 6  6  5  5  2  1  9  9  9  9  8  8  8  8 11 11 11 11 11 11  7  7  7

          There are combinations of pieces that are hard to for the pack routine.

          Like

  • Unknown's avatar

    Jim Randell 4:34 pm on 1 March 2024 Permalink | Reply
    Tags: by: Peter Good   

    Teaser 3206: Support measures 

    From The Sunday Times, 3rd March 2024 [link] [link]

    Two buildings on level ground with vertical walls were in need of support so engineers placed a steel girder at the foot of the wall of one building and leaned it against the wall of the other one. They placed a shorter girder at the foot of the wall of the second building and leaned it against the wall of the first one. The two girders were then welded together for strength.

    The lengths of the girders, the heights of their tops above the ground, the distance between their tops and the distance between the two buildings were all whole numbers of feet. The weld was less than ten feet above the ground and the shorter girder was a foot longer than the distance between the buildings.

    What were the lengths of the two girders?

    [teaser3206]

     
    • Jim Randell's avatar

      Jim Randell 4:53 pm on 1 March 2024 Permalink | Reply

      See: Enigma 775 for the calculation of the height of the weld above the ground.

      If the distance between the buildings is d, and the girders have lengths g1 and g2, and the top ends of the girders meet the walls at heights of h1 and h2, and cross each other at a height of H, and the tops are a distance z apart, then we have the following three Pythagorean triangles:

      (d, h1, g1)
      (d, h2, g2)
      (d, h1 − h2, z)

      subject to:

      h1 > h2
      g2 = d + 1
      H = (h1 × h2) / (h1 + h2) < 10

      This Python program considers possible Pythagorean triangles for the girders (up to a reasonable maximum length).

      It runs in 59ms. (Internal runtime is 409µs).

      from enigma import (defaultdict, pythagorean_triples, ihypot, fdiv, printf)

# index pythagorean triples by non-hypotenuse sides
ts = defaultdict(list)
for (x, y, z) in pythagorean_triples(250):
  ts[x].append((y, z))
  ts[y].append((x, z))

# consider possible distances
for (d, vs) in ts.items():
  # the second girder
  for (h2, g2) in vs:
    if not (g2 == d + 1): continue

    # the first girder
    for (h1, g1) in vs:
      if not (h1 > h2): continue
      # check the height of the weld is < 10
      if not (h1 * h2 < 10 * (h1 + h2)): continue
      # calculate the distance between the tops
      z = ihypot(h1 - h2, d)
      if z is None: continue

      # output solution
      H = fdiv(h1 * h2, h1 + h2)
      printf("g1={g1} g2={g2}; h1={h1} h2={h2} H={H:.2f}; d={d} z={z}")

      Solution: The girders were 109 ft and 61 ft long.

      The distance between the buildings is 60 ft, so the girders reach 11 ft and 91 ft up the walls, and the weld is about 9.81 ft above the ground (= 1001/102). The tops of the girders are 100 ft apart.

      Without the restriction on the height of the weld there is a further theoretical solution where the buildings are 6160 ft apart, and the girders have lengths of 9050 ft and 6161 ft (they reach 6630 ft and 111 ft up the buildings, and cross at a height of 109.17 ft).

      But this is the only other solution for girders with lengths up to 10 million feet.

      Like

      • Frits's avatar

        Frits 8:09 am on 2 March 2024 Permalink | Reply

        @Jim, you seem to reject the possibility of h1 = 2 * h2 as then the “ts” entry may only have 2 entries.

        Like

        • Jim Randell's avatar

          Jim Randell 8:18 am on 2 March 2024 Permalink | Reply

          @Frits: Yes, I was supposing the three Pythagorean triangles were all different. Which is not necessarily the case.

          Like

      • Frits's avatar

        Frits 1:42 pm on 2 March 2024 Permalink | Reply

        Using analysis of my other program.

        from enigma import (defaultdict, pythagorean_triples, subsets)

# set of valid widths
ws = {2 * n * (n + 1) for n in range(1, 10)}

M = 2717 # maximum any length
# index pythagorean triples by non-hypotenuse sides
ts = defaultdict(list)
for (x, y, z) in pythagorean_triples(M):
  if x in ws:
    ts[x].append((y, z))
  if y in ws:
    ts[y].append((x, z))

# smaller height must be less than 20
for k, vs in sorted(ts.items()):
  svs = sorted(vs)
  # pick two Pythagorean triangles
  for (c1, c2) in subsets(svs, 2):
    if c1[0] > 19: break
    if 2 * c1[0] == c2[0]:
      print(f"answer: {c1[1]} and {c2[1]}")

  # pick three Pythagorean triangles
  for (c1, c2 ,c3) in subsets(svs, 3):
    if c1[0] > 19: break
    if c1[0] + c2[0] == c3[0]:
      print(f"answer: {c1[1]} and {c3[1]}")
      if c2[0] < 20:
        print(f"    or  {c2[1]} and {c3[1]}")

        Like

      • Frits's avatar

        Frits 2:05 pm on 2 March 2024 Permalink | Reply

        Similar

            
from enigma import (defaultdict, pythagorean_triples, subsets)

# set of valid widths
ws = {2 * n * (n + 1) for n in range(1, 10)}

M = 2717 # maximum any length 
# index pythagorean triples by non-hypotenuse sides
ts = defaultdict(list)
for (x, y, z) in pythagorean_triples(M):
  if x in ws: 
    ts[x].append((y, z))
  if y in ws:
    ts[y].append((x, z))

# smaller height must be less than 20
for k, vs in sorted(ts.items()):
  svs = sorted(vs)
  # pick two Pythagorean triangles
  for (c1, c2) in subsets(svs, 2):
    if c1[0] > 19: break
    if 2 * c1[0] == c2[0]:
      print(f"answer: {c1[1]} and {c2[1]}")
    
    if (c3 := (m := (c1[0] + c2[0]), (k**2 + m**2)**.5)) in vs: 
      print(f"answer: {c1[1]} and {c3[1]}")
      if c2[0] < 20:
        print(f"    or  {c2[1]} and {c3[1]}")

        Like

        • Frits's avatar

          Frits 2:23 am on 5 March 2024 Permalink | Reply

          To explore the full solution set we can use maximum length 16199:

          # w^2 + h^2 = z^2   (with even w) 
# look for hypotenuse <z> so that (z + 1)^2 - z^2 > w^2
M = (max(ws)**2 - 1) // 2   # maximum any length

          Like

    • Frits's avatar

      Frits 8:05 am on 2 March 2024 Permalink | Reply

      There is an upper bound for the width and/or smaller height but not always for the greater height.

          
from enigma import is_square

#   |\     |        whole numbers: g1, g2, h1, h2, g3 and w
#   | \    |        g1^2 = h1^2 + w^2
# h1|  \g1 |        g2^2 = h2^2 + w^2
#   |   \ _/        g3^2 = (h1 - h2)^2 + w^2
#   | g2/\ |h2      g2 = w + 1 
#   |_/___\|        h3 < 10
#       w            

# h2^2 = g2^2 - w^2 = 2w + 1

# we have:
# 1/h3 = 1/h1 + 1/h2 with h3 < 10

# 1/h1 + 1/h2 > 0.1  or 10 * (h1 + h2) > h1 * h2)
# (h2 - 10) * h1 < 10 * h2 or h1 < 10 * h2 / (h2 - 10)

# also h1 > h2 so when is 10 * h2 / (h2 - 10) equal to h2?
# h2^2 - 20h2 = 0, h2(h2 - 20) = 0 --> h2 = 20 
# w < 200 and h2 < 20 

# h2 must be odd as h^2 = 2w + 1 --> h2 = 2n + 1, h2 < 20, n < 10
for n in range(1, 10):
  h2 = 2 * n + 1
  # h2^2 = 4n^2 + 4n + 1 = 2w + 1
  w = 2 * n * (n + 1)
  w2 = w * w
  ub_h1, r = divmod(10 * h2, h2 - 10)
  if not r: 
    ub_h1 -= 1
  if ub_h1 < 0: 
    ub_h1 = 2717 # Burj Khalifa

  for h1 in range(h2 + 1, ub_h1 + 1):
    if not (g1 := is_square(h1**2 + w2)): continue
    if not (g3 := is_square((h1 - h2)**2 + w2)): continue
    print(f"answer: {(g2 := w + 1)} and {g1}")

      Like

    • GeoffR's avatar

      GeoffR 2:29 pm on 2 March 2024 Permalink | Reply

      Using WP Reader to post a MiniZinc solution.

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

% Assumed UB of 120 for the six integers required
var 1..120:g1; var 1..120:g2; var 1..120:g3; var 1..120:w;
var 1..120:h1; var 1..120:h2; var 1.0..10.0:h3;

% Reusing Frits diagram for this solution
% g1 and g2 are the girder lengths, w is width between walls
% h1 and h2 are wall heights where girders meet the walls
% g3 is the distance between their tops, h3 the weld height

constraint g2 == w + 1 /\ g2 < g1;
constraint g1 * g1 == h1 * h1 + w * w;
constraint g2 * g2 == h2 * h2 + w * w;
constraint g3 * g3 == (h1 - h2) * (h1 - h2) + w * w;

solve satisfy;

output["g1, g2, g3 = " ++ show([g1, g2, g3]) ++
"\n" ++ "h1, h2, w = " ++ show([h1, h2, w]) ];

      Like

      • Jim Randell's avatar

        Jim Randell 7:47 am on 3 March 2024 Permalink | Reply

        @GeoffR: I think for a complete solution you also need a constraint for the weld height (although in this case it doesn’t eliminate any solution candidates).

        My MiniZinc specification looks like this:

        %#! python3 -m minizinc use_embed=1

{var("1..250", ["d", "g1", "g2", "h1", "h2", "z"])};

predicate is_pythagorean(var int: x, var int: y, var int: z)
  = (x * x + y * y = z * z);

% first girder
constraint is_pythagorean(d, h1, g1);

% second girder
constraint is_pythagorean(d, h2, g2);
constraint h2 < h1;
constraint g2 = d + 1;

% weld height H = (h1 * h2) / (h1 + h2)
constraint h1 * h2 < 10 * (h1 + h2);

% tops
constraint is_pythagorean(d, h1 - h2, z);

solve satisfy;

        Like

    • GeoffR's avatar

      GeoffR 4:31 pm on 3 March 2024 Permalink | Reply

      @Jim:

      A neat MiniZinc solution.

      Yes, the weld height would give a complete solution, although this is not a strict requirement of the teaser description.

      I was more interested in the derivation of your formula for the weld height.

      If x is the distance from left wall h1 to the weld height (h3), by similar triangles:

      h3/x = h2/w and h1/w = h3/(w – x).

      Algebraic manipulation gives 1/h3 = 1/h1 + 1/h2
      or h3 = h1.h2/(h1 + h2).

      As Brian has mentioned to me, this is the same formula in optics for the focal length, object and image distances, or two resistors in parallel.

      Like

    • Frits's avatar

      Frits 7:06 am on 5 March 2024 Permalink | Reply

      I believe this program fully explores the solution set (without calculating complex upper bounds).

      from math import isqrt

# for any pythagorean triangle with side y and hypothenuse z: 
# if z = y + i then the square of other side = 2 * i * y + i^2

# index pythagorean triples by non-hypotenuse sides
# set of valid widths (h2 = 2n + 1)
ts = {w: [(dm[0], dm[0] + i) for i in range(w - 2, 0, -2) 
          if (dm := divmod(w**2 - i**2, 2 * i))[1] == 0] 
          for w in [2 * n * (n + 1) for n in range(1, 10)]}

# smaller height must be less than 20
for n, (w, vs) in enumerate(ts.items(), start=1):
  # set up pythagorean triangle for smaller height 
  t1 = (2 * n + 1, w + 1) 
  # pick other Pythagorean triangles
  for t2 in vs:
    if t2 == t1: continue
    
    # we have a solution if greater height is double the small height
    if 2 * t1[0] == t2[0]:
      print(f"answer: {t1[1]} and {t2[1]} feet")
    
    # for non-hypotenuse sides h2 and (h1 - h2) check if h1^2 + w^2 is square
    if (z := isqrt((z2 := w**2 + (t1[0] + t2[0])**2)))**2 == z2:
      print(f"answer: {t1[1]} and {z} feet")
      if t2[0] < 20:
        print(f"    or  {t2[1]} and {z} feet")

      Like

      • Jim Randell's avatar

        Jim Randell 2:32 pm on 5 March 2024 Permalink | Reply

        @Frits: Well done on reaching a complete solution.

        I have to admit I just did a search for “longest steel girder” and chose a suitable upper value. (And I was surprised that the actual answer involved girders that were so long).

        But I thought I would do a complete solution too:

        If we know one of the non-hypotenuse sides of a Pythagorean triangle, say a in the triple (a, b, c), where c is the hypotenuse, then we have:

        a² = c² − b² = (c + b)(c − b)

        So by dividing a² into 2 divisors (say x and y), then we can find potential (b, c) pairs to make a Pythagorean triple as follows:

        b = |x − y| / 2
        c = (x + y) / 2

        And there are only a finite number of divisor pairs, so there are only a finite number Pythagorean triangles that share a leg.

        We can now provide a complete solution to the problem.

        As Frits notes above, h2 must be an odd number between 3 and 19, and for a given value of h2 we can recover the distance between the buildings d and the length of the shorter girder g2:

        d = (sq(h2) − 1) / 2
        g2 = d + 1

        So we can consider possible values for h2, calculate the corresponding value for d and then generate all possible Pythagorean triangles that have one leg d, and look for those with a longer g1 and corresponding h1, and then we can check for those that give an integer distance between the tops.

        This Python program has an internal runtime of 442µs.

        Run: [ @replit ]

        from enigma import (irange, sq, div, ihypot, divisors_pairs, fdiv, printf)

# h2 is odd, < 20
for h2 in irange(3, 19, step=2):
  d = div(sq(h2) - 1, 2)
  g2 = d + 1

  # look for pythagorean triples with a leg of d
  for (y, x) in divisors_pairs(d, 2):
    (h1, g1) = (div(x - y, 2), div(x + y, 2))
    if (not h1) or (not g1): continue
    # does this give a longer girder
    if not (g1 > g2): continue
    # check weld height H < 10
    if not (h1 * h2 < 10 * (h1 + h2)): continue
    # check distance between tops
    z = ihypot(d, h1 - h2)
    if z is None: continue
    # output solution
    H = fdiv(h1 * h2, h1 + h2)
    printf("g1={g1} g2={g2}; h1={h1} h2={h2} H={H:.2f}; d={d} z={z}")

        Like

        • Frits's avatar

          Frits 1:32 am on 8 March 2024 Permalink | Reply

          @Jim, I keep forgetting this trick.

          Processing the divisor pairs in reverse order allows for an early break with respect to the weld height check.

          Like

  • Unknown's avatar

    Jim Randell 4:37 pm on 8 December 2023 Permalink | Reply
    Tags: by: Peter Good   

    Teaser 3194: A proper lesson 

    From The Sunday Times, 10th December 2023 [link] [link]

    A maths teacher wrote a sequential list of numbers 1, 2, 3, 4, … on the blackboard and asked her pupils to find a pair of positive fractions adding up to 1. The pair was to have the two numerators and two denominators consisting of four different numbers from her list. They found all possible pairs.

    She then told them to group two of the pairs that used eight different numbers from her list, which was just long enough to enable them to do this. The class found all possible groups. One of the groups contained some fractions that were not used by any other group.

    Which of the teacher’s numbers were not used by that group?

    [teaser3194]

     
    • Jim Randell's avatar

      Jim Randell 4:56 pm on 8 December 2023 Permalink | Reply

      This Python program considers increasing maximum values written on the blackboard, and collects new pairs of fractions as they become available, until it is possible to form groups consisting of 2 pairs that use 8 different numbers in the fractions.

      It then examines the groups found to determine which of them contain fractions that only occur in that group, and these groups provide the answer.

      It runs in 53ms. (Internal runtime is 519µs).

      Run: [ @replit ]

      from enigma import (
  irange, inf, fraction, multiset, subsets, flatten, diff, chunk, join, sprintf as f, printf
)

# format a list of numbers as fraction sums
fmt = lambda ns: join((f("{a}/{b} + {c}/{d} = 1") for (a, b, c, d) in chunk(ns, 4)), sep="; ")

# collect possible pairs of fractions a/b + c/d = 1
ps = list()
# consider increasing 1..n values
for n in irange(4, inf):
  np = len(ps)
  # add in a/b, c/n pairs
  for c in irange(1, n - 1):
    (a, b) = (p, q) = fraction(1, 1, -c, n)
    while b < n:
      ns = (a, b, c, n)
      if len(set(ns)) == 4:
        ps.append(ns)
      a += p
      b += q
  if n < 8 or len(ps) == np: continue

  # find possible groups, and count occurrences of fractions
  (gs, m) = (list(), multiset())
  for ns in subsets(ps, size=2, fn=flatten):
    if len(set(ns)) == 8:
      printf("[n={n}: {ns}]", ns=fmt(ns))
      gs.append(ns)
      m.update_from_seq(chunk(ns, 2))
  if not gs: continue

  # find groups that contain fractions that only occur in one group
  for ns in gs:
    if any(m.count(x) == 1 for x in chunk(ns, 2)):
      # output solution
      ans = diff(irange(1, n), ns)
      printf("unused = {ans} [{ns}]", ans=join(ans, sep=", ", enc="()"), ns=fmt(ns))

  # we only need the smallest n that forms groups
  break

      Solution: The unused numbers are 7 and 8.

      The teacher wrote the numbers 1 .. 10 on the board.

      This gives 17 possible pairs of fractions that sum to 1:

      1/2 + 3/6 = 1
      2/4 + 3/6 = 1
      1/3 + 4/6 = 1
      3/4 + 2/8 = 1
      1/2 + 4/8 = 1
      3/6 + 4/8 = 1
      1/4 + 6/8 = 1
      4/6 + 3/9 = 1
      1/3 + 6/9 = 1
      4/5 + 2/10 = 1
      3/5 + 4/10 = 1
      1/2 + 5/10 = 1
      2/4 + 5/10 = 1
      3/6 + 5/10 = 1
      4/8 + 5/10 = 1
      2/5 + 6/10 = 1
      1/5 + 8/10 = 1

      Note that fractions do not have to be in their lowest terms, so 1/2 and 3/6 are considered to be different fractions (with the same value).

      These can be formed into 9 groups that use 8 distinct numbers in the fractions:

      1/2 + 3/6 = 1; 4/8 + 5/10 = 1
      2/4 + 3/6 = 1; 1/5 + 8/10 = 1
      1/2 + 4/8 = 1; 3/6 + 5/10 = 1
      3/6 + 4/8 = 1; 1/2 + 5/10 = 1
      4/6 + 3/9 = 1; 1/2 + 5/10 = 1
      4/6 + 3/9 = 1; 1/5 + 8/10 = 1
      1/3 + 6/9 = 1; 4/5 + 2/10 = 1 [*]
      1/3 + 6/9 = 1; 2/4 + 5/10 = 1
      1/3 + 6/9 = 1; 4/8 + 5/10 = 1

      And it is not possible to form any groups using 1 .. 8 or 1 .. 9, so 1 .. 10 is the smallest set of initial numbers on the blackboard.

      Of the fractions used in these groups, only 4/5 and 2/10 appear in only one group [*], and this group is:

      1/3 + 6/9 = 1; 4/5 + 2/10 = 1

      And so the 2 numbers on the blackboard that are not used in any of these four fractions are 7 and 8.

      Like

    • Frits's avatar

      Frits 10:50 am on 9 December 2023 Permalink | Reply 

       
# numbers 1, 2, 3, ..., n, we need 2 groups with in total 8 different numbers
n = 8   
while True:
  # determine numbers (a, b, c, d) do that a/b + c/d = 1 with c > a
  abcd = set((a, b, c, d)
             for a in range(1, n // 2 + n % 2)
             for b in range(a + 1, n + 1)
             for c in range(a + 1, n + 1)
             if c != b and \
             not (dm := divmod(b * c, b - a))[1] and \
             c < (d := dm[0]) <= n and d != b)
  
  # find 2 groups of <abcd> entries that use 8 different numbers among them
  two_groups = [(s1[:2], s1[2:], s2[:2], s2[2:]) for s1 in abcd for s2 in abcd
                if s1[0] < s2[0] and len(set(s1 + s2)) == 8]  
  
  if not two_groups: 
    n += 1   # try numbers 1, 2, 3, ..., n
    continue
  
  # one of the groups contained some fractions 
  # that were not used by any other group
  all_fractions = [f for g2 in two_groups for f in g2]
  unique_fractions = {f for f in all_fractions if all_fractions.count(f) == 1}
  
  for g2 in two_groups:
    # does a fraction in <g2> only occur in our <g2>?
    if any(f for f in g2 if f in unique_fractions):
      used = set(y for x in g2 for y in x)
      print(f"unused numbers: "
            f"{[i for i in range(1, n + 1) if i not in used]}")
            
  break

      Like

      • Frits's avatar

        Frits 12:36 pm on 9 December 2023 Permalink | Reply

        Slower but more compact.

           
from itertools import permutations
n = 8 
while True:
  # determine different numbers (a, b, c, d, e, f, g, h) so that 
  # a/b + c/d = 1 and e/f + g/h = 1 with c > a, g > e and a < e
  abcdefgh = [((a, b), (c, d), (e, f), (g, h)) 
               for a, b, c, d, e, f, g, h in permutations(range(1, n + 1), 8)
               if a < b and c < d and e < f and g < h and 
               a < c and e < g and a < e and 
               a * d + b * c == b * d and e * h + f * g == f * h]
  
  if not abcdefgh: 
    n += 1   # try numbers 1, 2, 3, ... for a higher n
    continue
  
  # one of the groups contained some fractions 
  # that were not used by any other group
  all_fractions = [fr for f4 in abcdefgh for fr in f4]
  unique_fractions = {f for f in all_fractions if all_fractions.count(f) == 1}
  
  for f4 in abcdefgh:
    # does a fraction in <f4> not occur in any other <abcdefg> entry?
    if any(f for f in f4 if f in unique_fractions):
      used = set(y for x in f4 for y in x)
      print(f"unused numbers: "
            f"{[i for i in range(1, n + 1) if i not in used]}")
            
  break  # we are done

        Like

  • Unknown's avatar

    Jim Randell 4:19 pm on 29 September 2023 Permalink | Reply
    Tags: by: Peter Good   

    Teaser 3184: Four away 

    From The Sunday Times, 1st October 2023 [link] [link]

    The rectangular snooker table had four corner pockets and two centre pockets (one each in the middle of the left and right sides, which were 12ft long). A ball always left the cushions at the same angle as it struck them. The cue ball was by the bottom right corner pocket and Joe hit it off the left cushion; it bounced off another seven cushions without hitting a ball or entering a pocket, then entered the right centre pocket. Four away!

    Joe replayed the shot but the cue ball hit the left cushion further up the table than before, bounced another ten times without hitting a ball or entering a pocket, then entered the right centre pocket. Four away!

    How much further up the table did the second shot hit the left cushion?

    [teaser3184]

     
    • Jim Randell's avatar

      Jim Randell 5:02 pm on 29 September 2023 Permalink | Reply

      (See also: Teaser 1917 and Teaser 3129).

      Fairly straightforward with some graph paper to find paths between the bottom right and centre right pockets that hit exactly 8 and 11 cushions.

      These give the angle of the shot, from which we can calculate the distance between the respective first bounces, and this gives the answer to the puzzle.

      Run: [ @replit ]

      from enigma import (Rational, irange, is_coprime, printf)

Q = Rational()

# g: bounce -> [((x, y), angle), ...]
g = { 8: [], 11: [] }

# consider bounces between (0, 0) and (x, y)
for y in irange(1, 24, step=2):
  for x in irange(2, 12, step=2):
    # check ball doesn't hit a pocket early
    if not is_coprime(x, y): continue
    # calculate number of bounces from (0, 0)
    b = (x - 1) + y // 2
    if b not in g: continue
    # calculate the angle
    t = Q(y, x)
    if t < 2:
      g[b].append(((x, y), t))

# look for 8 bounces
for ((x1, y1), t1) in g[8]:
  # look for 11 bounces, with a higher angle
  for ((x2, y2), t2) in g[11]:
    if not (t2 > t1): continue
    printf("(0, 0) -> ({x1}, {y1}) = 8 bounces [t = {t1}]")
    printf("-> (0, 0) -> ({x2}, {y2}) = 11 bounces [t = {t2}]")
    # calculate distance between first bounces
    d = 6 * (t2 - t1)
    printf("--> answer = {d:.2f} ft", d=float(d))

      Solution: The second shot hit the left cushion 4.5 feet further up the table than the first shot.

      In the following diagram the original table is in the bottom right corner, and the other rectangles are reflections of the table. We want to find paths between the red pocket in the extreme bottom right and a green pocket, that cross the boundaries of the table (the black lines) 8 and 11 times, but do not hit any intermediate pockets.

      The two paths are shown as dotted lines.

      We can denote the 8-bounce path is (8, 3) (i.e. 8 units horizontally, and 3 units vertically), and the 11-bounce path is (8, 9).

      There is a further 8-bounce path at (6, 7) and further 11-bounce path at (12, 1), but these are not involved in the answer to the puzzle.

      And here are the two paths (8-bounce = red, 11-bounce = green) plotted on the table:

      Like

  • Unknown's avatar

    Jim Randell 4:29 pm on 26 May 2023 Permalink | Reply
    Tags: by: Peter Good,   

    Teaser 3166: All their marbles 

    From The Sunday Times, 28th May 2023 [link] [link]

    In their art class, Jack and Jill each had a box of spherical glass marbles. Each box contained marbles of at least three different sizes, and the radius of every marble was a whole number of cm.

    Jack placed three marbles of equal size from his box onto a desk, and placed each of the other [sizes] in turn on top so that all four marbles touched each other and formed a triangular pyramid. He worked out the height of each pyramid (from desk to top of top marble) and obtained a different whole number of cm each time.

    Jill was also able to do this with her marbles but they were all of different sizes to Jack’s.

    None of the pyramids was higher than 30cm.

    List all of the different marble radii in ascending order.

    [teaser3166]

     
    • Jim Randell's avatar

      Jim Randell 5:53 pm on 26 May 2023 Permalink | Reply

      Presumably “at least three” is “exactly three”, otherwise there would be multiple solutions.

      But I think this puzzle is flawed. We don’t find 2 possible sets of marbles that satisfy the specified conditions of the puzzle. Although by increasing the maximum allowable pyramid height we can find a solution to the puzzle as worded. But these involve quite sizeable marbles (using mm instead of cm would make the puzzle more reasonable).

      By calculating the height h of the the (not regular) tetrahedron formed by the centres of the spheres we can determine the height of a pyramidal configuration of spheres, and reject non-viable configurations. And we can then look for disjoint sets of three spheres (a base size and two viable top sizes) for Jack and Jill that give valid configurations.

      Run: [ @replit ]

      from enigma import (
  irange, subsets, sq, is_square, group, item, delete,
  cproduct, disjoint_union, arg, printf
)

MAX_H = arg(30, 0, int)  # max pyramid height
MAX_R = (MAX_H - 1) // 2  # max sphere radius

# calculate integer height of a pyramid configuration
# with base spheres radius <R> and top sphere radius <r>
def height(R, r):
  if R % 3 != 0: return
  # vertical height between centres of spheres = h
  h = is_square(sq(r) + 2 * R * r - sq(R) // 3)
  if h is None: return
  H = h + R + r
  # check it is a valid pyramid
  if not (H > 2 * R): return
  return H

# generate possible base/top radii
def generate():
  # consider possible radii
  for (R, r) in subsets(irange(1, MAX_R), size=2, select="P"):
    # calculate height of the pyramid = H
    H = height(R, r)
    # check it forms a pyramid with H not exceeding MAX_H
    if H is None or H > MAX_H: continue
    printf("[R={R} r={r} -> H={H}]")
    yield (R, r)

# group top radii by base radius
g = group(generate(), by=item(0), f=item(1))
# discard sets with fewer than 3 different sizes
g = delete(g, (k for (k, vs) in g.items() if len(vs) < 2))

# look for 2 disjoint sets of 3 radii
for ((k1, vs1), (k2, vs2)) in subsets(g.items(), size=2):
  for (ts1, ts2) in cproduct(subsets(vs, size=2) for vs in (vs1, vs2)):
    ss = disjoint_union([ts1, ts2, [k1, k2]])
    if ss is None: continue
    # output solution
    printf("radii = {ss} [base = {k1} + tops = {ts1}; base = {k2} + tops = {ts2}]", ss=sorted(ss))

      My interpretation of the puzzle text is that in order for the marbles to form a structure that could be described as a triangular pyramid, the uppermost point of the top marble in the arrangement must project above the uppermost points of the three marbles forming the base. So that three planar triangles, each supported by two of the base marbles and the top marble, would form the inclined faces of a triangular based pyramid that exactly encloses the marbles.

      However, with this interpretation, there is no solution to the puzzle with the restrictions given.

      If we increase the maximum allowed height of the arrangements (to between 72 and 95), we can find a unique solution using valid pyramids:

      set 1 = (7, 12, 14) [base = 12, top = 7 → height = 32; base = 12, top = 14 → height 48]
      set 2 = (13, 18, 21) [base = 18, top = 13 → height 54; base = 18, top = 21 → height 72]

      And this gives an answer of: (7, 12, 13, 14, 18, 21).

      The marbles are quite large though, so perhaps this would work better if the radii were specified in millimetres instead of centimetres.

      Another way to find a solution is to abandon the requirement for a “triangular pyramid” arrangement, and just place the three base marbles on the desk, touching each other in a triangular arrangement, and then place the fourth marble on top of these. And we measure the elevation of the uppermost point of the top marble above the desk. (We don’t care if this is below the level of the uppermost points of the base marbles, or at the same level).

      And using such arrangements we can get a unique solution within the height restriction given in the puzzle text:

      set 1 = (1, 6, 7) [base = 6, top = 1 → height 8; base = 6, top = 7 → height 24]
      set 2 = (2, 4, 12) [base = 12, top =2 → height 16; base = 12, top 4 → height 24]

      Which gives an answer of: (1, 2, 4, 6, 7, 12).

      And it seems likely this is the intended solution.

      The published solution is: “1, 2, 4, 6, 7 and 12 cm”.

      Like

      • Frits's avatar

        Frits 9:52 pm on 26 May 2023 Permalink | Reply

        @Jim, using r = R in your height formula I don’t recognize the published height of a tetrahedron with 2 layers (2r(1 + sqrt(2/3)).

        No idea yet how to find the formula myself.

        Like

        • Jim Randell's avatar

          Jim Randell 10:01 pm on 26 May 2023 Permalink | Reply

          That is exactly what you get from my formula when R = r:

          H = 2r + √(r² +2r² − r²/3)
          H = 2r + √(8r²/3)
          H = 2r + 2r√(2/3)
          H = 2r(1 + √(2/3))

          The formula itself comes from a bit of trigonometry on a triangle whose hypotenuse connects the centres of the top sphere and one of the base spheres.

          Like

          • Frits's avatar

            Frits 10:38 pm on 26 May 2023 Permalink | Reply

            OK, I thought “h” was the height of the pyramid.

            Like

          • Frits's avatar

            Frits 11:01 pm on 26 May 2023 Permalink | Reply

            I verified your formula (using the formula for the distance between the centre of an equilateral triangle and any of its vertices)

            Like

      • Jim Randell's avatar

        Jim Randell 10:59 pm on 27 May 2023 Permalink | Reply

        If we ignore all the stuff about making “pyramids”, and just arrange 3 marbles of the same size in a triangular arrangement on the desk, with each marble touching the other two, and then place a different size fourth marble on top of these three marbles in the hollow between the lower three marbles. We can then measure the distance between the surface of the desk and the top of the fourth marble. And it is this distance we require to be an integer.

        With this wording the puzzle does have a unique solution, with distances not exceeding 30cm, and it is quite possible these are the sets the setter was intending us to find.

        My program (above) can be adapted for this scenario by removing the validity check at line 18.

        I’ve also uploaded a more generic program that allows you to experiment with various criteria for valid configurations. [@replit]

        Like

  • Unknown's avatar

    Jim Randell 4:30 pm on 17 March 2023 Permalink | Reply
    Tags: by: Peter Good   

    Teaser 3156: Balancing act 

    From The Sunday Times, 19th March 2023 [link] [link]

    A circus elephant standing on one end of a see-saw pivoted at the centre was balanced by a troupe of fewer than 20 acrobats, each of equal weight, standing on the other end. The elephant moved forwards and several acrobats jumped off to maintain balance. The elephant moved backwards and some of them climbed back on to the end to rebalance.

    The elephant always moved a prime number of feet and there was always a prime number of acrobats on the see-saw. If I told you how far backwards the elephant moved you could work out the numbers of acrobats.

    (In equilibrium, the product of weight and distance from pivot point must be the same on both sides).

    How far did the elephant move backwards, and how many acrobats are there in the troupe?

    [teaser3156]

     
    • Jim Randell's avatar

      Jim Randell 5:24 pm on 17 March 2023 Permalink | Reply

      I think it is necessary to assume that the elephant did not return to its original position. (i.e. “some of them” is interpreted as “some (but not all) of them”).

      So we suppose that we start off with a see-saw of length 2d and a unit weight acrobats on one end (a is a prime number, less than 20). They are balanced by an elephant of weight a on the other end.

      The elephant then moves forwards (towards the pivot) p feet (p is a prime number), and some of the acrobats jump off, leaving b acrobats balancing the elephant (b is a prime number, less than a):

      a . (d − p) = b . d

      The elephant then moves backwards (away from the pivot) q feet (q is a prime number, less than p), and some of the acrobats remount to make c acrobats balancing the elephant (c is a prime number, between b and a):

      a . (d − p + q) = c . d

      From these two equations we can determine p in terms of q and a, b, c:

      p . (c − b) = q . (a − b)

      There are only a certain number (a, b, c) values, so we can look at possible values for q, and see if there is only a single set of (a, b, c) values that give a viable value of p.

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

      Run: [ @replit ]

      from enigma import (primes, subsets, div, inf, fdiv, printf)

# collect possible (a, b, c) numbers of acrobats
abcs = list((a, b, c) for (b, c, a) in subsets(primes.between(2, 20), size=3))

# consider the distance the elephant moves back = q
for q in primes.irange(2, inf):
  # find viable p values
  ps = list()
  for (a, b, c) in abcs:
    p = div(q * (a - b), c - b)
    if p and p > q and p in primes:
      ps.append((a, b, c, p))
  if len(ps) == 1:
    (a, b, c, p) = ps[0]
    printf("q={q} -> a={a} b={b} c={c} p={p}; d={d:g}", d=fdiv(a * q, c - b))
    break

      Solution: The elephant moved backwards 11 ft. There are 19 acrobats in the troupe.

      The see-saw is 19 feet either side of the pivot (i.e. end to end length is 38 feet).

      And initially there are 19 acrobats on one end, balanced by an elephant that weighs the same as 19 acrobats on the other end.

      The elephant moves forward by 17 ft, so it is 2 ft from the pivot, and this is balanced by 2 acrobats 19 ft from the pivot (19 × 2 = 2 × 19).

      The elephant then moves backwards by 11 ft, so it is 13 ft from the pivot. And this is balanced by 13 acrobats 19 ft from the pivot (19 × 13 = 13 × 19).

      There are 16 candidate solutions.

      q=2 ⇒ 6 candidates
      q=3 ⇒ 6 candidates
      q=5 ⇒ 3 candidates
      q=11 ⇒ 1 candidate

      So the answer is found from q = 11.

      Like

      • Jim Randell's avatar

        Jim Randell 11:53 am on 18 March 2023 Permalink | Reply

        Even shorter (and exhaustive):

        q / p = (c − b) / (a − b)

        and both p and q are primes, so can be determined from their ratio.

        Run: [ @replit ]

        from enigma import (primes, subsets, fraction, filter_unique, item, fdiv, printf)

# generate candidates (p, q, a, b, c)
def candidates():
  for (b, c, a) in subsets(primes.between(2, 20), size=3):
    (q, p) = fraction(c - b, a - b)
    if primes.is_prime(q) and primes.is_prime(p):
      yield (p, q, a, b, c)

# find solutions unique by q (= item 1)
for (p, q, a, b, c) in filter_unique(candidates(), item(1)).unique:
    printf("q={q} -> a={a} b={b} c={c} p={p}; d={d:g}", d=fdiv(a * q, c - b))

        Like

    • Jim Randell's avatar

      Jim Randell 8:27 am on 18 March 2023 Permalink | Reply

      @GeoffR: I think 5 is also a prime.

      And there are additional candidate solutions where the length of the see-saw is not an even integer number of feet. But the length of the see-saw can be eliminated from the equations to keep the remaining variables integers. (Although it would be possible to also specify the see-saw length as an integer number of inches).

      Like

    • GeoffR's avatar

      GeoffR 10:00 am on 18 March 2023 Permalink | Reply 

      
from itertools import permutations
from enigma import is_prime

from collections import defaultdict
nums = defaultdict(list)

primes = (2, 3, 5, 7, 11, 13, 17, 19)

for acrobats in permutations(primes, 3):
  # A1 = full acrobat troupe
  # A2 = acrobats after elephant moves forward
  # A3 = acrobats after elephant then moves backwards
  A1, A2, A3 = acrobats
  if A1 > A2 and A1 > A3 and A2 < A3:
    # for intial balancing of elephant v. troupe
    # elephants weight = weight of acrobat troupe
    E = A1
    # assume max. half seesaw length = 25 ft.
    for dist in permutations(range(1, 26), 3):
      half_see_saw, p1, p2 = dist
      if p2 < p1 and is_prime(p1) and is_prime(p2):
        # Taking moments about centre pivot
        if (half_see_saw - p1) * E == half_see_saw * A2:
          if (half_see_saw - p1 + p2) * E ==  half_see_saw * A3:
            # index dictionary on distance elephant moved backwards
            nums[p2] += [(p1, p2, A1, A2, A3)]

# find a single solution
for k,v in nums.items():
    if len(v) == 1:
      print(f"Distance elephant moves backward = {k} ft.")
      print(f"Number of acrobats in troupe = {v[0][2]}.")

      Like

  • Unknown's avatar

    Jim Randell 4:26 pm on 16 December 2022 Permalink | Reply
    Tags: by: Peter Good   

    Teaser 3143: Pipe fittings 

    From The Sunday Times, 18th December 2022 [link] [link]

    A plumber had three thin metal pipes with square, rectangular and elliptical cross-sections. In order to fit them into his van, he slid the rectangular pipe inside the elliptical pipe and the elliptical pipe inside the square pipe, before placing the pipe assembly in the van. There are four points where the pipes all touch, as shown in the diagram. The maximum and minimum widths of the elliptical and rectangular pipes and the diagonal width of the square pipe were all even numbers of mm less than 1000, of which one was a perfect square.

    What were the five widths (in increasing order)?

    [teaser3143]

     
    • Jim Randell's avatar

      Jim Randell 5:20 pm on 16 December 2022 Permalink | Reply

      If we consider the diagram to be centred on the origin (0, 0), and the point where all four figures meet in the (+, +) quadrant is (x, y), then the rectangle has dimensions (2x, 2y) and the diagonal of the square is 2z where z = x + y.

      And if the ellipse has semi-major axis a and semi-minor axis b, then the equation of the tangent at the point (p, q) is:

      x(p/a²) + y(q/b²) = 1

      and this is the same as the line that defines the side of the square tube:

      x + y = z

      Hence:

      a² = x.z
      b² = y.z

      Assuming exactly one of the required widths is a perfect square gives a unique answer to the puzzle.

      This Python program runs in 134ms. (Internal runtime is 76ms).

      Run: [ @replit ]

      from enigma import (irange, decompose, is_square, icount_exactly as icount, printf)

# choose a value for z
for z in irange(5, 499):
  # consider values for x and y
  for (y, x) in decompose(z, 2, increasing=1, sep=1, min_v=1):
    # calculate values for a and b
    a = is_square(x * z)
    b = is_square(y * z)
    if a and b:
      # calculate the widths (in increasing order)
      ws = sorted(2 * n for n in (a, b, x, y, z))
      # check exactly one of the widths is a perfect square
      if icount(ws, is_square, 1):
        # output solution
        printf("ws={ws} [z={z} x={x} y={y} a={a} b={b}]")

      Solution: The widths are (in mm): 180, 300, 320, 400, 500.

      Swapping [[ icount_exactly() ]] for [[ icount_at_least() ]] reveals 4 further solutions, so it is necessary to assume exactly one of the widths is a perfect square.

      Solutions with at least one perfect square are:

      (36, 60, 64, 80, 100) [3]
      (144, 240, 256, 320, 400) [3]
      (180, 300, 320, 400, 500) [1]
      (100, 260, 576, 624, 676) [3]
      (324, 540, 576, 720, 900) [3]

      Like

      • Jim Randell's avatar

        Jim Randell 6:09 pm on 16 December 2022 Permalink | Reply

        Or we can use the [[ pythagorean_triples() ]] function from the enigma.py library to get a more efficient program.

        This Python program runs in 58ms. (Internal runtime is 777µs).

        Run: [ @replit ]

        from enigma import (pythagorean_triples, div, sq, is_square, icount_exactly as icount, printf)

# generate values for a, b, z, st: a^2 + b^2 = z^2
for (b, a, z) in pythagorean_triples(499):
  # calculate x and y
  (x, y) = (div(sq(n), z) for n in (a, b))
  if x is None or y is None: continue
  # calculate the widths (in increasing order)
  ws = sorted(2 * n for n in (a, b, x, y, z))
  # check exactly one of the widths is a perfect square
  if icount(ws, is_square, 1):
    # output solution
    printf("ws={ws} [z={z} a={a} b={b} x={x} y={y}]")

        Like

    • GeoffR's avatar

      GeoffR 4:51 pm on 17 December 2022 Permalink | Reply 

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

% x, y = rectangle dimensions and a,b ellipse semi major/minor axes
var 4..498:x; var 4..498:y;
var 4..498:a; var 4..498:b;
var 4..498:z;

constraint a > b /\ z = x + y;

% Using Jim's derivation and named variables
constraint a * a == x * z /\ b * b == y * z;

predicate is_sq(var int: m) =
exists(n in 1..ceil(sqrt(int2float(ub(m))))) (n*n = m );

constraint sum([is_sq(2*a), is_sq(2*b), is_sq(2*x),
 is_sq(2*y), is_sq(2*z)]) == 1;

solve satisfy;

output ["Five widths [2a, 2b, 2x, 2y, 2z ] = " ++ 
show([2*a, 2*b, 2*x, 2*y, 2*z])];

      Like

  • Unknown's avatar

    Jim Randell 4:00 pm on 15 October 2022 Permalink | Reply
    Tags: by: Peter Good,   

    Teaser 3134: Stringing along [revised] 

    From The Sunday Times, 16th October 2022 [link] [link]

    An artist hammered thin nails from a pack of 40 into a board to form the perimeter of a rectangle with a 1 cm gap between adjacent nails. He created a work of art by stringing a long piece of wire from one nail to another, such that no section of wire was parallel to an edge of the rectangle. The wire started and ended at two different nails, no nail was used more than once and the length of the wire was a whole number of cm. No longer wire was possible that satisfied the above conditions.

    What were the dimensions of the rectangle and the length of the wire chain (in cm)?

    This is a revised version of the puzzle posted as Teaser 3134. The underlined text has been changed from the previously published version on The Sunday Times website.

    This is the version of the puzzle that appeared in the printed newspaper.

    [teaser3134]

     
    • Jim Randell's avatar

      Jim Randell 4:01 pm on 15 October 2022 Permalink | Reply

      Having solved the (more general) previously published version of this puzzle [link], it is a simple case of adapting my program to account for the additional condition.

      For this version I am assuming we want to find the maximum achievable total length of wire between the nails that can be made using a rectangle constructed from up to 40 nails, with the wire strung between nails where no nail is used more than once and consecutive nails are on different edges of the rectangle (i.e. each linear section of wire must cross part of the interior of the rectangle, and be a whole number of centimetres long), and no linear section of wire is parallel to the edges of the rectangle.

      You can think of the wire being available in various stiff lengths with looped ends, but these individual links can only ever fit between nails that are a whole number of centimetres apart. We wish to make a chain of these wire links, where each link goes from the end of the previous link to a currently unoccupied nail. What is the longest possible chain that can be made, on a rectangle whose perimeter is constructed from no more than 40 nails spaced 1 cm apart, where each link must cross the interior of the rectangle not parallel to the edges of the rectangle, and the start and end of the complete chain are on different nails.

      This Python program runs in 104ms.

      Run: [ @replit ]

      from enigma import (irange, ihypot, chain, Accumulator, printf)

# generate possible <x> by <y> rectangles, using (up to) <n> nails
def generate(n):
  for y in irange(2, n // 4):
    for x in irange(2, (n - 2 * y) // 2):
      yield (x, y)

# find paths by adding nails to <vs>
def solve(x, y, nails, vs, d=0):
  # return the current path
  yield (d, vs)
  # choose the next nail
  (x1, y1) = vs[-1]
  for v in nails:
    (x2, y2) = v
    (dx, dy) = (x2 - x1, y2 - y1)
    if dx == 0 or dy == 0: continue
    dd = ihypot(dx, dy)
    if dd is not None:
      yield from solve(x, y, nails.difference([v]), vs + [v], d + dd)

# collect maximal distance paths
r = Accumulator(fn=max, collect=1)

# consider possible rectangles
for (x, y) in generate(40):
  # collect possible edge nails
  nails = set()
  for i in irange(0, x - 1):
    nails.update([(i, 0), (x - i, y)])
  for i in irange(0, y - 1):
    nails.update([(0, y - i), (x, i)])
  # start in the bottom/left quadrant
  botm = ((i, 0) for i in irange(0, x // 2))
  left = ((0, i) for i in irange(1, y // 2))
  for v in chain(botm, left):
    for (d, vs) in solve(x, y, nails.difference([v]), [v]):
      r.accumulate_data(d, (x, y, vs))

# output solution(s)
printf("max wire length = {r.value} cm")
for (x, y, vs) in r.data:
  printf("-> {x} cm by {y} cm grid {vs}")

      Solution: The rectangle was 12 cm × 8 cm. The total length of wire used was 102 cm.

      Here is a diagram of the maximal length layout:

      Like

      • Jim Randell's avatar

        Jim Randell 11:28 am on 28 October 2022 Permalink | Reply

        In my program above, in order to get a total distance that is a whole number we require the individual segments between consecutive pins in the stringing to be a whole number.

        This is a reasonable assumption. As we can show that if we have a collection of positive integers, and at least one of them has a square root that is irrational, then the sum of the square roots of the entire collection is irrational. (See below [*]).

        However, this does not mean we cannot construct stringings that are very close to an integer value using segments that are not themselves integers. And this lets us find solutions that are much longer than the published solution.

        For example here is a stringing on the 12cm × 8 cm grid that has a total length of 440.999925 cm (i.e. 750 nanometres short of 441 cm). It would be practically impossible to tell this apart from a 441 cm length of wire.

        Note that in this construction every pin is visited.

        If we want more accuracy we can get within 6nm of 438 cm.

        [*] The core of the proof is:

        Suppose x, y are integers, such that at least one of √x and √y are irrational.

        Then (x − y) is also an integer, and:

        (x − y) = (√x + √y)(√x − √y)

        If (√x + √y) is rational (= p), then:

        (√x − √y) = (x − y)/(√x + √y) is also rational (= q)

        But then:

        √x = (p + q)/2 is rational; and
        √y = (p − q)/2 is rational

        Which is a contradiction, hence the sum (√x + √y) is irrational.

        Like

    • Hugh Casement's avatar

      Hugh Casement 10:16 am on 16 October 2022 Permalink | Reply

      The change in wording makes quite a difference to the total length, at least with the solution I worked out.

      The puzzle does not seem to be well thought out. That the nails are thin clearly means that we are to ignore their diameter (and the thickness of the wire). But with centimetres as the unit they are not nails at all but pins, and it’s fine fuse wire. Inches would have been somewhat less unrealistic.

      I also feel that if the “artist” had allowed himself more nails, the resulting pattern could have been more interesting. For example, 12 occurs in the Pythagorean triangles (9, 12, 15) and (12, 16, 20) as well as (5, 12, 13), which would presumably give more scope. But the length + width of the rectangle must not exceed 20, so we are much restricted.

      Like

      • Jim Randell's avatar

        Jim Randell 12:03 pm on 17 October 2022 Permalink | Reply

        @Hugh: Yes for the original wording I found a maximal solution with 24 links. For this revised version there are only 10 links. The rectangle was the same in both cases.

        Like

  • Unknown's avatar

    Jim Randell 4:35 pm on 14 October 2022 Permalink | Reply
    Tags: by: Peter Good   

    Teaser 3134: Stringing along 

    From The Sunday Times, 16th October 2022 [link]

    An artist hammered thin nails from a pack of 40 into a board to form the perimeter of a rectangle with a 1 cm gap between adjacent nails. He created a work of art by stringing a long piece of wire from one nail to another, such that consecutive nails were on different edges of the rectangle. The wire started and ended at two different nails, no nail was used more than once and the length of the wire was a whole number of cm. No longer wire was possible that satisfied the above conditions.

    What were the dimensions of the rectangle and the length of the wire chain (in cm)?

    The wording of this puzzle was later revised. The underlined section was changed to a more restrictive condition.

    See: Teaser 3134: Stringing along [revised] for the revised puzzle.

    [teaser3134]

     
    • Jim Randell's avatar

      Jim Randell 5:07 pm on 14 October 2022 Permalink | Reply

      (Note: It seems that my initial interpretation of the puzzle may not be the intended one. See below for a more likely interpretation).

      It seems we would need to know the dimensions of the rectangle before we determined the maximum length of wire. I considered all rectangles that can be constructed using 40 nails, and found the maximum possible length of wire that touches each edge of the rectangle no more than once.

      This Python program tries all possible rectangles, and all possible stringings.

      It runs in 275ms.

      Run: [ @replit ]

      from enigma import (irange, inf, subsets, tuples, hypot, intr, Accumulator, printf)

# generate possible <x> by <y> rectangles, using <n> nails
def generate(n):
  for y in irange(3, inf):
    x = (n - 2 * y) // 2
    if x < 3: break
    yield (x, y)

# calculate length of wire required between points <vs>
def dist(vs):
  d = 0
  for ((x1, y1), (x2, y2)) in tuples(vs, 2):
    d += hypot(x2 - x1, y2 - y1)
  if abs(d - intr(d)) < 1e-6:
    return d

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

# consider possible rectangles
for (x, y) in generate(40):
  # choose top, bottom nails
  for (x1, x2) in subsets(irange(1, x - 1), size=2, select="R"):
    (T, B) = ((x1, y), (x2, 0))
    # choose left, right nails
    for (y1, y2) in subsets(irange(1, y - 1), size=2, select="P"):
      (L, R) = ((0, y1), (x, y2))
      # calculate possible lengths
      for vs in [(T, R, B, L), (T, R, L, B), (T, B, R, L)]:
        d = dist(vs)
        if d is None: continue
        printf("[({x}, {y}) {d:g} = {vs}]")
        r.accumulate_data(d, (x, y, vs))

printf("max wire length = {r.value:g} cm")
for (x, y, vs) in r.data:
  printf("-> {x} cm by {y} cm grid {vs}")

      Solution: The rectangle was 6 cm × 14 cm, and the wire was 37 cm long.

      This program finds what I assume is the required answer (where each section of the wire is an integer length). But by changing the tolerance at line 15 we can find a longer wire that is sufficiently close to an exact whole number of centimetres that it would be physically impossible to determine that it wasn’t.

      So we can create a stringing on a 6 cm × 14 cm rectangle that uses 40.0007 cm of wire.

      And also a stringing on a 4 cm × 16 cm rectangle that uses 44.99 cm of wire.

      Like

      • Jim Randell's avatar

        Jim Randell 11:19 pm on 14 October 2022 Permalink | Reply

        Using a different (and more likely) interpretation of the problem (see below), where each edge of the rectangle may be visited many times (and allowing the corner nails to be used), but each linear section of wire is a whole number of centimetres, we can get a much longer wire.

        To be clear: I am assuming we want to find the maximum achievable total length of wire between the nails that can be made using a rectangle constructed from up to 40 nails, with the wire strung between nails where no nail is used more than once and consecutive nails are on different edges of the rectangle (i.e. each linear section of wire must cross part of the interior of the rectangle, and be a whole number of centimetres long).

        Here is a quick program to explore that (although there may be some duplication in the patterns found).

        It runs in 942ms.

        Run: [ @replit ]

        from enigma import (irange, ihypot, chain, Accumulator, printf)

# generate possible <x> by <y> rectangles, using (up to) <n> nails
def generate(n):
  for y in irange(2, n // 4):
    for x in irange(2, (n - 2 * y) // 2):
      yield (x, y)

# find paths by adding nails to <vs>
def solve(x, y, nails, vs, d=0):
  # return the current path
  yield (d, vs)
  # choose the next nail
  (x1, y1) = vs[-1]
  for v in nails:
    (x2, y2) = v
    (dx, dy) = (x2 - x1, y2 - y1)
    if dx == 0 and (x1 == 0 or x1 == x): continue
    if dy == 0 and (y1 == 0 or y1 == y): continue
    dd = ihypot(dx, dy)
    if dd is not None:
      yield from solve(x, y, nails.difference([v]), vs + [v], d + dd)

# collect maximal distance paths
r = Accumulator(fn=max, collect=1)

# consider possible rectangles
for (x, y) in generate(40):
  # collect possible edge nails
  nails = set()
  for i in irange(0, x - 1):
    nails.update([(i, 0), (x - i, y)])
  for i in irange(0, y - 1):
    nails.update([(0, y - i), (x, i)])
  # start in the bottom/left quadrant
  botm = ((i, 0) for i in irange(0, x // 2))
  left = ((0, i) for i in irange(1, y // 2))
  for v in chain(botm, left):
    for (d, vs) in solve(x, y, nails.difference([v]), [v]):
      r.accumulate_data(d, (x, y, vs))

# output solution(s)
printf("max wire length = {r.value} cm")
for (x, y, vs) in r.data:
  printf("-> {x} cm by {y} cm grid {vs}")

        Solution: The rectangle was 12 cm × 8 cm. The total length of wire used was 258 cm.

        Here is a diagram of one maximal length arrangement (there are several):

        Like

    • Brian Gladman's avatar

      Brian Gladman 9:56 pm on 14 October 2022 Permalink | Reply

      The answer for this one depends on the assumptions being made. I found a different answer by assuming that the wire length was exact and that not all nails are used. I then looked for a number of Pythagorean triangle hypotenuses with a maximum sum (not necessarily alternating x, y edges).

      Like

      • Jim Randell's avatar

        Jim Randell 10:51 pm on 14 October 2022 Permalink | Reply

        @Brian: I was assuming that each edge of the rectangle was only used once (and the corners not at all). But the puzzle text only says consecutive nails are on different edges, so if we can visit edges more than once then we can use much more wire. (And get a more artful display into the bargain).

        In this case I assumed distance between each consecutive pair of nails was an exact whole number of cm, so that the total length of the wire is as well.

        (Although it still seems like we would need to know the size of the rectangle the artist had constructed before we could find the maximum length of wire he could use).

        Like

  • Unknown's avatar

    Jim Randell 4:32 pm on 20 May 2022 Permalink | Reply
    Tags: by: Peter Good,   

    Teaser 3113: The plumber’s buckets 

    From The Sunday Times, 22nd May 2022 [link] [link]

    A plumber was trying to empty a tank containing 100 litres of water using three buckets, each marked with a different whole number of litres capacity between 10 and 20 litres. He calculated that he could exactly empty the tank, but only by using all three buckets and completely filling each bucket a different number of times.

    He filled and emptied each bucket the calculated number of times but the tank still contained 6 litres of water, because the smallest bucket had a dent that reduced its capacity by 3 litres.

    What were the marked capacities of the three buckets?

    The version of this puzzle that appears in the book The Sunday Times Teasers Book 2 (2023) is as follows (with modified sections underlined):

    A plumber was trying to empty a tank containing 100 litres of water using three buckets, each marked with a different whole number of litres capacity between 10 and 20 litres. He calculated that he could exactly empty the tank, but only by using all three buckets.

    He then emptied the tank as calculated, filling each bucket a different number of times, but then found the tank still contained 6 litres of water, because the smallest bucket had a dent that reduced its capacity by 3 litres.

    What were the marked capacities of the three buckets?

    This corresponds to my own re-wording of the puzzle given in the comments.

    [teaser3113]

     
    • Jim Randell's avatar

      Jim Randell 4:51 pm on 20 May 2022 Permalink | Reply

      Perhaps I misread this puzzle, but I couldn’t find a solution that fits the text.

      However, I did find a solution where the dent reduces the capacity of the largest bucket (not the smallest) by 3 litres. This is my preferred way to “rescue” the puzzle, as it is a minimal change to the text, and the dent would be less noticeable in the largest bucket. However, another way to rescue the puzzle (but with a different solution) is if the capacity of the smallest bucket is reduced by 2 litres (not 3 litres).

      This Python program runs in 58ms.

      Run: [ @replit ]

      from enigma import (
  irange, subsets, express, seq_all_different as all_different,
  singleton, printf
)
 
# choose the labelled capacities of the buckets
for bs in subsets(irange(10, 20), size=3):
  # there is only one way to use the buckets
  qs = singleton(express(100, bs))
  if qs is None: continue
  # each bucket is used
  if 0 in qs: continue
  # the number of uses are all different
  if not all_different(qs): continue
  # largest [was: smallest] bucket must be used twice
  if qs[-1] != 2: continue
  printf("bs={bs} qs={qs}")

      Solution: The puzzle, as originally worded, has no solution.

      If we look for combinations of (correctly labelled) buckets that can be used (completely filling each bucket a number of times) to empty a 100 litre tank, such that all three buckets must be used, each of them a different number of times, we find there are 5 viable combinations (buckets × uses):

      (11, 18, 19) × (4, 1, 2)
      (12, 17, 18) × (1, 2, 3)
      (12, 17, 18) × (4, 2, 1)
      (13, 15, 19) × (1, 2, 3)
      (15, 18, 19) × (3, 2, 1)

      (And if we require there to be only a single way to use the buckets we can discard the (12, 17, 18) combination, leaving only 3 viable combinations).

      The original text asked for a combination where the smallest bucket was used twice, but as we see there are no such combinations.

      In my rescued version, where the largest bucket (not the smallest) has the dent, the solution is that the buckets are labelled (11, 18, 19) litres (although they are actually (11, 18, 16) litres).

      The published solution was that the buckets are labelled (13, 17, 19) litres (although they are actually (10, 17, 19) litres). Which corresponds to my re-wording of the puzzle given below.

      However we can use (correctly labelled) buckets (13, 17, 19) to empty the tank in the following ways:

      1× 13 + 4× 17 + 1× 19 = 100
      2× 13 + 1× 17 + 3× 19 = 100

      So it is not true to say that it can “only [be done] by using all three buckets and completely filling each bucket a different number of times”. (The first line achieves the required result using two of the buckets the same number of times). Hence the requirement for rewording of the puzzle.

      But if we suppose “the calculated number of times” requires that there is only one possible way to fill the buckets, then the reworded puzzle also has no solutions. (As there are 2 ways to use these (correctly labelled) buckets to empty the tank).

      It is possible that the setter intended that when the plumber sat down to work out how many times to use the buckets, he only considers using each bucket a different number of times. He tried using just one bucket and found it was not possible, then he tried using combinations of two buckets and found none of those were possible, and finally he tried using all three buckets and found that there was a single way they could be used. And he then proceeded to use this calculated number of ways, but when he finished there was 6 litres remaining in the tank, because the smallest bucket’s capacity was reduced by 3 litres from the labelled capacity.

      In this scenario, there are 9 candidate bucket combinations, and only one of them has the smallest bucket having 2 uses, so this gives a unique solution, and it is the published solution.

      The published solution is: “13, 17 and 19 litres”.

      Like

      • Jim Randell's avatar

        Jim Randell 5:58 pm on 20 May 2022 Permalink | Reply

        This might be a stricter interpretation of the puzzle text, which finds a couple more candidate solutions. But still doesn’t find a solution that fits the text.

        Instead I have coded it to find the same solution I found above.

        There remains an issue as to whether “he filled and emptied each bucket the calculated number of times” is intended to imply that there is only a single way of filling the buckets (each a different non-zero number of times), or he chose one from multiple viable ways. Fortunately this does not change the answer to my “rescued” version of the puzzle.

        This Python program runs in 56ms. (Internal run time is 1.58ms).

        Run: [ @replit ]

        from enigma import (irange, subsets, express, seq_all_different as all_different, printf)

# find viable ways to use the buckets
def buckets(t, bs):
  rs = list()
  for qs in express(t, bs):
    # each bucket is used
    if 0 in qs: return []
    # the numbers of uses are all different
    if not all_different(qs): return []
    # is viable
    rs.append(qs)
  return rs

# choose the labelled capacities of the buckets
for bs in subsets(irange(10, 20), size=3):
  # find viable ways to use the buckets
  for qs in buckets(100, bs):
    # largest [was: smallest] bucket must be used twice
    if qs[-1] != 2: continue
    # output solution
    printf("bs={bs} qs={qs}")

        The interpretation of the puzzle text where there is just a single way to fill the buckets can be implemented at line 13 by only returning the list of candidates if it has a length of 1. But this doesn’t change the answer found.

        Like

      • Frits's avatar

        Frits 5:59 pm on 20 May 2022 Permalink | Reply

        Correct, with SubstitutedExpression I end up with 3 options (the third solution would be if the capacity of the smallest bucket is reduced by 1.5 litres).

        Like

      • Jim Randell's avatar

        Jim Randell 8:26 am on 21 May 2022 Permalink | Reply

        It has been suggested to me that the intended interpretation of this puzzle is more like this (with {{ changed sections }} in double braces):

        A plumber was trying to empty a tank containing 100 litres of water using three buckets, each marked with a different whole number of litres capacity between 10 and 20 litres. {{ He calculated that by completely filling each bucket a number of times, he could exactly empty the tank, but only by using all three buckets. }}

        He filled and emptied each bucket the calculated number of times, {{ each bucket being used a different number of times. But when he finished }} the tank still contained 6 litres of water, because the smallest bucket had a dent that reduced its capacity by 3 litres.

        What were the marked capacities of the three buckets?

        To solve this formulation of the puzzle we can take my program and just move the “different number of times” test (line 10 in the program above is moved to line 18 below):

        Run: [ @replit ]

        from enigma import (irange, subsets, express, seq_all_different as all_different, printf)

# find viable ways to use the buckets
def buckets(t, bs):
  rs = list()
  for qs in express(t, bs):
    # each bucket is used
    if 0 in qs: return []
    # is viable
    rs.append(qs)
  return rs

# choose the labelled capacities of the buckets
for bs in subsets(irange(10, 20), size=3):
  # find viable ways to use the buckets
  for qs in buckets(100, bs):
    # the numbers of uses are all different
    if not all_different(qs): continue
    # smallest bucket must be used twice
    if qs[0] != 2: continue
    # output solution
    printf("bs={bs} qs={qs}")

        Like

      • Mark Valentine's avatar

        Mark Valentine 12:00 pm on 22 May 2022 Permalink | Reply

        I think the text is absolutely fine. Clearly you need three different bucket sizes, where no two (or one) of which can combine to make exactly 100. Then from these triples you apply the condition for the smallest bucket size.

        Like

        • Jim Randell's avatar

          Jim Randell 12:27 pm on 22 May 2022 Permalink | Reply

          @Mark: You also need to check that the numbers of uses of each bucket are all different. And where this requirement is placed in the puzzle text makes a difference.

          The original puzzle text has no solutions. My revised text does have a unique solution. (And it seems that this revised text corresponds to the intended puzzle).

          Like

          • Mark Valentine's avatar

            Mark Valentine 9:00 pm on 22 May 2022 Permalink | Reply

            Ok to be fair I didn’t check for uniqueness . Just stopped at a solution. so will defer.

            Like

    • Hugh+Casement's avatar

      Hugh+Casement 9:47 am on 21 May 2022 Permalink | Reply

      I don’t see that changing the passages in double braces makes any difference!

      Does the clue lie in “but only by using all three buckets” ?
      That is to say, no (different) integer multiples of any two undented buckets would sum to 100 litres.

      Like

      • Jim Randell's avatar

        Jim Randell 10:03 am on 21 May 2022 Permalink | Reply

        There is a subtle difference between “but only using all three buckets” and “but only using all three buckets, each a different number of times” that stops the puzzle from working in the originally published formulation.

        The “using all three buckets” requirement means we can’t use buckets with capacity 10 or 20, as then we could exactly empty the tank using just one of them. Similarly if a collection of buckets includes a pair that can be used to exactly empty the tank then that is also disallowed.

        Like

        • Hugh+Casement's avatar

          Hugh+Casement 12:23 pm on 21 May 2022 Permalink | Reply

          Yes, but he used the buckets the calculated number of times.

          Like

    • J Slusar's avatar

      J Slusar 6:55 pm on 21 May 2022 Permalink | Reply

      But what is wrong with buckets marked 13, 14 and 15 filling the smallest twice, the middle one once and the larger one 4 times? The total would have been 100, but the reduced capacity of the smaller bucket would mean 6 litres remained in the tank?

      Like

      • Jim Randell's avatar

        Jim Randell 10:01 pm on 21 May 2022 Permalink | Reply

        Thanks for the comment.

        I think this combination is ruled out by the requirement that “he could exactly empty the tank, but only by using all three buckets and completely filling each bucket a different number of times”.

        With (13, 14, 15) there are three ways we can make 100:

        100 = 0×13 + 5×14 + 2×15
        100 = 1×13 + 3×14 + 3×15
        100 = 2×13 + 1×14 + 4×15

        The first of these means that you don’t have to use all three buckets, and the second means that you don’t have to use each bucket a different number of times. So the requirement is not met.

        Like

    • bencooperjamin's avatar

      bencooperjamin 1:46 am on 23 May 2022 Permalink | Reply

      Doesnt work because 5*14 +2*15=100 ie the tank can be emptied with only 2 of the buckets.

      Like

    • GeoffR's avatar

      GeoffR 12:34 pm on 23 May 2022 Permalink | Reply

      I finally managed to find a program solution, which agrees with Jim’s last posting i.e 3rd posting (21 May 2022).

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

int: Tank == 100;   % litres

% Three buckets - capacity ranges in litres
var 10..20:B1; var 10..20:B2; var 10..20:B3; 

% Three different size buckets are required
constraint B1 < B2 /\ B2 < B3;

% No of times buckets B1, B2 and B3 are emptied
var 1..10:n1;  var 1..10:n2;  var 1..10:n3; 

constraint all_different([n1, n2, n3]);

% Smallest bucket B1 must be emptied twice due to a 3L dent
constraint n1 == 2;

% Tank emptying constraints for one and two buckets
% Tank cannot be emptied with any single bucket
constraint forall(i in 1..10) ( Tank mod (B1 * i) != 0 );
constraint forall(i in 1..10) ( Tank mod (B2 * i) != 0 );
constraint forall(i in 1..10) ( Tank mod (B3 * i) != 0 );

% Buckets B1 and B2 cannot empty tank on their own
constraint forall(i in 1..10, j in 1..10) (
      Tank mod (i * B1 + j * B2) != 0);

% Buckets B1 and B3 cannot empty tank on their own
constraint forall(i in 1..10, j in 1..10) (
      Tank mod (i * B1 + j * B3) != 0);
      
% Buckets B2 and B3 cannot empty tank on their own
constraint forall(i in 1..10, j in 1..10) (
      Tank mod (i * B2 + j * B3) != 0);

% Empty the tank with three buckets B1, B2 and B3
constraint Tank mod (n1 * B1 + n2 * B2 + n3 * B3) == 0;

solve satisfy;

output [" Capacities of three buckets (B1, B2, B3) = " 
++ show([B1, B2, B3 ] )
++ "\n" ++ " No of times each bucket emptied (n1, n2, n3) = "
 ++ show([n1, n2, n3 ]) ];

      Like

    • Frits's avatar

      Frits 10:39 am on 25 May 2022 Permalink | Reply

      To simplify restraints you can use:

         
constraint forall(i in 0..10, j in 0..10, k in 0..10) (
i * B1 + j * B2 + k * B3 != Tank \/ i * j * k > 0);

      Like

  • Unknown's avatar

    Jim Randell 4:35 pm on 25 March 2022 Permalink | Reply
    Tags: by: Peter Good,   

    Teaser 3105: Roman primes 

    From The Sunday Times, 27th March 2022 [link] [link]

    Romulus played a game using several identical six-sided dice. Each die face shows a different single-character Roman numeral. He rolled two dice and was able to form a prime number in Roman numerals by arranging the two characters. Romulus rolled more dice and, after each roll, formed a prime number with one more character, rearranging the sequence as needed, until he could no longer form a prime number less than 100. He was using standard notation where a character before another that is 5 or 10 times larger is subtracted from the larger one, e.g., IX = 9.

    After playing many games he realised that there were exactly three primes less than 100 that could not occur in any of the sequences.

    In decimal notation and in ascending order, what were those prime numbers?

    I found two different scenarios that fit the puzzle text, but lead to two different answers. So I have marked the puzzle as flawed.

    [teaser3105]

     
    • Jim Randell's avatar

      Jim Randell 5:28 pm on 25 March 2022 Permalink | Reply

      To represent numbers from 1 to 99 using Roman numerals requires five characters I, V, X, L, C. So we know those must be on the dice. The other symbol is probably D (= 500), which lets us express numbers up to 899 (with sufficient dice; it takes 12 to make 888 = DCCCLXXXVIII).

      I’m assuming that Romulus rolls 2 dice, arranges them to make the first prime in the sequence. Then rolls another single die, and arranges the 3 dice (without changing the numerals shown by the first two) to make the second prime, and so on. Rolling a single new die at each step until he is unable to rearrange the dice to make a prime, or he runs out of dice.

      Then we can find a scenario where there are three primes that cannot occur in any sequence.

      This Python program runs in 51ms.

      Run: [ @replit ]

      from enigma import (primes, int2roman, group, join, multiset, printf)

# primes less than 100
prms = list(primes.between(2, 99))

# record primes by their roman numeral content
d = group(prms, by=(lambda n: join(sorted(int2roman(n)))))

# find length n extensions of ks in d
def extend(d, ks, n):
  ss = list(multiset.from_seq(k) for k in ks)
  for k in d.keys():
    if len(k) == n:
      s = multiset.from_seq(k)
      if any(s.issuperset(s_) for s_ in ss):
        yield k
  
# generate possible throws with increasing lengths
def generate(d, n=2):
  # start with length n sequences
  ks = list(k for k in d.keys() if len(k) == n)
  while ks:
    yield (n, ks)
    # find keys that are one longer
    n += 1
    ks = list(extend(d, ks, n))

# start with the complete set of primes
ps = set(prms)
for (n, ks) in generate(d, 2):
  # and remove those reachable after n dice
  for k in ks:
    ps.difference_update(d[k])
  # we have a solution if there are 3 primes remaining
  if len(ps) == 3:
    printf("{n} dice -> {ps}", ps=sorted(ps))

      Solution: The prime numbers are: 5, 37, 83.

      This is the solution in the scenario where Romulus has 6 dice, with the symbols I, V, X, L, C, and one other.

      5 (= V) only requires 1 die, so cannot be constructed using 2-6 dice.

      83 (= LXXXIII) requires 7 dice, so cannot be constructed using 2-6 dice.

      37 (= XXXVII) can be constructed using 6 dice, but there is no predecessor prime using 5 dice.

      Possible predecessor numbers for 37 are: 27, 32, 34, 46. None of which are prime.

      However I was able to find another scenario (see below), where Romulus has more than 6 dice, with the symbols I, V, X, L, and two others, that do not include C.

      In this scenario 5 and 37 cannot be constructed (as above), but 83 can be constructed using 7 dice.

      However the standard representation of 97 in Roman numerals is XCVII, which cannot be constructed if the symbol C is not available. (In fact none of the numbers in [90, 499] can be constructed with these dice).

      So the solution in this scenario is: 5, 37, 97.

      It seems that this second scenario is what the setter had in mind (it is the published answer), although it seems less plausible to me.

      Perhaps the following would have been a better representation of the intended puzzle:

      Romulus found a box containing a large number of identical six-sided dice. Each die face shows a different Latin character, and Romulus found that when he rolled some of the dice he was sometimes able to rearrange them so that the top faces formed a Roman numeral (using standard notation).

      He played a game where he rolled two dice and was able to form a prime number by arranging the two characters. He then rolled another die and was able to arrange the three dice to form another prime number. He carried on rolling extra dice (one die each time), until he could no longer arrange the dice to form a prime number less than 100.

      After playing many games he realised that there were exactly three primes less than 100 that could not occur in any of the sequences.

      In decimal notation and in ascending order, what were those prime numbers?

      The published solution is: “5, 37 and 97”.

      Like

    • Robert Brown's avatar

      Robert Brown 7:39 am on 26 March 2022 Permalink | Reply

      When the text says ‘after many games’ I assumed that some of these would start with II (=2) and some with XI (=11). Clearly cannot find 5 (V) as it is length 1, but I only have one more prime which cannot be made with one of the two starting pairs.

      Like

      • Jim Randell's avatar

        Jim Randell 8:57 am on 26 March 2022 Permalink | Reply

        @Robert: It looks like you are 2/3 of the way to the answer.

        There is a scenario that satisfies the wording of the puzzle text, and there are three primes that are not constructible. And each of the three primes is non-constructible for a different reason.

        Like

    • Jim Randell's avatar

      Jim Randell 12:51 pm on 26 March 2022 Permalink | Reply

      I think there is potentially an alternative scenario that also gives three non-constructible primes:

      If the dice have the symbols I, V, X, L, D, M on them (so not C), then one of the primes is not constructible (using “standard” Roman numerals), no matter how many dice are used.

      We can modify the program for this scenario by only considering primes that don’t include C when constructing the dictionary d:

      # record constructible primes by their roman numeral content
d = group(prms, by=(lambda n: join(sorted(int2roman(n)))), st=lt(90))

      Or here is a version of my code that tries all possible combinations of 6 of the 7 symbols I, V, X, L, C, D, M for the dice [ @replit ], it finds three possibilities corresponding to the two scenarios outlined above.

      from enigma import (primes, int2roman, group, join, multiset, subsets, printf)

# primes less than 100
prms = list(primes.between(2, 99))
  
# find length n extensions of ks in d
def extend(d, ks, n):
  ss = list(multiset.from_seq(k) for k in ks)
  for k in d.keys():
    if len(k) == n:
      s = multiset.from_seq(k)
      if any(s.issuperset(s_) for s_ in ss):
        yield k

def generate(d, n=2):
  # start with length n sequences
  ks = list(k for k in d.keys() if len(k) == n)
  while ks:
    yield (n, ks)
    # find keys that are one longer
    n += 1
    ks = list(extend(d, ks, n))

# solve the puzzle for allowable symbols
def solve(symbols):

  # record primes their roman numeral content
  d = group(prms, by=(lambda n: join(sorted(int2roman(n)))))

  # remove keys with invalid symbols
  d = dict((k, v) for (k, v) in d.items() if symbols.issuperset(k))
  
  # start with the complete set of primes
  ps = set(prms)
  for (n, ks) in generate(d, 2):
    # remove those reachable after n dice
    for k in ks:
      ps.difference_update(d[k])
    # we have a solution if there are 3 primes remaining
    if len(ps) == 3:
      printf("{syms}: {n} dice -> {ps}", syms=join(sorted(symbols)), ps=sorted(ps))

# choose 6 symbols for the dice
for syms in subsets('IVXLCDM', size=6, fn=set):
  solve(syms)

      I think I prefer the original scenario given above, where a sufficient number of dice can be used to give the numbers from 1 to 899. A set of dice without C would only be able to go consecutively up to 89 (the next smallest constructible number would be 500). D and M don’t come into play until 400 and 900 respectively.

      Like

      • Jim Randell's avatar

        Jim Randell 9:58 am on 1 April 2022 Permalink | Reply

        Depending on the shape of the glyphs used on the dice, it may be possible to use a V on its side to represent C, which would leave only 2 primes non-constructible in this second scenario (unless the number of dice is limited – and then we get the same solution as my first scenario).

        Like

    • Hugh+Casement's avatar

      Hugh+Casement 1:21 pm on 26 March 2022 Permalink | Reply

      I came to the same conclusion as Robert. I feel the setter of this puzzle has played a trick on us, but Jim rumbled it (before he came up with the alternative scenario ). It would have been neater, to my mind, if the puzzle text had stated that there were just two primes less than 100 that could not occur.

      Like

      • Jim Randell's avatar

        Jim Randell 3:58 pm on 26 March 2022 Permalink | Reply

        There’s definitely some trickery going on, as what you might expect to be the normal interpretation does not give 3 non-constructible primes.

        We would need to have more information about the symbols or number of dice to work out which scenario the setter had in mind.

        Like

← Older posts

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