Solving 1001 mazes from Trend Micro CTF

#!/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[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
   # 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[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



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[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) 
         Walk(moves)
         mazesSolved += 1
         state = 0