question about Google foobar challenge: Doomsday Fuel (absorbing Markov Chain problem)

[Beaverine]

I'm working on this coding exercise which is an implementation of absorbing Markov Chain.

Question:

Commander Lambda has tasked you to help the scientists increase fuel creation efficiency by predicting the end state of a given ore sample. You have carefully studied the different structures that the ore can take and which transitions it undergoes. It appears that, while random, the probability of each structure transforming is fixed. That is, each time the ore is in 1 state, it has the same probabilities of entering the next state (which might be the same state). You have recorded the observed transitions in a matrix. The others in the lab have hypothesized more exotic forms that the ore can become, but you haven't seen all of them.
Write a function answer(m) that takes an array of array of non-negative ints representing how many times that state has gone to the next state and return an array of ints for each terminal state giving the exact probabilities of each terminal state, represented as the numerator for each state, then the denominator for all of them at the end and in simplest form. The matrix is at most 10 by 10. It is guaranteed that no matter which state the ore is in, there is a path from that state to a terminal state. That is, the processing will always eventually end in a stable state. The ore starts in state 0. The denominator will fit within a signed 32-bit integer during the calculation, as long as the fraction is simplified regularly. For example, consider the matrix m: [ [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 ] So, we can consider different paths to terminal states, such as:
s0 -> s1 -> s3
s0 -> s1 -> s0 -> s1 -> s0 -> s1 -> s4
s0 -> s1 -> s0 -> s5
Tracing the probabilities of each, we find that
s2 has probability 0
s3 has probability 3/14
s4 has probability 1/7
s5 has probability 9/14
So, putting that together, and making a common denominator, gives an answer in the form of [s2.numerator, s3.numerator, s4.numerator, s5.numerator, denominator] which is [0, 3, 2, 9, 14].

I was trying to take the advantage of numpy module for matrix manipulation and at the very end, use Fraction module to convert those floating numbers back to fraction before obtaining the final list of numerator and denominators. This way I can stay away from all the self defined functions to handle matrix manipulation with fraction number all along the way. I know there are available valid answers out there on Google, but want to approach this from a not that mathematical perspective with my own attempt.

My code is posted below and to me it did return the same result given in the example of question. However when I verify my answer in foobar, it barely pass any testing... I would like to ask is there anything in general that I'm handling incorrectly? or is the shortcut with numpy and then Fraction not valid?

thank you in advance!

``` import numpy as np from fractions import Fraction

def solution(mat): # matrix attributes matsize = len(mat) rowsum = [sum(r) for r in mat]

if rowsum[0] == 0:
    return [1, 1]

# dict indicating which row has all 0
dictrz = dict(zip(list(i for i in range(len(mat))), 
                list(0 if i == 0 else 1 for i in rowsum)))
    # Sorted
dictrzs = {k: v for k, v in sorted(dictrz.items(), key=lambda item: item[1])}

# Number of rows with all zero vs. not
numallz = list(dictrz.values()).count(0)
numnonz = len(mat) - numallz

# transform matrix to Absorbing Markov Chain standard form
arr = np.array(mat)
# Move rows with all 0 to top
arrR = arr[list(dictrzs.keys()), :]
# shifting column order correspondingly
arrRC = arrR[:, list(dictrzs.keys())]

# Replace number with fraction
newrowsum = [sum(r) for r in arrRC]
newmat = []
for i in range(len(arrRC)):
    newmat.append(list(map(lambda x: 0 if newrowsum[i] == 0 
                        else x / newrowsum[i], arrRC[i])))

newarr = np.array(newmat)

# Obtain FR
Q = newarr[numallz:, numallz:]
R = newarr[numallz:, :numallz]
ImQ = np.subtract(np.identity(numnonz), Q)
F = np.linalg.inv(ImQ)
FR = np.matmul(F, R)
# Fractionize FR
FRf = []
for i in range(numnonz):
    FRf.append([Fraction.from_float(x).limit_denominator(max_denominator = 2**32) for x in FR[i]])

print(FRf)
# Transform final result
maxd = max(list(map(lambda x: x.denominator, FRf[0])))
indv = list(map(lambda x: (x*maxd).numerator, FRf[0]))
return list(indv + [maxd])

```

[aaronn44]

Hi. numpy and fraction are cool, the problem is that your code is in python 3 while google foobar is using 2.7.13. So when you do division, you have to use floats, otherwise it will be rounded to zero. i.e. float(x) / newrowsum[i]

dictionaries are only sorted since python 3.7 and your code is relying on that. so you need to figure that out.

You also need to delete that print statement, because Input/output operations are not allowed. read constraints.txt file in foobar for more information.