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 challenge
We 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:

  1. Parse maze file separating mazes
  2. Parse a maze to data structure
  3. deal with health (13,000 start)
  4. 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*
  5. 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

! Your final energy is 4535. ... TMCTF{AMAZING1001MAZES_lool}