Implementation of the pathfinding algorithm to solve the 2011 Prosa CTF AMazeing Steganography challenge.

maze.py

#Johnny Vestergaard - 2011
#jkv@unixcluster.dk
#Implementation of the pathfinding (http://en.wikipedia.org/wiki/Pathfinding) algorithm to solve
#the 2011 Prosa CTF AMazeing Steganography challenge.

from PIL import Image
import cProfile
import signal
import pdb
from numpy import zeros

IMG = Image.open("maze_0896ece965ea014e4887fe2685426511.png").load()


#a usefull manhole!
def siguser1_handler(sig, frame):
    print "pdf due to SIGUSR1"
    pdb.set_trace()
#a usefull manhole!
def register_runtime_debug_listener():
    signal.signal(signal.SIGUSR1, siguser1_handler)

register_runtime_debug_listener()

def find_path():
  new_added = [(14999, 14999, 0)]
  new_added_length = 1
  valueArray = zeros((15000, 15000), int)
  blah = 0
  breakall = False
  
  #len(new_added) might be too slow to use here... whatever...
  while (new_added_length  > 0):
      p = new_added.pop()
      new_added_length = new_added_length - 1
      blah = blah + 1
      if (blah % 200000 == 0):
        print "Still working sir - " + str(p)
      
      newCounter = p[2] + 1
      
      for x, y in ((p[0], p[1]+1), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0]-1, p[1])):
        if (x == 1 and y == 1):
          print "Start point found! (this is good!)"
          breakall = True
        #3 is a wall
        if not IMG[x, y] == 3:
          if valueArray[x, y] == 0:
            valueArray[x, y] = newCounter
            new_added.append((x, y, newCounter))
            new_added_length = new_added_length + 1
          elif valueArray[x, y] > newCounter:
            valueArray[x, y] = newCounter
            new_added.append((x, y, newCounter))
            new_added_length = new_added_length + 1
      
      if breakall:
        break
  
  print "Tracking from start to end - work work all day. Hang on!"
  #start at maze entrance.
  sol = [(1, 1)]
  x = 1
  y = 1
  #14999,14999 is the exit!
  while (x != 14999 and y != 14999):
    down = 999999999999
    right = 999999999999
    up = 999999999999
    left = 999999999999
    
    if not valueArray[x, y+1] == 0:
      down = valueArray[x, y+1]
    if not valueArray[x+1, y] == 0:
      right = valueArray[x+1, y]
    if not valueArray[x, y-1] == 0:
      up = valueArray[x, y-1]
    if not valueArray[x-1, y] == 0:
      left = valueArray[x-1, y]
    
    #pick the tile with the lowest value.
    if down < right and down < up and down < left:
      y = y + 1
      sol.append((x, y))
    elif right < down and right < up and right < left:
      x = x + 1
      sol.append((x, y))
    elif up < left and up < down and up < right:
      y = y - 1
      sol.append((x, y))
    elif left < down and left < right and left < up:
      x = x - 1
      sol.append((x, y))
  return sol

def assemble_bits(sol):
    oArray = []
    bitCounter = 0
    bitByte = ""
    prefixBytesCounter = 0
    prefixByte = ""
    dataBytes = 0
  
    #assemble bits to bytes and write them to file. (first 4 bytes are length of data)
    for i in range(0, len(sol)):
      if IMG[sol[i][0], sol[i][1]] == 0 or IMG[sol[i][0], sol[i][1]] == 1:
        if IMG[sol[i][0], sol[i][1]] == 0:
          c = 1
        else:
          c = 0
        bitByte = bitByte + str(c)
        bitCounter = bitCounter + 1
        if bitCounter == 8:
          if prefixBytesCounter < 4:
            prefixByte = prefixByte + bitByte
            prefixBytesCounter = prefixBytesCounter + 1
            #aye aye lamer
            dataBytes = int(prefixByte, 2)
          else:
            oArray.append(int(bitByte, 2))
            if (dataBytes == len(oArray)):
              break
         
          bitCounter = 0
          bitByte = ""
    return (oArray, prefixByte)

def write_to_file(bytes, length):
    print "Writing to file!"
    print "Length of data: " + str(int(length, 2)) 
    fil = open("out.dat", "wb")
    for item in bytes:
      fil.write(chr(item))
    fil.close()
    
map = find_path()
data = assemble_bits(map)
write_to_file(data[0], data[1])