Enigmatic Code

Programming Enigma Puzzles

Enigma 1404: No repeats

From New Scientist #2564, 12th August 2006

Amber and Ben have a new game. They lay out a row of three coins, all showing heads. They take it in turns, beginning with Amber, to turn one of the coins over. They must not turn a coin so as to produce a pattern of heads and tails which is the same as a pattern that has occurred earlier in the game.

For example, if Amber’s first move is to THH then Ben cannot move back to HHH. The first person who cannot make a move is the loser.

Question 1. If both players play as well as possible, who is the winner?

They now change the game by playing with a row of four coins, but the other rules are unchanged.

Question 2. If again, both play as well as possible, who is the winner?

They now change the rules again. They go back to three coins, but the first person who cannot make a move is the winner.

Question 3. If again, both play as well as possible who is the winner?



One response to “Enigma 1404: No repeats

  1. Jim Randell 10 August 2013 at 4:46 pm

    I found this one quite a satisfying problem to solve.

    This Python program uses a recursive function to examine the game tree. It runs in 40ms.

    from enigma import printf
    # players are labelled 0 (goes first) and 1 (goes second)
    # play a game, return the winner
    # ss - sequence of moves so far
    # w - winning rule
    def play(ss, w):
      # which player are we? (0 or 1)
      p = (len(ss) % 2) ^ 1
      # take the previous position
      s = ss[-1]
      # and generate new moves from it
      ts = list()
      for (i, _) in enumerate(s):
        t = list(s)
        t[i] ^= 1
        if t not in ss: ts.append(t)
      # if there are no moves say which player wins
      if len(ts) == 0:
        return w(p)
        # find who wins each branch?
        for t in ts:
          # if there's a branch where we win then we'd do that
          if play(ss + [t], w) == p: return p
        # otherwise, the other player wins
        return p ^ 1
    # identify the players
    players = 'AB'
    # winning criteria, if p can't move who is the winner?
    loser_cant_move = lambda p: p ^ 1
    winner_cant_move = lambda p: p
    q1 = play([[0] * 3], loser_cant_move)
    printf("1: {q1} wins", q1=players[q1])
    q2 = play([[0] * 4], loser_cant_move)
    printf("2: {q2} wins", q2=players[q2])
    q3 = play([[0] * 3], winner_cant_move)
    printf("3: {q3} wins", q3=players[q3])

    Solution: 1. Amber; 2. Amber; 3. Ben.

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: