Google Doomsday Fuel не справляется со скрытыми тестами

Question

Задача заключается в следующем: Топливо Судного дня

Производство топлива для активной зоны реактора LAMBCHOP - сложный процесс из-за задействованной экзотической c материи. Он начинается с сырой руды, затем во время обработки начинает беспорядочно меняться между формами, в конечном итоге достигая стабильной формы. В образце может быть несколько стабильных форм, не все из которых могут быть использованы в качестве топлива.

Командир Лямбда поручил вам помочь ученым повысить эффективность создания топлива, предсказав конечное состояние данной руды. образец. Вы внимательно изучили различные структуры, которые может принимать руда, и какие переходы она претерпевает. Похоже, что, несмотря на случайность, вероятность преобразования каждой структуры фиксирована. То есть каждый раз, когда руда находится в 1 состоянии, она имеет одинаковые вероятности перехода в следующее состояние (которое может быть тем же состоянием). Вы записали наблюдаемые переходы в матрицу. Другие в лаборатории выдвинули гипотезу о других формах экзоти c, которыми может стать руда, но вы не видели их всех.

Напишите решение функции (m), которое принимает массив массивов неотрицательных ints, представляющие, сколько раз это состояние переходило в следующее состояние, и возвращающие массив целых чисел для каждого конечного состояния, дающие точные вероятности каждого конечного состояния, представленные в виде числителя для каждого состояния, а затем знаменатель для всех из них в конце и в простейшем виде. Матрица составляет не более 10 на 10. Гарантируется, что независимо от того, в каком состоянии находится руда, существует путь от этого состояния до конечного состояния. То есть обработка всегда в конечном итоге заканчивается в стабильном состоянии. Руда начинается в состоянии 0. Знаменатель будет соответствовать 32-битному целому числу со знаком во время вычисления, если дробь регулярно упрощается.

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].

Я прохожу 7 из 10 тестовых примеров. Я попытался поменять местами поглощающие строки, чтобы увидеть, «портит» ли это ответ, но это не так. Мой код следующий:

import numpy as np
from fractions import Fraction

def trans(m):
    trans_index = 0
    for i in range(len(m)):
        if sum(m[i]) == 0:
            trans_index = i
            break
    if trans_index == 0:
        raise Exception("No Trans Row")
    else:
        return trans_index

def decompose(m):
    Trans = trans(m)
    if Trans==0:
        raise Exception("No transient states - Not an Absorbing Markov Chain")
    Q = []
    for i in range(Trans):
        row = []
        for j in range(Trans):
            row.append(m[i][j])
        Q.append(row)
    R = []
    for i in range(Trans):
        row = []
        for j in range (Trans, len(m[i])):
            row.append(m[i][j])
        R.append(row)
    return Q, R

def identity(t):
    I = np.zeros(shape=(t,t))
    for i in range(t):
        for j in range(t):
            if i == j:
                I[i][j] = 1
    return I


def swap_rows(m, r1, r2):
    if r1==r2:
        return m
    temp = m[r1].copy()
    m[r1] = m[r2]
    m[r2] = temp
    return m

def sort(m):
    size = len(m)
    zero_row =-1
    n = m
    for i in range(size):
        Sum = sum(m[i])
        if Sum == 0.0:
            zero_row = i
            continue
        if Sum != 0 and zero_row > -1:
            n = swap_rows(m,i, zero_row)
            return sort(n)
    return n

def normalize(m):
    for i in range(len(m)):
        Sum = sum(m[i])
        if Sum == 0:
            continue
        else:
            m[i] = m[i]/Sum
    return m

def probability(Q,R,I):
    prob = np.subtract(I, Q)
    prob = np.linalg.inv(prob)
    prob = np.matmul(prob,R)
    return prob

def to_fraction(m, denom = 10000):
    fract = []
    for i in range(len(m[0])):
        fract.append(Fraction(m[0][i]).limit_denominator(denom))
    return fract

def find_lcm(p):
    lcm = p[0].denominator
    for i in range(len(p)-1):
        if np.lcm(p[i].denominator,p[i+1].denominator) > lcm:
            lcm = np.lcm(p[i].denominator,p[i+1].denominator)
    return lcm

def solution(m):
    mk_chain = np.array(m)
    mk_chain = mk_chain.astype(np.float32)
    mk_chain = normalize(mk_chain)
    mk_chain = sort(mk_chain)
    Q, R = decompose(mk_chain)
    I = identity(trans(mk_chain))
    non_trans = len(mk_chain)-trans(mk_chain)
    O = np.zeros(shape = (non_trans, non_trans))

    prob = probability(Q,R,I)
    prob = to_fraction(prob)
    lcm = find_lcm(prob)
    final = []

    for i in range(len(prob)):
        if prob[i].denominator != lcm:
            numerator = prob[i].numerator*(lcm/prob[i].denominator)
            denominator = prob[i].denominator*(lcm/prob[i].denominator)
            final.append(numerator)
        else:
            final.append(prob[i].numerator)
    final.append(lcm)

    return final

Я не совсем уверен, почему я не прохожу (скрытые) тестовые примеры. Есть ли исключение, которое я должен сделать? В каких случаях может произойти сбой и как это исправить?