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]
Frits are discussing. 
John Crabtree, 
GeoffR, and 
S2T2 
Jim Randell 7:07 am on 16 March 2025 Permalink |
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):
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:
And one of these words is included in each of the remaining phrases.
In fact, there are 36 possible sets of partial dice that can be used to make “TIME AND TIDE WAIT FOR NO MAN“.
All of them have A and E on the same die, so this eliminates all the other phrases apart from “DONT ROCK THE BOAT“.
Of these 36 sets, 12 of them also have O on same die as A and E, so those eliminate BOAT also (as above).
And the remaining 24 sets each have at least 2 letters of DONT on the same die, so these are not possible either.
LikeLike
Frits 3:04 pm on 16 March 2025 Permalink |
@Jim, your latest code (with seq_ordered ) also has the runtime unpredicability issue with CPython. If you solve this please let me know how you did this.
LikeLike
Jim Randell 4:30 pm on 16 March 2025 Permalink |
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).
But if you set the environment variable
PYTHONHASHSEEDto a fixed integer value, then CPython3 will behave in a repeatable fashion:LikeLike
Jim Randell 11:15 am on 19 March 2025 Permalink |
Here is a faster solution that collects the dice as a map (instead of a collection of sequences), as each symbol can only appear on one die.
It has an internal runtime of 4.8ms.
from enigma import (irange, multiset, fail, intersect, subsets, peek, group, remove, update, join, printf) # phrases to check phrases = [ "DONT ROCK THE BOAT", "EASY COME EASY GO", "GIVE A DOG A BAD NAME", "IF THE CAP FITS WEAR IT", "LIFE IS WHAT YOU MAKE IT", "MAKE LOVE NOT WAR", "YOU REAP WHAT YOU SOW", "IF YOU CANT BEAT THEM JOIN THEM", "DONT BURY YOUR HEAD IN THE SAND", "TIME AND TIDE WAIT FOR NO MAN", ] # analyse the phrases words = list() for ph in phrases: ws = list() for w in sorted(ph.split(), key=len, reverse=1): w = join(w, sort=1) s = set(w) fail(len(s) != len(w), "repeated letters found") if any(s.issubset(x) for x in ws): continue ws.append(w) words.append(ws) # complete dice (<d>, <r>) for words <ws> # d = map of symbols to die index # r = remaining count of symbols per die def construct(ws, d, r): # are we done? if not ws: yield (d, r) else: # choose the next word (maximal intersection) w = max(ws, key=lambda w: len(intersect([w, d.keys()]))) # find used dice, and unused symbols (ds, us) = (list(), list()) for x in w: i = d.get(x) if i is None: us.append(x) else: ds.append(i) # no die can be used more than once if len(ds) != len(set(ds)): return # assign unused symbols to the remaining dice rs = list(i for (i, x) in r.items() if i not in ds) if len(rs) < len(us): return for ss in subsets(rs, size=len(us), select='P'): d_ = update(d, us, ss) r_ = r.difference(ss) # and solve for the remaining words yield from construct(remove(ws, w), d_, r_) # find sets of <n> dice (<k>-sided) to display <ws> def dice(ws, n, k): (d, r) = (dict(), multiset.from_seq(irange(n), count=k)) # start with the first word w = ws[0] for (i, x) in enumerate(w): d[x] = i r.remove(i) # and add in the remaining words yield from construct(ws[1:], d, r) # format a set of dice def fmt(d): g = group(d.keys(), by=d.get) return join((join(g[k], sort=1) for k in sorted(g.keys())), sep=", ", enc="[]") # collect phrases that can be extended multiple = set() # examine all sets for phrase <i> def solve(i, n=4, k=6): if i in multiple: return # make a set of 4 dice (6-sided) for this phrase d = None for (d, r) in dice(words[i], n, k): # can we extend the dice to make any of the other phrases? for (j, ws1) in enumerate(words): if j == i: continue (d1, _) = peek(construct(ws1, d, r), default=(None, None)) if d1: multiple.update((i, j)) # output an extendable set printf("\"{ph}\" -> {d}", ph=phrases[i], d=fmt(d)) printf("+ \"{ph}\" -> {d1}", ph=phrases[j], d1=fmt(d1)) printf() return # return an example non-extendable set return d # consider each phrase for (i, ph) in enumerate(phrases): d = solve(i) if d: printf("SOLUTION = \"{ph}\" -> {d}", d=fmt(d)) printf()LikeLike
Frits 2:40 pm on 16 March 2025 Permalink |
The runtime of this program varies. Normally this is caused by using sets but removing sets as much as possible hasn’t removed the unpredictability of run times.
[program removed]
LikeLike
Frits 4:36 pm on 16 March 2025 Permalink |
Luckily no word contains duplicate letters otherwise a fix is needed.
LikeLike
Jim Randell 4:38 pm on 16 March 2025 Permalink |
@Frits: A letter can only appear on one die, so it wouldn’t be possible to make a word with repeated letters.
LikeLike
Frits 4:41 pm on 16 March 2025 Permalink |
@Jim, you are right.
LikeLike
Frits 5:28 pm on 16 March 2025 Permalink |
Thanks. I may try it.
I found the cause of the unpredictable behaviour in my code. If during the first sort (line 19) the data is sorted on both length and value then the behaviour is predictable again. I’ll send a new version tomorrow.
LikeLike
Frits 8:48 am on 19 March 2025 Permalink |
from itertools import combinations, permutations sayings_orig = ["Don't rock the boat", "Easy come, easy go", "Give a dog a bad name", "If the cap fits wear it", "Life is what you make it", "Make love not war", "You reap what you sow", "If you can't beat them join them", "Don't bury your head in the sand", "Time and tide wait for no man"] # convert to lowercase and remove non alphabetics sayings = [[''.join(c for c in w if c.isalpha()) for w in s.lower().split()] for s in sayings_orig] # remove words that are subsets of other words and # sort sayings on length and preserve original index sayings = list(enumerate(sorted([w1 for i, w1 in enumerate(s) if all(not set(w1).issubset(set(w2)) or (set(w1) == set(w2) and i < j) for j, w2 in enumerate(s) if i != j)], key=len, reverse=True) for s in sayings)) # sort by number of 4-character words (descending) sayings.sort(key = lambda x: -len([1 for y in x[1] if len(y) == 4])) ln = len(sayings) # try to place all letters on the dice in <ss> for all words in <ws> def solve(ws, ss=[]): if not ws: yield ss else: # try to add each letter of <w> to one of the 4 dice in <ss> if not ss: ss = ["" for _ in range(4)] fn = combinations w = ws[0] free_dice = range(4) else: fn = permutations w = list(ws[0]) free_dice = [n for n in range(4) if len(ss[n]) < 6] removed = set() for ltr in ws[0]: for n in range(4): # letter <ltr> already on a die? if ltr in ss[n]: if n in removed: return # two letters of current word on same die if n in free_dice: # credit: B. Gladman free_dice.remove(n) removed.add(n) w.remove(ltr) break # assign all unassigned letters to the available dice for p in fn(free_dice, len(w)): ss_ = ss.copy() for i, n in enumerate(p): ss_[n] += w[i] yield from solve(ws[1:], ss_) sols, processed = set(range(ln)), set() # for all sayings for i in range(ln): # skip if this saying is not the solution if (i_o := sayings[i][0]) not in sols: continue processed.add(i) for dice1 in solve(sayings[i][1]): # try to combine other sayings with these dice for j in range(ln): if j == i: continue # skip if saying <j> has been fully processed if (j_o := sayings[j][0]) in sols and j in processed: continue # skip if both sayings are not the solution if i_o not in sols and j_o not in sols: continue for dice2 in solve(sayings[j][1], dice1): print(f"with dice {[''.join(sorted(x)) for x in dice2]} " f"the following sayings can be constructed:") print("--", sayings_orig[i_o]) print("--", sayings_orig[j_o], "\n") sols -= {i_o, j_o} break # finding one example is enough to remove <j_o> from <sols> else: # no break continue break else: # no break continue break print(f"answer(s): '{' or '.join(sayings_orig[s] for s in sols)}'")LikeLike