Google Foo.bar中Python代码输出匹配但测试全失败问题排查

云上老周

2026-8-24

Google Foo.bar Doomsday Fuel 代码本地正常但平台全失败问题

问题背景

在完成Google Foo.bar的Doomsday Fuel挑战时，编写的Python代码在本地IDE及Python 2.7.13在线沙箱中输出均符合测试用例要求，但在Foo.bar平台上所有测试均失败。尝试调整输出格式为列表、数组等方式，均未解决问题。

已验证：返回的输出内容与样例完全一致，将输出转为numpy.ndarray类型后，与网上可正常运行的参考代码输出的内容、数据类型均完全相同，但代码仍无法通过测试。

挑战题目

Doomsday Fuel
为LAMBCHOP反应堆核心制造燃料是一个复杂的过程，涉及特殊物质。它从原始矿石开始，在加工过程中随机变换形态，最终达到稳定形态。样本可能最终达到多种稳定形态，并非所有形态都可用作燃料。
Lambda指挥官要求你帮助科学家提高燃料生产效率，预测给定矿石样本的最终状态。你仔细研究了矿石可能呈现的不同结构及其转换过程。研究发现，尽管转换是随机的，但每种结构转换的概率是固定的。即每次矿石处于某一状态时，进入下一状态（可能是同一状态）的概率相同。你记录了观察到的转换矩阵。实验室其他人假设了矿石可能变成的更多特殊形态，但你尚未全部观察到。
编写函数solution(m)，输入一个由非负整数组成的二维数组，表示每个状态转换到下一状态的次数，返回一个整数数组，每个元素对应一个终态的精确概率（以分子形式呈现），最后一个元素为所有概率的最简公分母。矩阵最大为10×10。确保无论矿石处于哪个状态，都存在一条通向终态的路径，即加工过程最终总会达到稳定状态。矿石从状态0开始。在定期简化分数的前提下，分母将适配有符号32位整数。
例如，考虑矩阵m:
[
  [0,1,0,0,0,1],  # s0，初始状态，以相等概率转移到s1和s5
  [4,0,0,3,2,0],  # s1可以转移到s0、s3或s4，但概率不同
  [0,0,0,0,0,0],  # s2是终态，且不可达（实际中未观察到）
  [0,0,0,0,0,0],  # s3是终态
  [0,0,0,0,0,0],  # s4是终态
  [0,0,0,0,0,0]   # s5是终态
]
因此，我们可以考虑通向终态的不同路径，例如：s0 -> s1 -> s3；s0 -> s1 -> s0 -> s1 -> s0 -> s1 -> s4；s0 -> s1 -> s0 -> s5。通过追踪每条路径的概率，我们发现s2的概率为0，s3的概率为3/14，s4的概率为1/7，s5的概率为9/14。将这些概率合并为相同公分母，结果形式为[s2.numerator, s3.numerator, s4.numerator, s5.numerator, denominator]，即[0, 3, 2, 9, 14]。
支持语言
提供Java解决方案，请编辑Solution.java；提供Python解决方案，请编辑solution.py
测试用例
你的代码应通过以下测试用例。请注意，它还可能会针对未显示的隐藏测试用例运行。
-- Java用例 --
输入: Solution.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]
输入: Solution.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]
-- Python用例 --
输入: solution.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]
输入: solution.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]

我的代码

import numpy as np
from fractions import Fraction
from math import gcd


def solution(M):
    height = (len(M))
    length = (len(M[0]))
    M = np.array(M)
    AB = []
    
    #Find B
    for i in range(0, height):
        #if B = 1
        if (sum(M[:,0])) == 0:
            sumB = 1 
        if(M[i,0]) != 0:
            B1 = Fraction((M[i,0]), (sum(M[i])))
            B2 = Fraction((M[0,i]), (sum(M[0])))
            B = B1 * B2

            #Find sum(B) to infinity
            sumB = (1/(1-B))

    #Find A
    boolean2 = 0
    count = 0
    index = []
    for i in range (0, height):
        if sum(M[i]) == 0:
            if boolean2 == 0:
                terminalstart = i
            boolean = 0
            boolean2 = 1
            for j in range(0, height):
                #if there is no A
                if j==height-1 and boolean == 0:
                    index.append(i-terminalstart)
                    count +=1
                if (M[j,i]) != 0:
                    boolean = 1
                    A1 = Fraction((M[j,i]), (sum(M[j])))
                    A = A1
                    if j!=0:
                        A2 = Fraction((M[0,j]), (sum(M[0])))
                        A = A1 * A2
                    
                    #Find AB
                    AB.append(A*sumB)

    #Find common denominators
    x = []
    y = []
    for i in range (0,len(AB)):
        x.append(AB[i].denominator)
    lcm = 1
    #change numerators to fit
    for i in x:
        lcm = lcm*i//gcd(lcm, i)
    for i in range (0, len(AB)):
        z = (lcm) / x[i]
        #
        z = float(z)
        #
        y.append(int((AB[i].numerator)*z))
        
    #insert 0s
    for i in range (0, count):
        y.insert(index[i], 0)

    #insert denominator
    y.append(lcm)
    return y

测试验证

曾在Foo.bar中使用直接返回样例输出的代码：

def solution(M):
    y = [0, 3, 2, 9, 14]
    return y

该代码可通过对应测试用例，说明输出格式要求正确。

参考代码及对比结果

找到一段可正常运行的参考代码：

import numpy as np

# Returns indexes of active & terminal states
def detect_states(matrix):
    active, terminal = [], []
    for rowN, row in enumerate(matrix):
        (active if sum(row) else terminal).append(rowN)
    return(active,terminal)

# Convert elements of array in simplest form
def simplest_form(B):
    B = B.round().astype(int).A1                   # np.matrix --> np.array
    gcd = np.gcd.reduce(B)
    B = np.append(B, B.sum())                      # append the common denom
    return (B / gcd).astype(int)

# Finds solution by calculating Absorbing probabilities
def solution(m):
    active, terminal = detect_states(m)
    if 0 in terminal:                              # special case when s0 is terminal
        return [1] + [0]*len(terminal[1:]) + [1]
    m = np.matrix(m, dtype=float)[active, :]       # list --> np.matrix (active states only)
    comm_denom = np.prod(m.sum(1))                 # product of sum of all active rows (used later)
    P = m / m.sum(1)                               # divide by sum of row to convert to probability matrix
    Q, R = P[:, active], P[:, terminal]            # separate Q & R
    I = np.identity(len(Q))
    N = (I - Q) ** (-1)                            # calc fundamental matrix
    B = N[0] * R * comm_denom / np.linalg.det(N)   # get absorbing probs & get them close to some integer
    return simplest_form(B)

对比两者输出：
参考代码输出：

[ 0  3  2  9 14]
<class 'numpy.ndarray'>
array([ 0,  3,  2,  9, 14])

我的代码输出（转为numpy.ndarray后）：

[ 0  3  2  9 14]
<class 'numpy.ndarray'>
array([ 0,  3,  2,  9, 14])

两者内容、数据类型完全一致，但我的代码仍无法通过Foo.bar测试。

问题分析与解决方法

核心问题：算法逻辑仅适配特定测试用例，不具备通用性

你的代码逻辑存在严重局限性，只针对样例中的特定状态结构编写，无法处理其他测试场景：

状态转换逻辑错误：计算B的部分仅处理了状态0与其他状态的双向转换，完全忽略了多活跃状态的复杂转移情况（比如存在3个及以上活跃状态的场景）。
终态处理不全面：插入0的逻辑依赖terminalstart，假设终态是连续排列的，但题目中终态可以是任意分散的状态，这种处理会导致索引计算错误。
浮点数精度隐患：将z转为float再计算，当分母较大时会出现精度丢失，导致分子计算错误。
特殊情况未处理：未考虑初始状态0本身就是终态的场景（此时应返回[1, 0, ..., 1]）。

解决步骤

重新实现吸收马尔可夫链的标准解法：按照参考代码的思路，基于吸收马尔可夫链的公式B = N * R（其中N是基本矩阵，R是活跃状态到终态的转移概率矩阵）来计算。
替换浮点数运算为分数运算：避免精度丢失，全程用fractions.Fraction处理概率计算，确保精确性。
处理所有边界情况：包括初始状态为终态、终态分散排列、多活跃状态转移等场景。
输出严格符合要求：确保返回的是Python原生列表而非numpy数组（虽然平台接受数组，但原生列表更稳妥），且分数已化简到最简形式。

修正后的可运行代码

from fractions import Fraction
import math

def solution(m):
    # 分离活跃状态和终态
    active = []
    terminal = []
    for idx, row in enumerate(m):
        if sum(row) == 0:
            terminal.append(idx)
        else:
            active.append(idx)
    
    # 初始状态是终态的特殊情况
    if 0 in terminal:
        res = [0]*len(terminal)
        res[terminal.index(0)] = 1
        res.append(1)
        return res
    
    # 构建Q（活跃状态间转移概率）和R（活跃到终态转移概率）矩阵
    size_q = len(active)
    q = [[Fraction(0, 1) for _ in range(size_q)] for _ in range(size_q)]
    r = [[Fraction(0, 1) for _ in range(len(terminal))] for _ in range(size_q)]
    
    for i, active_i in enumerate(active):
        total = sum(m[active_i])
        # 填充Q矩阵
        for j, active_j in enumerate(active):
            q[i][j] = Fraction(m[active_i][active_j], total)
        # 填充R矩阵
        for k, term_k in enumerate(terminal):
            r[i][k] = Fraction(m[active_i][term_k], total)
    
    # 计算基本矩阵N = (I - Q)^-1
    # 生成单位矩阵并减去Q
    i_minus_q = []
    for i in range(size_q):
        row = []
        for j in range(size_q):
            val = Fraction(1, 1) if i == j else Fraction(0, 1)
            row.append(val - q[i][j])
        i_minus_q.append(row)
    
    # 矩阵求逆（伴随矩阵法，适配小型矩阵）
    def matrix_det(mat):
        n = len(mat)
        if n == 1:
            return mat[0][0]
        det_val = Fraction(0, 1)
        for col in range(n):
            sign = Fraction(-1, 1) ** col
            # 生成余子式
            minor = [row[:col] + row[col+1:] for row in mat[1:]]
            det_val += sign * mat[0][col] * matrix_det(minor)
        return det_val
    
    det_val = matrix_det(i_minus_q)
    if det_val == 0:
        return []
    
    # 计算伴随矩阵
    n = size_q
    adjugate = [[Fraction(0, 1) for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            # 生成代数余子式
            minor = [row[:j] + row[j+1:] for row in (i_minus_q[:i] + i_minus_q[i+1:])]
            sign = Fraction(-1, 1) ** (i + j)
            adjugate[j][i] = sign * matrix_det(minor)
    
    # 计算逆矩阵
    inv = [[adjugate[i][j] / det_val for j in range(n)] for i in range(n)]
    
    # 计算B = N[0] * R，得到初始状态到各终态的概率
    probabilities = []
    for col in range(len(terminal)):
        prob = Fraction(0, 1)
        for row in range(size_q):
            prob += inv[0][row] * r[row][col]
        probabilities.append(prob)
    
    # 计算所有分数的最简公分母
    denominators = [f.denominator for f in probabilities]
    lcm = 1
    for d in denominators:
        lcm = lcm * d // math.gcd(lcm, d)
    
    # 转换为分子列表并添加公分母
    result = [f.numerator * (lcm // f.denominator) for f in probabilities]
    result.append(lcm)
    return result

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

Google Foo.bar中Python代码输出匹配但测试全失败问题排查

问题背景 #

挑战题目 #

测试用例 #

我的代码 #

测试验证 #

参考代码及对比结果 #

问题分析与解决方法 #

核心问题：算法逻辑仅适配特定测试用例，不具备通用性 #

解决步骤 #

修正后的可运行代码 #