Enigmatic Code

Programming Enigma Puzzles

Enigma 1423: Around the tree

From New Scientist #2583, 23rd December 2006

We have wrapped all this year’s presents in red or gold and placed them in a circle around the Christmas tree. The set of four anticlockwise starting with Joe’s present is gold, red, red, red. The set of four clockwise which starts with Joe’s present finishes with a red one.

In fact, if you name any sequence of four gold/red (e.g. GRGG, RGGR, etc) then there is a set of four consecutive presents which (clockwise, anticlockwise or both) coincides with your sequence. Furthermore, this would not have been possible with fewer presents.

(a) How many presents were round the tree?

(b) Starting with Joe’s and working clockwise, list the colours of the first five presents.

Enigma 1320 is also called “Around the tree”.

[enigma1423]

Advertisements

One response to “Enigma 1423: Around the tree

  1. Jim Randell 9 June 2013 at 10:14 am

    I didn’t think the puzzle was clear about whether all red and all green sequences were allowed (RRRR and GGGG). But if you do allow them you get the required answer.

    This Python program runs in 43ms.

    from itertools import product, count
    from enigma import printf
    
    # there 2^4 = 16 R/G sequences (assuming RRRR and GGGG are allowed)
    # but we can skip sequences that are the reverse of another sequence
    ss = list()
    for s in product('RG', repeat=4):
      if s[::-1] < s: continue
      ss.append(''.join(s))
    
    # check the sequences <ss> appear in the loop <s>
    def check(s, ss):
      # wrap the end on to the front
      s1 = s + s[:3]
      # reverse it
      s2 = s1[::-1]
      # check all the sequences appear in s1 or s2
      return all(x in s1 or x in s2 for x in ss)
    
    # with the conditions we are given there must be at least 12 elements
    # in the sequence
    for n in count(12):
      # accumulate the results
      r = list()
      # empty sequence
      s = [ None ] * n
      # fill out initial values
      s[0] = 'G'
      s[1] = s[2] = s[3] = s[-3] = 'R'
      # fill out the remaining values
      for s[4:-3] in product('RG', repeat=n - 7):
        for s[-2:] in product('RG', repeat=2):
          if check(''.join(s), ss):
            r.append(s[::])
      # did we find any solutions?
      if len(r) > 0: break
    
    printf("number of presents = {n}")
    for s in r:
      # order the presents clockwise from joe
      s.append(s.pop(0))
      s.reverse()
      # output the list of presents
      printf("presents = {t}", t=' '.join(s))
    

    Solution: (a) There were 14 presents around the tree; (b) The colours of the first five presents are: green, green, red, red, green.

    There are two possible sequences for the solution: G G R R G G G G R G R R R R and G G R R G R G G G G R R R R. They differ at the 6th and 9th positions.

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: