Page MenuHomedesp's stash
Files F213087

Solution.java
No OneTemporary
Actions

Solution.java
View Options

import java.util.stream.IntStream;
public class Solution {
public static int[] solution(int[][] m) {
double[][] matrix = new double[m.length][m.length]; //A, assume square matrix as stated
//find terminal layers
int[] sums = new int[m.length]; //stored for later use
int firstTerminal = m.length;
for (int i = 0; i < m.length; i++) {
sums[i] = IntStream.of(m[i]).sum();
if (sums[i] != 0) { //only normalize for non terminal states
for (int j = 0; j < m[0].length; j++) {
matrix[i][j] = m[i][j] / (double) sums[i];
}
} else {
firstTerminal--;
}
}
//exceptional case return
if(sums[0] == 0) { //s0 is terminal; cannot reach all other states
int[] fin = new int[m.length + 1];
fin[0] = fin[m.length] = 1;
return fin;
}
//continue computing
int pointer = 0;
//move terminal states to the end
for (int i = 0; i < m.length; i++) {
if (sums[i] == 0) {
boolean swapped = false;
int origPos =(int) matrix[i][0]; //store orig pos in first cell of terminal vector since its unused anyways
if(origPos == 0) origPos = ++pointer;
for (int j = i + 1; j < m.length; j++) {
if (sums[j] != 0) { //find earliest non terminal state to swap place
sums[i] = sums[j]; //update sums
sums[j] = 0;
for (int k = 0; k < m.length; k++) {
matrix[i][k] = matrix[j][k]; //swap row
matrix[j][k] = 0; //always zero in terminal state vector
}
for (int k = 0; k < m.length; k++) {
double temp = matrix[k][i];
matrix[k][i] = matrix[k][j]; //swap column
matrix[k][j] = temp;
}
matrix[j][0] = origPos;
swapped = true;
break;
}
}
if(!swapped) matrix[i][0] = origPos; //if not swapped, its original
}
}
int qSize = firstTerminal;
for (int i = 0; i < qSize; i++) { // I - Q, where Q is sub square matrix of A in the non terminal region
for (int j = 0; j < qSize; j++) {
matrix[i][j] = (i == j ? 1 : 0) - matrix[i][j];
}
}
//start inversing Q
double[][] inverse = new double[qSize][qSize];
//minor and cofactor calculation
for (int i = 0; i < qSize; i++) {
for (int j = 0; j < qSize; j++) {
inverse[i][j] = Math.pow(-1, i + j) * determinant(minor(matrix, i, j, qSize), qSize - 1);
}
}
//swap elements with determinant
double det = 1 / determinant(matrix, qSize);
for (int i = 0; i < qSize; i++) {
for (int j = 0; j <= i; j++) {
double temp = inverse[i][j];
inverse[i][j] = inverse[j][i] * det;
inverse[j][i] = temp * det;
}
}
//multiply inverse Q with terminal state sub matrix
double[] w = new double[matrix.length - firstTerminal];
for (int i = 0; i < w.length; i++) {
double sum = 0;
for (int k = 0; k < qSize; k++) {
sum += matrix[k][i + firstTerminal] * inverse[0][k]; //only need first row results
}
w[i] = sum;
}
//turn into fractions
int[][] fractions = new int[w.length][2];
int gcd = 1;
for (int i = 0; i < fractions.length; i++) {
int origPos = (int) matrix[i + firstTerminal][0] - 1; //fetch original pos from matrix
int[] f = decimalToFraction(w[i]);
fractions[origPos][0] = f[0];
fractions[origPos][1] = f[1];
if (f[1] != 1) //ignore denominator=1
gcd = (gcd * f[1]) / gcd(gcd, f[1]); //LCM
}
//get common denominator and populate the final returning array
int[] finalRes = new int[fractions.length + 1];
for (int i = 0; i < fractions.length; i++) {
finalRes[i] = fractions[i][0] * (gcd / fractions[i][1]);
}
finalRes[fractions.length] = gcd;
return finalRes;
}
/**
* START MATRIX HELPER METHODS
* * assumes square matrixes only
*/
private static double determinant(double[][] matrix, int n) {
if (matrix.length == 1 || n == 1)
return matrix[0][0];
double det = 0;
for (int i = 0; i < n; i++) {
det += Math.pow(-1, i) * matrix[0][i] * determinant(minor(matrix, 0, i, n), n - 1);
}
return det;
}
private static double[][] minor(double[][] matrix, int row, int column, int n) {
int size = n - 1;
double[][] minor = new double[size][size];
for (int i = 0; i < n; i++) {
for (int j = 0; i != row && j < n; j++) {
if (j != column) {
minor[i < row ? i : i - 1][j < column ? j : j - 1] = matrix[i][j];
}
}
}
return minor;
}
/**
* START FRACTION HELPER METHODS
*/
private static final double EPSILON = 1e-6;
private static int[] decimalToFraction(double d) {
int xF = (int) Math.round(d);
int yF = 1;
double error = Math.abs(d - xF);
for (int y = 2; error > EPSILON; y++) {
int x = (int) (d * y);
for (int i = 0; i < 2; i++) {
double e = Math.abs(d - ((double) x / y));
if (e < error) {
xF = x;
yF = y;
error = e;
}
x++;
}
}
return new int[] { xF, yF };
}
private static int gcd(int a, int b) {
if (a == 0)
return b;
return gcd(b % a, a);
}
}

File Metadata

Mime Type
text/x-java
Expires
Tue, Jan 7, 12:08 AM (1 h, 45 m)
Storage Engine
local-disk
Storage Format
Raw Data
Storage Handle
11/6d/e2e2546a369341e1d0a357f4c7e7

Event Timeline

Back to Main Site