# 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?

[enigma1404]

### 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)
else:
# 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.

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