Skip to content

Instantly share code, notes, and snippets.

@mgritter

mgritter/ghost.py

Created Mar 23, 2018
Embed
What would you like to do?
Solver for 'ghost' word game
words = set()
with open( "sowpods.txt", "r" ) as wordFile:
for x in wordFile:
words.add( x.rstrip() )
maxLen = max( len(x) for x in words )
alphabet = [ 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I',
'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R',
'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' ]
_infixes = [ set() for i in xrange( maxLen + 1 ) ]
_infixesBuilt = False
def build_infixes():
for w in words:
for l in xrange( 2, len( w ) ):
for i in xrange( 0, l ):
_infixes[l].add( w[i:i+l] )
global _infixesBuilt
_infixesBuilt = True
winners = {}
def winner( position ):
if not _infixesBuilt:
build_infixes()
# Previous player said a word, current player wins
if len( position ) >= 4 and position in words:
#print position, "word", "N"
return "N"
# No words available, current player challenges and wins
if len( position ) >= 2 and position not in _infixes[ len( position ) ]:
#print position, "noprefix", "N"
return "N"
if position in winners:
#print position, "already winner", "N"
return "N"
for a in alphabet:
for np in [ position + a, a + position ]:
if winner( np ) == "P":
winners[ position ] = np
#print position, "move to", np, "N"
return "N"
# Previous player wins only if next player has no winning move
#print position, "no good move", "P"
return "P"
def winningMove( position ):
# Doesn't return good results if this was not a part of the
# tree that was explored.
if position in winners:
print "move to", winners[position]
return
if len( position ) >=2 and position not in _infixes[ len( position ) ]:
print "challenge"
return
if len( position ) >=4 and position in words:
print "losing position, valid word"
return
print "losing position"
losingWords = []
challengeMoves = []
for a in alphabet:
for (w,short) in [ ( position + a, "*" + a ), ( a + position, a + "*" ) ]:
if len( w ) >= 4 and w in words:
losingWords.append( w )
elif w in winners:
print w, "response is", winners[w]
elif len ( w ) >= 2 and w not in _infixes[ len( w ) ]:
challengeMoves.append( short )
print "Valid words:", " ".join( losingWords )
print "Challenge positions:", " ".join( challengeMoves )
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment