Skip to content

Instantly share code, notes, and snippets.

# mrexcessive/Solving 1001 mazes from Trend Micro CTF Created Sep 27, 2015

 #!/usr/bin/python #TrendJP CTF Prog300 - maze solving #@mrexcessive @WHA import sys import copy import math from itertools import permutations debug = True debugLots = False #useful logfname="logTries.txt" def Log(s,alwaysLog = False): if logfname <> None: f=open(logfname,"a") f.write("%s\n" % s) f.close if debug and (alwaysLog or debugLots): print s walkingFname = "walking.txt" def Walk(s,logIt = True): Log("Walking [%s]" % s,True) if walkingFname <> None: f = open(walkingFname,"a") f.write("%s\n" % s) f.close() def NewWalk(): # start a new walk Walk("\n\n\nNEW WALK\n\n") #A* solving def GenerateMoves(m): board = {} bw = len(m) # YYY all walls have been removed at this point bh = len(m) print "Board width,height = %i,%i" % (bw,bh) # I is row number, J is minor index and column player = None exitGoals = [] # list of possible goals - will need to compute best energy for each possible goal... food = {} walls = {} checkpoints = [] # have to visit these - so they are sub-goals sigh for i in xrange(0,bh): # first row is label d = m[i] for j in xrange(0,bw): key = (j,i) board[key] = None # create cell on map cell = d[j] if cell == ".": # empty cell pass elif cell == "E": food[(j,i)] = 1 # good thing food - if not too far to go... elif cell == "C": checkpoints.append((j,i)) # gotta visit these before goals elif cell == "S": # player start player = (j,i) elif cell == "G": # player exit exitGoals.append((j,i)) # YYY note that j is X coord and i is Y coord... elif cell == "#": # wall walls[(j,i)] = 1 else: print "Failed to parse board, what is [%s]" % cell exit() assert(player <> None) assert(len(exitGoals) > 0) def hestimate(posa,posb): ax,ay = posa bx,by = posb d = math.sqrt( (ax - bx) * (ax - bx) + (ay - by) * (ay - by) ) return d # note this is a float def NeighbourList(posa): result = [] x,y = posa for (dx,dy) in [(-1,0),(1,0),(0,-1),(0,1)]: # no diagonal moves tx = x + dx # tentative ty = y + dy if tx >= 0 and tx <= bw and ty >= 0 and ty <= bh: # check within bounds result.append((tx,ty)) return result # need to generate an enumeration of checkpoints and goals, but only for checkpoints first in any order then goals # then generate a complete path from start, through each sequence of checkpoints, ending at each goal # then pick the lowest scored # XXX ideally need to track health accurately... so when walk over already covered point is -1 best_score = 8888 # less than one wall... best_path = None for checkpointSequence in permutations(checkpoints): # try all sequences through mandatory checkpoints for oneExitGoal in list(exitGoals): # and each checkpoint sequence with each possible exit point print "x" goalsRunningOrder = list(checkpointSequence) + [oneExitGoal] # OK so now calculate total path and score from start to first goal, first goal to second goal etc... this_score = 0 this_path = "" already_visited = {} # temporary list of places already visited this sequence run goalsRunningOrder = [player] + goalsRunningOrder # now can strip them off in pairs, player is first start location for i in xrange(0,len(goalsRunningOrder)-1): # minimum seq is (start, end) closedset = {} #A* algo see http://en.wikipedia.org/wiki/A*_search_algorithm openset = {} gscore = {} # known route scores to end fscore = {} # estimated total cost from start to goal through here start = goalsRunningOrder[i] goal = goalsRunningOrder[i+1] print "seq %i start %s end %s" % (i,start,goal) openset[ start ] = 1 came_from = copy.deepcopy(board) # YYY need to deepcopy each time or we'll mess with algo... gscore[start] = 0 # yes, yes - I am copying the wiki algo, not using my own map data entirely ... fscore[start] = gscore[start] + hestimate(start,goal) failedAstar = True while len(openset.keys()) > 0: minscore = 9999 minkey = None for k in openset.keys(): v = fscore[k] if v < minscore: minscore = v minkey = k assert(minkey <> None) current = minkey if current == goal: failedAstar = False break # exit while() del openset[current] closedset[current] = minscore # that's what the score was ^^^ neighbours = NeighbourList(current) for n in neighbours: if closedset.has_key(n): continue if walls.has_key(n): tentative_gscore = 9999 # can't go this way elif food.has_key(n): tentative_gscore = -20 # reward eating food elif already_visited.has_key(n): tentative_gscore = 1 # punishment else: tentative_gscore = gscore[current] + hestimate(current,n) if not openset.has_key(n) or tentative_gscore < gscore[n]: came_from[n] = current gscore[n] = tentative_gscore fscore[n] = gscore[n] + hestimate(n,goal) if not openset.has_key(n): openset[n] = 1 #end while() if failedAstar: print "bad failed... ?" exit() # should never happen # Derive path from scores generated total_path = [current] # current == goal at this point while current in came_from.keys(): current = came_from[current] total_path = [current] + total_path Log("Total path = %s" % total_path) # Here we have a path through points, turn it into directions nowx,nowy = total_path # first is always None, second is start point of playerone at start... skip that path = total_path[2:] # movestring = "" for p in path: already_visited[p] = 1 # only count midpoints as already visited (nx,ny) = p if nx > nowx: # implement a WASD controller... can only be one of these each time 'cos no diagonal moves ch = "R" elif nx < nowx: ch = "L" elif ny < nowy: ch = "U" elif ny > nowy: ch = "D" else: print "SOMETHING WENT HORRIBLY wrong %i,%i move to %i,%i" % (nowx,nowy,nx,ny) exit() movestring += ch nowx = nx nowy = ny # add moves to current attempt, also add the score this_path += movestring this_score += fscore[goal] #end for all the sequences if this_score < best_score: # lower is better best_score = this_score best_path = this_path Log("GenerateMoves says [%s]" % best_path) return best_path if __name__ == "__main__": fnamemaze = "maze.txt" f = open(fnamemaze,"rb") raw = f.read() f.close() NewWalk() rows = raw.split("\n") state = 0 # 0=> expecting numbers defining size new maze mazesSolved = 0 for onerow in rows: if onerow == "": break # all done if state == 0: nums = onerow.split(" ") width = int(nums) height = int(nums) food = int(nums) print "New maze %i * %i with %i food" % (width,height,food) state = 1 onemaze = [] elif state == 1: # reading blank ######## at head of this maze countrows = height - 2 # actual rows ignoring the boundaries state = 2 # next read data elif state == 2: # reading maze rows rowbit = onerow[1:-1] # skip first and last chars (which are boundary walls) onemaze.append(rowbit) countrows -= 1 if countrows == 0: state = 3 elif state == 3: # skip final blank row and solve maze Log( "So go solve maze %i\n%s" % (mazesSolved+1,"\n".join(onemaze)) ) moves = GenerateMoves(onemaze) Walk(moves) mazesSolved += 1 state = 0
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.