title: Google foo bar challenge Level 3 - Doomsday-fuel
body: <p>This question may be asked many times, but still, not all answers could be resolved. Since I have only less than 20 hours left so I hope someone can give me some advises. Really appreciate your help.</p>
  <p>Currently, I have only one test case fail left to deal with (test case 3) but I have no idea what situation I forgot to include. I have made a Matrix and Fraction class for me to do operation more easily. Sorry about the commented println as it was for my debugging.</p>
  <p>I used Absorbing Markov Chains concept to find Q, R, F and FR matrices which enlightened me by <a href="https://github.com/ivanseed/google-foobar-help/blob/master/challenges/doomsday_fuel/doomsday_fuel.md" rel="noreferrer">https://github.com/ivanseed/google-foobar-help/blob/master/challenges/doomsday_fuel/doomsday_fuel.md</a> .</p>
  <p>Thanks again if you have any comments! Please help!</p>
  <p>Question and my Solution.java is as follow:</p>
  <p>Question:</p>
  <pre><code>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. 
  
  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 -&gt; s1 -&gt; s3
  s0 -&gt; s1 -&gt; s0 -&gt; s1 -&gt; s0 -&gt; s1 -&gt; s4
  s0 -&gt; s1 -&gt; s0 -&gt; 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].
  </code></pre>
  <p>My Solution.java:</p>
  <pre><code>import java.lang.Math;
  import java.util.ArrayList;
  
  public class Solution {
      public static int[] solution(int[][] m) {
          // Your code here
          ArrayList&lt;Integer&gt; termStateList = new ArrayList&lt;Integer&gt;();
          ArrayList&lt;Integer&gt; nonTermStateList = new ArrayList&lt;Integer&gt;();
          ArrayList&lt;Integer&gt; stateDenominatorList = new ArrayList&lt;Integer&gt;();
          for (int i = 0; i &lt; m.length; i++) {
              boolean allZeroInState = true;
              int stateDenominatorTemp = 0;
              // loop through probability of all states for a particular state
              for (int j = 0; j &lt; m[0].length; j++) {
                  if (m[i][j] != 0) {
                      allZeroInState = false;
                      stateDenominatorTemp += m[i][j];
                  }
              }
              if (allZeroInState) {
                  termStateList.add(i);
              } else {
                  nonTermStateList.add(i);
                  stateDenominatorList.add(stateDenominatorTemp);
              }
          }
          ////system.out.println(Arrays.toString(termStateList.toArray()));
          ////system.out.println(Arrays.toString(nonTermStateList.toArray()));
          ////system.out.println(Arrays.toString(stateDenominatorList.toArray()));
  
          // Create I 0 R Q matrix -- may not need
          Fraction one = new Fraction(1);
          Fraction zero = new Fraction(0);
  
          // Create I
          ArrayList&lt;ArrayList&lt;Fraction&gt;&gt; IList = new ArrayList&lt;ArrayList&lt;Fraction&gt;&gt;();
          for (int i = 0; i &lt; nonTermStateList.size(); i++) {
              ArrayList&lt;Fraction&gt; IRow = new ArrayList&lt;Fraction&gt;();
              for (int j = 0; j &lt; nonTermStateList.size(); j++) {
                  if (i==j) {
                      IRow.add(one);
                  } else {
                      IRow.add(zero);
                  }
              }
              IList.add(IRow);
          }
          Matrix I = new Matrix(IList, nonTermStateList.size(), nonTermStateList.size());
          //system.out.println(&quot;I:&quot;);
          I.print();
  
          // Create Q
          ArrayList&lt;ArrayList&lt;Fraction&gt;&gt; QList = new ArrayList&lt;ArrayList&lt;Fraction&gt;&gt;();
          for (int i = 0; i &lt; nonTermStateList.size(); i++) {
              ArrayList&lt;Fraction&gt; QRow = new ArrayList&lt;Fraction&gt;();
              for (int j = 0; j &lt; nonTermStateList.size(); j++) {
                  QRow.add(new Fraction(m[nonTermStateList.get(i)][nonTermStateList.get(j)], stateDenominatorList.get(i)));
              }
              QList.add(QRow);
          }
  
          Matrix Q = new Matrix(QList, nonTermStateList.size(), nonTermStateList.size());
          //system.out.println(&quot;Q:&quot;);
          Q.print();
  
          // Create R
          ArrayList&lt;ArrayList&lt;Fraction&gt;&gt; RList = new ArrayList&lt;ArrayList&lt;Fraction&gt;&gt;();
          for (int i = 0; i &lt; nonTermStateList.size(); i++) {
              ArrayList&lt;Fraction&gt; RRow = new ArrayList&lt;Fraction&gt;();
              for (int j = 0; j &lt; termStateList.size(); j++) {
                  RRow.add(new Fraction(m[nonTermStateList.get(i)][termStateList.get(j)], stateDenominatorList.get(i)));
              }
              RList.add(RRow);
          }
  
          Matrix R = new Matrix(RList, nonTermStateList.size(), termStateList.size());
          //system.out.println(&quot;R:&quot;);
          R.print();
  
          // Find I - Q
          Matrix IminusQ = I.minus(Q);
          //system.out.println(&quot;IminusQ:&quot;);
          IminusQ.print();
          // Find F = (I - Q)^-1
          Matrix F = IminusQ.getInverseMatrix();
          //system.out.println(&quot;F:&quot;);
          F.print();
          // Find FR
          Matrix FR = F.multiply(R);
          //system.out.println(&quot;FR:&quot;);
          FR.print();
          // Take the first row of FR
          ArrayList&lt;Fraction&gt; FRRow = FR.getRow(0);
          ArrayList&lt;Fraction&gt; numeratorList = new ArrayList&lt;Fraction&gt;(); // numeratorList
          int[] denomList = new int[FRRow.size()]; // denomList
          // Find the numerators and the common denominator, make it an array
          for (int i = 0; i &lt; FRRow.size(); i++) {
              denomList[i] = FRRow.get(i).getDenominator();
              numeratorList.add(FRRow.get(i));
          }
          int lcm = getLcm(denomList);
          int[] result = new int[FRRow.size()+1];
          for (int j = 0; j &lt; result.length-1; j++) {
              numeratorList.set(j, numeratorList.get(j).multiply(new Fraction(lcm)));
              result[j] = numeratorList.get(j).getNumerator();
          }
          result[FRRow.size()] = lcm;
          //system.out.println(Arrays.toString(result));
  
          return result;
      }
  
      public static int getLcm(int arr[]) {
          int max = 0; 
          int n = arr.length;
          for (int i = 0; i &lt; n; i++) { 
              if (max &lt; arr[i]) { 
                  max = arr[i]; 
              } 
          }  
          int res = 1;   
          int factor = 2; 
          while (factor &lt;= max) {  
              ArrayList&lt;Integer&gt; arrIndex = new ArrayList&lt;Integer&gt;(); 
              for (int j = 0; j &lt; n; j++) { 
                  if (arr[j] % factor == 0) { 
                      arrIndex.add(arrIndex.size(), j); 
                  } 
              }
              if (arrIndex.size() &gt;= 2) { 
                  // Reduce all array elements divisible  
                  // by factor.  
                  for (int j = 0; j &lt; arrIndex.size(); j++) { 
                      arr[arrIndex.get(j)] /= factor; 
                  } 
    
                  res *= factor; 
              } else { 
                  factor++; 
              } 
          } 
    
          // Then multiply all reduced array elements  
          for (int i = 0; i &lt; n; i++) { 
              res *= arr[i]; 
          } 
    
          return res; 
      }
      
      private static class Matrix {
  
          private final int M;
          private final int N;
          private final Fraction det;
          private ArrayList&lt;ArrayList&lt;Fraction&gt;&gt; matrix;
          private ArrayList&lt;ArrayList&lt;Fraction&gt;&gt; inverseMatrix;
  
          public Matrix(ArrayList&lt;ArrayList&lt;Fraction&gt;&gt; mat, int m, int n) {
              this.matrix = mat;
              this.M = m;
              this.N = n;
              this.det = this.determinant(mat, n);
              this.inverseMatrix = this.inverse();
          }
  
          private void getCofactor(ArrayList&lt;ArrayList&lt;Fraction&gt;&gt; mat, ArrayList&lt;ArrayList&lt;Fraction&gt;&gt; tempMat, int p, int q, int n) {
              int i = 0;
              int j = 0;
              for (int row = 0; row &lt; n; row++) {
                  for (int col = 0; col &lt; n; col++) {
                      if (row != p &amp;&amp; col != q) {
                          tempMat.get(i).set(j++, mat.get(row).get(col));
                          if (j == n - 1) {
                              j = 0;
                              i++;
                          }
                      }
                  }
              }
          }
  
          private Fraction determinant(ArrayList&lt;ArrayList&lt;Fraction&gt;&gt; mat, int n) {
              Fraction ans = new Fraction(0, 1);
              if (this.M != this.N) {
                  return ans;
              }
              if (n == 1) {
                  return mat.get(0).get(0);
              }
              ArrayList&lt;ArrayList&lt;Fraction&gt;&gt; tempMat = new ArrayList&lt;ArrayList&lt;Fraction&gt;&gt;();
              // Init 2d fraction arraylist
              for (int i = 0; i &lt; this.M; i++) {
                  ArrayList&lt;Fraction&gt; tempMatRow = new ArrayList&lt;Fraction&gt;();
                  for (int j = 0; j &lt; this.N; j++) {
                      tempMatRow.add(new Fraction(0, 1));
                  }
                  tempMat.add(tempMatRow);
              }   
  
              int sign = 1;
              Fraction signFraction = new Fraction(sign, 1);
              for (int k = 0; k &lt; n; k++) {
                  this.getCofactor(mat, tempMat, 0, k, n);
                  ans = ans.plus(signFraction.multiply(mat.get(0).get(k).multiply(determinant(tempMat, n - 1))));
                  sign = -sign;
                  signFraction = new Fraction(sign, 1);
              }
              return ans;
          }
  
          private void adjoint(ArrayList&lt;ArrayList&lt;Fraction&gt;&gt; mat, ArrayList&lt;ArrayList&lt;Fraction&gt;&gt; adj) {
              if (this.N == 1) {
                  adj.get(0).set(0, new Fraction(1, 1));
                  return;
              }
              int sign = 1;
              
              ArrayList&lt;ArrayList&lt;Fraction&gt;&gt; tempMat = new ArrayList&lt;ArrayList&lt;Fraction&gt;&gt;();
              // Init 2d fraction arraylist
              for (int i = 0; i &lt; this.N; i++) {
                  ArrayList&lt;Fraction&gt; tempMatRow = new ArrayList&lt;Fraction&gt;();
                  for (int j = 0; j &lt; this.N; j++) {
                      tempMatRow.add(new Fraction(0, 1));
                  }
                  tempMat.add(tempMatRow);
              }
  
              for (int p = 0; p &lt; this.N; p++) {
                  for (int q = 0; q &lt; this.N; q++) {
                      this.getCofactor(mat, tempMat, p, q, this.N);
                      sign = ((p + q) % 2 == 0) ? 1 : -1;
                      Fraction signFraction = new Fraction(sign, 1);
                      adj.get(q).set(p, signFraction.multiply((this.determinant(tempMat, this.N - 1))));
                  }
              }
          }
  
          private ArrayList&lt;ArrayList&lt;Fraction&gt;&gt; inverse() {
              ArrayList&lt;ArrayList&lt;Fraction&gt;&gt; inv = new ArrayList&lt;ArrayList&lt;Fraction&gt;&gt;();
              // Init 2d fraction arraylist
              for (int i = 0; i &lt; this.M; i++) {
                  ArrayList&lt;Fraction&gt; invRow = new ArrayList&lt;Fraction&gt;();
                  for (int j = 0; j &lt; this.N; j++) {
                      invRow.add(new Fraction(0, 1));
                  }
                  inv.add(invRow);
              }
  
              if (this.det.equals(new Fraction(0))) {
                  return inv;
              }
  
              ArrayList&lt;ArrayList&lt;Fraction&gt;&gt; adj = new ArrayList&lt;ArrayList&lt;Fraction&gt;&gt;();
              // Init 2d fraction arraylist
              for (int i = 0; i &lt; this.M; i++) {
                  ArrayList&lt;Fraction&gt; adjRow = new ArrayList&lt;Fraction&gt;();
                  for (int j = 0; j &lt; this.N; j++) {
                      adjRow.add(new Fraction(0, 1));
                  }
                  adj.add(adjRow);
              }
  
              adjoint(this.matrix, adj);
              for (int p = 0; p &lt; this.N; p++) {
                  for (int q = 0; q &lt; this.N; q++) {
                      Fraction temp = adj.get(p).get(q).dividedBy(this.det);
                      inv.get(p).set(q, temp);
                  }
              }
              return inv;
          }
  
          public Matrix getInverseMatrix() {
              if (this.M != this.N) {
                  //system.out.println(&quot;No inverse matrix for non-square matrices&quot;);
              }
              return new Matrix(this.inverseMatrix, this.M, this.N);
          }
  
          public Fraction getElement(int m, int n) {
              return this.matrix.get(m).get(n);
          }
  
          public ArrayList&lt;Fraction&gt; getRow(int m) {
              if (m &lt;= this.M) {
                  return this.matrix.get(m);
              }
              return new ArrayList&lt;Fraction&gt;();
          }
  
          public Matrix plus(Matrix mat) {
              int M_m = mat.getDimension()[0];
              int N_m = mat.getDimension()[1];
              if (this.M != M_m || this.N != N_m) {
                  //system.out.println(&quot;Error in plus: Dimensions of two matrices are not equal!&quot;); // Debug
                  return mat;
              } else {
                  ArrayList&lt;ArrayList&lt;Fraction&gt;&gt; sum = new ArrayList&lt;ArrayList&lt;Fraction&gt;&gt;();
                  // Init 2d fraction arraylist
                  for (int i = 0; i &lt; this.M; i++) {
                      ArrayList&lt;Fraction&gt; sumRow = new ArrayList&lt;Fraction&gt;();
                      for (int j = 0; j &lt; this.N; j++) {
                          sumRow.add(new Fraction(0, 1));
                      }
                      sum.add(sumRow);
                  }
                  for (int i = 0; i &lt; this.M; i++) {
                      for (int j = 0; j &lt; this.N; j++) {
                          // sum[i][j] = this.matrix[i][j] + mat.getElement(i, j);
                          sum.get(i).set(j, this.matrix.get(i).get(j).plus(mat.getElement(i, j)));
                      }
                  }
                  return new Matrix(sum, this.M, this.N);
              }
          }
  
          public Matrix minus(Matrix mat) {
              int M_m = mat.getDimension()[0];
              int N_m = mat.getDimension()[1];
              if (this.M != M_m || this.N != N_m) {
                  //system.out.println(&quot;Error in minus: Dimensions of two matrices are not equal!&quot;); // Debug
                  return mat;
              } else {
                  ArrayList&lt;ArrayList&lt;Fraction&gt;&gt; difference = new ArrayList&lt;ArrayList&lt;Fraction&gt;&gt;();
                  // Init 2d fraction arraylist
                  for (int i = 0; i &lt; this.M; i++) {
                      ArrayList&lt;Fraction&gt; differenceRow = new ArrayList&lt;Fraction&gt;();
                      for (int j = 0; j &lt; this.N; j++) {
                          differenceRow.add(new Fraction(0, 1));
                      }
                      difference.add(differenceRow);
                  }
                  for (int i = 0; i &lt; this.M; i++) {
                      for (int j = 0; j &lt; this.N; j++) {
                          // difference[i][j] = this.matrix[i][j] + mat.getElement(i, j);
                          difference.get(i).set(j, this.matrix.get(i).get(j).minus(mat.getElement(i, j)));
                      }
                  }
                  return new Matrix(difference, this.M, this.N);
              }
          }
  
          public Matrix multiply(Matrix mat) {
              // M N M N
              // X(m, n) x Y(n, p) = Z(m, p)
              int M_m = mat.getDimension()[0];
              int p_m = mat.getDimension()[1];
              if (this.N != M_m) {
                  //system.out.println(&quot;Error in multiply: Dimensions of two matrices are valid for cross multiplication!&quot;); // Debug
                  return mat;
              } else {
                  ArrayList&lt;ArrayList&lt;Fraction&gt;&gt; product = new ArrayList&lt;ArrayList&lt;Fraction&gt;&gt;();
                  // Init 2d fraction arraylist
                  for (int i = 0; i &lt; this.M; i++) {
                      ArrayList&lt;Fraction&gt; productRow = new ArrayList&lt;Fraction&gt;();
                      for (int j = 0; j &lt; p_m; j++) {
                          productRow.add(new Fraction(0, 1));
                      }
                      product.add(productRow);
                  }
                  for (int i = 0; i &lt; this.M; i++) {
                      for (int j = 0; j &lt; p_m; j++) {
                          for (int k = 0; k &lt; this.N; k++) {
                              // product[i][j] += matrix[i][k] * mat.getElement(k, j);
                              Fraction temp = product.get(i).get(j);
                              product.get(i).set(j, temp.plus(this.matrix.get(i).get(k).multiply(mat.getElement(k, j))));
                          }
                      }
                  }
                  return new Matrix(product, this.M, p_m);
              }
  
          }
  
          public int[] getDimension() {
              return new int[] { this.M, this.N };
          }
  
          public void print() {
              for (int i = 0; i &lt; this.M; i++) {
                  for (int j = 0; j &lt; this.N; j++) {
                      //system.out.print(this.matrix.get(i).get(j).toString() + &quot;  &quot;);
                  }
                  //system.out.println();
              }
          }
  
          public void printInverse() {
              if (this.M != this.N) {
                  //system.out.println(&quot;No inverse matrix for non-square matrices&quot;);
                  return;
              }
              if (this.det.equals(new Fraction(0))) {
                  //system.out.println(&quot;Singular matrix, can't find its inverse&quot;);
                  return;
              }
              for (int i = 0; i &lt; this.M; i++) {
                  for (int j = 0; j &lt; this.N; j++) {
                      //system.out.print(this.inverseMatrix.get(i).get(j).toString() + &quot;  &quot;);
                  }
                  //system.out.println();
              }
          }
  
      }
  
      private static class Fraction {
  
          private int numerator;
          private int denominator = 1;
          private boolean sign = false; // true = negative, false = positive
  
          public Fraction(int num, int denom) {
              this.numerator = num;
              if (denom == 0) {
                  //system.out.println(&quot;Denominator cannot be 0. Setting it to 1&quot;);
              } else {        
                  this.denominator = denom;
              }
              this.simplify();
          }
  
          public Fraction(int num) {
              this.numerator = num;
              this.simplify();
          }
  
          private int getGcm(int num1, int num2) {
              return num2 == 0 ? num1 : this.getGcm(num2, num1 % num2);
          }
  
          // Simplify fraction to simplest form, runs in constructor
          public void simplify() {        
              this.sign = !(this.numerator &lt;= 0 &amp;&amp; this.denominator &lt;= 0) &amp;&amp; !(this.numerator &gt;= 0 &amp;&amp; this.denominator &gt;= 0);
  
              this.numerator = Math.abs(this.numerator);
              this.denominator = Math.abs(this.denominator);
  
              int gcm = this.getGcm(this.numerator, this.denominator);
              this.numerator = this.numerator / gcm;
              this.denominator = this.denominator / gcm;
              // When fraction is zero, make sure denominator is one and no negative sign
              if (this.numerator == 0 &amp;&amp; this.denominator != 0) {
                  this.denominator = 1;
                  this.sign = false;
              }
          }
  
          public Fraction plus(Fraction f1) {
              int num = 0;
              if (this.sign) { // this fraction is negative
                  if (f1.getSign()) { // f1 is negative
                      num = (-1) * this.numerator * f1.denominator + this.denominator * (-1) * f1.numerator;
                  } else { // f1 is positive
                      num = (-1) * this.numerator * f1.denominator + this.denominator * f1.numerator;                
                  }
              } else { // this fraction is positive
                  if (f1.getSign()) { // f1 is negative
                      num = this.numerator * f1.denominator + this.denominator * (-1) * f1.numerator; 
                  } else { // f1 is positive
                      num = this.numerator * f1.denominator + this.denominator * f1.numerator; 
                  }
              }
              int denom = this.denominator * f1.getDenominator();
              return new Fraction(num, denom);
          }
  
          public Fraction minus(Fraction f1) {
              int num = 0;
              if (this.sign) { // this fraction is negative
                  if (f1.getSign()) { // f1 is negative
                      num = (-1) * this.numerator * f1.denominator + this.denominator * f1.numerator;
                  } else { // f1 is positive
                      num = (-1) * this.numerator * f1.denominator - this.denominator * f1.numerator;                
                  }
              } else { // this fraction is positive
                  if (f1.getSign()) { // f1 is negative
                      num = this.numerator * f1.denominator + this.denominator * f1.numerator; 
                  } else { // f1 is positive
                      num = this.numerator * f1.denominator - this.denominator * f1.numerator; 
                  }
              }
              int denom = this.denominator * f1.getDenominator();
              return new Fraction(num, denom);
          }
  
          public Fraction multiply(Fraction f1) {
              int signInt = 1;
              // Either one fraction is negative will make the product fraction negative, but not for both fractions are negative.
              if (this.sign &amp;&amp; !f1.getSign() || !this.sign &amp;&amp; f1.getSign()) {
                  signInt = -1;
              }
              return new Fraction(signInt * this.numerator * f1.getNumerator(), this.denominator * f1.getDenominator());
          }
  
          public Fraction dividedBy(Fraction f1) {
              int signInt = 1;
              // Either one fraction is negative will make the product fraction negative, but not for both fractions are negative.
              if (this.sign &amp;&amp; !f1.getSign() || !this.sign &amp;&amp; f1.getSign()) {
                  signInt = -1;
              }
              return new Fraction(signInt *this.numerator * f1.getDenominator(), this.denominator * f1.getNumerator());
          }
  
          public boolean equals(Fraction f1) {
          return this.numerator == f1.getNumerator() &amp;&amp; this.denominator == f1.getDenominator() &amp;&amp; this.sign == f1.getSign();
          }
  
          public int getNumerator() {
              return this.numerator;
          }
  
          public int getDenominator() {
              return this.denominator;
          }
  
          public boolean getSign() {
              return this.sign;
          }
  
          public String toString() {
              String signStr = &quot;&quot;;
              String fractionStr = &quot;&quot;;
              if (this.sign) {
                  signStr = &quot;-&quot;;
              }
              if (numerator == denominator) {
                  fractionStr = &quot;1&quot;;
              } else if (denominator == 1) {
                  fractionStr = Integer.toString(numerator);
              } else {
                  fractionStr = numerator + &quot;/&quot; + denominator;
              }
              return signStr + fractionStr;
          }
      }
  
  
  }
  </code></pre>