Sunday Times Teaser 3289 – Spot Check

by BRG on October 5, 2025

by Peter Good

Published Sunday October 05 2025 (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?

From → Uncategorized

5 Comments Leave one →

BRG permalink

This follows the structure of Jim Randell’s code here.


# multiset (as dictionary) difference
def ms_diff(ds, vs):
  t = ds
  for key in vs:
    t = {k:(v - 1 if k == key else v) for k, v in t.items()}
    t = {k:v for k, v in t.items() if v}
  return t

# collect spots on dominoes and total spots
doms = tuple((x, y) for x in range(7) for y in range(x, 7) if x + y)
spots = sum(x + y for x, y in doms)

# map domino spot counts to the numer of dominos with each count
ds = {}
for d in doms:
  ds[s] = ds.get(s := sum(d), 0) + 1

# possible cubes
cubes = [x ** 3 for x in range(1, 6) if x ** 3 + 5 < spots]

# make total <t> using <k> ordered integers from <ns> (ordered)
def decompose(t, k, ns, ss=()):
  if k == 1:
    if t in ns and t >= ss[-1]:
      yield ss + (t,)
  else:
    for i, n in enumerate(ns):
      if n <= t:
        yield from decompose(t - n, k - 1, ns[i:], ss + (n,))  

# find an overall spot number for six groups of dominos, with 
# each group having a cubic spot sum
cube_sums = {}
for t in range(1, spots + 1):
  for r in decompose(t, 6, cubes):
    cube_sums[t] = cube_sums.get(t, ()) + (r,)

# find groups of dominos with a spot sum of <t> from dominos in <ds> 
def group(t, ds, ss=()):
  if t == 0:
    yield ss
  else:
    for v in ds.keys():
      if (t_ := t - v) >= 0:
        ds_ = ms_diff(ds, [v])
        yield from group(t_, ds_, ss + (v,))
  
# find groups of dominos with spot sums in <ts> from dominoes in <ds>
def groups(ts, ds, ps=()):
  if not ts:
    yield ps
  else:
    t = ts[0]
    for ss in group(t, ds):
      yield from groups(ts[1:], ms_diff(ds, ss), ps + (ss,))

# starting with total <t>, discard a domino and form the rest into six
# groups of dominos each with cubic sums; return a sequence with each
# element giving its discard, spot sum and domino spot count
def solve(t, ds, ss=()):
  if ss:
    yield ss
  # look for a domino to discard
  for x in ds.keys():
    # remaining total spots
    if (t_ := t - x) in cube_sums:
      ds_ = ms_diff(ds, [x])    
      # find six groups with cube sums of t_
      for ts in cube_sums[t_]:
        # can we find at least one such group
        for ps in groups(ts, ds_):
          if ps:
            yield from solve(t_, ds_, ss + ((x, t_, ps),))
            break
        else:
          continue
        break
            
        

ss_len, ss_max = 0, []
# find the maximum number of possible repeated discard/groups
for ss in solve(spots, ds):
  if (nl := len(ss)) >= ss_len:
    if nl > ss_len:
      ss_len = nl
      ss_max = []
    ss_max += [ss]

# output examples of the maximum discard/group cycles and results
for sq in ss_max:
  for x, t, ps in sq:
    print(f"{x:2}, {t:3} -> {list(list(sorted(p)) for p in ps)}")
  print()
print(f"{ss_len} discards with {t} spots on the remaining dominoes")

# multiset (as dictionary) difference

def ms_diff(ds, vs):

t = ds

for key in vs:

t = {k:(v - 1 if k == key else v) for k, v in t.items()}

t = {k:v for k, v in t.items() if v}

return t

# collect spots on dominoes and total spots

doms = tuple((x, y) for x in range(7) for y in range(x, 7) if x + y)

spots = sum(x + y for x, y in doms)

# map domino spot counts to the numer of dominos with each count

ds = {}

for d in doms:

ds[s] = ds.get(s := sum(d), 0) + 1

# possible cubes

cubes = [x ** 3 for x in range(1, 6) if x ** 3 + 5 < spots]

# make total <t> using <k> ordered integers from <ns> (ordered)

def decompose(t, k, ns, ss=()):

if k == 1:

if t in ns and t >= ss[-1]:

yield ss + (t,)

else:

for i, n in enumerate(ns):

if n <= t:

yield from decompose(t - n, k - 1, ns[i:], ss + (n,))

# find an overall spot number for six groups of dominos, with

# each group having a cubic spot sum

cube_sums = {}

for t in range(1, spots + 1):

for r in decompose(t, 6, cubes):

cube_sums[t] = cube_sums.get(t, ()) + (r,)

# find groups of dominos with a spot sum of <t> from dominos in <ds>

def group(t, ds, ss=()):

if t == 0:

yield ss

else:

for v in ds.keys():

if (t_ := t - v) >= 0:

ds_ = ms_diff(ds, [v])

yield from group(t_, ds_, ss + (v,))

# find groups of dominos with spot sums in <ts> from dominoes in <ds>

def groups(ts, ds, ps=()):

if not ts:

yield ps

else:

t = ts[0]

for ss in group(t, ds):

yield from groups(ts[1:], ms_diff(ds, ss), ps + (ss,))

# starting with total <t>, discard a domino and form the rest into six

# groups of dominos each with cubic sums; return a sequence with each

# element giving its discard, spot sum and domino spot count

def solve(t, ds, ss=()):

if ss:

yield ss

# look for a domino to discard

for x in ds.keys():

# remaining total spots

if (t_ := t - x) in cube_sums:

ds_ = ms_diff(ds, [x])

# find six groups with cube sums of t_

for ts in cube_sums[t_]:

# can we find at least one such group

for ps in groups(ts, ds_):

if ps:

yield from solve(t_, ds_, ss + ((x, t_, ps),))

break

else:

continue

break

ss_len, ss_max = 0, []

# find the maximum number of possible repeated discard/groups

for ss in solve(spots, ds):

if (nl := len(ss)) >= ss_len:

if nl > ss_len:

ss_len = nl

ss_max = []

ss_max += [ss]

# output examples of the maximum discard/group cycles and results

for sq in ss_max:

for x, t, ps in sq:

print(f"{x:2}, {t:3} -> {list(list(sorted(p)) for p in ps)}")

print()

print(f"{ss_len} discards with {t} spots on the remaining dominoes")

Frits permalink

There are also other variations of domino distributions that have the same end result.
Domino (0, 0) has been ignored as we are asked for a positive cube number of spots.


from collections import defaultdict

# make total spots <t> with <k> numbers from list <ns>
def decompose(t, k, ns, ss=[]):
  if k == 1:
    if t in ns and t >= ss[-1]:
      yield ss + [t]
  else:
    for i, n in enumerate(ns):
      if n > t: break
      yield from decompose(t - n, k - 1, ns[i:], ss + [n])  
      
def determine_dominoes(t, d, ss=[]):
  if t == 0:
    yield ss, d
  else:  
    for dom, cnt in d.items():
      #if cnt < 1: continue
      if dom > t: break
      # domino sums must not be decreasing
      if ss and dom < ss[-1]: continue
      # decrement counter
      d_ = {k: v if k != dom else v - 1 for k, v in d.items() 
               if k != dom or v > 1}
      yield from determine_dominoes(t - dom, d_, ss + [dom])               

# can we make <k> cubes from <cs> with remaining dominoes?
def make(cs, k, d, ss=[]):
  global cnt1
  if k == 0:
    yield ss
  else:
    # try to make cs[0] with remaining dominoes
    for x, d_ in determine_dominoes(cs[0], d):
      # if we have two of the same cubes then demand an order
      if not ss or sum(ss[-1]) != cs[0] or x >= ss[-1]:
        yield from make(cs[1:], k - 1, d_, ss + [x])
    
# play a round of discarding a non-blank domino
def play(d, spots, sols, lev=0, ss=[]):
  global mx, answs
  if lev > mx:
    answs = []
    mx = lev
  if lev >= mx:  
    # store examples for the answer
    answs.append([x for x in sols if x])  
  
  # deepcopy intermediate solutions
  sols_ = [x.copy() for x in sols]  
  
  # choose a non-blank domino to discard
  for discard in d.keys():
    # we should not have used up all dominoes for this sum
    if d[discard] == 0: continue
    n = spots - discard
    # with new total <n> it must be possible to form 6 cubes
    if n not in six_cubes: continue
    # decrement counter
    d_ = {k: (v if k != discard else v - 1) for k, v in d.items() 
              if k != discard or v > 1}
    
    # find a way to make <n> with 6 cubes
    for cs in six_cubes[n]:
      # find dominoes for each of the 6 cube1
      for dominoes_per_cube in make(cs, 6, d_):
        # store intermediate solution
        sols_[lev] = [n, dominoes_per_cube]
        # play another round
        play(d_, n, sols_, lev + 1, ss + [discard])
        break # try to discard another non-blank domino for this round
      else:
        continue
      break    

answs, mx = [], 0     

# the 28 dominoes
dominoes = tuple((i, j) for i in range(7) for j in range(i, 7))
# the total number of spots
n_spots = sum(a + b for a, b in dominoes)
      
# dictionary of number of dominoes per possible positive sum
d = {k: sum([a + b == k for a, b in dominoes]) for k in range(1, 13)}  
      
# generate positive cubes
cbs, n = [], 1      
while(n ** 3 + 5 <= n_spots):
  cbs.append(n**3)
  n += 1

# determine all total number of spots for which six cubes can be formed
six_cubes = defaultdict(list)
for n in range(6, n_spots):
  # find a way to make <n> with 6 cubes
  for cs in decompose(n, 6, cbs):
    six_cubes[n].append(cs)

# keep playing rounds until no longer six cubes can be formed
play(d, n_spots, [[] for _ in range(len(dominoes))])

print("examples:")
remaining_spots = set()
for ans in answs:
  for i, x in enumerate(ans):
    if not x: break
    (sm, lst) = x
    if x: print(sm, "-->", lst)
  remaining_spots.add(str(ans[-1][0]))  
  print()  
      
print("answer: number of dominoes discarded by Jack:", mx)
print("        remaining spots:", ' or '.join(remaining_spots))

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

from collections import defaultdict

# make total spots <t> with <k> numbers from list <ns>

def decompose(t, k, ns, ss=[]):

if k == 1:

if t in ns and t >= ss[-1]:

yield ss + [t]

else:

for i, n in enumerate(ns):

if n > t: break

yield from decompose(t - n, k - 1, ns[i:], ss + [n])

def determine_dominoes(t, d, ss=[]):

if t == 0:

yield ss, d

else:

for dom, cnt in d.items():

#if cnt < 1: continue

if dom > t: break

# domino sums must not be decreasing

if ss and dom < ss[-1]: continue

# decrement counter

d_ = {k: v if k != dom else v - 1 for k, v in d.items()

if k != dom or v > 1}

yield from determine_dominoes(t - dom, d_, ss + [dom])

# can we make <k> cubes from <cs> with remaining dominoes?

def make(cs, k, d, ss=[]):

global cnt1

if k == 0:

yield ss

else:

# try to make cs[0] with remaining dominoes

for x, d_ in determine_dominoes(cs[0], d):

# if we have two of the same cubes then demand an order

if not ss or sum(ss[-1]) != cs[0] or x >= ss[-1]:

yield from make(cs[1:], k - 1, d_, ss + [x])

# play a round of discarding a non-blank domino

def play(d, spots, sols, lev=0, ss=[]):

global mx, answs

if lev > mx:

answs = []

mx = lev

if lev >= mx:

# store examples for the answer

answs.append([x for x in sols if x])

# deepcopy intermediate solutions

sols_ = [x.copy() for x in sols]

# choose a non-blank domino to discard

for discard in d.keys():

# we should not have used up all dominoes for this sum

if d[discard] == 0: continue

n = spots - discard

# with new total <n> it must be possible to form 6 cubes

if n not in six_cubes: continue

# decrement counter

d_ = {k: (v if k != discard else v - 1) for k, v in d.items()

if k != discard or v > 1}

# find a way to make <n> with 6 cubes

for cs in six_cubes[n]:

# find dominoes for each of the 6 cube1

for dominoes_per_cube in make(cs, 6, d_):

# store intermediate solution

sols_[lev] = [n, dominoes_per_cube]

# play another round

play(d_, n, sols_, lev + 1, ss + [discard])

break # try to discard another non-blank domino for this round

else:

continue

break

answs, mx = [], 0

# the 28 dominoes

dominoes = tuple((i, j) for i in range(7) for j in range(i, 7))

# the total number of spots

n_spots = sum(a + b for a, b in dominoes)

# dictionary of number of dominoes per possible positive sum

d = {k: sum([a + b == k for a, b in dominoes]) for k in range(1, 13)}

# generate positive cubes

cbs, n = [], 1

while(n ** 3 + 5 <= n_spots):

cbs.append(n**3)

n += 1

# determine all total number of spots for which six cubes can be formed

six_cubes = defaultdict(list)

for n in range(6, n_spots):

# find a way to make <n> with 6 cubes

for cs in decompose(n, 6, cbs):

six_cubes[n].append(cs)

# keep playing rounds until no longer six cubes can be formed

play(d, n_spots, [[] for _ in range(len(dominoes))])

print("examples:")

remaining_spots = set()

for ans in answs:

for i, x in enumerate(ans):

if not x: break

(sm, lst) = x

if x: print(sm, "-->", lst)

remaining_spots.add(str(ans[-1][0]))

print()

print("answer: number of dominoes discarded by Jack:", mx)

print(" remaining spots:", ' or '.join(remaining_spots))

Frits permalink

@Brian, please delete.

Reply

Frits permalink

The following decompose() is more efficient for this teaser and still quite general.


 make total <t> with <k> elements taken from <m> numbers in list <ns> 
def decompose_(rest, m, t, k, ns, ss=[]):
  if m == 2:
    # example:
    # A + 8 * B + 27 * C + 64 * D + 125 * E = t and A + B + C + D + E = 6
    # lead to t - 6 - 26C - 63D - 124E = 7B
    ssrev = ss[::-1]
    # calculate 2nd quantity
    q2, r = divmod(t - k - sum([(x - 1) * y for x, y in 
                    zip(ns[2:], ssrev)]), ns[1] - 1) 
    if not r and q2 >= 0:
      if (q1 := k - q2 - sum(ss)) >= 0:
        yield [a for g in [y * [x] 
               for x, y in zip(ns, [q1, q2] + ssrev)] for a in g] 
  else:
    n = ns[m - 1]
    for amt in range(min(n, k - sum(ss), rest // n) + 1):
    #for amt in range(n + 1):
      #if amt * n > rest or sum(ss) + amt > k: break
      yield from decompose_(rest - amt * n, m - 1, t, k, ns, ss + [amt])  
 
# make total spots <t> with <k> numbers from list <ns>      
def decompose(t, k, ns):
  yield from decompose_(t, len(ns), t, k, ns)

make total <t> with <k> elements taken from <m> numbers in list <ns>

def decompose_(rest, m, t, k, ns, ss=[]):

if m == 2:

# example:

# A + 8 * B + 27 * C + 64 * D + 125 * E = t and A + B + C + D + E = 6

# lead to t - 6 - 26C - 63D - 124E = 7B

ssrev = ss[::-1]

# calculate 2nd quantity

q2, r = divmod(t - k - sum([(x - 1) * y for x, y in

zip(ns[2:], ssrev)]), ns[1] - 1)

if not r and q2 >= 0:

if (q1 := k - q2 - sum(ss)) >= 0:

yield [a for g in [y * [x]

for x, y in zip(ns, [q1, q2] + ssrev)] for a in g]

else:

n = ns[m - 1]

for amt in range(min(n, k - sum(ss), rest // n) + 1):

#for amt in range(n + 1):

#if amt * n > rest or sum(ss) + amt > k: break

yield from decompose_(rest - amt * n, m - 1, t, k, ns, ss + [amt])

# make total spots <t> with <k> numbers from list <ns>

def decompose(t, k, ns):

yield from decompose_(t, len(ns), t, k, ns)

JohnZ permalink


from itertools import product

# make groups of the remaining dominos to form the 6 cubic sums
# cubes: the six cube sums, rd: the remaining doms, presult: result for 1 cube
def doms2cubes(cubes, rd, presult = [], result = []):
  # skip the last group because f^3 = tot - a^3 - b^3 - c^3 - d^3 - e^3
  if len(cubes) == 1:
     yield result + [rd]
  else:
    for i, d in enumerate(rd):
      if cubes[0] > d:
        # deduct the domino from the current cube value then try next domino
        yield from doms2cubes([cubes[0] - d] + cubes[1:],
                              rd[:i] + rd[i + 1:], presult + [d], result)
      elif cubes[0] == d:
        # cube value reached by the domino, go on to next cube
        yield from doms2cubes(cubes[1:], rd[:i] + rd[i + 1:], [],
                              result + [presult +[d]])

# find all possible discard sequences of dominos from 'root' (168) to 'leaves'
# n: number of discards; s: the current sum of dominos; rd: remaining dominos
def disc_seq(n, s, rd, discards = []):
  # consider next domino <d> to discard
  for d in set(rd):
    if (s - d) in cgsd.keys():
      # if 1 is a required cube value, the [0|1] domino must still be available
      if not((d == 1 or 1 in discards) and cgsd[s - d][0] == 1):
        i = rd.index(d)
        yield from disc_seq(n + 1, s - d, rd[:i] + rd[i + 1:], discards + [d])
  yield (n, s, rd, discards)

# generate dominos; only the sum of each domino's dots is needed; discard [0|0]
dom = sorted([a + b for a in range(7) for b in range(a, 7)])[1:]
sd = sum(dom)

# make dictionary: keys = all possible cube group sums; values = cubes
# for example  {116: (1, 8, 8, 8, 27, 64) } etc.
cgsd = {cgs: cg for cp in product((0, 1), range(7), range(7), range(3), (0, 1))
         if sum(cp) == 6 and (cgs := sum(cg :=
         tuple((i + 1) ** 3 for i in range(5) for j in range(cp[i])))) <= sd}

mdisc = 0 # maximum number of discards

# consider all discard sequences with results sorted by number of discards
for sol in sorted(disc_seq(0, sd, dom), reverse = True):

  # stop if number of discards is less than maximum
  if sol[0] < mdisc:
    break
  
  # verify that final and intermediate sums can be reached after each discard
  start, domc, cumul = sd, dom.copy(), []
  # consider each discard in turn
  for disc in sol[3]:
    start -= disc
    domc.remove(disc)
    # find arrangement of dominos <aod> into cube sums                                                  
    for aod in doms2cubes(list(cgsd[start]), domc):
      cumul += [[start, cgsd[start], aod]]
      # found: only one arrangement of dominos into cube groups is needed
      break
    # no arrangements found: break outer loop (for disc in sol[3])
    else:
      break

  # verification passed; print solution  
  else:
    # set initial maximum discards if not already found
    mdisc = max(mdisc, sol[0])
     
    print("removed:", sol[0], "; sum of remaining:", sd - sum(sol[3]))
    for c in cumul:
      print(*c, '\n----------------------------')
    print('\n****************************\n')

from itertools import product

# make groups of the remaining dominos to form the 6 cubic sums

# cubes: the six cube sums, rd: the remaining doms, presult: result for 1 cube

def doms2cubes(cubes, rd, presult = [], result = []):

# skip the last group because f^3 = tot - a^3 - b^3 - c^3 - d^3 - e^3

if len(cubes) == 1:

yield result + [rd]

else:

for i, d in enumerate(rd):

if cubes[0] > d:

# deduct the domino from the current cube value then try next domino

yield from doms2cubes([cubes[0] - d] + cubes[1:],

rd[:i] + rd[i + 1:], presult + [d], result)

elif cubes[0] == d:

# cube value reached by the domino, go on to next cube

yield from doms2cubes(cubes[1:], rd[:i] + rd[i + 1:], [],

result + [presult +[d]])

# find all possible discard sequences of dominos from 'root' (168) to 'leaves'

# n: number of discards; s: the current sum of dominos; rd: remaining dominos

def disc_seq(n, s, rd, discards = []):

# consider next domino <d> to discard

for d in set(rd):

if (s - d) in cgsd.keys():

# if 1 is a required cube value, the [0|1] domino must still be available

if not((d == 1 or 1 in discards) and cgsd[s - d][0] == 1):

i = rd.index(d)

yield from disc_seq(n + 1, s - d, rd[:i] + rd[i + 1:], discards + [d])

yield (n, s, rd, discards)

# generate dominos; only the sum of each domino's dots is needed; discard [0|0]

dom = sorted([a + b for a in range(7) for b in range(a, 7)])[1:]

sd = sum(dom)

# make dictionary: keys = all possible cube group sums; values = cubes

# for example {116: (1, 8, 8, 8, 27, 64) } etc.

cgsd = {cgs: cg for cp in product((0, 1), range(7), range(7), range(3), (0, 1))

if sum(cp) == 6 and (cgs := sum(cg :=

tuple((i + 1) ** 3 for i in range(5) for j in range(cp[i])))) <= sd}

mdisc = 0 # maximum number of discards

# consider all discard sequences with results sorted by number of discards

for sol in sorted(disc_seq(0, sd, dom), reverse = True):

# stop if number of discards is less than maximum

if sol[0] < mdisc:

break

# verify that final and intermediate sums can be reached after each discard

start, domc, cumul = sd, dom.copy(), []

# consider each discard in turn

for disc in sol[3]:

start -= disc

domc.remove(disc)

# find arrangement of dominos <aod> into cube sums

for aod in doms2cubes(list(cgsd[start]), domc):

cumul += [[start, cgsd[start], aod]]

# found: only one arrangement of dominos into cube groups is needed

break

# no arrangements found: break outer loop (for disc in sol[3])

else:

break

# verification passed; print solution

else:

# set initial maximum discards if not already found

mdisc = max(mdisc, sol[0])

print("removed:", sol[0], "; sum of remaining:", sd - sum(sol[3]))

for c in cumul:

print(*c, '\n----------------------------')

print('\n****************************\n')

Sunday Times Teaser 3289 – Spot Check

by Peter Good

Published Sunday October 05 2025 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta