Spiral_Square_matrix

#!/usr/bin/python
"""(C)24th June 2013, WhiZTiM
   contact: ionogu@acm.org
        twitter.com/ionogu
        facebook.com/onogu
   blog.whiztim.com
   PREAMBLE:
    this program transverse a square grid in spiral form... and its design is:
    nextMove()
    this function is the traveller... and it attempts to move up, right, down and left the grid
    it returns the successful move.
"""

def nextMove(x, y, state_grid, lst = 0):
    """ @param:x and @param:y
        This represents an (x,y) coordinate
    @param:state_grid:
        this is a mutuable grid of boolean values to indicate whether we have
        travelled to a coordinate, if not... we go according to @param:lst and
        set that coordinates travel-able value to False
    @param:lst:
        this helps to bring spiral transversal form to life....
        Its values ranges from 0 to 3 and is used to make direction preference
    """

    limit = len(state_grid[0])      #dimension of the square array

    """ 'first' is a preferencial determiner, i.e
    if the while loop executes once without success, preference is reset to 0
    and if there is still no success, it will break by the else clause
    """
    first = True

    while(True):
    if(x-1 >= 0 and lst < 1):       #1st preference: move left
        if(state_grid[x-1][y]):     #if its visit-able
        state_grid[x-1][y] = False  #then make it unvisit-able cause we are going to visit it
        lst = 0             #set preference to this direction
        return (True, (x-1), y, lst)    #return turple

    if(y+1 < limit and lst < 2):        #2nd preference: move up
        if(state_grid[x][y+1]):     #similar as above
        state_grid[x][y+1] = False
        lst = 1
        return (True, x, (y+1), lst)

    if(x+1 < limit and lst < 3):        #3rd preference: move right
        if(state_grid[x+1][y]):     #similar as above
        state_grid[x+1][y] = False
        lst = 2
        return (True, (x+1), y, lst)

    if(y-1 >= 0 and lst < 4):       #4th preference: move down
        if(state_grid[x][y-1]):     #similar as above
        state_grid[x][y-1] = False
        lst = 3
        return (True, x, (y-1), lst)

    if(first):      #we will be here if we have tried preferences without success
        lst = 0     #lower or reset preference
        first = False   #dont execute this block again
    else: break     #free to execute the next one

    return (False, x, y, lst)   #Finally failed! stop!!!

def readinput():
    """ Read the space separated n * n elements from stdin
    Uses first line to automatically determine the size of the array
    """
    first = True        #tells us whether we are reading the first line
    n = 999999999L  #number of lines, we assume the grids will never reach the square of this
    rtn = []        #return value. a 2D array(list)
    while(True):
    if(n == 0): break   #if the last line has been read, break
    w = raw_input()     #get raw_input() from stdin
    if(first):      #if first line
        n = len(w.split())  #use the number of items to automatically determine
                    #the number of lines to be read
        first = False   #we are no more in the first line

    rtn.append(w.split())   #split the whitespace delimited elements in the line and append to return variable
    n -= 1          #we now need to read fewer lines

    return rtn

def main():
    """ read input;
    setup variables for calling on the traveller
    ...till the traveller returns false
    """
    array = readinput()
    # 't' represents the dimension of the array
    t = len(array[0])

    # state_grid represents a 2D array(list) of boolean values all initialized to True
    # and its used for indicating whether a coordinate is visitable or not
    state_grid = [[True for i in range(t)] for i in range(t)]

    rtn = []    #holds return value
    x = 0   # 'x' or 'i'th dimension
    y = 0   # 'y' or 'j'th dimension
    lst = 0 #variable to indicate last direction of travel

    #we append the first item to our return, and set it's visit-able state_grid to False
    rtn.append(array[x][y])
    state_grid[x][y] = False

    while(True):
    #next move returns a turple of types(bool, int, int, int)
    c, x, y, lst = nextMove(x, y, state_grid, lst)

    if not c: #test if there is no more move
        break
    #append results
    rtn.append(array[x][y])

    #print answer
    print rtn

if(__name__ == "__main__"):
    main()
    pass