Created
June 2, 2013 18:33
-
-
Save brandjon/5694417 to your computer and use it in GitHub Desktop.
Python implementation of Toads and Frogs solver.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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') |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
it doesn't work