Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Second solution in Clear category for Haunted House by sawako.oono
import copy
def checkio(house, stephan, ghost):
"""
Simulate ghost's next location,based on it's logic.
Then among the Stephen's next move options,
take the option which moves Staphan as close to the exit as possible
while possible distance from ghost is larger than 0.
When Stephan is at 1, let's get away !
"""
directions={"E":(0,1),"W":(0,-1),"S":(1,0),"N":(-1,0)}
oppos={"N":"S","S":"N","E":"W","W":"E"}
gy,gx=(ghost-1)//4,(ghost-1)%4
sy,sx=(stephan-1)//4,(stephan-1)%4
g_options=[]
#Create distance map from the exit
distance=[]
for i in range(16):
if i%4==0:
distance.append([])
distance[-1].append(None if i!=0 else 0)
d_copy=[]
while d_copy!=distance:
d_copy=copy.deepcopy(distance)
for Y in range(4):
for X in range(4):
if Y==0 and X==0:continue
options=[]
for key,(y,x) in directions.items():
if 0<=(Y+y)<=3 and 0<=(X+x)<=3:
if oppos[key] not in house[4*(Y+y)+X+x] and key not in house[4*Y+X]:
options.append(distance[Y+y][X+x])
options=[i for i in options if i!= None]
distance[Y][X]=min(options)+1 if options!=[] else None
#Ghost move
for key,(y,x) in directions.items():
if 0<=(gy+y)<=3 and 0<=(gx+x)<=3:
if oppos[key] not in house[4*(gy+y)+gx+x] and key not in house[4*gy+gx]:
g_options.append(((gy+y,gx+x),abs(gy+y-sy)+abs(gx+x-sx)))
assumed=[i[1] for i in g_options]
#List of possible next positions of ghost
g_next=[i[0] for i in g_options if i[1]==min(assumed)]
#Create distance map from each possible next position of ghodst
ghost_dist={}
for pat in g_next:
gt=pat[0]*4+pat[1]
gdistance=[]
for i in range(16):
if i%4==0:
gdistance.append([])
gdistance[-1].append(None if i!=gt else 0)
gd_copy=[]
while gd_copy!=gdistance:
gd_copy=copy.deepcopy(gdistance)
for Y in range(4):
for X in range(4):
if Y==pat[0] and X==pat[1]:continue
options=[]
for key,(y,x) in directions.items():
if 0<=(Y+y)<=3 and 0<=(X+x)<=3:
if oppos[key] not in house[4*(Y+y)+X+x] and key not in house[4*Y+X]:
options.append(gdistance[Y+y][X+x])
options=[i for i in options if i!= None]
gdistance[Y][X]=min(options)+1 if options!=[] else None
ghost_dist[pat]=gdistance
#Stephan move
def Stephan(ghost_dist,distance):
s_options=[]
if stephan==1:
return "N"
for key,(y,x) in directions.items():
if 0<=(sy+y)<=3 and 0<=(sx+x)<=3:
if oppos[key] not in house[4*(sy+y)+sx+x] and key not in house[4*sy+sx]:
s_options.append(((sy+y,sx+x),min([ghost_dist[pat][sy+y][sx+x] for pat in g_next]),distance[sy+y][sx+x],key))
s_options.sort(key=lambda x:x[2]) #Sort Stephan's move so that closer-to-exit options come first
if len(s_options)!=1:
s_options=[i for i in s_options if i[1]!=0] #If there is a risk of running into ghost, throw that option away
s_options=(i[3] for i in s_options)
#Take the first one of remaining
return next(s_options)
return Stephan(ghost_dist,distance)
if __name__ == '__main__':
#This part is using only for self-checking and not necessary for auto-testing
from random import choice
DIRS = {"N": -4, "S": 4, "E": 1, "W": -1}
def check_solution(func, house):
stephan = 16
ghost = 1
for step in range(30):
direction = func(house[:], stephan, ghost)
if direction in house[stephan - 1]:
print('Stefan ran into a closed door. It was hurt.')
return False
if stephan == 1 and direction == "N":
print('Stefan has escaped.')
return True
stephan += DIRS[direction]
if ((direction == "W" and stephan % 4 == 0) or (direction == "E" and stephan % 4 == 1) or
(stephan < 1) or (stephan > 16)):
print('Stefan has gone out into the darkness.')
return False
sx, sy = (stephan - 1) % 4, (stephan - 1) // 4
ghost_dirs = [ch for ch in "NWES" if ch not in house[ghost - 1]]
if ghost % 4 == 1 and "W" in ghost_dirs:
ghost_dirs.remove("W")
if not ghost % 4 and "E" in ghost_dirs:
ghost_dirs.remove("E")
if ghost <= 4 and "N" in ghost_dirs:
ghost_dirs.remove("N")
if ghost > 12 and "S" in ghost_dirs:
ghost_dirs.remove("S")
ghost_dir, ghost_dist = "", 1000
for d in ghost_dirs:
new_ghost = ghost + DIRS[d]
gx, gy = (new_ghost - 1) % 4, (new_ghost - 1) // 4
dist = (gx - sx) ** 2 + (gy - sy) ** 2
if ghost_dist > dist:
ghost_dir, ghost_dist = d, dist
elif ghost_dist == dist:
ghost_dir += d
ghost_move = choice(ghost_dir)
ghost += DIRS[ghost_move]
if ghost == stephan:
print('The ghost caught Stephan.')
return False
print("Too many moves.")
return False
assert check_solution(checkio,
["", "S", "S", "",
"E", "NW", "NS", "",
"E", "WS", "NS", "",
"", "N", "N", ""]), "1st example"
assert check_solution(checkio,
["", "", "", "",
"E", "ESW", "ESW", "W",
"E", "ENW", "ENW", "W",
"", "", "", ""]), "2nd example"
July 9, 2021