Sunday Times Teaser 3266 – Where are the Keys?


# the note sequence for the melody
tune = "WUQRVWQRXWTRUQWRVQWTSRQWVRSTWQVRWQURTWXRQVWRTSX"

# form all adjacent triples of notes
n3s = [frozenset(tune[i : i + 3]) for i in range(len(tune) - 2)]

# No four adjacent notes can be be keys since they cover two overlapping 
# three note sequences which must have different keys (credit: JohnZ)
bad_keys = {frozenset(tune[i : i + 4]) for i in range(len(tune) - 3)}

# place all note triples into keys with the triples remaining
# to be placed in <n3s>, <keys> holding created keys and the
# last key changed in <last_key>
def place(n3s, keys=[], last_key=0):
  if not n3s:
    yield keys
  else:
    # the next triple
    n3 = n3s.pop()
    # consider it as the start of a new key
    if len(keys) < 7:
      yield from place(n3s[1:], keys + [n3], n3)
    
    # consider it as an extension of existing keys
    for i, key in enumerate(keys):
      # adjacent keys must be different
      if key == last_key:
        continue
      # keys have a maximum length of four and not be bad ones
      if len(new_key := key.union(n3)) > 4 or new_key in bad_keys:
        continue
      if new_key == key:
        yield from place(n3s[1:], keys, key)
      # check that the triple is not part of any other key
      elif not any(n3 <= k for k in keys if k != key):
        keys[i] = new_key
        yield from place(n3s[1:], keys, key)
        keys[i] = key
 
for n4s in place(n3s):
  keys = sorted(''.join(sorted(n4)) for n4 in sorted(n4s))
  keys = ' '.join(k if 'X' in k else k.lower() for k in keys) 
  print(f"Keys (Solution in upper case): {keys}")

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

# the note sequence for the melody

tune = "WUQRVWQRXWTRUQWRVQWTSRQWVRSTWQVRWQURTWXRQVWRTSX"

# form all adjacent triples of notes

n3s = [frozenset(tune[i : i + 3]) for i in range(len(tune) - 2)]

# No four adjacent notes can be be keys since they cover two overlapping

# three note sequences which must have different keys (credit: JohnZ)

bad_keys = {frozenset(tune[i : i + 4]) for i in range(len(tune) - 3)}

# place all note triples into keys with the triples remaining

# to be placed in <n3s>, <keys> holding created keys and the

# last key changed in <last_key>

def place(n3s, keys=[], last_key=0):

if not n3s:

yield keys

else:

# the next triple

n3 = n3s.pop()

# consider it as the start of a new key

if len(keys) < 7:

yield from place(n3s[1:], keys + [n3], n3)

# consider it as an extension of existing keys

for i, key in enumerate(keys):

# adjacent keys must be different

if key == last_key:

continue

# keys have a maximum length of four and not be bad ones

if len(new_key := key.union(n3)) > 4 or new_key in bad_keys:

continue

if new_key == key:

yield from place(n3s[1:], keys, key)

# check that the triple is not part of any other key

elif not any(n3 <= k for k in keys if k != key):

keys[i] = new_key

yield from place(n3s[1:], keys, key)

keys[i] = key

for n4s in place(n3s):

keys = sorted(''.join(sorted(n4)) for n4 in sorted(n4s))

keys = ' '.join(k if 'X' in k else k.lower() for k in keys)

print(f"Keys (Solution in upper case): {keys}")

Reply

Frits permalink

Another idea would be to derive partial keys when setting up n3s (after setting up bad_keys).
The following code generates 7 keys of three notes.
As your version is already very fast this concept doesn’t improve the performance.
With a longer melody and more notes and keys it might.


n3s, ks = [], []
for i in range(len(melody) - 2):
  n3s.append(t := frozenset(melody[i:i + 3]))
  for k in ks:
    u = t - k   # notes not in key <k>
    if len(u) == 0: break
    elif len(u) == 1 and (k | u) not in bad_keys:
      # no new key is needed if combined key doesn't exist in <bad_keys>
      break
  else: # no break
    ks.append(t)

1

2

3

4

5

6

7

8

9

10

11

12

13

n3s, ks = [], []

for i in range(len(melody) - 2):

n3s.append(t := frozenset(melody[i:i + 3]))

for k in ks:

u = t - k # notes not in key <k>

if len(u) == 0: break

elif len(u) == 1 and (k | u) not in bad_keys:

# no new key is needed if combined key doesn't exist in <bad_keys>

break

else: # no break

ks.append(t)

Reply

BRG permalink

I also tried some approaches that reduced the number of recursive calls but
none improved the speed. As you suggest, this puzzle’s solution space is too
small to small to test such ideas.

Reply

Frits permalink


melody = "WUQRVWQRXWTRUQWRVQWTSRQWVRSTWQVRWQURTWXRQVWRTSX"
notes = set("QRSTUVWX")          

# three consecutive notes 
triples = [melody[i:i + 3] for i in range(len(melody) - 2)]

# process every triple and determine seven keys
def solve(ts, ks=[], prev=set()):
  if not ts:
    if len(ks) == 7:
      yield ks
  else:
    # three consecutive notes (triple)
    ns = set(ts[0])
    
    # reuse a key if applicable
    if ks and len(q := [key for key in ks if key.issuperset(ns)]) == 1:
      # the key has to change at every step
      if (key := q[0]) != prev: 
        yield from solve(ts[1:], ks, key)

    # add a new key if needed
    if not ks or (len(q) == 0 and len(ks) < 7):
      # select a different note to create a new key
      for n in notes.difference(ns):
        key = ns | {n}
        yield from solve(ts[1:], ks + [key], key)

for ks in solve(triples):
  # double check if all triples belong to one key
  if any(sum(key.issuperset(t) for key in ks) != 1 for t in triples): continue
  print("answer:", [''.join(sorted(key)) for key in ks if "X" in key])

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

melody = "WUQRVWQRXWTRUQWRVQWTSRQWVRSTWQVRWQURTWXRQVWRTSX"

notes = set("QRSTUVWX")

# three consecutive notes

triples = [melody[i:i + 3] for i in range(len(melody) - 2)]

# process every triple and determine seven keys

def solve(ts, ks=[], prev=set()):

if not ts:

if len(ks) == 7:

yield ks

else:

# three consecutive notes (triple)

ns = set(ts[0])

# reuse a key if applicable

if ks and len(q := [key for key in ks if key.issuperset(ns)]) == 1:

# the key has to change at every step

if (key := q[0]) != prev:

yield from solve(ts[1:], ks, key)

# add a new key if needed

if not ks or (len(q) == 0 and len(ks) < 7):

# select a different note to create a new key

for n in notes.difference(ns):

key = ns | {n}

yield from solve(ts[1:], ks + [key], key)

for ks in solve(triples):

# double check if all triples belong to one key

if any(sum(key.issuperset(t) for key in ks) != 1 for t in triples): continue

print("answer:", [''.join(sorted(key)) for key in ks if "X" in key])

Reply

Frits permalink

A more efficient version using Brian’s set up. I do some of the checks after the recursion.


melody = "WUQRVWQRXWTRUQWRVQWTSRQWVRSTWQVRWQURTWXRQVWRTSX"

# three consecutive notes 
triples = [melody[i:i + 3] for i in range(len(melody) - 2)]

# process every triple and determine seven keys
def solve(ts, ks=[], prev=set()):
  if not ts:
    # seven keys of four notes
    if len(ks) == 7 and all(len(k) == 4 for n, k in ks):
      yield ks
  else:
    # three consecutive notes (triple)
    t = set(ts[0])
    
    # combine triple with existing keys
    for n, key in ks:
      if n == prev: continue
      if len(key_ := key | t) > 4: continue
      # update the <ks> list with the combined key
      ks_ = [(n, k) if k != key else (n, key_) for n, k in ks]
      yield from solve(ts[1:], ks_, n)

    # add a new partial key (containing the triple)
    if (ln := len(ks)) < 7:
      yield from solve(ts[1:], ks + [(len(ks), t)], ln)

for ks in solve(triples):
  # double check if all triples can belong to only one key
  if any(sum(key.issuperset(t) for n, key in ks) != 1 for t in triples): continue
  print("answer:", *[''.join(sorted(key)) for n, key in ks if "X" in key])

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

melody = "WUQRVWQRXWTRUQWRVQWTSRQWVRSTWQVRWQURTWXRQVWRTSX"

# three consecutive notes

triples = [melody[i:i + 3] for i in range(len(melody) - 2)]

# process every triple and determine seven keys

def solve(ts, ks=[], prev=set()):

if not ts:

# seven keys of four notes

if len(ks) == 7 and all(len(k) == 4 for n, k in ks):

yield ks

else:

# three consecutive notes (triple)

t = set(ts[0])

# combine triple with existing keys

for n, key in ks:

if n == prev: continue

if len(key_ := key | t) > 4: continue

# update the <ks> list with the combined key

ks_ = [(n, k) if k != key else (n, key_) for n, k in ks]

yield from solve(ts[1:], ks_, n)

# add a new partial key (containing the triple)

if (ln := len(ks)) < 7:

yield from solve(ts[1:], ks + [(len(ks), t)], ln)

for ks in solve(triples):

# double check if all triples can belong to only one key

if any(sum(key.issuperset(t) for n, key in ks) != 1 for t in triples): continue

print("answer:", *[''.join(sorted(key)) for n, key in ks if "X" in key])

Reply

Frits permalink

We can bring down the number of recursion calls to 99 if we add code after line 22 but It slightly increases the run time.

Python

if any(sum(key_.issuperset(t_) for n_, key_ in ks_) > 1 for t_ in triples): continue

1
2
3
4

if any(sum(key_.issuperset(t_) for n_, key_ in ks_) > 1
for t_ in triples): continue

Reply

JohnZ permalink


from itertools import combinations as cmb

melody = 'WUQRVWQRXWTRUQWRVQWTSRQWVRSTWQVRWQURTWXRQVWRTSX'

# set of sets of three consecutive characters
threes = {frozenset(melody[i: i + 3]) for i in range(len(melody) - 2)}

# No four adjacent notes in melody can be keys since they cover two
# three note sequences, each of which must have different keys
fours = {frozenset(melody[i: i + 4]) for i in range(len(melody) - 3)}

# potential keys are unions of pairs of triplets with exactly four notes;
# remove non-keys that are four adjacent notes 
pkeys = {c for a, b in cmb(threes, 2) if len(c:= a | b) == 4} - fours

# find combinations of 7 keys that obey the rules
for keys in cmb(pkeys, 7):

  # Every three consecutive notes have to belong to exactly one of the keys
  if all(sum(t.issubset(k) for k in keys) == 1 for t in threes):

    sol =  sorted(''.join(sorted(x)) for x in keys)
    print('Solution keys:', ' '.join(s for s in sol if 'X' in s))
    print('Other keys:', ' '.join(s for s in sol if 'X' not in s))

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

from itertools import combinations as cmb

melody = 'WUQRVWQRXWTRUQWRVQWTSRQWVRSTWQVRWQURTWXRQVWRTSX'

# set of sets of three consecutive characters

threes = {frozenset(melody[i: i + 3]) for i in range(len(melody) - 2)}

# No four adjacent notes in melody can be keys since they cover two

# three note sequences, each of which must have different keys

fours = {frozenset(melody[i: i + 4]) for i in range(len(melody) - 3)}

# potential keys are unions of pairs of triplets with exactly four notes;

# remove non-keys that are four adjacent notes

pkeys = {c for a, b in cmb(threes, 2) if len(c:= a | b) == 4} - fours

# find combinations of 7 keys that obey the rules

for keys in cmb(pkeys, 7):

# Every three consecutive notes have to belong to exactly one of the keys

if all(sum(t.issubset(k) for k in keys) == 1 for t in threes):

sol = sorted(''.join(sorted(x)) for x in keys)

print('Solution keys:', ' '.join(s for s in sol if 'X' in s))

print('Other keys:', ' '.join(s for s in sol if 'X' not in s))

Reply

Frits permalink

Very nice.

Reply
BRG permalink

Hi John, Its nice to see a different approach!

I know almost nothing about music so I am unclear how you derived the constraint
on line 9? Why does a change of key mean that there cannot be four consecutive
notes?

Reply
John Z permalink

Hi Brian,

I probably know less about music than you!

Starting from the left the melody’s first four notes are WUQR. This gives two groups of three: WUQ and UQR. If WUQR is a key (QRUW sorted) then both groups of three are in the same key which violates the last rule: “and the key had to change at every step.” Consequently, consecutive groups of four notes cannot form a key.

Leaving out the ” – fours ” from line 13 gives the same result, just takes longer.

The trick with my approach is to weed out the candidate keys to a reasonable number so that the final

Python

for keys in cmb(pkeys, 7):

1
2
3

for keys in cmb(pkeys, 7):

doesn’t take too long. Taking the potential keys as the fourwise combinations of all of the eight notes also works but the execution time is very, very long.

Reply

BRG permalink

Thanks John, I now get the connection. The word ‘consecutive’ can add to confusion in
this teaser since it could mean consecutive by position or consecutive by value (e.g.
“QRST”). So I have changed the comments in my code to avoid this word.

It would be nice to add a bit more to your line 9 such as:


# No four adjacent notes in melody can be be keys since they cover two
# three note sequences, all of which must have different keys

1

2

3

4

# No four adjacent notes in melody can be be keys since they cover two

# three note sequences, all of which must have different keys

Reply

JohnZ permalink


# This code approximates the reasoning of a manual solution where we set a
# new course as we go along, based on what we have already found.
from itertools import combinations as cmb

melody = 'WUQRVWQRXWTRUQWRVQWTSRQWVRSTWQVRWQURTWXRQVWRTSX'

# set of sets of three consecutive caracters
threes = {frozenset(melody[i: i + 3]) for i in range(len(melody) - 2)}

# No four adjacent notes in melody can be keys since they cover two
# three note sequences, each of which must have different keys
fours = {frozenset(melody[i: i + 4]) for i in range(len(melody) - 3)}

# potential keys are unions of pairs of triplets with exactly four notes;
# remove non-keys that are four adjacent notes 
pkeys = {c for a, b in cmb(threes, 2) if len(c:= a | b) == 4} - fours

# for each triplet, make a list of keys in which it is included
t2k = {t: [k for k in(pkeys) if t.issubset(k)] for t in threes}

# if a triplet is included in only one key, that key is one of the seven keys
psol = {key[0] for key in t2k.values() if len(key) == 1}

assert len(psol) == 6 # we have found 6 of the 7 keys, a partial solution

# get all of the triplets included in these six keys
trs = {t for t, keys in t2k.items() if (set(keys) & psol)}

assert len(rem := threes - trs) == 2 # 2 triplets have not yet found their key

# their union forms the last key
key7 = frozenset().union(*rem)

sol =  sorted(''.join(sorted(x)) for x in(psol | {key7}))
print('Keys with "X":', ' '.join(s for s in sol if 'X' in s))
print('Other keys:', ' '.join(s for s in sol if 'X' not in s))

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

# This code approximates the reasoning of a manual solution where we set a

# new course as we go along, based on what we have already found.

from itertools import combinations as cmb

melody = 'WUQRVWQRXWTRUQWRVQWTSRQWVRSTWQVRWQURTWXRQVWRTSX'

# set of sets of three consecutive caracters

threes = {frozenset(melody[i: i + 3]) for i in range(len(melody) - 2)}

# No four adjacent notes in melody can be keys since they cover two

# three note sequences, each of which must have different keys

fours = {frozenset(melody[i: i + 4]) for i in range(len(melody) - 3)}

# potential keys are unions of pairs of triplets with exactly four notes;

# remove non-keys that are four adjacent notes

pkeys = {c for a, b in cmb(threes, 2) if len(c:= a | b) == 4} - fours

# for each triplet, make a list of keys in which it is included

t2k = {t: [k for k in(pkeys) if t.issubset(k)] for t in threes}

# if a triplet is included in only one key, that key is one of the seven keys

psol = {key[0] for key in t2k.values() if len(key) == 1}

assert len(psol) == 6 # we have found 6 of the 7 keys, a partial solution

# get all of the triplets included in these six keys

trs = {t for t, keys in t2k.items() if (set(keys) & psol)}

assert len(rem := threes - trs) == 2 # 2 triplets have not yet found their key

# their union forms the last key

key7 = frozenset().union(*rem)

sol = sorted(''.join(sorted(x)) for x in(psol | {key7}))

print('Keys with "X":', ' '.join(s for s in sol if 'X' in s))

print('Other keys:', ' '.join(s for s in sol if 'X' not in s))

Reply

Sunday Times Teaser 3266 – Where are the Keys?

by Colin Vout

Published Sunday April 27 2025 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta