Enigmatic Code

Programming Enigma Puzzles

Enigma 988: Cards high and low

From New Scientist #2143, 18th July 1998 [link]

Benjamin and Matthew have a new card game involving 50 cards numbered 1 to 50. They deal out the cards and Matthew finds he has 1 to 16 and 36 to 44. The game consists of 25 rounds. In each round one player places one of his cards face-up on the table and then the other places one of his face-up on the table. The one who has played the higher card wins that round; the two cards on the table are discarded. For the first round the players toss [a coin] to see who goes first, but after that, each round is begun by the winner of the previous round.

Benjamin and Matthew are both experts at the game and each plays so as to win as many rounds as possible.

(1) How many rounds does Benjamin win?
(2) For the next game Matthew has 1 to 7 and 16 to 33. How many rounds does Benjamin win?
(3) For the final game Matthew has 1 to 8 and 30 to 46. How many rounds does Benjamin win?

[enigma988]

One response to “Enigma 988: Cards high and low

  1. Jim Randell 18 October 2019 at 9:20 am

    See also: Enigma 1201, Enigma 1321.

    This puzzle is very similar to Enigma 1201 (although it was published some 4 years before it).

    I have refined the program I wrote when I solved that puzzle.

    I still separate the cards into 4 categories, which I label category 0, 1, 2, 3, and a card in any category beats all the cards in any lower numbered category, and is beaten by all the cards in any higher numbered category. The players hold cards in distinct categories, so there are no draws. Each round is won by one of the players, so we can consider the number of rounds won by player A as a measure of the game. Player A seeks to maximise this measure, and Player B seeks to minimise it.

    The following Python program solves all 3 parts of the puzzle in 174ms.

    Run: [ @repl.it ]

    from enigma import cached, printf
    
    # win for card a against card b
    winA = lambda a, b: (a > b)
    winB = lambda a, b: (a < b)
    # strategy for A: maximise number of wins for A
    bestA = max
    # strategy for B: minimise number of wins for A
    bestB = min
    
    # remove cards
    def remove(cards, xs):
      return tuple(n - (i in xs) for (i, n) in enumerate(cards))
    
    # return: wins for A
    # cards = (c0, c1, c2, c3): number of cards in each category
    # go = 1 if A's go, 0 if B's go
    @cached
    def play(cards, go=1):
    
      # if one player is holding only one type of card
      if 0 in cards:
        As = [0] * cards[0] + [2] * cards[2]
        Bs = [1] * cards[1] + [3] * cards[3]
        return sum(winA(a, b) for (a, b) in zip(As, Bs))
    
      if go == 1:
        # A goes first
        (xs, ys, fn, bestX, bestY) = ((0, 2), (1, 3), winA, bestA, bestB)
      else:
        # B goes first
        (xs, ys, fn, bestX, bestY) = ((1, 3), (0, 2), winB, bestB, bestA)
    
      # X goes first
      Xs = list()
      # choose a card for X to play
      for x in xs:
        if not cards[x]: continue
        # choose a card for Y to play
        Ys = list()
        for y in ys:
          if not cards[y]: continue
          w = fn(x, y)
          # and play the remaining cards
          r = play(remove(cards, (x, y)), w)
          Ys.append(r + w)
        # Y chooses the best outcome for them
        Xs.append(bestY(Ys))
      # X chooses the best outcome for them
      return bestX(Xs)
    
    # consider the given situations
    qs = [(16, 19, 9, 6), (7, 8, 18, 17), (8, 21, 17, 4)]
    for (i, cards) in enumerate(qs, start=1):
      # toss the coin
      for p in (1, 0):
        m = play(cards, p)
        printf("({i}) cards = {cards}, first = {p}: M wins {a}, B wins {b}", a=m, b=25 - m, p="BM"[p])
      printf()
    

    Solution: In the three games Benjamin wins: (1) 16 rounds; (2) 17 rounds; (3) 12 rounds.

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: