Pattern matching in a two dimensional matrix

Problem:
You are given a 2D array of characters and a character pattern. WAP to find if pattern is present in 2D array. Pattern can be in any way (all 8 neighbors to be considered) but you can’t use same character twice while matching. Return 1 if match is found, 0 if not.
Java Program:

public class Matrix {
 private static boolean[][] visited;
 private char[][] grid = {{'a','i','b'},
        {'m','b','c'},
        {'g','r','i'},
        {'o','o','t'},
        {'s','f','m'}};
 private String searchString = "microsoft";
 public static void main(String[] args) {
  Matrix gridObject = new Matrix();
  gridObject.initialize(gridObject.grid.length, gridObject.grid[0].length);
  boolean result = false;
  for (int i = 0; i < gridObject.grid.length; i++) {
   for(int j = 0; j < gridObject.grid[i].length; j++) {
    result = gridObject.traverseAndFind(gridObject.grid, i, j, gridObject.searchString, 0);
    if(result) {
     break;
    }
   }
   if(result) {
    break;
   }
  }
  if(result) {
   System.out.println("The string is present in the grid");
  }
  else {
   System.out.println("The string is not present in the grid");
  }
 }
 //Function to do all the primary initialization.
 public void initialize(int x, int y) {
  visited = new boolean[x][y];
 }
 
 public boolean traverseAndFind(char[][] inputGrid, int r, int c, String inputString, int index) {
  if(index == inputString.length()) {
   return true;
  }
  else if(r >= 0 && r < inputGrid.length && c >= 0 && c < inputGrid[r].length 
    && !visited[r][c] && inputGrid[r][c] == inputString.charAt(index)) {
   visited[r][c] = true;
   return (traverseAndFind(inputGrid, r, c + 1, inputString, index + 1)) ||
   traverseAndFind(inputGrid, r + 1, c + 1, inputString, index + 1) ||
   traverseAndFind(inputGrid, r + 1, c, inputString, index + 1) ||
   traverseAndFind(inputGrid, r + 1, c - 1, inputString, index + 1) ||
   traverseAndFind(inputGrid, r, c - 1, inputString, index + 1) ||
   traverseAndFind(inputGrid, r - 1, c - 1, inputString, index + 1) ||
   traverseAndFind(inputGrid, r - 1, c, inputString, index + 1) ||
   traverseAndFind(inputGrid, r - 1, c + 1, inputString, index + 1);
  }
  else if(r >= 0 && r < inputGrid.length && c >= 0 && c < inputGrid[r].length) {
   visited[r][c] = false;
  }
  return false;
 }
}

[Fox and Rabbit Problem]: How many rabbits can the fox eat

Problem:
Given a grid, the coordinates of a fox and the coordinates of the rabbits, find out the number of rabbits that the fox can eat.
Condition:
The fox can only eat rabbits which are in its own row, own column or in any of the diagonals.
Example configuration:



Java Code

import java.util.ArrayList;
import java.util.List;

class Coordinate {
 Integer x;
 Integer y;
 public int getX() {
  return x;
 }
 public void setX(int x) {
  this.x = x;
 }
 public int getY() {
  return y;
 }
 public void setY(int y) {
  this.y = y;
 }
 Coordinate(int x, int y) {
  this.x = x;
  this.y = y;
 }
 public String toString() {
  return "(" + this.x.toString() + "," + this.y.toString() + ").";
 }
}

