You were right about the videos being very helpful. Using the approach described there I was able to come up with a solution that almost satisfies the test. I started writing code 2.5 weeks ago, so I apologize for the overall unreadability. Please let me know if you have any thoughts regarding the case that I seem to be missing. And thank you for your time.
Python Code:
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