Google foo-bar 挑战第 3 级 - 世界末日燃料 - 马尔可夫链

Question

我一直在尝试解决 google foo-bar 的挑战，但由于测试用例失败，我陷入了第 3 级。我应用了那里解释的马尔可夫链理论：https://github.com/ivanseed/google-foobar-help/blob/master/challenges/doomsday_fuel/doomsday_fuel.md

我的代码通过了除 4、5、6、7 之外的所有测试用例。我最初认为这是因为我使用浮点数来表示分数。因此，我花了几个小时仅使用有理分数来实现相同的解决方案（这需要更多时间，因为您必须重写矩阵运算才能使用分数）。可惜！相同的测试用例失败了。

如果我知道这些测试的输入就好了！

这是我的第一个解决方案，使用浮点数矩阵，随后转换为分数：

import numpy as np
from fractions import Fraction

def find_empty_rows(matrix):
    return np.where(~matrix.any(axis=1))[0]

def calculate_row_sums(matrix):
    row_sums = np.sum(matrix, axis=1)
    return row_sums

def convert_values_into_fractions(matrix, row_sums):
    matrix = matrix.astype(float)

    row_sums[row_sums == 0] = 1
    row_sums = row_sums.reshape(-1, 1)

    probability_matrix = matrix / row_sums

    return probability_matrix
    

def extract_submatrix(matrix, row_indices, col_indices):
    submatrix = matrix[np.ix_(row_indices, col_indices)]
    return submatrix


def float_to_fraction(number, precision=1e-10):
    # Find the numerator and denominator using Fraction
    fraction_result = Fraction(number).limit_denominator()

    # Check if the precision is sufficient
    while abs(float(fraction_result) - number) > precision:
        # Increase the denominator for better precision
        fraction_result = Fraction(number).limit_denominator(fraction_result.denominator * 2)

    return fraction_result

vectorized_float_to_fraction = np.vectorize(float_to_fraction)
    
class NonSimplifiedFraction:
    def __init__(self, numerator, denominator):
        self.numerator = numerator
        self.denominator = denominator

def normalize_fractions(fraction_matrix, common_denominator):
    result_matrix = np.empty_like(fraction_matrix, dtype=object)

    for row in range(fraction_matrix.shape[0]):
        for col in range(fraction_matrix.shape[1]):
            current_fraction = fraction_matrix[row, col]
            result_matrix[row, col] = NonSimplifiedFraction((current_fraction.numerator * common_denominator) // current_fraction.denominator ,
                                               common_denominator)

    return result_matrix

def solution(matrix):

    m = np.array(matrix)

    empty_rows = find_empty_rows(m)

    if 0 in empty_rows:
        return [1] + [0]*(len(matrix) - 1 ) + [1]

    non_empty_rows = np.setdiff1d(np.arange(m.shape[0]), empty_rows)

    row_sums = calculate_row_sums(m)

    m = convert_values_into_fractions(m, row_sums) #change matrix into fractional floats
    R = extract_submatrix(m, non_empty_rows, empty_rows)
    Q = extract_submatrix(m, non_empty_rows, non_empty_rows)

    I = np.identity(Q.shape[0]) #create identity matrix same size as Q

    IminusQ = I - Q

    F = np.linalg.inv(IminusQ)  #take inverse of matrix

    FR = np.dot(F, R)

    fraction_matrix = vectorized_float_to_fraction(FR)   #convert floats to Fractions

    flattened_fractions = fraction_matrix.flatten()

    denominators = [fraction.denominator for fraction in flattened_fractions]

    common_denominator = np.lcm.reduce(denominators)

    fractions_with_common_denominator = normalize_fractions(fraction_matrix, common_denominator)

    end_array = [fraction.numerator for fraction in fractions_with_common_denominator[0]]
    end_array.append(common_denominator)

    return end_array

我错过了什么？

Answer 1

几个月前我完成了这个挑战并完成了所有测试用例。据我所知：这就是我的建议。

潜在问题和改进

1. 精度和算术方法：

   • 最初，您使用浮点数，然后将它们转换为

     Fraction

     对象。这种方法可能会导致浮点不准确。更好的方法是从一开始就使用

     Fraction

     进行所有算术运算。这可以确保您始终处理精确的算术，这对于涉及概率和矩阵运算的问题至关重要。

2. 分数矩阵运算：

   • 重写分数的矩阵运算时，确保精确处理这些运算非常重要。 Python 中内置的

     Fraction

     类提供了一种方法来执行此操作，但您需要确保所有矩阵运算（如求逆、乘法等）与

     Fraction

     对象兼容。这可能意味着手动实现这些操作或使用支持小数算术的库。

3. 处理零行总和：

   • 在代码中，您将零行总和替换为一，以避免被零除。这种方法是合乎逻辑的，但必须确保这不会导致错误的概率计算，尤其是在边缘情况下。在马尔可夫链中，全零的行通常代表吸收状态，这需要在您的计算中正确反映。

4. 矩阵求逆和乘法：

   • 您可以使用 NumPy 的

     linalg.inv

     进行矩阵求逆，使用

     dot

     进行乘法。虽然这些很有效，但它们对于

     Fraction

     对象可能不精确。考虑实现专为小数算术定制的自定义矩阵求逆方法。

5. 分数标准化：

   • 最后将分数归一化为公分母的方法很好，但要确保此过程不会引入任何错误，尤其是在处理非常大或很小的数字时。