Guy*_*lks 3 java testing markov-chains
我正在努力完成 Google Foobar 挑战，现在处于 3 级挑战 Doomsday Fuel。说明如下：
由于涉及外来物质，为 LAMBCHOP 的反应堆堆芯制造燃料是一个棘手的过程。它从原始矿石开始，然后在加工过程中开始在各种形式之间随机变化，最终达到稳定的形式。样品最终可能有多种稳定形式，并非所有形式都可用作燃料。
Lambda 指挥官要求您通过预测给定矿石样本的最终状态来帮助科学家提高燃料生产效率。您已经仔细研究了矿石可以采用的不同结构以及它经历的转变。看起来，虽然随机，但每个结构变换的概率是固定的。也就是说，每次矿石处于 1 个状态时，它进入下一个状态（可能是相同的状态）的概率相同。您已经在矩阵中记录了观察到的转变。实验室中的其他人假设了矿石可以变成更奇特的形式，但你还没有看到所有这些形式。
编写一个函数 solution(m)，它采用非负整数数组，表示该状态进入下一个状态的次数，并为每个终止状态返回一个整数数组，给出每个终止状态的确切概率，表示为每个状态的分子，然后是所有状态最后和最简单形式的分母。矩阵最多为 10 x 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];
}
}
}
}
它通过了所有测试用例，但我看不到两个隐藏的测试用例。
我已经尝试了所有可能的测试用例来找到我的代码中的错误，但我不能。
这里有没有我的代码失败的测试用例？
小智 5
问题出在线路上
double[] unsimplifiedAns = FRMatrix[0];
仅当状态 0 是非终止时，上述情况才成立。
否则，输出数组将全部为 0，除了第一个和最后一个元素为 1。