Enigmatic Code

Programming Enigma Puzzles

Enigma 1037: The perfect shuffle

From New Scientist #2193, 3rd July 1999 [link]

I recently took an ordinary pack of playing cards and placed them on the table, face down. Somewhere in the pack the four aces were together, and in places further down the kings were together, the queens were together, and the jacks were together.

I then did the “perfect shuffle”. In other words I took the top 26 cards in my left hand, and the other 26 in my right, I flicked the bottom left-hand card on to the table, followed by the bottom right-hand card on top of it, followed by the next left on top of them, next right, next left, and so on. The cards remained face down at all times.

My fellow players were so impressed with this performance that I did three more perfect shuffles with the same pack. When I had finished, the arrangement of suits within the pack was exactly the same as when I started (for example, the top card was a heart before and after the four shuffles, the next was a spade before and after the four shuffles, and so on).

Counting from the top, what was the position of the ace of hearts after the four shuffles?

[enigma1037]

One response to “Enigma 1037: The perfect shuffle

  1. Jim Randell 9 November 2018 at 8:13 am

    Programatically it’s a bit tricky to come up with a general program, and as it turns out the full generality is not needed to solve this puzzle. (See the manual solution below).

    This Python program runs in 73ms.

    Run: [ @repl.it ]

    from itertools import product, combinations
    from enigma import flatten, irange, find, update, tuples, arg, printf
    
    def interleave(*s):
      return flatten(zip(*s))
    
    def shuffle(pack):
      n = len(pack) // 2
      return list(interleave(pack[n:], pack[:n]))
    
    # original pack, top card = 0, bottom card = 51
    pack = list(irange(0, 51))
    
    # suffle the pack n times
    n = arg(4, 0, int)
    p = pack
    for _ in irange(1, n):
      p = shuffle(p)
    
    # associate suits with cards (order is the same in p and pack)
    def associate(p):
    
      suit = [None] * 52
    
      def associate(i, s):
        while suit[i] is None:
          suit[i] = s
          i = p[i]
        assert suit[i] == s
    
      # initial assignments:
      initial = [
        # current card 0 is a heart
        (0, 'H'),
        # original card 0 is a heart
        (p.index(0), 'H'),
        # current card 1 is a spade
        (1, 'S'),
        # original card 1 is a spade
        (p.index(1), 'S'),
      ]
      for (i, s) in initial:
        associate(i, s)
    
      # now fill in remaining values
      v = 1
      while True:
        i = find(suit, None)
        if i == -1: break
        associate(i, v)
        v += 1
    
      # count the number of cards for each value
      vs = set(suit)
      d = dict((v, suit.count(v)) for v in vs)
    
      # available suits
      suits = set('CDHS')
      # we can discard any suits with 13 cards already
      for s in 'HS':
        if d[s] == 13:
          vs.discard(s)
          suits.discard(s)
    
      # and assign the values to suits
      vs = list(vs)
      for ss in product(suits, repeat=len(vs)):
        # count cards in assigned suits
        _d = dict((s, d.get(s, 0)) for s in suits)
        for (v, s) in zip(vs, ss):
          _d[s] += d[v]
        if not all(x == 13 for x in _d.values()): continue
    
        # return a suit assignment
        r = suit
        for (v, s) in zip(vs, ss):
          r = update(r, list(i for (i, x) in enumerate(r) if x == v), [s] * d[v])
        yield r
    
    # associate suits to the shuffed pack
    for suit in associate(p):
      # find locations where each of the 4 suits occur next to each other
      js = list(j for (j, s) in enumerate(tuples(suit, 4)) if len(set(s)) == 4)
      # choose 4 locations for the A, K, Q, J cards in the original pack,
      # A comes first and we don't really care what order the K, Q, J are in
      for (A, K, Q, J) in combinations(js, 4):
        # check they do not overlap
        if not(A + 3 < K and K + 3 < Q and Q + 3 < J): continue
        # find the ace of hearts
        for i in irange(A, A + 3):
          if suit[i] == 'H':
            # where does card i end up in the suffled pack?
            j = p.index(i)
            printf("initially AH at index {i}, finally AH at index {j}")
    

    Solution: The Ace of Hearts is the 44th card down in the shuffled pack.

    If we number the cards from 1 (top) to 52 (bottom), after 4 shuffles we have the following situation:

    (The diagram should really be one long table, with card 1 at the top and card 52 at the bottom. I’ve split it into 4 sections to make it more screen friendly).

    The first column gives the final position of the cards, and the second column gives the initial position of the corresponding card.

    The third column gives the suits of the cards. The sequence of suits is the same in the shuffled pack as the original pack.

    Here is a manual solution:

    So we are told the top card of the shuffled pack is a Heart. The top card of the shuffled pack is the 10th card in the original pack, so the 10th card in the shuffled pack must also be a Heart. And the 10th card in the shuffled pack is the 47th card in the original pack, so the 47th card in the shuffled pack must also be a Heart. And so on.

    In this way we can mark the cards in positions: 1, 10, 47, 46, 36, 42, 49, 13, 24, 28, 15, 44, 16, as Hearts. And this accounts for all 13 Hearts.

    Similarly, the 2nd card in the shuffled pack is a Spade. So we can mark the cards in positions: 2, 20, 41, 39, 19, 31, 45, 26, 48, 3, 30, 35, 32 as Spades. And this accounts for all 13 Spades.

    The next card that is not allocated a suit is card 4. As no distinction is made in the puzzle between Clubs and Diamonds we can mark card 4 as a Club, and this leads us to marking cards: 4, 40, 29, 25, 38, 9, 37, 52, 43, 6, 7, 17, 11 as Clubs. This accounts for all 13 Clubs.

    Card 5 can then be marked as a Diamond, and this leads to marking the cards: 5, 50, 23, 18, 21, 51, 33, 12, 14, 34, 22, 8, 27 as Diamond. This accounts for all 13 Diamonds.

    Now all cards have been assigned a suit (there is a second solution where Clubs and Diamonds are interchanged, but it won’t change the answer to the puzzle).

    We can now look for consecutive sequences of cards of length 4 where all suits are represented, and we find the following sequences work:

    (16, 17, 18, 19), (23, 24, 25, 26), (24, 25, 26, 27), (25, 26, 27, 28), (26, 27, 28, 29), (27, 28, 29, 30), (34, 35, 36, 37)

    And we need 4 non-overlapping sequences. The only possible option is:

    (16, 17, 18, 19), (23, 24, 25, 26), (27, 28, 29, 30), (34, 35, 36, 37)

    So cards (16, 17, 18, 19) in the original pack are the Aces, and the other three sequences are the Kings, Queens and Jacks.

    So the Ace of Hearts was card 16 in the initial pack, and card 16 ends up in position 44 in the shuffled pack, so in the shuffled pack the Ace of Hearts is the 44th card.

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: