ivanseed / google-foobar-help Goto Github PK

 from collections import deque

 def memodict(f):
    """ Memoization decorator for a function taking a single argument """
    class memodict(dict):

        def __missing__(self, key):
            ret = self[key] = f(key)
            return ret
    return memodict().__getitem__
    


 @memodict
 def adjacent_to((maze_dim, point)):
    neighbors = (
        (point[0] - 1, point[1]),
        (point[0], point[1] - 1),
        (point[0], point[1] + 1),
        (point[0] + 1, point[1]))

    return [p for p in neighbors if 0 <= p[0] < maze_dim[0] and 0 <= p[1] < maze_dim[1]]


 def removable(maz, ii, jj):
    counter = 0
    for p in adjacent_to(((len(maz), len(maz[0])), (ii, jj))):
        if not maz[p[0]][p[1]]:
            if counter:
                return True
            counter += 1
    return False


 def answer(maze):

    path_length = 0

    if not maze:
        return

    dims = (len(maze), len(maze[0]))
    end_point = (dims[0]-1, dims[1]-1)

    # list of walls that can be removed
    passable_walls = set()
    for i in xrange(dims[0]):
        for j in xrange(dims[1]):
            if maze[i][j] == 1 and removable(maze, i, j):
                passable_walls.add((i, j))

    shortest_path = 0
    best_possible = dims[0] + dims[1] - 1

    path_mat = [[None] * dims[1] for _ in xrange(dims[0])]  # tracker matrix for shortest path
    path_mat[dims[0]-1][dims[1]-1] = 0  # set the starting point to destination (lower right corner)

    for wall in passable_walls:
        temp_maze = maze
        if wall:
            temp_maze[wall[0]][wall[1]] = 0

        stat_mat = [['-'] * dims[1] for _ in xrange(dims[0])]  # status of visited and non visited cells

        q = deque()
        q.append(end_point)

        while q:
            curr = q.popleft()

            if curr == (0,0):
                break

            for next in adjacent_to((dims, curr)):
                if temp_maze[next[0]][next[1]] == 0:  # Not a wall
                    temp = path_mat[curr[0]][curr[1]] + 1
                    if temp < path_mat[next[0]][next[1]] or path_mat[next[0]][next[1]] == None:  # there is a shorter path to this cell
                        path_mat[next[0]][next[1]] = temp
                    if stat_mat[next[0]][next[1]] != '+':  # Not visited yet
                        q.append(next)

            stat_mat[curr[0]][curr[1]] = '+'  # mark it as visited

        if path_mat[0][0]+1 <= best_possible:
            break        

    if shortest_path == 0 or path_mat[0][0]+1 < shortest_path:
        shortest_path = path_mat[0][0]+1

    return shortest_path

import sys


from fractions import Fraction


def matmult(a,b):
    #the matmult function was post by Akavall and is more elegant than what I would have kludged together
    #accessed 1/6/2017: http://stackoverflow.com/questions/10508021/matrix-multiplication-in-python
    zip_b = zip(*b)
    # uncomment next line if python 3 :
    # zip_b = list(zip_b)
    #print [[sum(ele_a*ele_b for ele_a, ele_b in zip(row_a, col_b))
             #for col_b in zip_b] for row_a in a]
    return [[sum(ele_a*ele_b for ele_a, ele_b in zip(row_a, col_b))
             for col_b in zip_b] for row_a in a]


from copy import deepcopy
def invert(X):
    """
    Invert a matrix X according to gauss-jordan elimination
    In gauss-jordan elimination, we perform basic row operations to turn a matrix into
    row-echelon form.  If we concatenate an identity matrix to our input
    matrix during this process, we will turn the identity matrix into our inverse.
    X - input list of lists where each list is a matrix row
    output - inverse of X
    """
    #copy X to avoid altering input
    #X = deepcopy(X)

    #Get dimensions of X
    rows = len(X)
    cols = len(X[0])

    #Get the identity matrix and append it to the right of X
    #This is done because our row operations will make the identity into the inverse
    identity = make_identity(rows,cols)
    for i in xrange(0,rows):
        X[i]+=identity[i]

    i = 0
    for j in xrange(0,cols):
        #print("On col {0} and row {1}".format(j,i))
        #Check to see if there are any nonzero values below the current row in the current column
        zero_sum, first_non_zero = check_for_all_zeros(X,i,j)
        #If everything is zero, increment the columns
        #if zero_sum==0:
            #if j==cols:
                #return X
            #raise Exception("Matrix is singular.")
        #If X[i][j] is 0, and there is a nonzero value below it, swap the two rows
        if first_non_zero != i:
            X = swap_row(X,i,first_non_zero)
        #Divide X[i] by X[i][j] to make X[i][j] equal 1
        X[i] = [Fraction(m,X[i][j]) for m in X[i]]

        #Rescale all other rows to make their values 0 below X[i][j]
        for q in xrange(0,rows):
            if q!=i:
                scaled_row = [X[q][j] * m for m in X[i]]
                X[q]= [X[q][m] - scaled_row[m] for m in xrange(0,len(scaled_row))]
        #If either of these is true, we have iterated through the matrix, and are done
        if i==rows or j==cols:
            break
        i+=1

    #Get just the right hand matrix, which is now our inverse
    for i in xrange(0,rows):
        X[i] = X[i][cols:len(X[i])]

    print X
    return X


def check_for_all_zeros(X,i,j):
    """
    Check matrix X to see if only zeros exist at or below row i in column j
    X - a list of lists
    i - row index
    j - column index
    returns -
        zero_sum - the count of non zero entries
        first_non_zero - index of the first non value
    """
    non_zeros = []
    first_non_zero = -1
    for m in xrange(i,len(X)):
        non_zero = X[m][j]!=0
        non_zeros.append(non_zero)
        if first_non_zero==-1 and non_zero:
            first_non_zero = m
    zero_sum = sum(non_zeros)
    return zero_sum, first_non_zero


def swap_row(X,i,p):
    """
    Swap row i and row p in a list of lists
    X - list of lists
    i - row index
    p - row index
    returns- modified matrix
    """
    X[p], X[i] = X[i], X[p]
    return X


def make_identity(r,c):
    """
    Make an identity matrix with dimensions rxc
    r - number of rows
    c - number of columns
    returns - list of lists corresponding to  the identity matrix
    """
    identity = []
    for i in xrange(0,r):
        row = []
        for j in xrange(0,c):
            elem = 0
            if i==j:
                elem = 1
            row.append(elem)
        identity.append(row)

    return identity


def answer(m):
    #m = [[0, 2, 1, 0, 0], [0, 0, 0, 3, 4], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
    #m = [[0,1,0,0,0,1],[4,0,0,3,2,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
    #m = [[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,1,0,0,0,1],[4,0,0,3,2,0]]
    #m=[[0,0,1],[0,0,0],[1,0,0]]
    #print m
    x = 1

    if len(m)==1:
        return [1,1]
    terminallist=[]
    transientlist=[]
    mrows = {}
    mcols = {}
    denominator = {}
    relaventindex = []
    #to identify null rows and columns
    for i in xrange(len(m)):
        mcols[i]=[]
        if sum(m[i])>0:
            denominator[i]=sum(m[i])
        else:denominator[i]=1

    for i in xrange(len(m)):
        mrows[i]=m[i]
        mrows[i][:]=[Fraction(x,denominator[i]) for x in mrows[i][:]]
        for j in xrange(len(m)):
            mcols[j].append(m[i][j])

    #to identify terminal and transient operations
    for i in xrange(len(m)):
        if max(mrows[i])==0 and min(mrows[i])==0:
            #if max(mcols[i]) != 0 or min(mcols[i]) != 0: #bounces unconnected locations
                terminallist.append(i)
        if max(mrows[i])!=0 or min(mrows[i])!=0:
            transientlist.append(i)

    new_order = terminallist+transientlist
    #print new_order
    #print "terminallist",terminallist
    #print "transientlist", transientlist
    #print "mrows",mrows
    #print "mcols",mcols
    #to build the matrices that will be dumped into gauss_jordan
    modrows={}
    modlist = []
    m1=[[m[i][j] for j in new_order] for i in new_order]
    #print "M1M1M1M1",m1
    #print "MMMMMMMM",m
    identitymat = make_identity(len(transientlist),len(transientlist))
    Q = []
    Qind=[]
    for i in xrange(-len(transientlist),0,1):
        templist =[]
        tempind=[]
        for j in xrange(-len(transientlist), 0, 1):
            templist.append(m1[i][j])
            tempind.append(i)
            tempind.append(j)
        Q.append(templist)
        Qind.append(tempind)
    #print Q
    #print Qind
    iminusQ = identitymat
    for i in range(len(identitymat)):
        for j in range(len(identitymat[0])):
            iminusQ[i][j] = identitymat[i][j] - Q[i][j]
    #print iminusQ
    F= invert(iminusQ)
    R= []
    Rind = []
    for i in xrange(-len(transientlist),0,1):
        templist =[]
        tempind=[]
        for j in xrange(len(terminallist)):
            templist.append(m1[i][j])
            tempind.append(i)
            tempind.append(j)
        R.append(templist)
        Rind.append(tempind)
    #print R
    #print Rind
    FR = matmult(F,R)
    #for i in xrange(len(FR[0])):
        #FR[0][i]=FR[0][i].limit_denominator(100)
    denlist = []
    numlist = []
    solution = []
    for i in xrange(len(FR[0])):
        denlist.append(FR[0][i].denominator)
    for i in xrange(len(FR[0])):
        numlist.append(FR[0][i]*max(denlist))
    #print numlist
    for i in xrange(len(FR[0])):
        solution.append(numlist[i].numerator)
    #print solution
    solution.append(max(denlist))
    print solution
    print type(solution[1])
    return solution