Download and view my resume (PDF)

Thursday, June 27, 2013

Longest Increasing Sequence (Small Solution)

This code finds the length of the Longest Increasing Sequence through adjacent numbers (including diagonals) in a rectangular grid of integers.
For example:
8 2 4
0 7 1
3 7 9

The path can only connect adjacent locations (you could not connect 8 -> 9), and cannot connect equal numbers (you could not connect 7 -> 7). The longest possible sequence for this example would be of length 5 by tracing the path 0->2->4->7->9 or 1->2->4->7->8.
public class SmallCalcLIS {
 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}};
  System.out.println(longestIncreasingSequence(values));
 }
 
 static private int longestIncreasingSequence(int[][] values) {
  int longestIncreasingSequence = 0;
  for(int row = 0; row < values.length; row++) {
   for(int col = 0; col < values[0].length; col++) {
    if(lisFrom(values, row, col) > longestIncreasingSequence) longestIncreasingSequence = lisFrom(values, row, col);
   }
  }
  return longestIncreasingSequence;
 }
 
 /**
  * This recursive method calculates a 'longest increasing sequence' for a grid from a certain point.
  * It does this by calling itself recursively for points neighboring the given point.
  * 
  * This method is designed for minimum lines of code (for fun), not maximum efficiency. For instance,
  * it makes up to twice as many recursive calls as it needs to.
  */
 static private int lisFrom(int[][] values, int row, int col) {
  int lis = 1;
  if(row-1 >= 0 && row-1 < values.length && col   >= 0 && col   < values[0].length && values[row][col] < values[row-1][col])   if(lisFrom(values, row-1, col)   >= lis) lis = lisFrom(values, row-1, col)   + 1;
  if(row-1 >= 0 && row-1 < values.length && col+1 >= 0 && col+1 < values[0].length && values[row][col] < values[row-1][col+1]) if(lisFrom(values, row-1, col+1) >= lis) lis = lisFrom(values, row-1, col+1) + 1;
  if(row   >= 0 && row   < values.length && col+1 >= 0 && col+1 < values[0].length && values[row][col] < values[row][col+1])   if(lisFrom(values, row,   col+1) >= lis) lis = lisFrom(values, row,   col+1) + 1;
  if(row+1 >= 0 && row+1 < values.length && col+1 >= 0 && col+1 < values[0].length && values[row][col] < values[row+1][col+1]) if(lisFrom(values, row+1, col+1) >= lis) lis = lisFrom(values, row+1, col+1) + 1;
  if(row+1 >= 0 && row+1 < values.length && col   >= 0 && col   < values[0].length && values[row][col] < values[row+1][col])   if(lisFrom(values, row+1, col)   >= lis) lis = lisFrom(values, row+1, col)   + 1;
  if(row+1 >= 0 && row+1 < values.length && col-1 >= 0 && col-1 < values[0].length && values[row][col] < values[row+1][col-1]) if(lisFrom(values, row+1, col-1) >= lis) lis = lisFrom(values, row+1, col-1) + 1;
  if(row   >= 0 && row   < values.length && col-1 >= 0 && col-1 < values[0].length && values[row][col] < values[row][col-1])   if(lisFrom(values, row,   col-1) >= lis) lis = lisFrom(values, row,   col-1) + 1;
  if(row-1 >= 0 && row-1 < values.length && col-1 >= 0 && col-1 < values[0].length && values[row][col] < values[row-1][col-1]) if(lisFrom(values, row-1, col-1) >= lis) lis = lisFrom(values, row-1, col-1) + 1;
  return lis;
 }
}

1 comment: