Google Foobar末日燃料问题：代码无法通过隐藏测试用例#5求助

在Google Foobar挑战中遇到了「Doomsday Fuel」问题，该问题核心是**吸收马尔可夫链（absorbing Markov chains）**的应用。我基于公开的理论方案编写了代码，大部分测试用例都能通过，但始终无法通过隐藏测试用例#5，原因不明。

问题描述 #

为LAMBCHOP反应堆制造燃料时，矿石会在不同形态间随机转换，最终进入稳定的终端状态。需要实现函数solution(m)：

• 输入：由非负整数组成的状态转移矩阵
• 输出：各终端状态的精确概率，格式为「分子数组 + 最简公分母」
• 约束：矿石初始状态为0，矩阵最大为10×10，且所有状态均可到达终端状态

初始实现代码 #

from fractions import Fraction
def subtract(matrix1, matrix2):
    result = [[a - b for a, b in zip(row1, row2)] for row1, row2 in zip(matrix1, matrix2)]
    return result
    
def matrix_minor(matrix, row, col):
    return [[matrix[i][j] for j in range(len(matrix[i])) if j != col] for i in range(len(matrix)) if i != row]

def determinant(matrix):
    if len(matrix) == 1:
        return matrix[0][0]
    elif len(matrix) == 2:
        return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0]
    else:
        det = 0
        for col in range(len(matrix[0])):
            det += ((-1) ** col) * matrix[0][col] * determinant(matrix_minor(matrix, 0, col))
        return det

def transpose(matrix):
    return [[matrix[j][i] for j in range(len(matrix))] for i in range(len(matrix[0]))]

def cofactor(matrix):
    cofactors = [[(((-1) ** (i + j)) * determinant(matrix_minor(matrix, i, j))) for j in range(len(matrix[i]))] for i in range(len(matrix))]
    return cofactors

def scalar_multiply(matrix, scalar):
    return [[element * scalar for element in row] for row in matrix]

def inverse(matrix):
    det = determinant(matrix)
    cofactors = cofactor(matrix)
    adjugate = transpose(cofactors)
    inverse = scalar_multiply(adjugate, 1 / det)
    return inverse
    
def multiply(matrix1, matrix2):
    result = [[0 for _ in range(len(matrix2[0]))] for _ in range(len(matrix1))]
    for i in range(len(matrix1)):
        for j in range(len(matrix2[0])):
            for k in range(len(matrix2)):
                result[i][j] += matrix1[i][k] * matrix2[k][j]
    return result
    
def solution(m):
    term = []
    nonterm = []
    if len(m) == 1:
        frac=Fraction(1-m[0][0]).limit_denominator()
        return [frac.numerator, frac.denominator]
            
    for i in range(len(m)):
        if sum(m[i]) == 0:
            term.append(i)
        else:
            nonterm.append(i)
            
    if 0 in term:                              
        return [1] + [0]*(len(term)-1) + [1]
        

    new_matrix = [m[i] for i in nonterm]
    row_sums = [sum(row) for row in m]
    non_zero_rows = [i for i in range(len(m)) if row_sums[i] != 0]
    P = [[Fraction(m[i][j], row_sums[i]) for j in range(len(m[i]))] for i in non_zero_rows]
    Q = [[row[i] for i in nonterm] for row in P]
    R = [[row[i] for i in term] for row in P]
    size = len(Q)
    I = [[1.0 if i == j else 0.0 for j in range(size)] for i in range(size)]
    intermediate=subtract(I,Q)
    N=inverse(intermediate)
    B=multiply(N,R)
    B=B[0]
    fractions_list = [Fraction(prob).limit_denominator() for prob in B]
    common_denominator = max(f.denominator for f in fractions_list)
    numerators = [f.numerator * (common_denominator // f.denominator) for f in fractions_list]
    return numerators + [common_denominator]

已处理的边缘场景 #

• 单状态矩阵的情况
• 初始状态（状态0）本身就是终端状态的情况
• 使用Fraction类全程处理分数，避免浮点数精度丢失
• 确保代码在目标环境Python 2.7中正常运行

问题定位与解决 #

最终发现问题出在概率分数的格式化逻辑上：原代码使用分母的最大值作为公分母，这会导致部分分数无法被正确通分（最大值不一定是所有分母的公倍数）。

原问题代码片段 #

fractions_list = [Fraction(prob).limit_denominator() for prob in B]
common_denominator = max(f.denominator for f in fractions_list)
numerators = [f.numerator * (common_denominator // f.denominator) for f in fractions_list]
return numerators + [common_denominator]

修复后的实现 #

替换为基于**最小公倍数（LCM）**的outputFormat函数，确保所有分数都能被正确通分到最简公分母：

def outputFormat(probabilities):
    res = []
    denominator = probabilities[0]._denominator
    for probability in probabilities[1:]:
        denominator = lcm(denominator, probability._denominator)
    for probability in probabilities:
        res.append(
            probability._numerator * (denominator / probability._denominator))
    res.append(denominator)
    return res

替换后，隐藏测试用例#5顺利通过。

内容的提问来源于stack exchange，提问作者Anirvesh Arcot