Python implementation of Toads and Frogs solver.

toadsfrogs.py

# Python implementation of Toads and Frogs.
# See http://en.wikipedia.org/wiki/Toads_and_Frogs_(game)
# Author: Jon Brandvein


# Toads move right, frogs move left. Each piece can jump over
# the opposite kind of piece.
p1_rules = [
    ('t.', '.t'),
    ('tf.', '.ft'),
]
p2_rules = [
    ('.f', 'f.'),
    ('.tf', 'ft.'),
]


def step(state, trans):
    """Take in a state and a list of transition rules, and produce a
    list of possible successor states. States are represented as
    strings, and a transition rule is a pair of an input substring
    and its corresponding output substring.
    """
    next_states = []
    
    # Try matching each rule at each index.
    for i in range(len(state)):
        for rule_in, rule_out in trans:
            n = len(rule_in)
            if state[i:i+n] == rule_in:
                next = state[:i] + rule_out + state[i+n:]
                next_states.append(next)
    
    return next_states


def play(state):
    """Take in an initial state and produce a list of all possible
    outcomes. An outcome is a pair of a final state and a winning
    player.
    """
    turn = 'p1'
    switchturn = {'p1': 'p2', 'p2': 'p1'}
    states = {state}
    outcomes = set()
    
    # Breadth-first search through game tree.
    while len(states) > 0:
        rules = {'p1': p1_rules, 'p2': p2_rules}[turn]
        next_round = set()
        
        for in_s in states:
            next_states = step(in_s, rules)
            if len(next_states) == 0:
                winner = switchturn[turn]
                outcomes.add((in_s, winner))
            next_round.update(next_states)
        
        states = next_round
        turn = switchturn[turn]
    
    return sorted(outcomes)


def show_play(state):
    """Play and pretty-print the outcomes."""
    outcomes = play(state)
    for state, winner in outcomes:
        winnerstr = {'p1': 'toads win', 'p2': 'frogs win'}[winner]
        print(state + '  ' + winnerstr)
    print()


# Example runs.

show_play('.tt.ff')
show_play('tt..ff')
show_play('tt...ff')

it doesn't work