Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Haunted House by htamas
# in this solution rooms are numbered from 0 to 15
from itertools import product
dirs = {'N': -4, 'E': +1, 'S': +4, 'W': -1}
edges = ['NW', 'N', 'N', 'NE', 'W', '', '', 'E', 'W', '', '', 'E', 'WS', 'S', 'S', 'ES']
strategy = {}
def sqdist(a, b):
'''squared distance between two rooms (that the dumb ghost tries to minimize)'''
return (a%4 - b%4)**2 + (a//4 - b//4)**2
def precompute(house):
'''precompute Stephen's strategy'''
# calculate our allowed steps and the ghost's possible steps in response
steps = [[d for d in dirs if d not in house[pos] and d not in edges[pos]]
for pos in range(16)]
response = {}
for spos, gpos in product(range(16), range(16)):
gdist = sorted((sqdist(gpos + dirs[d], spos), d) for d in steps[gpos])
response[(spos, gpos)] = [d for dist, d in gdist if dist == gdist[0][0]]
# find a winning move for Stephen in each game state where one exists
global strategy
for pos in range(16):
strategy[(0, pos)] = (0, 'N') # Stephen wins in 0 steps after a move N
strategy[(pos, pos)] = None # ghost wins
for moves, spos, gpos in product(range(1, 31), range(16), range(16)):
if (spos, gpos) in strategy: continue # already calculated
# ghost wins by default, we'll overwrite this if we find a winning move for
# Stephen and clear it if we find one whose results aren't calculated yet
strategy[(spos, gpos)] = None
for sstep in steps[spos]:
snew = spos + dirs[sstep]
if snew == gpos: continue # we'd rather not step into the ghost
gstrat = [] # states that the ghost can achieve with dumb moves
for gstep in response[(snew, gpos)]:
gnew = gpos + dirs[gstep]
if (snew, gnew) in strategy:
gstrat.append(strategy[(snew, gnew)])
if None in gstrat: continue # ghost may move to a state where he wins
if len(gstrat) == len(response[(snew, gpos)]):
# we already calculated all states that the ghost can achieve
# and Stephen can win in all of them
if max(i[0] for i in gstrat) < moves:
strategy[(spos, gpos)] = (moves, sstep)
break
# ghost may move to an uncalculated state, but Stephen can win in all
# the calculated ones => defer this calculation to a later move
if (spos, gpos) in strategy:
del strategy[(spos, gpos)]
def checkio(house, stephen, ghost):
if not strategy:
precompute(house)
return strategy[(stephen-1, ghost-1)][1]
Nov. 5, 2013
Comments:
