Enigmatic Code

Programming Enigma Puzzles

Enigma 1201: Cards on the table

From New Scientist #2357, 24th August 2002 [link]

Frances and Matthew are playing a game of cards. There are 30 cards in the game, numbered 1, 2, 3, …, 30 and each player has 15 [cards] at the start of the game. Frances has 5, 6, …, 16 and 28, 29, 30, while Matthew has 1, 2, 3, 4 and 17, 18, …, 27.

The game consists of 15 rounds. In each round the player who won the previous round goes first, except that in the first round Frances goes first. A round consists of the players alternately taking a card from their hand and putting it face up on the table. When all cards are on the table, the last two to be put on the table are compared and the player who put the higher of those two cards wins the round. The two cards that were compared are then discarded from the game and the players pick up their remaining cards; they then play the next round. Frances and Matthew are both superb players, playing as well as anyone could.

Question 1: At the end of the game, how many rounds had Frances won?

On another occasion they used 100 cards. Frances started with 28, 29, …, 37 and 61, 62, …, 100, and Matthew with the other fifty cards.

Question 2: At the end of the game, how many rounds had Frances won?

On a third occasion they used 200 cards. Frances started with 76, 77, …, 130 and 156, 157, …, 200, and Matthew with the other 100 cards.

Question 3: At the end of the game, how many rounds had Frances won?

Enigma 1252 is also called “Cards on the table”.

[enigma1201]

Advertisements

5 responses to “Enigma 1201: Cards on the table

  1. Jim Randell 21 September 2015 at 9:04 am

    First a bit of analysis to simplify the problem.

    Frances has: 5 – 16, 28 – 30
    Matthew has: 1 – 4, 17 – 27

    As the cards are contiguous numbered blocks we can replace these cards by 4 categories:

    Frances: 12× 2, 3× 4
    Matthew: 4× 1, 11× 3

    Where 4 beats (3, 2, 1); 3 beats (2, 1); 2 beats (1).

    If we get to a situation where either player holds only one type of card then the result of the remaining rounds is determined.

    So the interesting cases are (for the final card):

    F plays 2, M plays 1 = F wins
    F plays 2, M plays 3 = M wins
    F plays 4, M plays 1 = F wins
    F plays 4, M plays 3 = F wins

    The only way M can win is if F plays a 2 card and M plays a 3.

    The problem is similar to Enigma 1321. The following Python program examines the possible games for each initial set-up, and at each stage F plays to maximise her score and M plays to minimise F’s score (and so maximise his own score). It analyses all three cases in 2.1s.

    from enigma import cached, printf
    
    # is this a win for F?
    def win(f, m):
      return int(f > m)
    
    # remove an <x> from a sequence <s>
    def remove(s, x):
      i = s.index(x)
      return s[:i] + s[i + 1:]
    
    # F attempts to maximise the number of wins for F
    def bestF(fr):
      return max(fr, key=lambda r: r[0])
    
    # M attempts to minimise the number of wins for F
    def bestM(mr):
      return min(mr, key=lambda r: r[0])
    
    # return (wins for F, final cards for F, final cards for M)
    # F - F's cards
    # M - M's cards
    # go - who's go is it? (1 = F, 0 = M)
    @cached
    def play(F, M, go=1):
    
      (Fs, Ms) = (set(F), set(M))
    
      # if one player is holding only one type of card
      if len(Fs) == 1 or len(Ms) == 1:
        return (sum(win(f, m) for (f, m) in zip(F, M)), F, M)
    
      if go == 1:
        # F to play
        fr = list()
        for f in Fs:
          # M's response
          mr = list()
          for m in Ms:
            w = win(f, m)
            # play the remaining cards
            (r, fs, ms) = play(remove(F, f), remove(M, m), w)
            mr.append((r + w, f + fs, m + ms))
          # M chooses the lowest score
          fr.append(bestM(mr))
        # F chooses the highest score
        return bestF(fr)
    
      else:
        # M to play
        mr = list()
        for m in Ms:
          # F's response
          fr = list()
          for f in Fs:
            w = win(f, m)
            # play the remaining cards
            (r, fs, ms) = play(remove(F, f), remove(M, m), w)
            fr.append((r + w, f + fs, m + ms))
          # F chooses the highest score
          mr.append(bestF(fr))
        # M chooses the lowest score
        return bestM(mr)
    
    
    # cards for Frances and Matthew in each of the questions
    qs = (
      ('2' * 12 + '4' *  3, '1' *  4 + '3' * 11),
      ('2' * 10 + '4' * 40, '1' * 27 + '3' * 23),
      ('2' * 55 + '4' * 45, '1' * 75 + '3' * 25),
    )
    
    # play the game
    for (q, (F, M)) in enumerate(qs, start=1):
    
      n = len(F)
      assert n == len(M)
    
      (f, fs, ms) = play(F, M)
      printf("({q}) Frances wins {f}, Matthew wins {m} [{fs},{ms}]", m = n - f)
    

    Solution: (1) Frances wins 7 of the rounds; (2) Frances wins 40 of the rounds; (3) Frances wins 75 of the rounds.

    • Hugh Casement 21 September 2015 at 6:18 pm

      Is it possible to come up with a general strategy for the player who goes first in any round?
      For example, either to sacrifice the low-scoring cards in the first few rounds, or else to leave them until the end?  Or is it more subtle than that?

      • Jim Randell 21 September 2015 at 7:35 pm

        I haven’t done a deep analysis, but in the three situations given a strategy for Frances seems to be to finish each round with one of her lower scoring cards (the 2’s in my renaming) until those are exhausted. The strategy for Matthew doesn’t seem to be quite so simple.

        • Hugh Casement 22 September 2015 at 7:53 am

          Thanks, Jim.  I feel there’s a certain advantage in losing a round, because then the opponent goes first in the next round and you can see what you’re up against.  But I can well believe Frances and Matthew need somewhat different strategies, because the cards are not evenly distributed.

  2. arthurvause 11 October 2015 at 11:51 am

    Using Jim’s notation of reducing the cards to 1,2,3,4, the code below calculates the wins if Matthew follows what I think is an optimum strategy.

    Frances’ best strategy when leading is to lead a 2, (otherwise leading a 4 will result in Matthew discarding a 1, and Frances still has the lead).

    I have checked that the strategy in my code produces the same result as Jim’s minimax search for all combinations of cards in a deck of 100.

    There is probably a simpler formula that expresses the number of wins in terms of N1,N2,N3,N4 (the number of cards of value 1,2,3,4 respectively), but that’s for another post, as is a rigorous proof that the strategy in this code is optimal.

    def MatthewWins(N1,N2,N3,N4):
      # first round, Frances leads a 2, which Matthew wins with a 3
      wins=1
      N2-=1
      N3-=1
    
      while min((N1,N2,N3,N4))>0:
    
        if N3==N2==1:
          # the game's up, Matthew can't win any more rounds
          return wins
          
        elif N3>=N2:
          # Matthew leads a 3, Frances wins with a 4
          # Frances returns a 2 which Matthew wins with a 3
          wins+=1
          N4-=1
          N2-=1
          N3-=2
    
        elif  N3<N2:
          # Matthew leads a 1, Frances wins with a 2
          # Frances returns a 2 which Matthew wins with a 3
          wins+=1
          N1-=1
          N2-=2
          N3-=1
    
        else:
          # we should have covered all cases
          raise ValueError('Unexpected values for N2, N3',N2,N3)
          
         
      # one value has been completely used up
      wins += min((N2,N3))
    
      return wins  
    
    for (N1,N2,N3,N4) in ( (4,12,11,3), (27,10,23,40), (75,55,25,45) ):
      mw = MatthewWins(N1,N2,N3,N4)
      fw = N2+N4-mw
      print "(N1,N2,N3,N4)= ({},{},{},{}), Frances wins {}, Matthew wins {}".format(N1,N2,N3,N4,fw,mw)
    
    

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: