#!/usr/bin/python3 # # ./run.py < aamc2019.txt # import sys import random import time import maze import mouse def contest(actual): me = mouse.Mouse() # Prepare what we know about the maze. # Our starting location is EXPLORED. There is an exit NORTH. # There is a wall EAST. HERE is 0 steps from the start. known = maze.Maze() known.cells[me.r][me.c].allow = maze.EXPLORED known.cells[me.r-1][me.c].S = maze.ABSENT known.cells[me.r][me.c+1].W = maze.PRESENT known.cells[me.r][me.c].pathlen = 0 ### display the starting state known.display() run(me, known, actual) # run again! me.reset() run(me, known, actual) me.reset() run(me, known, actual) me.reset() run(me, known, actual) me.reset() run(me, known, actual) def run(me, known, actual): path = mouse.Path() path.moved_to(me.r, me.c) while True: # Step 1: Move forward to the next cell. distance = known.cells[me.r][me.c].pathlen me.forward() path.moved_to(me.r, me.c) # Where are we? here = known.cells[me.r][me.c] assert here.allow != maze.AVOID, f'moved {me.d} to {me.r},{me.c}' # We might run in circles. Remember how many times we've been # to this cell, and select paths with lower visits. here.visited += 1 # Remember how far this cell is from the starting location. # NOTE: another (shorter) path may have reached this cell. # We want this cell to remember the *shortest* path. here.pathlen = min(here.pathlen, distance + 1) ### if prior cell had STEPS to a solution, then HERE is at ### least one more step away. Propagate STEPS. # Did we reach the target location? WIN! if here.steps == 0: print(f'SUCCESS! Reached {me.r},{me.c}; path length {len(path.crumbs)}; {me.moves} moves; distance {known.cells[15][0].steps}') # Backport knowledge throughout the maze, for the next run. analyze(path, known, False) # We are done with this run. break is_new = here.allow != maze.EXPLORED # Step 2: Explore this location. explore(me, known, actual) # Step 3: Analyze what we (now) know. This may update HERE, # based on neighbor data from prior runs. analyze(path, known, is_new) # Step 4: Decide where to go. loc = decide_next(me, path, known) if loc is None: # We have no valid destination. Retreat. gen = path.retreat() _ = next(gen) loc = next(gen) print('NEXT:', loc) # Step 5: Maybe turn, in order to move forward to desired cell. me.turn_towards(loc[0], loc[1]) ### debug the map after each step/analysis we make. Note that ### decide_next() can mark sections of the map as AVOID, so we ### defer printing to here. known.display() ### for now, just move north until we hit a wall if known.north_wall(me.r, me.c) != maze.ABSENT: pass#break # /loop ### print out the path we took if False: for r, c in path.retreat(): print('LOC:', r, c) def explore(me, known, actual): "Explore this location, extending KNOWN [using actual]." ### could also imagine: using a camera, whiskers, or other sensors here = known.cells[me.r][me.c] if here.allow == maze.EXPLORED: # Already done. Fast-exit. return # Mark that we have explored this cell. here.allow = maze.EXPLORED # Explore the four walls. Note that at least one wall is ABSENT, # since we had to arrive here from somewhere else. ### using ACTUAL, assuming sensors told us this data. known.set_north(me.r, me.c, actual.north_wall(me.r, me.c)) known.set_east(me.r, me.c, actual.east_wall(me.r, me.c)) known.set_south(me.r, me.c, actual.south_wall(me.r, me.c)) known.set_west(me.r, me.c, actual.west_wall(me.r, me.c)) def analyze(path, known, is_new): "Expand KNOWN based on arrival here." ### do any neighbor cells have known STEPS? Set this cell's value ### as that, +1 more step. Reflect back along PATH. ### actually: propagate across entire maze. known.propagate() ### if decide_next() decides to AVOID a cell, then it must handle ### the repercussion. unclear on what that may be. ### PATHLEN from start. propagate changes in case we ran into a ### not-new cell. We may have found a faster route to HERE. ### if this is newly-discovered, then examine other cells to ### determine if they should be AVOIDed because they cannot be ### part of the puzzle solution. Mark them so. ### Note: expensive(??), only do when a new cell is explored. if is_new: pass ### what else? pass def decide_next(me, path, known): "Given openings and knowledge of neighbors, where to go?" choices = known.choices(me.r, me.c) # On the path we have navigated, the last element is where we are # located. The *prior* position should be in the list of choices. # If that is the *only* choice, then we just hit a dead-end. Mark # this cell as AVOID and retreat to the prior location. if len(choices) == 1: known.cells[me.r][me.c].allow = maze.AVOID # None indicates a retreat. return None # Latest PATH crumb is HERE. Previous crumb is where we came from, # and should be removed from the choices. It MUST be present in # the list of choices (so throw an exception if not). assert path.crumbs[-1] == (me.r, me.c) choices.remove(path.crumbs[-2]) print(f'CHOICES[{me.r},{me.c}]:', choices) # If any of the choices are the destination, THEN GO!! pathlens = sorted((known.cells[r][c].pathlen, r, c) for (r, c) in choices) print('PATHLENS:', pathlens) if pathlens[0][0] == 0: return pathlens[0][1], pathlens[0][2] # r,c of destination # If there are cells NOT-EXPLORED, then choose one of those. unknown = [ (r, c) for (r, c) in choices if known.cells[r][c].allow == maze.UNKNOWN ] if unknown: return random.choice(unknown) # NOTE: ALL choices are EXPLORED. # Of the EXPLORED cells, if they ALL have a solution, then choose # the one with fewest steps to a solution. We may as well solve the # maze right now, as we *may* have nothing more to learn. # # NOTE: it is entirely possible, that on the way there, we'll find # an unexplored path, and try that out instead of heading directly # to the destination. # NOTE: it is also possible that something along our path could have # led to a better solution. We will not go back to try that. solved = sorted((known.cells[r][c].steps, r, c) for (r, c) in choices) print('SOLVED:', solved) # A cell without a solved path to the destinatino will have FAR_AWAY # for its STEPS. If we see that, then this algorithm is not applicable. if solved[-1][0] < maze.FAR_AWAY: # Sweet. Grab the lowest STEPS. return solved[0][1], solved[0][2] ### examine PATH ??? Look for exploration options. # NOTE: AT LEAST ONE choice has no known solution. # Can we find a better solution? Let's explore. # Avoid revisiting cells, by selecting for cells we have visited # less frequently. Maybe something on that path will have options. vcount = sorted((known.cells[r][c].visited, r, c) for (r, c) in choices) print('VISITED:', vcount) lowest, r, c = vcount[0] # If they are not *ALL* equal to the LOWEST, then choose the LOWEST. if any(v > lowest for (v, _, _) in vcount): return r, c # NOTE: equal visitation to our navigation choices. # We have walked through the exits and equal number of times. # Maybe there is something on the path that is FURTHEST from the # start location. In other words, choose a path that leads *away* # from the start, rather than *towards* the start. highest = pathlens[-1][0] return random.choice(list((r, c) for (l, r, c) in pathlens if l == highest)) if __name__ == '__main__': ### create repeatable runs. random.seed(1) actual = maze.Maze.load(sys.stdin) t = time.time() contest(actual) print(f'ELAPSED: {(time.time()-t)*1000:.1f}ms')