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]

Advertisements

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)
    
    # start with the set of smallest dolls
    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]))
    

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: