Solution to Doomsday Fuel foobar challenge

doomsday_fuel.py

from fractions import Fraction

# Replace trials by probabilties of occurrences
def replace_probability(m):        
    for row in range(len(m)):
        total = 0
        for item in range(len(m[row])):
            total += m[row][item]
        if total != 0:
            for item in range(len(m[row])):
                m[row][item] /= float(total)
    return m

# R - non-terminal -> terminal
# Q - non-terminal -> non-terminal
def RQ(m, terminal_state, non_terminal_state):
    R = []
    Q = []
    for i in non_terminal_state:
        temp_t = []
        temp_n = []
        for j in terminal_state:
            temp_t.append(m[i][j])
        for j in non_terminal_state:
            temp_n.append(m[i][j])
        R.append(temp_t)
        Q.append(temp_n)
    return R, Q

# Get Identity Matrix - Q
def subtract_Q_from_identity(Q):
    """
    If Q = [
        [1,2,3],
        [4,5,6],
        [7,8,9],
    ]
    I - Q:
    [[1,0,0]            [[0,-2,-3]
     [0,1,0]   - Q =     [-4,-4,-6]
     [0,0,1]]            [-7,-8,-8]]
    """

    n = len(Q)
    for row in range(len(Q)):
        for item in range(len(Q[row])):
            if row == item:
                Q[row][item] = 1 - Q[row][item]
            else:
                Q[row][item] = -Q[row][item]
    return Q

# Get minor matrix
def get_minor_matrix(Q,i,j):
    """
    Q = [
        [1,2,3],
        [4,5,6],
        [7,8,9],
    ]
    Minor matrix corresponding to 0,0 is
    [
        [5,6],
        [8,9],
    ]
    """

    minor_matrix = []
    for row in Q[:i] + Q[i+1:]:
        temp = []
        for item in row[:j] + row[j+1:]:
            temp.append(item)
        minor_matrix.append(temp)
    return minor_matrix

# Get determinant of a square matrix
def get_determinant(Q):
    if len(Q) == 1:
        return Q[0][0]
    if len(Q) == 2:
        return Q[0][0]*Q[1][1] - Q[0][1]*Q[1][0]
    
    determinant = 0
    for first_row_item in range(len(Q[0])):
        minor_matrix = get_minor_matrix(Q, 0, first_row_item)
        determinant += (((-1)**first_row_item)*Q[0][first_row_item] * get_determinant(minor_matrix))

    return determinant

# Get transpose of a square matrix
def get_transpose_square_matrix(Q):
    for i in range(len(Q)):
        for j in range(i, len(Q), 1):
            Q[i][j], Q[j][i] = Q[j][i], Q[i][j]
    return Q


def get_inverse(Q):
    Q1 = []
    for row in range(len(Q)):
        temp = []
        for column in range(len(Q[row])):
            minor_matrix = get_minor_matrix(Q, row, column)
            determinant = get_determinant(minor_matrix)
            temp.append(((-1)**(row+column))*determinant)
        Q1.append(temp)
    main_determinant = get_determinant(Q)
    Q1 = get_transpose_square_matrix(Q1)
    for i in range(len(Q)):
        for j in range(len(Q[i])):
            Q1[i][j] /= float(main_determinant)
    return Q1

def multiply_matrix(A, B):
    result = []
    dimension = len(A)
    for row in range(len(A)):
        temp = []
        for column in range(len(B[0])):
            product = 0
            for selector in range(dimension):
                product += (A[row][selector]*B[selector][column])
            temp.append(product)
        result.append(temp)
    return result

def gcd(a ,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)   

def sanitize(M):
    needed = M[0]
    to_fraction = [Fraction(i).limit_denominator() for i in needed]
    lcm = 1
    for i in to_fraction:
        if i.denominator != 1:
            lcm = i.denominator
    for i in to_fraction:
        if i.denominator != 1:
            lcm = lcm*i.denominator/gcd(lcm, i.denominator)
    to_fraction = [(i*lcm).numerator for i in to_fraction]
    to_fraction.append(lcm)
    return to_fraction

def solution(m):
    n = len(m)
    if n==1:
        if len(m[0]) == 1 and m[0][0] == 0:
            return [1, 1]
    terminal_state = []
    non_terminal_state = []

    # Get terminal and non-terminal states
    for row in range(len(m)):
        count = 0
        for item in range(len(m[row])):
            if m[row][item] == 0:
                count += 1
        if count == n:
            terminal_state.append(row)
        else:
            non_terminal_state.append(row)
    # Replace trials by probabilties
    probabilities = replace_probability(m)
    # Get R and Q matrix
    R, Q = RQ(probabilities, terminal_state, non_terminal_state)
    IQ = subtract_Q_from_identity(Q)
    # Get Fundamental Matrix (F)
    IQ1 = get_inverse(IQ)
    product_IQ1_R = multiply_matrix(IQ1, R)
    return sanitize(product_IQ1_R)

# Case where state 0 itself is a terminal state
assert(solution(
    [
        [0],
    ]
)) == [1, 1]

assert(solution(
    [
        [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],
    ]
)) == [7, 6, 8, 21]

assert(solution(
    [
        [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],
    ]
)) == [0, 3, 2, 9, 14]

really thanks to KaustubhRakhade . I noticed test case 9 is about the special case where the source is terminal!

@kavinyudhitia

I just saw someone was able to use numpy!!! I swear I was not able to use it in the beginning but It was able when I tried....

Yeah, even I was not able to use it. But it turns out you can. Good luck with the submission.

Currently I am only failing test 3, I was decided to not search on foruns directly related to the foobar chalange, but with only one day to go I'm beginnig to get desperate LOL
Anyone has any insight regarding test 3?

Nevermind I got it, it was something on the way I was getting R and Q Matrices

Hi there!
I share my solution, I didnt used matrix stuff like inverse or traspose because I don't understand how to apply this concept to this excercise at all, but think it is useful for someone that is making it in the same way than me:

def solution(m):
    
    #case when 0 is terminal state
    if(not any(m[0])):
        return [1] + ([0] * (len(m)-1)) + [1]
   
    #diagonal values arent relevant 
    cleanDiagonal(m)
    
    #useful structures
    probabilitiesMatrix = generateProbabilityMatrix(m)
    terminals, notTerminals = getTerminalsAndNotTerminals(m)
    
    #we will remove one by one all of the not-terminals nodes 
    for i in notTerminals:
        absorbNode(probabilitiesMatrix, i)
    
    #now we can take the solution
    terminalsProbabilities = list(map(lambda x: probabilitiesMatrix[0][x], terminals))
    commonDenominator = getCommonDenominator(list(map(lambda x: x[1], terminalsProbabilities)))
    unsimplifiedNumerators = list(map(lambda x: fracUnsimplify(x, commonDenominator)[0], terminalsProbabilities))
    
    return unsimplifiedNumerators + [commonDenominator]
    
   
def cleanDiagonal(m):
    for i in range(len(m)):
        m[i][i] = 0


def generateProbabilityMatrix(m):
    result = []
    for i in range(len(m)):
        result.append([None] * len(m))
        for j in range(len(m)):
            result[i][j] = fracDiv([m[i][j],1], [sum(m[i]),1])
    return result
            
            
def getTerminalsAndNotTerminals(m):
    terminals = []
    notTerminals = list(range(1, len(m)))
    for i in range(len(m)):
        if(not any(m[i])):
            terminals.append(i)
            notTerminals.remove(i)
    return terminals, notTerminals
    
    
def absorbNode(pm, node):
    for i in range(len(pm)):
        for j in range(len(pm)):
            if(i != node and j != node):
                pm[i][j] = fracAdd(pm[i][j], fracMult(pm[i][node], pm[node][j]))
                
    for k in range(len(pm)):
        pm[k][node] = [0, 1]
        pm[node][k] = [0, 1]
        
    for i in range(len(pm)):
        if(pm[i][i] != [0, 1]):
            multiplier = solveGeometricSeries(pm[i][i])
            for j in range(len(pm)):
                if(i == j):
                    pm[i][j] = [0, 1]
                else:
                    pm[i][j] = fracMult(pm[i][j] ,multiplier)
                    
                    
#we will work with fractions, so lets create some functions 

