Enigmatic Code

Programming Enigma Puzzles

Enigma 1516: A colourful turn

From New Scientist #2678, 18th October 2008

I have a little trick with eight cards. Their backs are all white but the fronts are one each of apricot, blue, chocolate, green, orange, primrose, red and terracotta. I place them in a pile in a certain order, white sides up. Then I spell out one of the colours, moving one card from the top of the pile to the bottom as I say each letter. As I reach the last letter of the spelling I turn over that card and (lo and behold) it is that colour. I then place that card at the bottom of the pile and spell out another colour. In this way I work through all the colours, finishing with the apricot. In the course of the trick the chocolate card is turned over later than the terracotta one.

List (by their initials) the order in which I spell out the colours.

[enigma1516]

Advertisements

5 responses to “Enigma 1516: A colourful turn

  1. Jim Randell 18 September 2012 at 8:43 am

    The following Python program runs in 740ms (under PyPy).

    from itertools import count, permutations
    from enigma import irange, printf
    
    colours = set((
      'Apricot',
      'Blue',
      'Chocolate',
      'Green',
      'Orange',
      'Primrose',
      'Red',
      'Terracotta'
    ))
    N = len(colours)
    
    # check pile after revealing specified cards
    def check(pile, cards):
      # we finish on apricot
      if len(cards) > 0 and cards[-1] == 'Apricot':
        # have all the colours been used?
        if len(cards) == N:
          # 'Terracotta' should occur before 'Chocolate'
          if cards.index('Terracotta') < cards.index('Chocolate'):
            print(', '.join(cards))
            print(' '.join(c[0] for c in cards))
        return
      
      # start moving the cards from the top of the pile to the bottom
      m = max(len(c) for c in colours.difference(cards))
      for n in irange(1, m):
        # move a card from the top to the bottom of the pile
        pile = pile[1:] + pile[:1]
        # does the colour of the moved card match the count?
        if len(pile[-1]) == n and pile[-1] not in cards:
          # try with the remaining cards
          check(pile, cards + [pile[-1]])
    
    # the cards are placed in some order
    for pile in permutations(colours):
      check(pile, [])
    

    Solution: The order is P O G B T C R A.

  2. arthurvause 18 September 2012 at 3:37 pm

    Here’s another way of looking at it: start with the spelling out order and see if it matches a feasible initial order

    from itertools import permutations as perm
    
    colours={3:'Red',4:'Blue',5:'Green',6:'Orange',7:'Apricot',8:'Primrose',
             9:'Chocolate',10:'Terracotta'}
    
    for spell_order in perm(range(3,11)):
      if spell_order.index(10) < spell_order.index(9) and spell_order[7]==7:
        # The initial position of n-th card spelt out is (sum(spell_order[0:n+1])-1)%8 )
        # so see if the initial positions of the cards are all different.
        if len(set([(sum(spell_order[0:n+1])-1)%8 for n in range(8)]))==8:
            print ''.join([colours[spell_order[i]]+' ' for i in range(8)])
    
    • arthurvause 19 September 2012 at 7:38 am

      The puzzle (without the specific constraints on the card order) is equivalent to question 1002 posed in Mathematics Magazine, Vol. 49, No. 5 (Nov 1976), p. 253, Mathematical Association of America, http://www.jstor.org/stable/2689460, which asked:

      1002. a. For which values of n is it possible to find a permutation of [0, 1,. .., n-1] so that the partial sums, when reduced modulo n, are also a permutation of [0, 1,. .., n-1]? [Bernardo Recamán, University of Warwick.]
      b.* Find the number of permutations of [0, 1,. .., n – 1] for n ≤ 12 which solve part a. Can a general formula for the number of solutions be found? [John Hoyt, Indiana University of Pennsylvania.]

      The answer to part a. was given in Mathematics Magazine, Vol. 51, No. 4 (Sep 1978), p. 247, http://www.jstor.org/stable/2689475. the answer being that even values of n can have such a permutation. The editor notes that part b. was not answered, but that there are 24 permutations for n=8, found with the aid of a computer.

      The answer given does not help in identifying the possible permutations, but all such permutations must have 0 as the first element (i.e. 0 is permuted to itself). Using this together with the constraints of the puzzle, we can rewrite the code as:

      from itertools import permutations as perm
      
      colours={3:'Red',4:'Blue',5:'Green',6:'Orange',7:'Apricot',0:'Primrose',
               1:'Chocolate',2:'Terracotta'}
      
      for p in perm(range(1,7)):
        if p.index(2) < p.index(1):
          spell_order = p + (7,)
          if set([sum(spell_order[0:n+1])%8 for n in range(7)])==set(range(1,8)):
              print 'Primrose', ''.join([colours[spell_order[i]]+' ' for i in range(7)])
      
      • Jim Randell 24 September 2012 at 11:20 am

        A good bit of research, Arthur.

        In my original Perl program to solve this I noted that the lengths of the colours where 0-7 (modulo 8), and I treated the pile as a circular buffer with a pointer, rather than re-arranging the pile itself. Although I do remember writing out the initials of the colours on pieces of paper to satisfy myself that the solution was indeed correct.

        In my Python program above I somewhat mechanically manipulate the pile in the way described in the puzzle to attempt to give code that is more obviously solving the puzzle.

        A more efficient way though is to solve the puzzle backwards, and reconstruct the initial pile starting from the last card turned over (which we are helpfully told is “Apricot”, and we know how many cards must have been moved before we got to it).

        The following recursive algorithm runs in 32ms.

        from enigma import printf
        
        colours = set((
          'Apricot',
          'Blue',
          'Chocolate',
          'Green',
          'Orange',
          'Primrose',
          'Red',
          'Terracotta'
        ))
        N = len(colours)
        
        # solve working backwards
        # p = position in pile
        # pile = initial pile, as worked out so far
        # used = cards used
        # rest = cards that are left
        def solve(p, pile, used, rest):
          # are we done?
          if len(rest) == 0:
            printf("pile = {pile}")
            printf("order = {used}")
            printf("order = {cards}", cards=' '.join(c[0] for c in used))
          # are we looking at an empty slot in the pile?
          if pile[p]: return
          # pick an unused colour
          for c in rest:
            # can only use 'Terracotta' if 'Chocolate' is already in used
            if c == 'Terracotta' and not('Chocolate' in used): continue
            # and count back the length of the colour
            q = (p - len(c)) % N
            # is it unused?
            if pile[q]: continue
            # solve with this colour filled out in the pile
            pile[p] = c
            solve(q, pile, [c] + used, rest.difference([c]))
            pile[p] = None
        
        # the initial pile of cards
        pile = [None] * N
        
        # but we finish on Apricot, so...
        p = sum(len(x) for x in colours) % N
        pile[(p - 1) % N] = 'Apricot'
        
        # and solve for the remainder, working backwards 
        solve(p, pile, ['Apricot'], colours.difference(['Apricot']))
        
  3. Tessa 30 April 2015 at 3:40 pm

    The script below in Matlab was used to find the solution (then submitted) to the puzzle when it was originally posed.

    % enigma 1516
    tpm = [ 0 0 0 0 0 0 7];
    r = [ 1 2 3 4 5 6];
    rpm = perms(r);
    % test each perm
    % for ct = 1:720
    for ct = 1:720
        tpm(1:6) = rpm(ct, :);
        fail = 0;
        for len = 2:6
            for stt = 1:( 7 - len + 1)
                tv = tpm (stt: stt+len-1);
                tvs = sum(tv);
                if mod(tvs, 8) == 0
                    fail = 1;
                    break
                end
            end
        end
        if fail == 0
            disp (' a permutation is')
            p = [fail, tpm]
        end
    end
    %  
    

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: