# Enigmatic Code

Programming Enigma Puzzles

## Enigma 243B: Dolly catch

From New Scientist #1389, 22nd December 1983 [link]

Uncle Henry has bought his five nieces one of those Russian dolls each for Christmas. You know the things I mean — each doll unscrews and inside are four further dolls nested inside each other. Each set is a different colour but Henry has thought of a way to beat such dull uniformity. He has redistributed the dolls and now there is one of each colour in each set. As it happens, no red doll contains a doll with a green doll inside it. No doll contains a blue doll with a yellow doll inside it. No green doll contains an orange doll with a blue doll inside it.

So that is fine and he has just wrapped them up in jolly holly paper with lots of ribbon. But what has he done with his little gold pencil for writing the names on the cards? Oh dear, he remembers putting it in the smallest red doll for some reason. To save his undoing all his good work, could you please tell him the colour of the largest doll he must open to get at it?

This is the second Enigma of three that were published in the Christmas 1983 issue of New Scientist.

[enigma243b] [enigma243]

### 2 responses to “Enigma 243B: Dolly catch”

1. Jim Randell 11 December 2014 at 8:30 am

This recursive Python 3 program runs in 58ms.

```from enigma import irange, printf

# solve a list of colour sequences (smallest to largest)
# ss - current state of dolls
# n - size of doll we are placing
# i - set of dolls we dealing with
# cs - colours of this size already used
# the next colour to place is size n, set i
def solve(ss, n, i=0, cs=''):
# are we done?
if n == 5:
yield ss
else:
# choose a colour for size n, set i
for c in 'BGORY':
# colour can not have been used in this size, or this set
if c in cs or c in ss[i]: continue
# check the rules
s = ss[i]
# "no red doll contains a doll with a green doll inside it"
if c == 'R' and 'G' in s and n - s.find('G') > 1: continue
# "no doll contains a blue doll with a yellow doll inside it"
if c == 'B' and 'Y' in s and n < 4: continue
# "no green doll contains an orange doll with a blue doll inside it"
if c == 'G' and 'O' in s and 'B' in s and s.find('B') < s.find('O'): continue
# place the next doll
ss2 = list(ss)
ss2[i] = s + c
if i == 4:
yield from solve(ss2, n + 1, 0, '')
else:
yield from solve(ss2, n, i + 1, cs + c)

for ss in solve(['B', 'G', 'O', 'R', 'Y'], 1):
# output the largest doll for the set with R as the smallest
printf("{r} {ss}", r=ss[3][-1])
```

Solution: He should open the set with the largest green doll on the outside, to find the smallest red doll.

Of course he will have to unwrap some of the dolls to find the large green doll, so this approach may not save him from undoing all his wrapping. (Although I suppose he only needs to peek inside the wrapping to find out the colour of the largest doll). Maybe he should just shake the presents to see which one rattles like it has a pencil inside.

The sets of dolls he has made are:

Blue inside Yellow inside Green inside Red inside Orange.
Green inside Red inside Orange inside Blue inside Yellow.
Orange inside Blue inside Yellow inside Green inside Red.
Red inside Orange inside Blue inside Yellow inside Green. (This set includes the smallest red doll).
Yellow inside Green inside Red inside Orange inside Blue.

2. Brian Gladman 11 December 2014 at 11:34 pm
```from itertools import permutations, product
from collections import defaultdict

colours = ('red', 'green', 'blue', 'yellow', 'orange')
# let colour permutations from left to right represent outer to inner
# layers and collect permutations for each outer colour
outer = defaultdict(list)
for p in permutations(colours):
# no red doll contains a doll with a green doll inside it
if not (p.index('green') - p.index('red') > 1):
# No doll contains a blue doll with a yellow doll inside it
if not (p.index('blue') and p.index('blue') < p.index('yellow')):
# no green doll contains an orange doll with a blue doll inside it
if not (p.index('green') < p.index('orange') < p.index('blue')):
outer[p[0]] += [p]

# find a set of dolls for which each layer contains all five colours
for dolls in product(*(outer[c] for c in colours)):
if all(set(c) == set(colours) for c in zip(*dolls)):
# now find the outer doll with a red doll as its smallest
for doll in dolls:
if doll[4] == 'red':
print('He should open the {} doll.'.format(doll[0]))
```