def fracSimplify(a):
    if(a[0] == 0):
        a[1] = 1
    i=2
    while (i <= max(a)):
        if(a[0]%i == 0 and a[1]%i == 0):
            a[0] //= i
            a[1] //= i
        else:
            i += 1
    return a
    
def fracAdd(a, b):
    return fracSimplify([a[0]*b[1] + b[0]*a[1] , a[1]*b[1]])
    
def fracSubs(a, b):
    return fracSimplify([a[0]*b[1] - b[0]*a[1] , a[1]*b[1]])
    
def fracMult(a, b):
    return fracSimplify([a[0]*b[0], a[1]*b[1]])

def fracDiv(a, b):
    if(a[1] == 0 or b[1] == 0):
        return [0, 1]
    return fracSimplify([a[0]*b[1], a[1]*b[0]])

def solveGeometricSeries(r):
    if(r == [1,1]):
        return [1,1]
    n = [1,1]
    d = fracSubs([1,1], r)
    return fracDiv(n, d)
    
def getCommonDenominator(l):
    greater = min(l)
    while(not all(list(map(lambda x: greater % x == 0, l)))):
        greater += 1
    return greater

def fracUnsimplify(a, d):
    return [int(a[0]*(d/a[1])), d]

Does anybody know why my code works fine for the two given test cases in my IDE, but it fails all test cases in foobar?
import numpy as np
from fractions import Fraction
#from fractions import gcd #python 2.7
from math import gcd
def solution(m):
#ai represents the chance of starting from state i and going to certain terminal state
'''
[
[0,1,0,0,0,1], # s0, the initial state, goes to s1 and s5 with equal probability
[4,0,0,3,2,0], # s1 can become s0, s3, or s4, but with different probabilities
[0,0,0,0,0,0], # s2 is terminal, and unreachable (never observed in practice)
[0,0,0,0,0,0], # s3 is terminal
[0,0,0,0,0,0], # s4 is terminal
[0,0,0,0,0,0], # s5 is terminal
]
Terminal state 5:
a0 = 0.5 + 0.5a1
a1 = 4/9a0
=> a0 = 9/14, a1 = 2/7
terminal 5 = 9/14
Terminal state 3:
a0 = 0.5a1
a1 = 4/9a0 + 3/9
a0 = 3/14, a1 = 3/7
terminal 3 = 3/14
Terminal state 4:
a0 = 0.5a1
a1 = 4/9a0 + 2/9
a0 = 1/7, a1 = 2/7
Terminal 4: 1/7
ans = 0:3/14:1/7:9/14 = 0:3:2:9
'''
#find all terminal state
def lcm(x, y):
return x * y // gcd(x, y)
Terminal = set()
ans = []
res = []
l = 1 # lcm of demoninator
for i in range(1,len(m)):
isTerminal = True
for j in range(0, len(m[i])):
if m[i][j] !=0:
isTerminal = False
break
if isTerminal == True:
Terminal.add(i)
#convert each line into probability
terminal =[]
for elem in Terminal:
terminal.append(elem)
terminal.sort()
for i in range(0,len(m)):
ttl = 0
if i not in terminal:
for j in range(0, len(m[i])):
ttl += m[i][j]
for j in range(0, len(m[i])):
m[i][j] =m[i][j]/ttl
#loop for each terminal state, list out the linear equation and solve it
lc = 1#lcm
for t in terminal:
#define coefficient matrix and constant vector
vector = []
coei = []
for i in range(0,len(m)):
if i in terminal:#terminal state
continue
con = 0
c = [1] *(len(m)-len(terminal))# current state's coefficient is 1
for j in range(0, len(m[i])):
if j ==i:
continue
if j in terminal:
if j==t:
con = m[i][j]
else:#not terminal state
c[j]=-m[i][j]
vector.append(con)
coei.append(list(c))
y = np.linalg.solve(coei, vector)
# Convert the solution to fractions
y_fraction = [Fraction(num).limit_denominator() for num in y]
numerator = y_fraction[0].numerator
denominator = y_fraction[0].denominator
lc = lcm(lc,denominator)
res.append([numerator,denominator])
for r in res:
a = int(r[0]*lc//r[1])
ans.append(a)
ans.append(int(lc))
return ans

天才，我大概看懂了题解，实在是不知道怎么用保持分数的形式进行运算，比如说求逆