# Labyrinth of 1001 mazes

**@mrexcessive WHA**

## Trend Micro CTF 2015 Programming 300

#### The problem

*
There are 1001 mazes in this challenge.*

To begin with, you have 13000 points as 'energy'. Every time you go past a specific location that you already have, your energy will be reduced by one point each time. You must finish all the mazes without running out of energy. If you run out of energy before reaching the goal of the final maze, you must start from the beginning.

However, you can find energy drink in the mazes. Once you use it, you cannot use it again. It's a one-time option.

If there are checkpoints in a maze, you must go to all of them. If you reach a goal in a maze without going to all the checkpoints, you cannot go to the next maze.

Also, if you reach a particular goal for the second time or more, your energy will be reduced by one point each time.

*Survive from the 1001 mazes.*

Coding offline challengeWe are also given some technical info. and a single file full of mazes depicted in ASCII.

The first three numbers indicate the width, height and the number of checkpoints of a maze. Characters in the maze file have the following meanings: \# : Wall (壁) S : Start (スタート) G : Goal (ゴール) C : Checkpoint (チェックポイント) E : Energy drink (+20 points) (エネルギードリンク +20ポイント) . : Nothing (Pathway) Correct solution will be in the form of 1001 lines of instructions. Each line will contain only characters U, D, L and R as required. Example maze and solution: ** Sample (サンプル) ** 7 7 1 ####### #S#G..# #.###.# #C....# #.###.# #....E# ####### ** Example answer (解答例) ** DDRRRRUULL or DDRRRRDDUUUULL

Full maze data https://gist.github.com/mrexcessive/caf5cf0b800a9c14d84a

#### The solution

This looks like it needs a maze route algorithm. I coded an A* algo (see http://en.wikipedia.org/wiki/A*_search_algorithm) once before for the WibblyWobbly challenge of LegitBS CTF, can some of that code be reused ?

First important point, is this going to need **constraint solving** ?

If there was a way to go back from a maze to an earlier one... maybe... but the mazes are independent apart from the energy being totalled overall. We just need a collection of the most energy positive correct solutions for each maze.

And no need for dealing with constraint solving or hill climbing - phew!

Let's draw up a plan:

- Parse maze file separating mazes
- Parse a maze to data structure
- deal with health (13,000 start)
- Implement an A* algorithm using my old code as basis

Collect 1 or more C if some present... have to contribute more than they lose Count cost of paths - probably can build into A* - Generate move string UDLR and \n for end of each maze

Well no plan survives contact intact... but it's a start.

First something to parse the maze file and separate it into mazes:

fnamemaze = "maze.txt" f = open(fnamemaze,"rb") raw = f.read() f.close() rows = raw.split("\n") state = 0 for onerow in rows: if onerow == "": break # all done if state == 0: nums = onerow.split(" ") width = int(nums[0]) height = int(nums[1]) food = int(nums[2]) 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) # GenerateMoves() will do the A* algo Walk(moves) # Walk() will log the individual maze solution mazesSolved += 1 state = 0

Just the minor matter of getting the A* algorithm right.

I modified my existing one to deal with the new features and different characters for walls. It solved the mazes for the simple task of getting from start to exit, but failed to score at maze 232 when first checkpoint was introduced. Helpfully the scoring page on Trend Micro's CTF told me the maze number which failed.

To cope with the checkpoints(**C**) took a while. All must be visited, and then one of the (one or more) exits(**G**). We just need the route through a maze which consumes the least energy... hmmm...

So the algo. needs to try ALL possible permutations of checkpoint sequences, and for each of those all possible exits.

For example if there were two checkpoints (C1 and C2) and two exits (E1 and E2) then we need to try four combinations and calculate which is best from an energy point of view. Start -> C1 -> C2 -> E1 = route 1 Start -> C2 -> C1 -> E1 Start -> C1 -> C2 -> E2 Start -> C2 -> C1 -> E2 = route 4

To calculate the shortest routes (marked **->** above) we can simply use the A* algo.

So, even in this simple case above we are running the A* algo. 12 times, keeping 4 energy scores and 4 complete routes.

Aside - I realised while writing this up that I need only have calculated each of the separate sections once (so C1 -> C2 only once, not twice, for example), and then assemble the pieces. This wasn't an issue as everything ran fast enough anyway - but it might be necessary on a more complicated challenge or even just one with much larger mazes.

The core of the code is the **GenerateMoves(maze)** function, which prepares the maze data for the A* algorithm; runs all required permutations of the Checkpoints and Goals; picks the most energy efficient route.

It took a few tweaks, around the energy deduction for retracing steps, before it worked correctly and the website gave me the flag.

def GenerateMoves(m): board = {} bw = len(m[0]) # 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 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[1] # 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

The complete code is here https://gist.github.com/mrexcessive/421e2cc90468178e151f