Download and view my resume (PDF)

Tuesday, June 4, 2013

Longest Increasing Sequence (Big Solution)

This code calculates the Longest Increasing Sequence in a grid of integers. This solution creates a grid of node objects which are aware of their neighbors, able to calculate their L.I.S. by querying their neighbors, and remember their L.I.S. so that it doesn't need to be recalculated later. As explained in the comments, one benefit to the heavyweight infrastructure used here is that doing other calculations on the grid of numbers becomes easier. For instance, printing the L.I.S. path is trivial once the L.I.S. value has been determined.
public class BigCalcLIS {

 public static void main(String[] args) {  
  int[][] values =   {{2, 4, 7, 7, 0, 0},
       {3, 1, 4, 8, 0, 0},
       {4, 0, 9, 0, 0, 0}};

  BigCalcLIS calcLIS = new BigCalcLIS(values);
  calcLIS.longestIncreasingSequence();
 }
 
 int [][] values = null;
 public BigCalcLIS(int[][] values) {
  this.values = values;
 }
 
 public void longestIncreasingSequence() {
  Grid grid = new Grid(values);
  Node node = grid.getNodeWithLongestIncreasingSequence();
  
  System.out.println("Longest increasing sequence: " + node.getLongestIncreasingSequence());
  node.printPath();
 }

 /**
  * Represents an object in a Grid. A Node has eight neighbors, some of which may be null if this Node
  * is on the edge of a Grid. A Node knows how to calculate its own longest increasing path by asking
  * each of its neighbors for its own longest path. In this way, calculating the longest increasing path
  * is a sort of recursive operation upon the Grid.
  */
 private class Node {
  public int value = 0;
  
  public Node n = null;
  public Node ne = null;
  public Node e = null;
  public Node se = null;
  public Node s = null;
  public Node sw = null;
  public Node w = null;
  public Node nw = null;
  
  // a node 'is calculated' if we have already searched neighbors for their longest path
  private boolean isCalculated = false;
  
  // if no neighbor nodes can be connected to then this value is null, otherwise it takes on
  // the neighbor with the longest increasing sequence
  private Node neighborWithLongestIncreasingSequence = null;
  
  public Node(int value) {
   this.value = value;
  }
  
  /**
   * Calculates and returns the longest increasing sequence for this node.
   */
  public int getLongestIncreasingSequence() {
   if(!this.isCalculated) {
    this.neighborWithLongestIncreasingSequence = findNeighborWithLongestIncreasingSequence();
    this.isCalculated = true;
   }
   
   
   return (this.neighborWithLongestIncreasingSequence == null)
    ? 1
    : this.neighborWithLongestIncreasingSequence.getLongestIncreasingSequence() + 1;
  }
  
  public void printPath() {
   System.out.print(value);
   if(this.neighborWithLongestIncreasingSequence != null) {
    System.out.print("->");
    this.neighborWithLongestIncreasingSequence.printPath();
   } else {
    System.out.print("\n");
   }
  }
  
  public String toString() {
   return "{NODE=" + this + " value=" + value +  " n="+n +  " ne="+ne +  " e="+e + " se="+se + " s="+s + " sw="+sw + " w="+w + " nw="+nw + "}";
  }
  
  /**
   * Searches neighbor nodes for one with the longest increasing sequence
   */
  private Node findNeighborWithLongestIncreasingSequence() {
   Node neighborWithLongestIncreasingSequence = null;
   for(Node node : new Node[] { n, ne, e, se, s, sw, w, nw }) {   
    if(this.canConnectTo(node)
     && (neighborWithLongestIncreasingSequence == null
      ||node.getLongestIncreasingSequence() > neighborWithLongestIncreasingSequence.getLongestIncreasingSequence())) {
     neighborWithLongestIncreasingSequence = node;
    }
   }
   return neighborWithLongestIncreasingSequence;
  }
  
  /**
   * Determines whether this node can connect to the given node such as to create an increasing sequence.
   */
  private boolean canConnectTo(Node node) {
   return (node != null) && (node.value > this.value);
  }
 }
 
 /**
  * A Grid comprises a rectangular array of Nodes. A Grid knows how to calculate the longest increasing
  * sequence within its Nodes by asking each Node to calculate its own longest increasing sequence.
  */
 private class Grid {
  private Node[][] nodes = null;
  private boolean isCalculated = false;
  private Node nodeWithLongestIncreasingSequence = null;
  
  public Grid(int[][] values) {
   this.buildGrid(values);
  }
  
  public Node getNodeWithLongestIncreasingSequence() {
   if(!this.isCalculated) {
    this.nodeWithLongestIncreasingSequence = findNodeWithLongestIncreasingSequence();
   }
   
   return this.nodeWithLongestIncreasingSequence;
  }
  
  /**
   * Searches neighbor nodes for one with the longest increasing sequence
   */
  private Node findNodeWithLongestIncreasingSequence() {
   Node nodeWithLongestIncreasingSequence = null;
   for(int row = 0; row < values.length; row++) {
    for(int col = 0; col < values[0].length; col++) {
     if(nodeWithLongestIncreasingSequence == null
      || this.nodes[row][col].getLongestIncreasingSequence() > nodeWithLongestIncreasingSequence.getLongestIncreasingSequence()) {
      nodeWithLongestIncreasingSequence = this.nodes[row][col];
     }
    }
   }
   return nodeWithLongestIncreasingSequence;
  }
  
  /**
   * Clears and rebuilds the grid of Nodes. Each node is connected to each of its neighbors.
   */
  private void buildGrid(int[][] values) {
   this.nodes = new Node[values.length][values[0].length];
   
   // first create all the nodes
   for(int row = 0; row < values.length; row++) {
    for(int col = 0; col < values[0].length; col++) {
     this.nodes[row][col] = new Node(values[row][col]);
    }
   }
   
   // then link each node to its neighbors
   for(int row = 0; row < values.length; row++) {
    for(int col = 0; col < values[0].length; col++) {
     if(row-1 >= 0 && row-1 < values.length && col >= 0 && col < values[0].length)
      this.nodes[row][col].n = this.nodes[row-1][col];
     
     if(row-1 >= 0 && row-1 < values.length && col+1 >= 0 && col+1 < values[0].length)
      this.nodes[row][col].ne = this.nodes[row-1][col+1];
     
     if(row >= 0 && row < values.length && col+1 >= 0 && col+1 < values[0].length)
      this.nodes[row][col].e = this.nodes[row][col+1];
     
     if(row+1 >= 0 && row+1 < values.length && col+1 >= 0 && col+1 < values[0].length)
      this.nodes[row][col].se = this.nodes[row+1][col+1];
     
     if(row+1 >= 0 && row+1 < values.length && col >= 0 && col < values[0].length)
      this.nodes[row][col].s = this.nodes[row+1][col];
     
     if(row+1 >= 0 && row+1 < values.length && col-1 >= 0 && col-1 < values[0].length)
      this.nodes[row][col].sw = this.nodes[row+1][col-1];
     
     if(row >= 0 && row < values.length && col-1 >= 0 && col-1 < values[0].length)
      this.nodes[row][col].w = this.nodes[row][col-1];
     
     if(row-1 >= 0 && row-1 < values.length && col-1 >= 0 && col-1 < values[0].length)
      this.nodes[row][col].nw = this.nodes[row-1][col-1];
    }
   }
  }
 }
}

No comments:

Post a Comment