I have been working on the Google foobar issue for several days and go through all but one test, and I'm pretty stuck at this point. Let me know if you have any ideas! I use the method described here and I have a working example on repl.it here . Here's the spec problem:
Judgment Day
The production of fuel for the core of the LAMBCHOP reactor is a complex process due to the participation of an exotic substance. It begins as raw ore, then during processing it begins to randomly change between forms, eventually reaching a stable form. There may be several stable forms that the sample could achieve, not all of which are useful as fuel.
Commander Lambda instructed you to help scientists increase fuel efficiency by predicting the final state of a given ore sample. You have carefully studied the various structures that ore can take, and what transitions it undergoes. It seems that by chance, the probability of transformation of each structure is fixed. That is, every time the ore is in 1 state, it has the same probability of entering the next state (which can be of the same state). You recorded the observed transitions in the matrix. Others in the laboratory hypothesized more exotic forms that could become ore, but you did not see them.
Write the response of function (m), which takes an array of non-negative int arrays, representing how many times this state has passed to the next state, and returns an int array for each terminal state, giving the exact probabilities of each terminal state, presented as a numerator for each state, then the denominator for all of them at the end and in the simplest form. The matrix is no more than 10 by 10. It is guaranteed that no matter what state the ore is in, there is a path from this state to the state of the terminal. That is, processing will always end in a stable state. The ore starts at state 0. The denominator will fit into the signed 32-bit integer during the calculation if 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
Tracking the probabilities of each of them, we find that s2 has a probability of 0 s3 has a probability of 3/14 s4 has a probability of 1/7 s5 has a probability of 9/14 So, combining this and making a common denominator, we give the answer in the form [s2.numerator, s3 .numerator, s4.numerator, s5.numerator, denominator], which is [0, 3, 2, 9, 14] . *
Test cases
Inputs: (int) 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]] Output: (int list) [7, 6, 8, 21] Inputs: (int) 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]] Output: (int list) [0, 3, 2, 9, 14]
Here is my code so far.
from __future__ import division from itertools import compress from itertools import starmap from operator import mul import fractions def convertMatrix(transMatrix): probMatrix = [] for i in range(len(transMatrix)): row = transMatrix[i] newRow = [] rowSum = sum(transMatrix[i]) if all([v == 0 for v in transMatrix[i]]): for j in transMatrix[i]: newRow.append(0) newRow[i] = 1 probMatrix.append(newRow) else: for j in transMatrix[i]: if j == 0: newRow.append(0) else: newRow.append(j/rowSum) probMatrix.append(newRow) return probMatrix def answer(m):