我正在努力通过谷歌Foobar挑战，现在在第3关挑战末日燃料。说明如下。
为LAMBCHOP反应堆核心制造燃料是一个棘手的过程，因为其中涉及的是奇异的物质。它开始时是原矿，然后在加工过程中，开始在不同形态之间随机变化，最终达到稳定的形态。一个样本最终可能会达到多种稳定形态，并非所有的形态都能作为燃料使用。
兰姆达指挥官给你下达了任务，让你通过预测给定矿石样品的最终状态，帮助科学家提高燃料创造效率。你已经仔细研究了矿石可以采取的不同结构，以及它所经历的转变。看来，虽然是随机的，但每种结构转变的概率是固定的。也就是说，每次矿石处于1种状态时，它进入下一种状态（可能是同一种状态）的概率是相同的。 你已经将观察到的转变记录在一个矩阵中。实验室里的其他人假设了矿石可以变成的更奇特的形式，但你还没有看到所有的形式。
写一个函数solution(m)，取一个非负的ints数组，代表该状态到下一个状态的次数，并返回每个终端状态的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].
要提供一个Java解决方案，请编辑Solution.java 要提供一个Python解决方案，请编辑solution.py。
Test cases
==========
>Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.
>-- Java cases --
Input:
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}})
Output:
[7, 6, 8, 21]
>Input:
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}})
Output:
[0, 3, 2, 9, 14]
>-- Python cases --
Input:
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]])
Output:
[7, 6, 8, 21]
>Input:
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]])
Output:
[0, 3, 2, 9, 14]
>Use verify [file] to test your solution and see how it does. When you are finished editing your code, use submit [file] to submit your answer. If your solution passes the test cases, it will be removed from your home folder.
I have written the following code to solve it:
import java.util.ArrayList;
public class Solution {
public static int[] solution(int[][] m) {
double[][] mDouble = toDouble(m);
//TODO: change the double back into an int
// GOAL ONE: find Q matrix :
// 1:seperate the input into two 2d arrays
ArrayList<double[]> ters = new ArrayList<double[]>();
ArrayList<double[]> nonTers = new ArrayList<double[]>();
for(int i = 0; i < mDouble.length; i++){
boolean isTerminal = true;
int sum = 0;
for(int j = 0; j < mDouble[0].length; j++){
sum += mDouble[i][j];
if(mDouble[i][j] != 0){
isTerminal = false;
}
}
if(isTerminal){
ters.add(mDouble[i]);
}else{
for(int j = 0; j < mDouble[0].length; j++){
mDouble[i][j] = mDouble[i][j]/sum;
}
nonTers.add(mDouble[i]);
}
}
double[][] terminalStates = new double[ters.size()][m.length];
double[][] nonTerminalStates = new double[nonTers.size()][m.length];
for(int i = 0; i < ters.size(); i++){
terminalStates[i] = ters.get(i);
}
for(int i = 0; i < nonTers.size(); i++){
nonTerminalStates[i] = nonTers.get(i);
}
// 2: Plug into a function that will create the 2d array
double[][] QMatrix = getQMatrix(nonTerminalStates);
// GOAL TWO: find I matrix
double[][] IMatrix = makeIMatrix(QMatrix.length);
//GOAL 3: Find F matrix
//1: subtract the q matrix from the I matrix
double[][] AMatrix = SubtractMatrices(IMatrix, QMatrix);
//2: find the inverse TODO WRITE FUNCTION
double[][] FMatrix = invert(AMatrix);
//GOAL 4: multiply by R Matrix
//1: find r Matrx
double[][] RMatrix = getRMatrix(nonTerminalStates, terminalStates.length);
//2: use multiply function to get FR Matrix
double[][] FRMatrix = multiplyMatrices(FMatrix, RMatrix);
//GOAL 5: find answer array
//1: get the one dimensional answer
double[] unsimplifiedAns = FRMatrix[0];
//2: get fractions for the answers
int[] ans = fractionAns(unsimplifiedAns);
return ans;
}
public static int[] fractionAns(double[] uAns){
int[] ans = new int[uAns.length + 1];
int[] denominators = new int[uAns.length];
int[] numerators = new int[uAns.length];
for(int i = 0; i < uAns.length; i++){
denominators[i] = (int)(convertDecimalToFraction(uAns[i])[1]);
numerators[i] = (int)(convertDecimalToFraction(uAns[i])[0]);
}
int lcm = (int) lcm_of_array_elements(denominators);
for(int i = 0; i < uAns.length; i++){
ans[i] = numerators[i]*(lcm/convertDecimalToFraction(uAns[i])[1]);
}
ans[ans.length-1] = lcm;
return ans;
}
static private int[] convertDecimalToFraction(double x){
double tolerance = 1.0E-10;
double h1=1; double h2=0;
double k1=0; double k2=1;
double b = x;
do {
double a = Math.floor(b);
double aux = h1; h1 = a*h1+h2; h2 = aux;
aux = k1; k1 = a*k1+k2; k2 = aux;
b = 1/(b-a);
} while (Math.abs(x-h1/k1) > x*tolerance);
return new int[]{(int)h1, (int)k1};
}
public static long lcm_of_array_elements(int[] element_array)
{
long lcm_of_array_elements = 1;
int divisor = 2;
while (true) {
int counter = 0;
boolean divisible = false;
for (int i = 0; i < element_array.length; i++) {
// lcm_of_array_elements (n1, n2, ... 0) = 0.
// For negative number we convert into
// positive and calculate lcm_of_array_elements.
if (element_array[i] == 0) {
return 0;
}
else if (element_array[i] < 0) {
element_array[i] = element_array[i] * (-1);
}
if (element_array[i] == 1) {
counter++;
}
// Divide element_array by devisor if complete
// division i.e. without remainder then replace
// number with quotient; used for find next factor
if (element_array[i] % divisor == 0) {
divisible = true;
element_array[i] = element_array[i] / divisor;
}
}
// If divisor able to completely divide any number
// from array multiply with lcm_of_array_elements
// and store into lcm_of_array_elements and continue
// to same divisor for next factor finding.
// else increment divisor
if (divisible) {
lcm_of_array_elements = lcm_of_array_elements * divisor;
}
else {
divisor++;
}
// Check if all element_array is 1 indicate
// we found all factors and terminate while loop.
if (counter == element_array.length) {
return lcm_of_array_elements;
}
}
}
public static double[][] toDouble(int[][] ma){
double[][] retArr = new double[ma.length][ma.length];
for(int i = 0; i < retArr.length; i++){
for(int j = 0; j < retArr[0].length; j++){
retArr[i][j] = (ma[i][j]);
}
}
return retArr;
}
public static double[][] getRMatrix(double[][] nonTerminals, int terminalLength){
double[][] retArr = new double[nonTerminals.length][terminalLength];
for(int i = 0; i < retArr.length; i++){
for(int j = nonTerminals.length; j < nonTerminals[0].length; j++){
retArr[i][j-nonTerminals.length] = (nonTerminals[i][j]);
}
}
return retArr;
}
public static double[][] multiplyMatrices(double[][] firstMatrix, double[][] secondMatrix){
int r1 = firstMatrix.length;
int c1 = firstMatrix[0].length;
int c2 = secondMatrix[0].length;
double[][] product = new double[r1][c2];
for(int i = 0; i < r1; i++) {
for (int j = 0; j < c2; j++) {
for (int k = 0; k < c1; k++) {
product[i][j] += firstMatrix[i][k] * secondMatrix[k][j];
}
}
}
return product;
}
public static double[][] inverseMatrix(double[][] Amatrix){
return null;
}
public static double[][] SubtractMatrices(double[][] I, double[][] Q){
double[][] retArr = new double[I.length][I.length];
for(int i = 0; i < retArr.length; i++){
for(int j = 0; j < retArr.length; j++){
retArr[i][j] = I[i][j]-Q[i][j];
}
}
return retArr;
}
public static double[][] getQMatrix(double[][] qArr){
int size = qArr.length;
double[][] retArr = new double[size][size];
for(int i = 0; i < size; i++){
for(int j = 0; j < size; j++){
retArr[i][j] = qArr[i][j];
}
}
return retArr;
}
public static double[][] makeIMatrix(int size){
double[][] retArr = new double[size][size];
for(int i = 0; i < size; i++){
for(int j = 0; j < size; j++){
if(i == j){
retArr[i][j] = 1;
}else{
retArr[i][j] = 0;
}
}
}
return retArr;
}
public static double[][] invert(double a[][])
{
int n = a.length;
double x[][] = new double[n][n];
double b[][] = new double[n][n];
int index[] = new int[n];
for (int i=0; i<n; ++i)
b[i][i] = 1;
// Transform the matrix into an upper triangle
gaussian(a, index);
// Update the matrix b[i][j] with the ratios stored
for (int i=0; i<n-1; ++i)
for (int j=i+1; j<n; ++j)
for (int k=0; k<n; ++k)
b[index[j]][k]
-= a[index[j]][i]*b[index[i]][k];
// Perform backward substitutions
for (int i=0; i<n; ++i)
{
x[n-1][i] = b[index[n-1]][i]/a[index[n-1]][n-1];
for (int j=n-2; j>=0; --j)
{
x[j][i] = b[index[j]][i];
for (int k=j+1; k<n; ++k)
{
x[j][i] -= a[index[j]][k]*x[k][i];
}
x[j][i] /= a[index[j]][j];
}
}
return x;
}
// Method to carry out the partial-pivoting Gaussian
// elimination. Here index[] stores pivoting order.
public static void gaussian(double a[][], int index[])
{
int n = index.length;
double c[] = new double[n];
// Initialize the index
for (int i=0; i<n; ++i)
index[i] = i;
// Find the rescaling factors, one from each row
for (int i=0; i<n; ++i)
{
double c1 = 0;
for (int j=0; j<n; ++j)
{
double c0 = Math.abs(a[i][j]);
if (c0 > c1) c1 = c0;
}
c[i] = c1;
}
// Search the pivoting element from each column
int k = 0;
for (int j=0; j<n-1; ++j)
{
double pi1 = 0;
for (int i=j; i<n; ++i)
{
double pi0 = Math.abs(a[index[i]][j]);
pi0 /= c[index[i]];
if (pi0 > pi1)
{
pi1 = pi0;
k = i;
}
}
// Interchange rows according to the pivoting order
int itmp = index[j];
index[j] = index[k];
index[k] = itmp;
for (int i=j+1; i<n; ++i)
{
double pj = a[index[i]][j]/a[index[j]][j];
// Record pivoting ratios below the diagonal
a[index[i]][j] = pj;
// Modify other elements accordingly
for (int l=j+1; l<n; ++l)
a[index[i]][l] -= pj*a[index[j]][l];
}
}
}
}
它通过了所有的测试用例，但有两个隐藏的测试用例我看不到。
我已经尝试了所有的测试用例，我可能会找到我代码中的错误，但我不能。
这里有什么测试用例是我的代码失败的吗？
问题在于行
double[] unsimplifiedAns = FRMatrix[0];
只有当状态0是非终止状态时，上述情况才为真。
否则，输出数组除了第一个和最后一个元素为 "1 "外，其余都是 "0"。