Saturday, January 2, 2016

Find if a word is present in a matrix

Find if all the characters of a given word is present in a two dimensional matrix if the matrix can be traversed as described in the image below:

Java Program:

public class MatrixTraversalPrograms {
 public boolean driverForIsWordPresent(char[] in, char[][] matrix) {
  boolean wordFound = false;
  for(int i=0;i<matrix.length;i++) {
   for(int j=0;j<matrix[i].length;j++) {
    if(in[0] == matrix[i][j]) {
     wordFound = isWordPresent(in, matrix, i, j, 0);
    }
    if(wordFound) {
     break;
    }
   }
   if(wordFound) {
    break;
   }
  }
  return wordFound;
 }
 
 public boolean isWordPresent(char[] in, char[][] matrix, int i, int j, int index) {
  if(index == in.length - 1) {
   return true;
  }
  else {
   boolean complete = false;
   //Top Right
   if(i-1 >= 0 && j+1 < matrix[i].length && matrix[i-1][j+1] == in[index+1]) {
    complete = isWordPresent(in, matrix, i-1, j+1, index + 1);
    if(complete) {
     return true;
    }
   }
   //Right
   if(!complete && i >= 0 && i < matrix.length && j+1 < matrix[i].length && matrix[i][j+1] == in[index+1]) {
    complete = isWordPresent(in, matrix, i, j+1, index + 1);
    if(complete) {
     return true;
    }
   }
   //Bottom Right
   if(!complete && i+1 < matrix.length && j+1 < matrix[i+1].length && matrix[i+1][j+1] == in[index+1]) {
    complete = isWordPresent(in, matrix, i+1, j+1, index + 1);
    if(complete) {
     return true;
    }
   }
   //Bottom
   if(!complete && i+1 < matrix.length && j >= 0 && j < matrix[i+1].length && matrix[i+1][j] == in[index+1]) {
    complete = isWordPresent(in, matrix, i+1, j, index + 1);
    if(complete) {
     return true;
    }
   }
   //Bottom Left
   if(!complete && i+1 < matrix.length && j-1 >= 0 && matrix[i+1][j-1] == in[index+1]) {
    complete = isWordPresent(in, matrix, i+1, j-1, index + 1);
    if(complete) {
     return true;
    }
   }
   //Left
   if(!complete && i>=0 && i < matrix.length && j-1 >= 0 && matrix[i][j-1] == in[index+1]) {
    complete = isWordPresent(in, matrix, i, j-1, index + 1);
    if(complete) {
     return true;
    }
   }
   //Top Left
   if(!complete && i-1 >= 0 && j-1 >= 0 && matrix[i-1][j-1] == in[index+1]) {
    complete = isWordPresent(in, matrix, i-1, j-1, index + 1);
    if(complete) {
     return true;
    }
   }
   //Top
   if(!complete && i-1 >= 0 && j >= 0 && j < matrix[i-1].length && matrix[i-1][j] == in[index+1]) {
    complete = isWordPresent(in, matrix, i-1, j, index + 1);
    if(complete) {
     return true;
    }
   }
   return false;
  }
 }
}
 
Unit Tests:
 
import static org.junit.Assert.*;

import org.junit.Test;

import junit.framework.Assert;

public class MatrixTraversalTests {
 
 MatrixTraversalPrograms programInstance = new MatrixTraversalPrograms();
 @Test
 public void testTwoCharacterPresent() {
  char[] in = {'a','b'};
  char[][] matrix = new char[][]{ 
   {'x','b'},
   {'a','x'}
   };
  Assert.assertTrue(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testTwoOnePresent() {
  char[] in = {'a','b'};
  char[][] matrix = new char[][]{ 
   {'x','c'},
   {'a','x'}
   };
  Assert.assertFalse(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testTwoBiggerMatrix() {
  char[] in = {'a','b'};
  char[][] matrix = new char[][]{ 
   {'x','x','x'},
   {'x','b','x'},
   {'a','x','x'}
   };
  Assert.assertTrue(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testTwoRepeated() {
  char[] in = {'a','b'};
  char[][] matrix = new char[][]{ 
   {'x','x','x'},
   {'x','b','x'},
   {'a','b','x'}
   };
  Assert.assertTrue(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testLarge() {
  char[] in = {'M','i','c','r','o','s','o','f','t'};
  char[][] matrix = new char[][]{
   {'x','x','x','x','x','x'},
   {'x','r','o','x','x','x'},
   {'x','x','c','s','x','x'},
   {'x','x','i','o','f','x'},
   {'x','M','x','x','f','x'},
   {'x','x','x','t','x','x'}
   };
  Assert.assertTrue(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testLargePartialPresent() {
  char[] in = {'M','i','c','r','o','s','o','f','t'};
  char[][] matrix = new char[][]{
   {'x','x','x','x','x','x'},
   {'x','r','o','x','x','x'},
   {'x','x','c','s','x','x'},
   {'x','x','i','o','f','x'},
   {'x','M','x','x','f','x'},
   {'x','x','x','x','x','x'}
   };
  Assert.assertFalse(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testOneCharacterPresent() {
  char[] in = {'a'};
  char[][] matrix = new char[][]{
   {'a'}
   };
  Assert.assertTrue(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testOneCharacterAbsent() {
  char[] in = {'a'};
  char[][] matrix = new char[][]{
   {'b'}
   };
  Assert.assertFalse(programInstance.driverForIsWordPresent(in, matrix));
 }
}