public class Fox {
 private static final String prefixEatString = "Fox can eat the rabbit at: ";
 private static final String prefixCannotEatString = "Fox cannot eat the rabbit at: ";
 private static final String prefixTotalEatableString = "In all the fox can eat ";
 private static final String suffixTotalEatableString = " rabbits.";
 public static void main(String[] args) {
  Coordinate foxCoordinates = new Coordinate(0,0);
  List rabbitCoordinates = new ArrayList();
  //Initialize the coordinates of the rabbits.
  for (int i =-2; i <= 2; i++) {
   for (int j =-2; j <= 2; j++) {
    if(foxCoordinates.getX() == i && foxCoordinates.getY() == j) {
     continue;
    }
    rabbitCoordinates.add(new Coordinate(i, j));
   }
  }
  int foodCount = 0;
  for (int i=0; i<rabbitCoordinates.size(); i++) {
   int diffX = foxCoordinates.getX() - rabbitCoordinates.get(i).getX();
   int diffY = foxCoordinates.getY() - rabbitCoordinates.get(i).getY();
   if (diffX == 0) {
    foodCount++;
    System.out.println(prefixEatString + rabbitCoordinates.get(i).toString());
   }
   else if (diffY == 0) {
    foodCount++;
    System.out.println(prefixEatString + rabbitCoordinates.get(i).toString());
   }
   else if (diffY/diffX == 1 || diffY/diffX == -1) {
    foodCount++;
    System.out.println(prefixEatString + rabbitCoordinates.get(i).toString());
   }
   else {
    System.out.println(prefixCannotEatString + rabbitCoordinates.get(i).toString());
   }
  }
  System.out.println(prefixTotalEatableString + foodCount + suffixTotalEatableString);
 }
}
Output:
Fox can eat the rabbit at: (-2,-2).
Fox cannot eat the rabbit at: (-2,-1).
Fox can eat the rabbit at: (-2,0).
Fox cannot eat the rabbit at: (-2,1).
Fox can eat the rabbit at: (-2,2).
Fox cannot eat the rabbit at: (-1,-2).
Fox can eat the rabbit at: (-1,-1).
Fox can eat the rabbit at: (-1,0).
Fox can eat the rabbit at: (-1,1).
Fox cannot eat the rabbit at: (-1,2).
Fox can eat the rabbit at: (0,-2).
Fox can eat the rabbit at: (0,-1).
Fox can eat the rabbit at: (0,1).
Fox can eat the rabbit at: (0,2).
Fox cannot eat the rabbit at: (1,-2).
Fox can eat the rabbit at: (1,-1).
Fox can eat the rabbit at: (1,0).
Fox can eat the rabbit at: (1,1).
Fox cannot eat the rabbit at: (1,2).
Fox can eat the rabbit at: (2,-2).
Fox cannot eat the rabbit at: (2,-1).
Fox can eat the rabbit at: (2,0).
Fox cannot eat the rabbit at: (2,1).
Fox can eat the rabbit at: (2,2).
In all the fox can eat 16 rabbits.

Recursive program to find the number of ways a particular amount can be obtained using a given set of Currency values.

public class Coins {
 private static int count = 0;
 public static void main(String[] args) {
  int[][] currencyList = {{5,10,20},{0,0,0}};
  //The first row contains the list of the currency values available.
  //The second row contains the frequency of each currency value.
  //The number of columns in both the rows should be the same.
  //Else an index-out-of-bounds exception will happen.
  int sum=0;
  int amount = 20;
  int index=0;
  computeCombinations(currencyList, sum, amount, index);
  System.out.println("Total possible combinations: "+ Coins.count);
 }

 public static void computeCombinations(int[][] currencyList, int sum, int amount, int index) {
  if(index >= currencyList[0].length) {
   return;
  }
  else {
   for(int i=0; i<=(amount/currencyList[0][index]);i++) {
    currencyList[1][index]=i;
    sum+=currencyList[0][index]*currencyList[1][index];
    if(sum == amount) {
     count++;
     for(int j=0;j <=index; j++) {
                                                if(currencyList[1][j] != 0) {
                                                        System.out.print(currencyList[0][j] + "-->" + currencyList[1][j] + " ");
      }
     }
     System.out.println();
    }
    else {
     computeCombinations(currencyList, sum, amount, index + 1);
     sum-=currencyList[0][index]*currencyList[1][index];
    }
   }
  }
 }
}
Output:
20-->1 
10-->2 
5-->2 10-->1 
5-->4 
Total possible combinations: 4