Matt Parker's Card Flip Game

README.md

This is based on Matt Parker's Youtube Video

Card Flip Game

The card flip game is played by two players.

The first player will place n (usually four) cards face down in a row and then flip some of the cards face up.

The second player will now attempt to flip individual cards in order to make all the cards face down. However, the second player cannot see the cards, they can only describe which card to flip. (first on the left, second on the right etc.)

The game ends when all the cards are face down. The players may then swap roles and try to win in the least flips.

Problem

What is the minimum number of moves that the second player can make and be certain to win.

Solution

There are 2n - 1 initial configurations for the cards. Each flip can only increase the number of checked configurations by 1. Therefore the minimum number of flips must be at least 2n - 1.

If it were smaller, there would be unchecked configurations, and by setting the initial configuration to one of these unchecked configurations the first player could ensure that the second player would not win within the smaller number of moves.

Consider this strategy for flipping cards:

On the nth flip, flip the (k + 1)th card, where k is the number of trailing zeros in the binary representation of n.

Turn	Turn2	Flip
1	1	1
2	10	2
3	11	1
4	100	3
5	101	1
6	110	2
7	111	1
8	1000	4

There is a graph below and some numbers in a spreadsheet.

This strategy will ensure that after 2n - 1 flips, every cobination of the n cards will have been checked.

The proof of this can be done by induction on n, noticing that if the last card starts face down then the solution will be found within 2n-1 - 1 moves, and if it starts face up then the 2n-1th move will flip the last card (since 2n-1 has n - 1 trailing zeros). We can then find the solution within 2n-1 - 1 more moves, and 2n-1 + 2n-1 - 1 = 2n - 1.

Therefore the second player can employ this strategy to win within 2n - 1 moves and there is no strategy to win in less moves, so this is an optimal strategy.

Also this strategy doesn't take the total number of cards on the table into account when deciding which card to flip; in fact if the number of cards is not known by the second player, this strategy will still find the solution eventually!

cards.py

from random import randint

class Card:
  """
  Represents a card on the table which is either face up or face down.
  """
  def __init__(self, initialState=False):
    self._state = initialState

  def flip(self):
    """
    Flips the card.
    """
    self._state = not self._state

  def __bool__(self):
    """
    The card is truthy if it is face up, and falsy if it is face down.
    """
    return self._state

  def __str__(self): return 'up' if self._state else 'down'

class FlipCard:
  """
  Represents a game of flip card.
  """
  def __init__(self, numCards=4):
    # At least one, and perhaps more could be face up.
    configuration = randint(1, 2**numCards - 1)
    self._cards = [Card(bool(configuration >> i & 1)) for i in range(numCards)]

  def flip(self, i):
    """
    Flips the ith card from the left starting from 0.
    """
    self._cards[i].flip()

  def __bool__(self):
    """
    The game is only truthy when all cards are face down
    """
    return all(not card for card in self._cards)

  def __str__(self): return ' '.join(map(str, self._cards))

graph.png

main.py

from cards import FlipCard
from math import log2

def flipIndex(t):
  """
  Returns the index to flip given the try number.
  """
  # t & ~(t - 1) is just t with all **but** the last 1, set to 0.
  return int(log2(t & ~(t - 1)))

def playGame(n):
  """
  Plays a game of "flip card" with n cards and tries to win within 2^n moves.
  """
  game = FlipCard(n)
  maxTries = 2**n
  
  tries = 0
  while not game and tries < maxTries:
    tries += 1
    f = flipIndex(tries)
    # flip card f
    game.flip(f)

  if game:
    # Solution found!
    return True
  else:
    # Oh dear... Solution not found.
    return False

if playGame(4):
  print('We Won!')
else:
  print('We lost....')