#!/usr/bin/python3 import sys # Maps are represented as a dictionary of (x,y) tuples -> '#', '.' dx = [0, 1, 0, -1] dy = [-1, 0, 1, 0] dn = "NESW" def explore(start, avoid=None): # Input is the info at the current location # Returns a map, the final square and the info after falling through trapdoor as a tuple # If no trapdoor reached, returns (map, None, None) will_visit = {(0,0)} stack = [] avoid_walk = None def add(x, y, info, walk): nonlocal avoid_walk for i in range(4): nx, ny = x + dx[i], y + dy[i] if (nx,ny) not in map: map[(nx, ny)] = '?' if info[i] == '.' else info[i] if avoid and nx == avoid[0] and ny == avoid[1]: if not avoid_walk or len(walk) < len(avoid_walk): avoid_walk = walk + dn[i] continue if info[i] == '.' and (nx,ny) not in will_visit: stack.append((x, y, dn[(i+2)%4])) stack.append((nx, ny, dn[i])) will_visit.add((nx, ny)) map={(0,0): '.'} walk = '' add(0, 0, start, walk) while len(stack) > 0: (x, y, dir) = stack.pop() print(dir) walk += dir if len(walk) >= 2: last2 = walk[-2:] if last2 in ['UD', 'DU', 'RL', 'LR']: walk = walk[:-2] info = input().split(' ') add(x, y, info[0], walk) if info[1] == 'trap': map[(x,y)] = 'T' return (map, (x,y), info[2]) map[(x,y)] = '.' if not avoid_walk: return (map, (0,0), None) for c in avoid_walk[:-1]: print(c) ignore = input() stack.append((avoid[0], avoid[1], avoid_walk[-1])) avoid = None while len(stack) > 0: (x, y, dir) = stack.pop() print(dir) info = input().split(' ') add(x, y, info[0], '') if info[1] == 'trap': map[(x,y)] = 'T' return (map, (x,y), info[2]) map[(x,y)] = '.' raise Exception('Shouldn\'t happen') def final_explore(map, sx, sy, trap): # Explore the missing part of the map once we know where the traps are. # Avoid all traps. Once we can't get any further, walk onto the given trap # and continue explore (and avoid traps) until we can't get any further. sys.stderr.write('Starting final explore at %c\n' % map[(sx, sy)]) will_visit = {(sx,sy)} stack = [] trap_walk = None def add(x, y, info, walk): nonlocal trap_walk for i in range(4): nx, ny = x + dx[i], y + dy[i] if (nx,ny) not in map: assert info map[(nx, ny)] = info[i] if map[(nx, ny)] == trap: if not trap_walk or len(walk) < len(trap_walk): trap_walk = walk + dn[i] if map[(nx, ny)] in 'abS.?' and (nx,ny) not in will_visit: stack.append((x, y, dn[(i+2)%4])) stack.append((nx, ny, dn[i])) will_visit.add((nx, ny)) walk = '' add(sx, sy, None, walk) while len(stack) > 0: (x, y, dir) = stack.pop() print(dir) walk += dir if len(walk) >= 2: last2 = walk[-2:] if last2 in ['UD', 'DU', 'RL', 'LR']: walk = walk[:-2] info = input().split(' ') add(x, y, info[0], walk) assert info[1] == 'ok' if map.get((x,y), '?') == '?': map[(x,y)] = '.' for c in trap_walk[:-1]: print(c) ignore = input() (tx, ty) = next(x for x in map.items() if x[1]==trap.lower())[0] stack.append((tx, ty, trap_walk[-1])) sys.stderr.write('Final explore, preparing to walk on trap %c reaching %d,%d\n' % (trap, tx, ty)) avoid = None first = True while len(stack) > 0: (x, y, dir) = stack.pop() print(dir) info = input().split(' ') assert (info[1] == 'trap') == first first = False add(x, y, info[0], '') if map.get((x,y), '?') == '?': map[(x,y)] = '.' def get_map(map): minx = min(map.keys(), key=lambda xy:xy[0])[0] maxx = max(map.keys(), key=lambda xy:xy[0])[0] miny = min(map.keys(), key=lambda xy:xy[1])[1] maxy = max(map.keys(), key=lambda xy:xy[1])[1] final_map = [] for y in range(miny, maxy+1): final_map.append(''.join([map.get((x, y), '#') for x in range(minx, maxx+1)])) return final_map def show_map(map): map = get_map(map) print('done') print('%d %d' % (len(map), len(map[0]))) for s in map: print(s) def incompat(old_char, new_char): if old_char == '#' and new_char != '#': return True if new_char == '#' and old_char != '#': return True if old_char in 'AB' and new_char in 'AB' and old_char != new_char: return True if old_char in 'ab' and new_char in 'ab' and old_char != new_char: return True if old_char in 'AB' and new_char in '.#': return True if new_char in 'AB' and old_char in '.#': return True return False def prio_char(old_char, new_char): for c in '#ABSab.?': if c == old_char or c == new_char: return c raise Exception('Should not happen') def build_map(bmap, partial_map, ox, oy, o, trap): if bmap is None: return None for (x,y), c in partial_map.items(): nx, ny = x+ox, y+oy if c == 'T': tx, ty = nx, ny continue # Handled below if (nx,ny) in bmap and incompat(bmap[(nx,ny)], c): return None else: bmap[(nx,ny)] = prio_char(bmap.get((nx,ny), '?'), c) if incompat(bmap[(ox,oy)], o): return None bmap[(ox,oy)] = o if (tx,ty) in bmap and incompat(bmap[(tx, ty)], trap): return None bmap[(tx, ty)] = trap return bmap def get_trap_positions(partial_map): # returns a dict {'A' -> (Ax, Ay) etc } pos = {} for (x, y), c in partial_map.items(): if c in 'ABab': pos[c] = (x, y) return pos def diff(c1, c2): (x1, y1) = c1 (x2, y2) = c2 return (x1 - x2, y1 - y2) if __name__ == "__main__": start_info = input() (start_map, (sx, sy), new_info) = explore(start_info) if not new_info: # Simple case - no traps start_map[(0,0)] = 'S' show_map(start_map) exit(0) sys.stderr.write('Starting phase 1\n') (map1, (x1, y1), new_info) = explore(new_info) sys.stderr.write('Starting phase 2\n') (map2, (x2, y2), new_info) = explore(new_info, (x1, y1)) sys.stderr.write('Starting phase 3, avoiding %d,%d\n' % (x2,y2)) (map3, (x3, y3), new_info) = explore(new_info, (x2, y2)) if x2==x3 and y2==y3: # Must mean there is only one trap current_map = {} current_map = build_map(current_map, start_map, x1-sx, y1-sy, 'S', 'A') current_map = build_map(current_map, map1, 0, 0, 'a', 'A') current_map = build_map(current_map, map2, 0, 0, 'a', 'A') assert current_map show_map(current_map) sys.stderr.write('Case AAA\n') exit(0) # Assume we fell down into 'A' and 'A' on start_map and map1 # and then into 'B' on map2 and 'A' again in map3 aaba_map = {} aaba_map = build_map(aaba_map, start_map, x1-sx, y1-sy, 'S', 'A') aaba_map = build_map(aaba_map, map1, 0, 0, 'a', 'A') aaba_map = build_map(aaba_map, map2, 0, 0, 'a', 'B') aaba_map = build_map(aaba_map, map3, x1-x3, y1-y3, 'b', 'A') # Assume we fell down into 'A' and 'A' on start_map and map1 # and then into 'B' on map2 and 'B' again in map3 aabb_map = {} aabb_map = build_map(aabb_map, start_map, x1-sx, y1-sy, 'S', 'A') aabb_map = build_map(aabb_map, map1, 0, 0, 'a', 'A') aabb_map = build_map(aabb_map, map2, 0, 0, 'a', 'B') aabb_map = build_map(aabb_map, map3, x2-x3, y2-y3, 'b', 'B') # Assume we fell down into 'A' then 'B' then 'B' then 'A' abba_map = {} abba_map = build_map(abba_map, start_map, x3-sx, y3-sy, 'S', 'A') abba_map = build_map(abba_map, map1, x2-x1, y2-y1, 'a', 'B') abba_map = build_map(abba_map, map2, 0, 0, 'b', 'B') abba_map = build_map(abba_map, map3, 0, 0, 'b', 'A') # Assume ABAA abaa_map = {} abaa_map = build_map(abaa_map, start_map, x3-sx, y3-sy, 'S', 'A') abaa_map = build_map(abaa_map, map1, 0, 0, 'a', 'B') abaa_map = build_map(abaa_map, map2, x3-x2, y3-y2, 'b', 'A') abaa_map = build_map(abaa_map, map3, 0, 0, 'a', 'A') num_possible_maps = (1 if aaba_map else 0) + (1 if aabb_map else 0) + (1 if abba_map else 0) + (1 if abaa_map else 0) if num_possible_maps == 2 and aabb_map and abba_map: sys.stderr.write('\n') sys.stderr.write('\n'.join(get_map(aabb_map))) sys.stderr.write('\n\n') sys.stderr.write('\n'.join(get_map(abba_map))) sys.stderr.write('\n') aabb_pos = get_trap_positions(aabb_map) abba_pos = get_trap_positions(abba_map) d1 = diff(aabb_pos['A'], aabb_pos['b']) d2 = diff(aabb_pos['B'], aabb_pos['b']) d3 = diff(abba_pos['A'], abba_pos['b']) d4 = diff(abba_pos['B'], abba_pos['b']) sys.stderr.write('%d,%d %d,%d\n' % (d1[0], d1[1], d2[0], d2[1])) sys.stderr.write('%d,%d %d,%d\n' % (d3[0], d3[1], d4[0], d4[1])) if d2 == d3: d = d2 e = d4 elif d1 == d3: d = d1 e = d4 elif d2 == d4: d = d2 e = d3 elif d1 == d4: d = d1 e = d3 else: assert(False) (map4, (x4, y4), new_info) = explore(new_info, (x3, y3)) (map5, (x5, y5), new_info) = explore(new_info, d) # Now it's either AABBB or ABBAB if (x5, y5) == e: final_explore(aabb_map, x2-x3, y2-y3, 'A') show_map(aabb_map) sys.stderr.write('Case AABBB\n') exit(0) final_explore(abba_map, x2-x1, y2-y1, 'B') show_map(abba_map) sys.stderr.write('Case ABBAB\n') exit(0) if num_possible_maps > 1: sys.stderr.write('OOPS %d possible maps:\n' % num_possible_maps) if aaba_map: sys.stderr.write('AABA ') if aabb_map: sys.stderr.write('AABB ') if abba_map: sys.stderr.write('ABBA ') if abaa_map: sys.stderr.write('ABAA ') sys.stderr.write('\n') sys.stderr.write('%d %d\n' % (x1==x2 and y1==y2, x2==x3 and y2==y3)) if abba_map: final_explore(abba_map, x2-x1, y2-y1, 'B') show_map(abba_map) sys.stderr.write('Case ABBA\n') exit(0) if aaba_map: final_explore(aaba_map, 0, 0, 'B') show_map(aaba_map) sys.stderr.write('Case AABA\n') exit(0) if aabb_map: final_explore(aabb_map, x2-x3, y2-y3, 'A') show_map(aabb_map) sys.stderr.write('Case AABB\n') exit(0) if abaa_map: final_explore(abaa_map, 0, 0, 'B') show_map(abaa_map) sys.stderr.write('Case ABAA\n') exit(0) # Must be ABAB - we need another walk, to force us to fall down into B again sys.stderr.write('Starting phase 4, avoiding %d,%d\n' % (x2,y2)) (map4, (x4, y4), new_info) = explore(new_info, (x2, y2)) if (x4, y4) != (x2,y2): current_map = {} current_map = build_map(current_map, start_map, x2-sx, y2-sy, 'S', 'A') current_map = build_map(current_map, map1, x4-x1, y4-y1, 'a', 'B') current_map = build_map(current_map, map2, 0, 0, 'b', 'A') current_map = build_map(current_map, map3, x4-x3, y4-y3, 'a', 'B') current_map = build_map(current_map, map4, 0, 0, 'b', 'B') assert current_map final_explore(current_map, 0, 0, 'A') show_map(current_map) sys.stderr.write('Case ABABB\n') exit(0) # This could happen if there is no way from b to B without hitting A first # We're now at ABABA - it must now be possible to fall down in A again, # otherwise the input is invalid sys.stderr.write('Starting phase 5, avoiding %d,%d\n' % (x3,y3)) (map5, (x5, y5), new_info) = explore(new_info, (x3, y3)) if (x5, y5) != (x3, y3): current_map = {} current_map = build_map(current_map, start_map, x5-sx, y5-sy, 'S', 'A') current_map = build_map(current_map, map1, 0, 0, 'a', 'B') current_map = build_map(current_map, map2, x5-x2, y5-y2, 'b', 'A') current_map = build_map(current_map, map3, 0, 0, 'a', 'B') current_map = build_map(current_map, map4, x5-x4, y5-y4, 'b', 'A') current_map = build_map(current_map, map5, 0, 0, 'a', 'A') assert current_map final_explore(current_map, 0, 0, 'B') show_map(current_map) sys.stderr.write('Case ABABAA\n') exit(0) # We have two partitions. This can only mean A and B are next to each other. # Try the four different alignments # Case is ABABAB for i in range(4): current_map = {} current_map = build_map(current_map, map4, 0, 0, 'b', 'A') current_map = build_map(current_map, map5, x4-x5+dx[i], y4-y5+dy[i], 'a', 'B') if current_map: current_map[(x4-sx, y4-sy)] = 'S' show_map(current_map) sys.stderr.write('Case ABABAB\n') exit(0) # Shouldn't happen!? sys.stderr.write('OOPS! Case not handled\n')