Failing one test on doomsday_fuel

[jimismash]

@ivanseed ,

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

[ivanseed]

Sorry, it is a bit hard to follow the code - also my Python is not the best.

There is a way you can figure out what inputs you are getting though; you probably already tried to use something like print m but whenever that line is executed it would throw back an error.

What you should do is try and figure out some properties of the matrix that is causing you to fail. If you were to put:

if (false)
   print 'Hello World'

It would not throw an error because that line of code will never be executed. So what you can do is;

if (m.length == 1)
    return NULL

This will cause all tests to fail where the map is a 1x1, see if you still have the same passing and failing tests as you did before.

If the same tests are failing then put;

if (m.length == 1)
    print 'I will cause an error'

Now if you get an error when you run this, then you know that the failing test is a 1x1 matrix. You can do this for NxN matrix to figure out what is causing your code to fail.

My advice is that most people forget about the case where the matrix is 1x1 (already in terminal state) and 2x2.

[jimismash]

@ivanseed

I ran: if len(m) == N: return 0 or if len(m) == N: raise Exception("I will cause and error")
I cycled N from 0 through 10. Using the return 0 I identified the length of every other test, and then using the "Exception" I was able to determine that the test I'm failing was not a unique length(unless it is longer than 10) test, i.e. I don't think my code has an issue with a specific size of matrix. I have the intuition that the test I'm failing involves a 10x10, but that's only based on tests 5 and 7-10 being 10x10.

I'm storing all of the numbers using the built in Fraction variable type which automatically handles the fraction reduction; I don't know if this could cause any issues with denominators being stored as signed 32-bit integer. I'm trying to think of other exception cases, but this is outside of my area of expertise.

You've been very helpful, thank you for your time!

If it helps at all, one of my previous attempts involved solving systems of multiple equations. The best I could do with that approach was passing 7/10 tests.

[ivanseed]

Mmm you could also test if that the Matrix at m[0] is of terminal state. Meaning that the first state is the terminal state. It should be all zeros. If it is not that then maybe it is just how you are storing fractions. But check if m[0] contains only 0s.

[jimismash]

@ivanseed ,

I still didn't pass test six, but detecting S0 as a terminal state was something that my code was not doing. It's probably for the best, classes are starting on Monday so I won't have time to fool around with the harder challenges anyway.

I appreciate all the help you have provided, especially the rundown on Markov Chains.