I have been working on this java code for the doomsday-fuel problem which deals with the absorbing markov chains. It has passed every test except for test four. Is there any particular type of input I may have missed while testing my code? I have only about 12 hours left. I have tested four one dimensional arrays and am curious as to if this test failure is somehow a precision error or something else.
Context:
Making fuel for the LAMBCHOP's reactor core is a tricky process because of the exotic matter involved. It starts as raw ore, then during processing, begins randomly changing between forms, eventually reaching a stable form. There may be multiple stable forms that a sample could ultimately reach, not all of which are useful as fuel.
Commander Lambda has tasked you to help the scientists increase fuel creation efficiency by predicting the end state of a given ore sample. You have carefully studied the different structures that the ore can take and which transitions it undergoes. It appears that, while random, the probability of each structure transforming is fixed. That is, each time the ore is in 1 state, it has the same probabilities of entering the next state (which might be the same state). You have recorded the observed transitions in a matrix. The others in the lab have hypothesized more exotic forms that the ore can become, but you haven't seen all of them.
Write a function solution(m) that takes an array of array of nonnegative ints representing how many times that state has gone to the next state and return an array of ints for each terminal state giving the exact probabilities of each terminal state, represented as the numerator for each state, then the denominator for all of them at the end and in simplest form. The matrix is at most 10 by 10. It is guaranteed that no matter which state the ore is in, there is a path from that state to a terminal state. That is, the processing will always eventually end in a stable state. The ore starts in state 0. The denominator will fit within a signed 32-bit integer during the calculation, as long as the fraction is simplified regularly.
public static int[] returnFractionPair(double x) {
double tolerance = 1.0E-14;//Handles the extent of precision used
double numerator=1;//Kept as one because initially the decimal may be greater than zero
double numeratorStorage=0;
double denominator=0;
double denominatorStorage=1;//prevents division by zero
double decimal = x;
double comparison = 0;
do {
double flooredDecimal = (double)(int)decimal;//Floors decimal
double aux = numerator;//Sets auxilary to be the numerator
numerator =(flooredDecimal*numerator)+numeratorStorage;
numeratorStorage = aux;
aux = denominator;
denominator = (flooredDecimal*denominator)+denominatorStorage;
denominatorStorage = aux;
decimal = 1/(decimal-flooredDecimal);
comparison = x-(numerator/denominator);
} while( returnAbs(comparison) > (x*tolerance) );//Tests if the difference between the initial decimal and this new numerator/denominator is greater than that of x multiplied by the level of tolerance it has
int[] res = new int[]{(int)numerator, (int)denominator};
return res;
}
public static double returnAbs(double value){
if(value < 0){
value *= -1;
}
return value;
}
public static int getLCD(int[][] fractions){
int num = 0;
int den = 1;
int lcd = 1;
for(int i = 0; i < fractions.length; i++){
lcd *= fractions[i][den];
}
for(int i = 2; i < lcd; i++){
boolean foundLeastCommon = true;
for(int j = 0; j < fractions.length; j++){
if( (double)( i%fractions[j][den] ) != 0){
foundLeastCommon = false;
}
}
if(foundLeastCommon == true){
lcd = i;
return lcd;
}
}
return lcd;
}
public static double[] returnRowSums(int[][] matrix){
//Assume all values in matrix are positive
double[] sumsOfEachRow = new double[matrix.length];
for(int i = 0; i < matrix.length; i++){
for(int j = 0; j < matrix.length; j++){
sumsOfEachRow[i] += matrix[i][j];
}
}
return sumsOfEachRow;
}
public static double returnMatrixCellSum(double[] row, double[] column){//Assume row size == column size.
if(row.length != column.length){
return 0;
}
double sum = 0;
for(int i = 0; i < row.length; i++){
sum += (column[i] * row[i]);
}
return sum;
}
public static int[] returnRearrangedIndices(double[] sumsOfEachRow){
int[] indicesOfRearrangedMatrix = new int[sumsOfEachRow.length];
int indicesIndex = 0;
for(int i = 0; i < sumsOfEachRow.length; i++){
if(sumsOfEachRow[i] <= 1){
indicesOfRearrangedMatrix[indicesIndex] = i;
indicesIndex++;
}//TerminalStates first
}
for(int i = 0; i < sumsOfEachRow.length; i++){
if(sumsOfEachRow[i] > 1){
indicesOfRearrangedMatrix[indicesIndex] = i;
indicesIndex++;
}
}
return indicesOfRearrangedMatrix;
}
public static double[][] subtractMatrix(double[][] matrix1, double[][] matrix2){//assumes matrices are of same dimensions
double[][] matrix3 = new double[matrix1.length][matrix1.length];
for(int i = 0; i < matrix1.length;i++){
for(int j = 0; j < matrix1[i].length; j++){
matrix3[i][j] = matrix1[i][j] - matrix2[i][j];
}
}
return matrix3;
}
public static double[][] rotateMatrix(double[][] matrix){
double[][] rotatedMatrix = new double[matrix[0].length][matrix.length];
for(int i = 0; i < rotatedMatrix.length;i++){
for(int j = 0; j < rotatedMatrix[0].length; j++){
rotatedMatrix[i][j] = matrix[j][i];
}
}
return rotatedMatrix;
}
public static double[][] getRemainingValues(double[][] matrix, int rowIgnored, int columnIgnored){
double[][] newMatrix = new double[matrix.length-1][matrix.length-1];
int iC = 0;
int iR = 0;
for(int k = 0; k < matrix.length; k++){
if(k != rowIgnored){
iR = 0;
for(int j = 0; j < matrix[k].length;j++){
if(j != columnIgnored){
newMatrix[iC][iR] = matrix[k][j];
iR++;
}
}
iC++;
}
}
return newMatrix;
}
public static double getDeterminant(double[][] matrix){
//uses top rows only
double determinant = 0;
if(matrix.length == 1 && matrix[0].length == 1){
return matrix[0][0];
}
boolean negative = false;
double[][] newMatrix = new double[matrix.length-1][matrix.length-1];
for(int i = 0; i < matrix.length; i++){
newMatrix = getRemainingValues(matrix, 0, i);
if(negative == false){
determinant += matrix[0][i]*getDeterminant(newMatrix);
negative = true;
}else{
determinant -= matrix[0][i]*getDeterminant(newMatrix);
negative = false;
}
//System.out.println(determinant);
}
return determinant;
}
public static double[][] getMinorMatrix(double[][] matrix){
double[][] newMatrix = new double[matrix.length][matrix.length];
double[][] remainderMatrix;
if(matrix.length-1 != 0){
remainderMatrix = new double[matrix.length-1][matrix.length-1];
}else{
remainderMatrix = new double[matrix.length][matrix.length];
}
for(int i = 0; i < newMatrix.length;i++){
for(int j = 0; j < newMatrix.length;j++){
remainderMatrix = getRemainingValues(matrix, i, j);
newMatrix[i][j] = getDeterminant(remainderMatrix) + 0.0;//Prevent -0.0 float values
}
}
return newMatrix;
}
public static double[][] divideMatrixByScalar(double[][] matrix, double scalar){
double[][] newMatrix = new double[matrix.length][matrix[0].length];
newMatrix = matrix;
for(int i = 0; i < matrix.length; i++){
for(int j = 0; j < matrix[i].length;j++){
newMatrix[i][j] /= scalar;
}
}
return newMatrix;
}
public static double[][] invertMatrix(double[][] matrix){
double[][] minorMatrix = new double[matrix.length][matrix.length];
if(minorMatrix.length == 2){
minorMatrix = matrix;
double temp = minorMatrix[0][0];
minorMatrix[0][0] = minorMatrix[1][1];
minorMatrix[1][1] = temp;
minorMatrix[0][1] *= -1;
minorMatrix[0][1] += 0;
minorMatrix[1][0] *= -1;
minorMatrix[1][0] += 0;
for(int i = 0; i < minorMatrix.length; i++){
for(int j = 0; j < minorMatrix[i].length; j++){
System.out.print(minorMatrix[i][j] + " ");
}
System.out.print("\n");
}
}else{
minorMatrix = getMinorMatrix(matrix);
System.out.println("Getting minorMatrix");
for(int i = 0; i < minorMatrix.length; i++){
for(int j = 0; j < minorMatrix[i].length; j++){
System.out.print(minorMatrix[i][j] + " ");
}
System.out.print("\n");
}
boolean isNegative = false;
System.out.println("Getting adjoint of minorMatrix");//Not doing things correctly
for(int i = 0; i < minorMatrix.length;i++){
for(int j = 0; j < minorMatrix[i].length;j++){
if(isNegative == true){
minorMatrix[i][j] *= -1;
minorMatrix[i][j] += 0;
isNegative = false;
}else{
isNegative = true;
}
System.out.print(minorMatrix[i][j] + " ");
}
if(minorMatrix[i].length % 2 == 0){
if(isNegative == true){
isNegative = false;
}else{
isNegative = true;
}
}
System.out.print("\n");
}
minorMatrix = rotateMatrix(minorMatrix);//rotates the minorMatrix
}
double determinant = getDeterminant(matrix);
System.out.println(determinant);
if(determinant != 0){
minorMatrix = divideMatrixByScalar(minorMatrix, determinant);
System.out.println("Result");
for(int i = 0; i < minorMatrix.length; i++){
for(int j = 0; j < minorMatrix[i].length; j++){
System.out.print(minorMatrix[i][j] + " ");
}
System.out.print("\n");
}
return minorMatrix;//Inverse is good
}else{
return matrix;
}
}
public static double[][] returnUnabsorbedToUnabsorbed(double[][] matrix, int terminalStates){//Assumes matrix layers go from absorbed to unabsorbed
double[][] unabsorbedToUnabsorbed = new double[matrix.length-terminalStates][matrix.length-terminalStates];
int uIndex = 0;
int uuIndex = 0;
for(int i = terminalStates; i < matrix.length;i++){
uuIndex = 0;
for(int j = terminalStates; j < matrix.length;j++){
unabsorbedToUnabsorbed[uIndex][uuIndex] = matrix[i][j];
uuIndex++;
}
uIndex++;
}
return unabsorbedToUnabsorbed;
}
public static double[][] returnUnabsorbedToAbsorbed(double[][] matrix, int terminalStates){//Assumes matrix layers go from absorbed to unabsorbed
double[][] unabsorbedToAbsorbed = new double[matrix.length-terminalStates][terminalStates];
int uIndex = 0;
int uuIndex = 0;
for(int i = terminalStates; i < matrix.length;i++){
uuIndex = 0;
for(int j = 0; j < terminalStates;j++){
unabsorbedToAbsorbed[uIndex][uuIndex] = matrix[i][j];
uuIndex++;
}
uIndex++;
}
return unabsorbedToAbsorbed;
}
public static double[][] getFundamental(double[][] matrix){
double[][] modifiedMatrix = new double[matrix.length][matrix[0].length];
modifiedMatrix = matrix;
double[][] identity = new double[matrix.length][matrix.length];
for(int i = 0; i < identity.length; i++){
for(int j = 0;j < identity[i].length;j++){
if(i == j){
identity[i][j] = 1;
}else{
identity[i][j] = 0;
}
}
}
modifiedMatrix = subtractMatrix(identity, modifiedMatrix);//Modified matrix is returning properly
/*System.out.println("Getting matrix to be inverted");
for(int i = 0; i < modifiedMatrix.length; i++){
for(int j = 0; j < modifiedMatrix[i].length; j++){
System.out.print(modifiedMatrix[i][j] + " ");
}
System.out.print("\n");
}*/
modifiedMatrix = invertMatrix(modifiedMatrix);//Problem here(?)
return modifiedMatrix;
}
public static double[][] multiplyMatrix(double[][] matrix1, double[][] matrix2){//Assume all rows are equal.
double[][] result = new double[matrix1.length][matrix2[0].length];
double[][] rotatedM2 = new double[matrix2[0].length][matrix2.length];
rotatedM2 = rotateMatrix(matrix2);
for(int i = 0; i < result.length;i++){
for(int j = 0; j < result[i].length; j++){
result[i][j] = returnMatrixCellSum(matrix1[i], rotatedM2[j]);
//RotateMatrix does not increase matrix sums by how it should be
}
}
return result;
}
public static int[] algorithm(int[][] matrix, int startingPoint){
if(matrix.length == 0){
return new int[]{0, 1};
}
if(matrix.length == 1){
int[] ans = new int[matrix.length+1];
for(int i = 0; i < ans.length;i++){
ans[i] = 1;
}
for(int i = 0; i < ans.length; i++){
System.out.println(ans[i]);
}
return ans;
}
double[] sumsOfEachRow = new double[matrix.length];
sumsOfEachRow = returnRowSums(matrix);
double[][] probMatrix = new double[matrix.length][matrix.length];
int terminalStates = 0;//Number of terminal states
for(int i = 0; i < probMatrix.length; i++){
for(int j = 0; j < probMatrix[i].length; j++){
if(sumsOfEachRow[i] != 0){
probMatrix[i][j] = (double)matrix[i][j];
probMatrix[i][j] /= sumsOfEachRow[i];
}else{
probMatrix[i][j] = 0;
}
}
}
boolean startingIsTerminal = false;
for(int i = 0; i < probMatrix.length;i++){
boolean foundOne = false;
for(int j = 0; j < probMatrix[i].length;j++){
if(probMatrix[i][j] == 1 && i == j){
terminalStates++;
foundOne = true;
if(i == startingPoint){
startingIsTerminal = true;
}
}
}
if(foundOne == false){
if(sumsOfEachRow[i] == 0){
terminalStates++;
}
}
}
if( (sumsOfEachRow[startingPoint] == 0) || startingIsTerminal == true){
int[] ans = new int[terminalStates+1];
for(int i = 0; i < terminalStates;i++){
if(i != startingPoint){
ans[i] = 0;
}else{
ans[i] = 1;
}
}
ans[terminalStates] = 1;
for(int i = 0; i < ans.length; i++){
System.out.println(ans[i]);
}
return ans;
}
int[] indicesOfRearrangedMatrix = new int[probMatrix.length];
indicesOfRearrangedMatrix = returnRearrangedIndices(sumsOfEachRow);
double[][] rearranged = new double[probMatrix.length][probMatrix[0].length];
for(int i = 0; i < matrix.length; i++){
for(int j = 0; j < matrix[i].length; j++){
rearranged[i][j] = probMatrix[indicesOfRearrangedMatrix[i]][indicesOfRearrangedMatrix[j]];
System.out.print(rearranged[i][j] + " ");
}
System.out.print("\n");
}//Get rearranged matrix divided
System.out.println("Matrix rearranged");
double[][] unabsorbedToUnabsorbed = new double[probMatrix.length-terminalStates][probMatrix.length-terminalStates];
unabsorbedToUnabsorbed = returnUnabsorbedToUnabsorbed(rearranged, terminalStates);//Get Unabsorbed Matrix
for(int i = 0; i < unabsorbedToUnabsorbed.length; i++){
for(int j = 0; j < unabsorbedToUnabsorbed[i].length; j++){
System.out.print(unabsorbedToUnabsorbed[i][j] + " ");
}
System.out.print("\n");
}
System.out.println("unabsorbedToUnabsorbed");
double[][] unabsorbedToAbsorbed = new double[probMatrix.length-terminalStates][terminalStates];
unabsorbedToAbsorbed = returnUnabsorbedToAbsorbed(rearranged, terminalStates);
for(int i = 0; i < unabsorbedToAbsorbed.length; i++){
for(int j = 0; j < unabsorbedToAbsorbed[i].length; j++){
System.out.print(unabsorbedToAbsorbed[i][j] + " ");
}
System.out.print("\n");
}
System.out.println("unabsorbedToAbsorbed");
double[][] fundamental = new double[unabsorbedToUnabsorbed.length][unabsorbedToUnabsorbed.length];
fundamental = getFundamental(unabsorbedToUnabsorbed);//Gets fundamental
double[][] probResult = multiplyMatrix(fundamental, unabsorbedToAbsorbed);
System.out.println("ProbResult got");
for(int i = 0; i < probResult.length; i++){
for(int j = 0; j < probResult[i].length; j++){
System.out.print(probResult[i][j] + " ");
}
System.out.print("\n");
}
int[][] fractionPairs = new int[terminalStates][2];
for(int i = 0; i < probResult[startingPoint].length; i++){
fractionPairs[i] = returnFractionPair(probResult[startingPoint][i]);
}
int lcd = getLCD(fractionPairs);
int[] ans = new int[terminalStates+1];
int num = 0;
int den = 1;
for(int i = 0; i < fractionPairs.length;++i){
int newNumerator = (lcd/fractionPairs[i][den]) * fractionPairs[i][num];
ans[i] = newNumerator;
}
ans[ans.length-1] = lcd;
for(int i = 0; i < ans.length; i++){
System.out.println(ans[i]);
}
return ans;
}
public static int[] solution(int[][] m) {
return algorithm(m, 0);
}
}