Google Interview Question Software Engineer / Developers
Country: India
How did you come up with the values for delta i and j arrays ?
static int delta_i[8]={-1, -1, -1, 0, 1, 1, 1, 0};
static int delta_j[8]={1, 0, -1, -1, -1, 0, 1, 1};
One Correction in Code to compare last element of matrix with last element in pattern
OLD Code if(i<0 || i>=m-1 || j<0 || j>=n-1) return false;
New Code if(i<0 || i>m-1 || j<0 || j>n-1) return false;
It is as simple as this
public static void main(String[] args) {
int k = 0;
Point p;
for (int i = 0; i < row; i++)
for (int j = 0; j < column; j++) {
p = new Point(i, j);
System.out.println(hasWord(k, p));
}
}
private static boolean hasWord(int k, Point p) {
if (!isValidPoint(p))
return false;
if (k == B.length)
return true;
if (A[p.x][p.y] == B[k]) {
k++;
if (hasWord(k, p.left()) || hasWord(k, p.right())
|| hasWord(k, p.top()) || hasWord(k, p.bottom())
|| hasWord(k, p.bottomright())
|| hasWord(k, p.bottonleft()) || hasWord(k, p.topleft())
|| hasWord(k, p.topright())) {
System.out.println(p + " has " + B[k - 1]);
return true;
}
}
return false;
}
Put the Pattern in the HashMap with Key as char and value as frequency.
Iterate through the 2D array and if u get the collision decrement the value of that char in the HashMap. After completion just check the HashMap whether it has frequency as all zero if yes we have the pattern else we do not have.
@Free Bird
Just like you are decrementing a HashMap value, you also need to increment it if, on the course of backtracking you found that a particular element was not leading to a solution and should be marked as unused. In that case, the frequency of that character should be incremented by 1.
public class PatternInMatrix
{
static boolean used[][];
public static boolean findPattern(char[][] matrix, int nRow, int nCol, char[] pattern) {
used = new boolean[nRow][nCol];
for (int i = 0; i < nRow; i++)
for (int j = 0; j < nCol; j++)
{
used[i][j] = false;
}
for (int i = 0; i < nRow; i++)
for (int j = 0; j < nCol; j++)
{
if (matrix[i][j] == pattern[0])
if (search(matrix, nRow, nCol, i, j, pattern, 0))
return true;
}
return false;
}
private static boolean search(char[][] matrix, int nRow, int nCol, int row, int col, char[] pattern, int index) {
if (index == pattern.length - 1)
return true;
// check up
if (row-1 >= 0 && !used[row-1][col]) {
if (matrix[row-1][col] == pattern[index + 1]) {
used[row-1][col] = true;
if (search(matrix, nRow, nCol, row-1, col, pattern, index + 1)) {
return true;
}
used[row-1][col] = false;
}
}
// check down
if (row+1 < nRow && !used[row+1][col]) {
if (matrix[row+1][col] == pattern[index + 1]) {
used[row+1][col] = true;
if (search(matrix, nRow, nCol, row+1, col, pattern, index + 1)) {
return true;
}
used[row+1][col] = false;
}
}
// check left
if (col-1 >= 0 && !used[row][col-1]) {
if (matrix[row][col-1] == pattern[index+1]) {
used[row][col-1] = true;
if (search(matrix, nRow, nCol, row, col-1, pattern, index+1)) {
return true;
}
used[row][col-1] = false;
}
}
// check right
if (col+1 < nCol && !used[row][col+1]) {
if (matrix[row][col+1] == pattern[index+1]) {
used[row][col+1] = true;
if (search(matrix, nRow, nCol, row, col+1, pattern, index+1)) {
return true;
}
used[row][col+1] = false;
}
}
// check left up
if (row-1 >= 0 && col-1 >=0 &&!used[row-1][col-1]) {
if (matrix[row-1][col-1] == pattern[index+1]) {
used[row-1][col-1] = true;
if (search(matrix, nRow, nCol, row-1, col-1, pattern, index+1)) {
return true;
}
used[row-1][col-1] = false;
}
}
// check left down
if (row+1 < nRow && col-1 >= 0 && !used[row+1][col-1]) {
if (matrix[row+1][col-1] == pattern[index+1]) {
used[row+1][col-1] = true;
if (search(matrix, nRow, nCol, row+1, col-1, pattern, index+1)) {
return true;
}
used[row+1][col-1] = false;
}
}
// check right up
if (row-1 >= 0 && col+1 < nCol && !used[row-1][col+1]) {
if (matrix[row-1][col+1] == pattern[index+1]) {
used[row-1][col+1] = true;
if (search(matrix, nRow, nCol, row-1, col+1, pattern, index+1)) {
return true;
}
used[row-1][col+1] = false;
}
}
// check right down
if (row+1 < nRow && col+1 < nCol && !used[row+1][col+1]) {
if (matrix[row+1][col+1] == pattern[index+1]) {
used[row+1][col+1] = true;
if (search(matrix, nRow, nCol, row+1, col+1, pattern, index+1)) {
return true;
}
used[row+1][col+1] = false;
}
}
return false;
}
public static void main(String[] args)
{
char[][] m = {{'A','C','P','R','C'},
{'X','S','O','P','C'},
{'V','O','V','N','I'},
{'W','G','F','M','N'},
{'Q','A','T','I','T'}};
String pattern = "MICROSOFT";
System.out.println(findPattern(m, 5, 5, pattern.toCharArray()));
}
}
Using the Divide & Conquer + Dynamic Programming approach
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;
public class FindWordSolution {
// given array
private static final char array[][] = {
{'A','C','P','R','C'},
{'X','S','O','P','C'},
{'V','O','V','N','I'},
{'W','G','F','M','N'},
{'Q','A','T','F','T'}
};
// Stores hash for <string, different paths that build this string>
Hashtable<String, List<Path>> hash = new Hashtable<String, List<Path>>();
public FindWordSolution()
{
buildInitialHash();
}
// Builds hash for <letter, positions list>
public void buildInitialHash()
{
// Scan
for(int i = 0; i < array[0].length; i++)
{
for(int j = 0; j < array.length; j++)
{
List list = hash.get(String.valueOf(array[i][j]));
if(list != null)
{
list.add(new Path(new Pair(i, j)));
}
else
{
list = new ArrayList<Pair>();
list.add(new Path(new Pair(i, j)));
hash.put(String.valueOf(array[i][j]), list);
}
}
}
}
// recursive function that follows divide and conquer
public List<Path> figureOut(String word)
{
// Using hashed results like in Dynamic Programming
if(hash.containsKey(word))
{
return hash.get(word);
}
String left = word.substring(0, word.length() / 2);
String right = word.substring(word.length() / 2, word.length());
List<Path> list = new ArrayList<Path>();
List<Path> leftPaths = figureOut(left);
List<Path> rightPaths = figureOut(right);
if(leftPaths != null && rightPaths != null)
{
for(Path leftPath : leftPaths)
{
for(Path rightPath : rightPaths)
{
if(Path.canBeAppended(leftPath, rightPath))
{
Path path = new Path();
for(Pair pair : leftPath.list)
{
path.list.add(pair);
}
for(Pair pair : rightPath.list)
{
path.list.add(pair);
}
list.add(path);
}
}
}
}
hash.put(word, list);
return list;
}
public static void main(String[] args)
{
FindWordSolution solution = new FindWordSolution();
List<Path> solutionPaths = solution.figureOut("MICROSOFT");
System.out.println(solutionPaths.size() + " solution(s)");
for(Path solutionPath : solutionPaths)
{
System.out.println(solutionPath.toString());
}
}
}
class Pair
{
int i, j;
public Pair(int i, int j)
{
this.i = i;
this.j = j;
}
public String toString()
{
return "(" + i + ", " + j + ")";
}
}
class Path
{
List<Pair> list = new ArrayList<Pair>();
public Path(Pair pair)
{
list.add(pair);
}
public Path(){}
public static boolean canBeAppended(Path path1, Path path2)
{
if(path1.list.size() == 0 || path2.list.size() == 0)
return true;
Pair pair1 = path1.list.get(path1.list.size() - 1);
Pair pair2 = path2.list.get(0);
if(Math.abs(pair1.i - pair2.i) <= 1 && Math.abs(pair1.j - pair2.j) <= 1)
{
return true;
}
return false;
}
public String toString()
{
StringBuffer stringBuffer = new StringBuffer();
for(Pair pair : list)
{
stringBuffer.append(pair + " -> ");
}
return stringBuffer.toString();
}
}
#include <iostream>
#include <string>
#include<stdio.h>
using namespace std;
int Check(int , int , int ) ;
char b[10];
char a[6][6]={{'A','C','P','R','C'},
{'X','S','O','P','C'},
{'V','O','V','N','I'},
{'W','G','F','M','N'},
{'Q','A','T','I','T'}} ;
int main()
{
char c='y';
while(c=='y'||c=='Y')
{ int j,k,flag1;
flag1=0;
cout<<"Array:\n";
for(j=0;j<5;j++)
{ cout<<"\n";
for(k=0;k<5;k++)
{cout<<a[j][k];}
}
cout<<"\nEnter the pattern to be found:\n";
cin>>b;
for(j=0;j<5;j++)
for(k=0;k<5;k++)
{
if(b[0]==a[j][k])
{ flag1=Check(j,k,1);
if(flag1==1)
{
break;
}
}
if(flag1==1)
{
break;
}
}
if(flag1==1)
cout<<"\n\nPattern present";
else
cout<<"\n\nPattern not present";
cout<<"\nWant to look for more??(y/n)";
cin>>c;
}
return(0);
}
int Check(int x, int y, int r)
{
int flag2=2;
cout<<"\nPassed values"<<x<<y<<r;
for(int p=x-1;(p<x+3);p++)
for (int q=y-1;(q<y+3);q++)
{
if((p<0 || q<0)||(p==x && q==y))
{
continue;
}
if (b[r]==a[p][q])
{
if (b[r+1]=='\0')
{
return(1);
}
else
{
flag2=Check(p,q,++r);
if(flag2==0)
continue;
else
{
return(1);
}
}
}
}
}
break the word microsoft into the alphabets.Store them into a hashtable.
key value
m 1
i 1
c 1
r 1
o 1
s 1
f 1
t 1
Now use :
boolean findPattern(Char a[i][j],int i, int j, HashMap<Character,Integer> hashmap)
{
if((i== -1 || j== -1) || (i == size || j == size))
{
return false;
}
if(isTraversed[i][j])
{
return false;
}
if(hashmap.isEmpty())
{
return true;
}
Integer count = hashmap.get(a[i][j]);
if(count != null)
{
int value = count.intValue();
value--;
hashmap.remove(a[i][j]);
if(value != 0)
hashmap.put(a[i][j], value);
}
return findPattern(a,i+1, j, hashmap) ||
findPattern(a,i, j+1, hashmap) ||
findPattern(a,i-1, j, hashmap) ||
findPattern(a,i, j-1, hashmap) ||
findPattern(a,i+1, j+1, hashmap) ||
findPattern(a,i-1, j-1, hashmap) ||
findPattern(a,i+1, j-1, hashmap) ||
findPattern(a,i-1, j+1, hashmap);
}
boolean isPatternFound(Char a[i][j],int i, int j, HashMap<Character,Integer> hashmap)
{
return findPattern(a,0,0,hashmap);
}
This is what I came up with. I think the only thing it doesn't support is the "dont use the same char twice":
public class Find2D {
private static final char array[][] = {
{'A','C','P','R','C'},
{'X','S','O','P','C'},
{'V','O','V','N','I'},
{'W','G','F','M','N'},
{'Q','A','T','I','T'}
};
public static final void main(String[] args)
{
System.out.println(find("MICROSOFT"));
}
/**
*
* 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.
*
* @param key
* @return
*/
public static int find(String key)
{
char keyArray[] = key.toCharArray();
for(int i = 0; i < array.length; i++)
{
for(int j = 0; j < array[i].length; j++)
{
int ret = checkAround(array, key.toCharArray(), i, j, -1, -1, 0);
if(ret == 1)
{
return ret;
}
}
}
return 0;
}
public static int checkAround(char[][] array, char[] search, int x, int y, int prevX, int prevY, int pos)
{
for(int i = -1; i <= 1; i++)
{
for(int j = -1; j <= 1; j++)
{
int newX = x+i;
int newY = y+j;
if(!(i == 0 && j == 0)
&&
(newX >= 0 && newY >= 0 && newX < array.length && newY < array[newX].length )
&&
!(newX == prevX && newY == prevY)
)
{
System.out.println(array[newX][newY] + " == " + search[pos] + "?");
if(array[newX][newY] == search[pos])
{
System.out.println("TRUE");
if((pos == search.length-1) || (checkAround(array, search, newX, newY, x, y, pos+1) == 1))
{
return 1;
}
}
}
}
}
return 0;
}
}
This is an iterative approach.
for(i=0 to ROW_LENGTH){
for(j=0 to COL_LENGTH){
if(pattern contains MATRIX[i][j])
remove MATRIX[i][j] from pattern
}
}
if pattern length=0 return 1
else return 0
public int found (char[][]s, String p,int row,int column){
for(int i=0;i<row;i++){
for(int j=0;j<column;j++){
if( p.indexOf(Character.toLowerCase(s[i][j]))!=-1){
p=p.replace(Character.toString(Character.toLowerCase(s[i][j])),"");
System.out.println(p);
}
}
}
if(p.length()==0) return 1;
else return 0;
}
Need a more proper explanation of the question. Did the example mean that it needs to be found out whether "Microsoft" can be formed from the letters present in the 2D array or not?
No it means it should find out weather neighbor element can form the MICROSOFT from given matrix or not...!!!
public boolean findPattern(String pattern, char[][] m) {
boolean isFound = false;
char[] pat = pattern.toCharArray();
int count = 0;
for (int i = 0; i < m.length && !isFound; i++) {
int length = m[i].length;
for (int j = 0; j < length && !isFound; j++) {
if (pat[count] == m[i][j]) {
Hashtable<Integer, Boolean> locations = new Hashtable<Integer, Boolean>();
locations.put(i * length + j, true);
isFound = find(pat, count + 1, locations, m, i, j);
}
}
}
return isFound;
}
public boolean find(char[] pat, int p, Hashtable<Integer, Boolean> loc,
char[][] m, int r, int c) {
boolean isFound = false;
if (p == pat.length) {
isFound = true;
} else {
for (int i = r - 1; i <= r + 1 && !isFound; i++) {
if (i >= 0 && i < m.length) {
int length = m[i].length;
for (int j = c - 1; j <= c + 1 && !isFound; j++) {
if (j >= 0 && j < length) {
if (!loc.containsKey(i * length + j) && m[i][j] == pat[p]) {
Hashtable<Integer, Boolean> locCopy = new Hashtable<Integer, Boolean>(loc);
locCopy.put(i * length + j, true);
isFound = find(pat, p + 1, locCopy, m, i, j);
}
}
}
}
}
}
return isFound;
}
package com.algorithms;
import java.util.LinkedList;
public class GooglePattern {
static class MyInteger{
private int value;
public MyInteger(int value){
this.value=value;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
public static int findPattern(char[][] matrix,char[] pattern){
MyInteger found=new MyInteger(0);
find(new int[]{1,1},matrix,pattern,found);
return found.getValue();
}
private static void find(int[] header, char[][] matrix, char[] pattern,MyInteger found) {
int currX=header[0];
int currY=header[1];
int nextY=currY;
int nextX=currX+1;
if(currY==matrix.length-1)
return ;
if(nextX==matrix[0].length-1){
nextY=currY+1;
nextX=1;
}
char[] chars = {matrix[currY][currX+1],matrix[currY][currX],matrix[currY][currX-1]
,matrix[currY+1][currX-1],matrix[currY+1][currX],matrix[currY+1][currX+1],
matrix[currY-1][currX-1],matrix[currY-1][currX],matrix[currY-1][currX+1]
};
String toCheck=new String(chars);
LinkedList<String> list=new LinkedList<String>();
getAllCombo("",toCheck,list);
for (String el : list){
if (el.equals(new String(pattern))){
found.setValue(1);
}
}
if (found.getValue()!=1)
find(new int[]{nextX,nextY},matrix,pattern,found);
}
private static void getAllCombo(String beg, String end,
LinkedList<String> list) {
if (end.length()<=0){
list.add(beg+end);
}else{
for (int i=0 ; i<end.length();i++){
String newString=end.substring(0,i)+end.substring(i+1);
getAllCombo(beg+end.charAt(i),newString,list);
}
}
}
public static void main(String[] args) {
char[][] matrix={{'A','C','P','R','C'},
{'X','S','O','P','C'},
{'V','O','V','N','I'},
{'W','G','F','M','N'},
{'Q','A','T','I','T'}};
char[] pattern={'M','I','C','R','O','S','O','F','T'};
System.out.println(findPattern(matrix, pattern));
}
}
Pseudocode:
char[][] input is a class variable.
for(int i = 0; i < height; i++)
for(int j = 0; j < width; j++)
if(input[i][j] == pattern[0])
{
used[i][j] = true;
if(Recurse(used, pattern.substring(1))
{
return true;
}
else
{
used[i][j] = false;
}
}
return false;
Recurse(char[][] used, string pattern)
{
if(pattern.Length == 0)
{
return true;
}
for(int i = 0; i < 8; i++)
{
char c = GetNeighbour(i);
if(c == input[0])
{
MarkNeighbourUsed(ref used, i);
if(Recurse(used, input.substr(1)))
{
return true;
}
else
{
MarkNeighbourUnused(i)
}
}
}
return false;
}
This would by my solution too. The recursion makes the back-tracking easy :-)
I'd just explicitly state a few properties of the GetNeighbour(i) function:
1) It must return a never-matching char if the neighbour i is already used.
2) It must return a never-matching char if the neighbour i is invalid for the cell. The function
must be "topology-aware": the 2D array is not a torus, so corner cells have only 3 neighbours and edge cells only 5.
Approach is following
1) First think of 2-D array as 1-D array with appropriate indexes
$matrix = array(array('A','C','P','R','C'), //0 1 2 3 4
array('X','S','O','P','C'), //5 6 7 8 9
array('V','O','V','N','I'), //10 11 12 13 14
array('W','G','F','M','N'), //15 16 17 18 19
array('Q','A','T','I','T'));//20 21 22 23 24
2) now create arrays containing searched word's characters indexes.
3) Now check if these consecutive arrays are connected.
4) Filter out the connected components and come up with final array.
5) if all array indexes have some value then word is found.
working code as below.
<?php
$matrix = array(array('A','C','P','R','C'), //0 1 2 3 4
array('X','S','O','P','C'), //5 6 7 8 9
array('V','O','V','N','I'), //10 11 12 13 14
array('W','G','F','M','N'), //15 16 17 18 19
array('Q','A','T','I','T'));//20 21 22 23 24
$word = "QGVPC";
$check = checkWordInMatrix($matrix, $word);
function checkWordInMatrix($matrix, $word) {
$charIndexes = array();
$wordLen = strlen($word);
$charMap = array();
for ($i = 0; $i < $wordLen; $i++) {
$charIndexes = array();
if (!$charMap[$word[$i]]) {
$charMap[$word[$i]] = array();
}
$charMap[$word[$i]][] = $i;
}
$h = count($matrix);
$w = count($matrix[0]);
$t = $h * $w;
for ($i = 0; $i < $t; $i++) {
$pair = getRowColumnFromIndex($i, $w, $h);
$row = $pair[0];
$col = $pair[1];
$entry = $matrix[$row][$col];
if ($charMap[$entry]) {
for ($k = 0; $k < count($charMap[$entry]); $k++) {
$charIndexes[$charMap[$entry][$k]][] = $i;
}
}
}
for ($i = 0; $i < $wordLen; $i++) {
if (count($charIndexes[$i]) == 0) {
return false;
}
}
for ($i = 0; $i < $wordLen - 1; $i++) {
for ($j = 0; $j < count($charIndexes[$i]); $j++) {
if (!areLevelsConnected(array($charIndexes[$i][$j]), $charIndexes[$i + 1], $w, $h)) {
unset($charIndexes[$i][$j]);
}
}
}
$matches = 0;
for ($i = 0; $i < $wordLen; $i++) {
if (count($charIndexes[$i]) > 0) {
$matches++;
}
}
return ($matches == $wordLen);
}
function areLevelsConnected($level1, $level2, $w, $h) {
for ($i = 0; $i < count($level1); $i++) {
for ($j = 0; $j < count($level2); $j++) {
if (isConnected($level1[$i], $level2[$j], $w, $h)) {
return true;
}
}
}
return false;
}
function getRowColumnFromIndex($i, $w, $h) {
$arr = array();
$arr[] = (int) ($i / $w);
$arr[] = $i % $w;
return $arr;
}
function isConnected($index1, $index2, $w, $h) {
$pair1 = getRowColumnFromIndex($index1, $w, $h);
$pair2 = getRowColumnFromIndex($index2, $w, $h);
$row1 = $pair1[0];
$col1 = $pair1[1];
$row2 = $pair2[0];
$col2 = $pair2[1];
$dist = sqrt(pow(($row2 - $row1), 2) + pow(($col2 - $col1), 2));
return ($dist == 1) || ($dist == sqrt(2));
}
?>
a = [ [ 1, 2, 3, 4], [5, 6, 7, 8]]
def part(a, r, l, pat):
if (len(pat)==0):
return 1
if (a[r][l] == pat[0]):
out = 0
pat_ = [pat[i] for i in range(1,len(pat))]
out += part(a, max(0,r-1), max(0,l), pat_)
out += part(a, max(0,r), max(0,l-1), pat_)
out += part(a, min(1,r+1), min(0,l), pat_)
out += part(a, min(1,r), min(3,l+1), pat_)
if (out>0):
return 1
else:
return 0
else:
return 0
print(part(a, 1, 2, [7, 3, 2]))
#include <stdio.h>
int findPattern(char *str)
{
char arr[][5] = {{'A','C','P','R','C'},
{'X','S','O','P','C'},
{'V','O','V','N','I'},
{'W','G','F','M','N'},
{'Q','A','T','I','T'}};
int i,j;
for(i = 0; i < 5; i++)
{
for(j = 0; j < 5; j++)
{
if(arr[i][j] == *str)
{
//printf("POSITION(%d, %d) \n", i, j);
if(matchChar(arr, i, j, str+1))
{
printf("POSITION(%d, %d) %c\n", i, j, *str);
return 1;
}
}
}
}
printf("\nPattern was not found \n\n");
return 0;
}
int matchChar(char arr[][5], int i, int j, char *ch)
{
if(*ch)
{
int m , n;
int foundmatch = 0;
if(j -1 >= 0)
{
if(arr[i][j -1] == *ch)
{
m = i;
n = j-1;
if(matchChar(arr, m, n, ch + 1))
{
printf("POSITION(%d, %d) %c\n", m, n, *ch);
return 1;
}
}
if(i -1 >= 0)
{
if(arr[i -1][j -1] == *ch)
{
m = i-1;
n = j-1;
if(matchChar(arr, m, n, ch + 1))
{
printf("POSITION(%d, %d) %c\n", m, n, *ch);
return 1;
}
}
}
if(i + 1 <= 4)
{
if(arr[i + 1][j -1] == *ch)
{
m = i+1;
n = j-1;
if(matchChar(arr, m, n, ch + 1))
{
printf("POSITION(%d, %d) %c\n", m, n, *ch);
return 1;
}
}
}
}
if(j + 1 <= 4)
{
// printf("J+1 POSITION(%d, %d) \n", i, j);
if(arr[i][j + 1] == *ch)
{
m = i;
n = j+1;
if(matchChar(arr, m, n, ch + 1))
{
printf("POSITION(%d, %d) %c\n", m, n, *ch);
return 1;
}
}
if(i -1 >= 0)
{
if(arr[i -1][j + 1] == *ch)
{
m = i-1;
n = j+1;
if(matchChar(arr, m, n, ch + 1))
{
printf("POSITION(%d, %d) %c\n", m, n, *ch);
return 1;
}
}
}
if(i + 1 <= 4)
{
if(arr[i + 1][j + 1] == *ch)
{
m = i+1;
n = j+1;
if(matchChar(arr, m, n, ch + 1))
{
printf("POSITION(%d, %d) %c\n", m, n, *ch);
return 1;
}
}
}
}
if(i + 1 <= 4)
{
if(arr[i + 1][j] == *ch)
{
m = i+1;
n = j;
if(matchChar(arr, m, n, ch + 1))
{
printf("POSITION(%d, %d) %c\n", m, n, *ch);
return 1;
}
}
}
if(i -1 >= 0)
{
if(arr[i -1][j] == *ch)
{
m = i-1;
n = j-1;
if(matchChar(arr, m, n, ch + 1))
{
printf("POSITION(%d, %d) %c\n", m, n, *ch);
return 1;
}
}
}
return 0;
}
else
return 1;
}
int main(int argc, char *argv[])
{
char *str = "MICROSOFT";
findPattern(str);
system("PAUSE");
return 0;
}
public bool FindMatch(char[][] input, string target, int index)
{
for (int row = 0; row < input.GetLength(0); row++)
{
for (int col = 0; col < input[row].GetLength(0); col++)
{
if (FindMatch(input, target, 0, row, col))
{
return true;
}
}
}
return false;
}
public bool FindMatch(char[][] input, string target, int index, int row, int col)
{
List<Point> available = new List<Point>()
{
new Point(row-1, col+1),
new Point(row-1, col),
new Point(row-1, col-1),
new Point(row, col+1),
new Point(row, col-1),
new Point(row+1, col+1),
new Point(row+1, col),
new Point(row+1, col-1)
};
for (int i = 0; i < 8; i++)
{
bool temp = FindChar(input, target[index], available[i].X, available[i].Y);
if (temp)
{
input[available[i].X][available[i].Y] = ' ';
if (index + 1== target.Length)
{
return true;
}
bool match = FindMatch(input, target, index + 1, available[i].X, available[i].Y);
if (match)
{
return true;
}
else
{
input[available[i].X][available[i].Y] = target[index];
}
}
}
return false;
}
private bool FindChar(char[][] input, char target, int row, int col)
{
if (row>=0 && row<input.GetLength(0) && col>=0 && col<input[row].GetLength(0))
{
return target == input[row][col];
}
return false;
}
You can test this with:
Google1 target = new Google1(); // TODO: Initialize to an appropriate value
char[][] input = {
new char[] {'A','C','P','R','C'},
new char[]{'X','S','O','P','C'},
new char[]{'V','O','V','N','I'},
new char[]{'W','G','F','M','N'},
new char[]{'Q','A','T','I','T'}
}; // TODO: Initialize to an appropriate value
string target1 = "MICROSOFT"; // TODO: Initialize to an appropriate value
int index = 0; // TODO: Initialize to an appropriate value
bool expected = true; // TODO: Initialize to an appropriate value
bool actual;
actual = target.FindMatch(input, target1, index);
Console.WriteLine(actual);
C# code.
Use recursion, check the provide C++ code
static bool findPattern(char *str, int len, char** arr, int n, int m)
{
if (len <= 0)
return 0;
int i = 0, j = 0;
for (i = 0;i<5;i++)
for(j = 0;j<5;j++)
{
if (arr[i][j] == str[0])
{
cout << "found the first char\n";
return findPattern(str,len,0,arr,n,m,i,j);
}
}
return 0;
}
static bool findPattern(char *str, int len, int k, char** arr, int n, int m, int i, int j)
{
if (k < 0 || k >= len || i < 0 || j < 0 || i >= n || j >= m)
return 0;
if (arr[i][j] == str[k])
{
if (k == len-1)
return 1;
int sum = 0;
for (int r = -1; r <= 1; r++)
for (int t = -1; t <= 1; t++)
if (r!=0 || t!=0)
{
sum += (int)findPattern(str,len,k+1,arr,n,m,i+r,j+t);
}
return (sum>0);
}
return 0;
}
#include<stdio.h>
#include<stdlib.h>
char arr[5][5]={
{'A','C','P','R','C'},
{'X','S','O','P','C'},
{'V','O','V','N','I'},
{'W','G','F','M','N'},
{'Q','A','T','I','T'}
};
char* pattern="MICROSOFT";
int x,y;
int check_pattern(int i,int j)
{
int mx,my;
int len;
char *p;
int broken;
int found;
int i1;
char** store=(char**)calloc(x,sizeof(char*));
for(i1=0;i1<x;i1++)
{
store[i1]=(char*)calloc(y,sizeof(char));
}
store[i][j]=1;
for(len=0,p=pattern;*p++!='\0';len++);
p=pattern;broken=0;
len--;
while(len--&&!broken)
{
found=0;
char toMatch=*++p;
for(mx=-1;mx<=1;mx++)
{
for(my=-1;my<=1;my++)
{
if((i+mx)<0||(i+mx)>=x)
break;
if((j+my<0)||(j+my)>=y)
continue;
if(store[i+mx][j+my])
continue;
if(toMatch==arr[i+mx][j+my])
{
i=i+mx;j=j+my;
store[i][j]=1;
found=1;
printf("%c %d\n",arr[i][j],found);
break;
}
}
if(found)
break;
}
if(!found)
broken=1;
}
for(i1=0;i1<x;i1++)
{
free(store[i1]);
}
return broken?-1:0;
}
int main()
{
y=sizeof(arr[0])/sizeof(arr[0][0]);
x=sizeof(arr)/(y*sizeof(char));
int i,j;
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
{
if(arr[i][j]==*pattern)
{
if(0==check_pattern(i,j))
{
printf("pattern found\n");
return 0;
}
}
}
}
printf("pattern not found\n");
return -1;
}
My brute force searching solution.
#include <stdio.h>
#define M 100
#define N 50
char str[M + 1][M + 1];
char pat[N + 1];
int lp;
char flag[M + 1][M + 1];
int n, m;
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int do_dfs(int x, int y, int idx) {
int i, tx, ty;
if (idx == lp - 1) {
return 1;
}
else {
for (i = 0; i < 8; i++) {
tx = (x + dx[i] + n) % n;
ty = (y + dy[i] + m) % m;
if ((!flag[tx][ty]) && (str[tx][ty] == pat[idx + 1])) {
flag[tx][ty] = 1;
if (do_dfs(tx, ty, idx + 1)) {
return 1;
}
else {
flag[tx][ty] = 0;
}
}
}
}
return 0;
}
int is_matching()
{
int x, y, i, j;
for (x = 0; x < n; x++) {
for (y = 0; y < m; y++) {
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
flag[i][j] = 0;
}
}
if (str[x][y] == pat[0]) {
flag[x][y] = 1;
if (do_dfs(x, y, 0)) {
return 1;
}
}
}
}
return 0;
}
int main()
{
int i;
n = 5, m = 5;
str[0][0] = 'a', str[0][1] = 'c', str[0][2] = 'p', str[0][3] = 'r', str[0][4] = 'c';
str[1][0] = 'x', str[1][1] = 's', str[1][2] = 'o', str[1][3] = 'p', str[1][4] = 'c';
str[2][0] = 'v', str[2][1] = 'o', str[2][2] = 'v', str[2][3] = 'n', str[2][4] = 'i';
str[3][0] = 'w', str[3][1] = 'g', str[3][2] = 'f', str[3][3] = 'm', str[3][4] = 'n';
str[4][0] = 'q', str[4][1] = 'a', str[4][2] = 't', str[4][3] = 'i', str[4][4] = 't';
gets(pat);
lp = strlen(pat);
printf("%d\n", is_matching());
return 0;
}
Please check out this
public class PatternMathc {
static boolean travasel[][];
public static boolean findPattern(char[][] arr,int[] cRows, int[] cColumns,int intRow, int intCol,char[] pattern)
{
travasel = new boolean[intRow][intCol];
for(int i = 0; i< intRow; i++)
{
for(int j = 0; j< intCol; j++)
{
travasel[i][j] = false;
}
}
for(int i = 0; i< intRow; i++)
{
for(int j = 0; j< intCol; j++)
{
if(arr[i][j] == pattern[0])
{
if(checkPattern(arr,cRows,cColumns,i,j,pattern,0))
return true;
}
}
}
return false;
}
public static boolean checkPattern(char[][] m,int[] cRows, int[] cColumns,int tRows,int tCol, char[] pattern,int index)
{
if (index == pattern.length - 1)
return true;
for(int i =0; i < cRows.length; i++)
{
if(tRows+cRows[i] >= 0 && tRows+cRows[i] <= m.length -1 && tCol+cColumns[i] >= 0 && tCol+cColumns[i] <= m.length -1)
{
if(m[tRows+cRows[i]][tCol+cColumns[i]] == pattern[index +1])
{
travasel[tRows+cRows[i]][tCol+cColumns[i]] = true;
if(checkPattern(m,cRows,cColumns,tRows+cRows[i],tCol+cColumns[i],pattern,index + 1))
{
return true;
}
travasel[tRows+cRows[i]][tCol+cColumns[i]] = false;
}
}
}
return false;
}
public static void main(String[] args) {
int[] incRows = {-1,1,0,0,-1,-1,1,1};
int[] incColumns = {0,0,1,-1,-1,1,-1,1};
char[][] m = {{'A','C','P','R','C'},
{'X','S','O','P','C'},
{'V','O','V','N','I'},
{'W','G','F','M','N'},
{'Q','A','T','I','T'}};
String pattern = "ACPOVFTAQWVXAC";
System.out.println(findPattern(m,incRows,incColumns,m.length,m.length,pattern.toCharArray()));
}
}
check this out
public class PatternMathc {
static boolean travasel[][];
public static boolean findPattern(char[][] arr,int[] cRows, int[] cColumns,int intRow, int intCol,char[] pattern)
{
travasel = new boolean[intRow][intCol];
for(int i = 0; i< intRow; i++)
{
for(int j = 0; j< intCol; j++)
{
travasel[i][j] = false;
}
}
for(int i = 0; i< intRow; i++)
{
for(int j = 0; j< intCol; j++)
{
if(arr[i][j] == pattern[0])
{
if(checkPattern(arr,cRows,cColumns,i,j,pattern,0))
return true;
}
}
}
return false;
}
public static boolean checkPattern(char[][] m,int[] cRows, int[] cColumns,int tRows,int tCol, char[] pattern,int index)
{
if (index == pattern.length - 1)
return true;
for(int i =0; i < cRows.length; i++)
{
if(tRows+cRows[i] >= 0 && tRows+cRows[i] <= m.length -1 && tCol+cColumns[i] >= 0 && tCol+cColumns[i] <= m.length -1)
{
if(m[tRows+cRows[i]][tCol+cColumns[i]] == pattern[index +1])
{
travasel[tRows+cRows[i]][tCol+cColumns[i]] = true;
if(checkPattern(m,cRows,cColumns,tRows+cRows[i],tCol+cColumns[i],pattern,index + 1))
{
return true;
}
travasel[tRows+cRows[i]][tCol+cColumns[i]] = false;
}
}
}
return false;
}
public static void main(String[] args) {
int[] incRows = {-1,1,0,0,-1,-1,1,1};
int[] incColumns = {0,0,1,-1,-1,1,-1,1};
char[][] m = {{'A','C','P','R','C'},
{'X','S','O','P','C'},
{'V','O','V','N','I'},
{'W','G','F','M','N'},
{'Q','A','T','I','T'}};
String pattern = "ACPOVFTAQWVXAC";
System.out.println(findPattern(m,incRows,incColumns,m.length,m.length,pattern.toCharArray()));
}
}
#include<stdio.h>
#include<conio.h>
int main()
{
char a[][5]={{'A','C','P','R','C'},
{'X','S','O','P','C'},
{'V','O','V','N','I'},
{'W','G','F','M','N'},
{'Q','A','T','I','T'}} ;
int b[26]={0},i,j;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
b[a[i][j]-65]++;
}
}
char str[20];
int flag=0;
for(i=0;i<26;i++)
printf("%d ",b[i]);
printf("\n enter the string");
scanf("%c",str);
for(i=0;str[i]!='\0';i++)
{
if(b[str[i]-65]>0)
{
b[str[i]-65]--;
flag=1;
continue;
}
else{
flag=0;
break;
}
}
printf("\n after");
for(i=0;i<26;i++)
printf("%d ",b[i]);
if(flag==1)
printf("\n yes");
else
printf("\n NO");
getch();
return 0;
}
#include<stdio.h>
#include<conio.h>
int main()
{
char a[][5]={{'A','C','P','R','C'},
{'X','S','O','P','C'},
{'V','O','V','N','I'},
{'W','G','F','M','N'},
{'Q','A','T','I','T'}} ;
int b[26]={0},i,j;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
b[a[i][j]-65]++;
}
}
char str[20];
int flag=0;
for(i=0;i<26;i++)
printf("%d ",b[i]);
printf("\n enter the string");
scanf("%c",str);
for(i=0;str[i]!='\0';i++)
{
if(b[str[i]-65]>0)
{
b[str[i]-65]--;
flag=1;
continue;
}
else{
flag=0;
break;
}
}
printf("\n after");
for(i=0;i<26;i++)
printf("%d ",b[i]);
if(flag==1)
printf("\n yes");
else
printf("\n NO");
getch();
return 0;
}
public class PatternIn2DArray {
public static boolean findPattern(char[][] array, char[] pattern) {
int[][] visited = new int[array.length][array[0].length];
for (int row = 0; row < array.length; row++) {
for (int col = 0; col < array[row].length; col++) {
if (matches(array, row, col, pattern, 0, visited)) {
return true;
}
}
}
return false;
}
private static boolean matches(char[][] array, int row, int col, char[] pattern, int index, int[][] visited) {
if (visited[row][col] == 1 || array[row][col] != pattern[index]) {
return false;
}
visited[row][col] = 1;
if (index == pattern.length - 1) {
return true;
}
boolean matches = (row - 1 >= 0 && col - 1 >= 0 && matches(array, row - 1, col - 1, pattern, index + 1, visited))
|| (row - 1 >= 0 && matches(array, row - 1, col, pattern, index + 1, visited))
|| (row - 1 >= 0 && col + 1 < array[0].length && matches(array, row - 1, col + 1, pattern, index + 1, visited))
|| (col - 1 >= 0 && matches(array, row, col - 1, pattern, index + 1, visited))
|| (col + 1 < array[0].length && matches(array, row, col + 1, pattern, index + 1, visited))
|| (row + 1 < array.length && col - 1 >= 0 && matches(array, row + 1, col - 1, pattern, index + 1, visited))
|| (row + 1 < array.length && matches(array, row + 1, col, pattern, index + 1, visited))
|| (row + 1 < array.length && col + 1 < array[0].length && matches(array, row + 1, col + 1, pattern, index + 1, visited));
if (!matches) {
visited[row][col] = 0;
return false;
}
return true;
}
public static void main(String args[]) {
char[][] array = {
{'A', 'C', 'P', 'R', 'C'},
{'X', 'S', 'O', 'P', 'C'},
{'V', 'O', 'V', 'N', 'I'},
{'W', 'G', 'F', 'M', 'N'},
{'Q', 'A', 'T', 'I', 'T'}
};
String pattern = "MICROSOFT";
System.out.println(findPattern(array, pattern.toCharArray()));
}
}
public class PatternIn2DArray {
public static boolean findPattern(char[][] array, char[] pattern) {
int[][] visited = new int[array.length][array[0].length];
for (int row = 0; row < array.length; row++) {
for (int col = 0; col < array[row].length; col++) {
if (matches(array, row, col, pattern, 0, visited)) {
return true;
}
}
}
return false;
}
private static boolean matches(char[][] array, int row, int col, char[] pattern, int index, int[][] visited) {
if (visited[row][col] == 1 || array[row][col] != pattern[index]) {
return false;
}
visited[row][col] = 1;
if (index == pattern.length - 1) {
return true;
}
boolean matches = (row - 1 >= 0 && col - 1 >= 0 && matches(array, row - 1, col - 1, pattern, index + 1, visited))
|| (row - 1 >= 0 && matches(array, row - 1, col, pattern, index + 1, visited))
|| (row - 1 >= 0 && col + 1 < array[0].length && matches(array, row - 1, col + 1, pattern, index + 1, visited))
|| (col - 1 >= 0 && matches(array, row, col - 1, pattern, index + 1, visited))
|| (col + 1 < array[0].length && matches(array, row, col + 1, pattern, index + 1, visited))
|| (row + 1 < array.length && col - 1 >= 0 && matches(array, row + 1, col - 1, pattern, index + 1, visited))
|| (row + 1 < array.length && matches(array, row + 1, col, pattern, index + 1, visited))
|| (row + 1 < array.length && col + 1 < array[0].length && matches(array, row + 1, col + 1, pattern, index + 1, visited));
if (!matches) {
visited[row][col] = 0;
return false;
}
return true;
}
public static void main(String args[]) {
char[][] array = {
{'A', 'C', 'P', 'R', 'C'},
{'X', 'S', 'O', 'P', 'C'},
{'V', 'O', 'V', 'N', 'I'},
{'W', 'G', 'F', 'M', 'N'},
{'Q', 'A', 'T', 'I', 'T'}
};
String pattern = "MICROSOFT";
System.out.println(findPattern(array, pattern.toCharArray()));
}
}
public class PatternIn2DArray {
public static boolean findPattern(char[][] array, char[] pattern) {
int[][] visited = new int[array.length][array[0].length];
for (int row = 0; row < array.length; row++) {
for (int col = 0; col < array[row].length; col++) {
if (matches(array, row, col, pattern, 0, visited)) {
return true;
}
}
}
return false;
}
private static boolean matches(char[][] array, int row, int col, char[] pattern, int index, int[][] visited) {
if (row < 0 || col < 0 || row >= array.length || col >= array[0].length
|| visited[row][col] == 1 || array[row][col] != pattern[index]) {
return false;
}
visited[row][col] = 1;
if (index == pattern.length - 1) {
return true;
}
boolean matches = matches(array, row - 1, col - 1, pattern, index + 1, visited)
|| matches(array, row - 1, col, pattern, index + 1, visited)
|| matches(array, row - 1, col + 1, pattern, index + 1, visited)
|| matches(array, row, col - 1, pattern, index + 1, visited)
|| matches(array, row, col + 1, pattern, index + 1, visited)
|| matches(array, row + 1, col - 1, pattern, index + 1, visited)
|| matches(array, row + 1, col, pattern, index + 1, visited)
|| matches(array, row + 1, col + 1, pattern, index + 1, visited);
if (!matches) {
visited[row][col] = 0;
return false;
}
return true;
}
public static void main(String args[]) {
char[][] array = {
{'A', 'C', 'P', 'R', 'C'},
{'X', 'S', 'O', 'P', 'C'},
{'V', 'O', 'V', 'N', 'I'},
{'W', 'G', 'F', 'M', 'N'},
{'Q', 'A', 'T', 'I', 'T'}
};
String pattern = "MICROSOFT";
System.out.println(findPattern(array, pattern.toCharArray()));
}
}
package junk;
import java.util.HashMap;
public class GridMatch {
static int pInd = 0; // current index on pattern, ie pattern.charAt(pInd) is to be searched next.
static HashMap<String, Integer> hm=null;
static int delta_i[]={ -1, -1, -1, 0, 0, 1, 1, 1 };
static int delta_j[]={ -1, 0, 1, -1, 1, -1, 0, 1 };
static char[][] grid = { { 'A', 'C', 'P', 'R', 'C' },
{ 'X', 'S', 'O', 'P', 'C' },
{ 'V', 'O', 'V', 'N', 'I' },
{ 'W', 'G', 'F', 'M', 'N' },
{ 'Q', 'A', 'T', 'I', 'T' } };
static HashMap<String, Integer> createMap(String s){
HashMap<String, Integer> hm = new HashMap<String, Integer>();
for(int i=0;i<s.length();i++){
if(hm.get(String.valueOf(s.charAt(i))) != null)
hm.put(String.valueOf(s.charAt(i)), hm.get(String.valueOf(s.charAt(i)))+1);
else{
hm.put(String.valueOf(s.charAt(i)), 1);
}
}
return hm;
}
static boolean isAllowed(int row, int col){
if (row >= grid.length || row < 0 || col >= grid[0].length || col < 0)
return false;
else return true;
}
static boolean searchGrid(int row, int col, String pat, boolean[][] visited, int pInd){
// this char matched now remove one occurrence of it, mark relevant cell visited and move on to the next char in pattern .
if (hm.get(String.valueOf(grid[row][col])) > 1)
hm.put(String.valueOf(grid[row][col]), hm.get(String.valueOf(grid[row][col])) - 1);
else
hm.remove(String.valueOf(grid[row][col]));
visited[row][col] = true;
pInd++;
if(hm.size()==0) // every character matched for this recursion stack
return true;
for(int dir=0;dir<8;dir++){
int k=0; int row_i = row+delta_i[dir]; int col_j = col+delta_j[dir];
if(!isAllowed(row_i, col_j) || visited[row_i][col_j])
continue;
String currChar = String.valueOf(grid[row_i][col_j]);
// if currChar is present, check recursively further
if (grid[row_i][col_j] == pat.charAt(pInd)) {
if (searchGrid(row_i, col_j, pat, visited,pInd))
return true;
}
}
// backtracking visited, pInd and hm's state by adding removed char and by default return false,
visited[row][col] = false;
pInd--;
if (hm.get(String.valueOf(grid[row][col])) !=null)
hm.put(String.valueOf(grid[row][col]), hm.get(String.valueOf(grid[row][col])) + 1);
else
hm.put(String.valueOf(grid[row][col]),1);
return false;
}
public static void main(String[] args) {
int count=0;
String pattern = "MICROSOFT";
// String pattern = "Oa";
hm = createMap(pattern);
boolean[][] visited = new boolean[grid.length][grid[0].length];
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
count++;
if(grid[i][j]==pattern.charAt(pInd))
if(searchGrid(i,j,pattern,visited,pInd)){
System.out.println("Present");
return;
}
}
}
System.out.println("Not Present "+count);
}
}
public class PatternMatch {
static boolean travasel[][];
public static boolean findPattern(char[][] arr,int[] cRows, int[] cColumns,int intRow, int intCol,char[] pattern)
{
travasel = new boolean[intRow][intCol];
for(int i = 0; i< intRow; i++)
{
for(int j = 0; j< intCol; j++)
{
travasel[i][j] = false;
}
}
for(int i = 0; i< intRow; i++)
{
for(int j = 0; j< intCol; j++)
{
if(arr[i][j] == pattern[0])
{
if(checkPattern(arr,cRows,cColumns,i,j,pattern,0))
return true;
}
}
}
return false;
}
public static boolean checkPattern(char[][] m,int[] cRows, int[] cColumns,int tRows,int tCol, char[] pattern,int index)
{
if (index == pattern.length - 1)
return true;
for(int i =0; i < cRows.length; i++)
{
if(tRows+cRows[i] >= 0 && tRows+cRows[i] <= m.length -1 && tCol+cColumns[i] >= 0 && tCol+cColumns[i] <= m.length -1 && !(travasel[tRows+cRows[i]][tCol+cColumns[i]]))
{
if(m[tRows+cRows[i]][tCol+cColumns[i]] == pattern[index +1])
{
travasel[tRows+cRows[i]][tCol+cColumns[i]] = true;
if(checkPattern(m,cRows,cColumns,tRows+cRows[i],tCol+cColumns[i],pattern,index + 1))
{
return true;
}
travasel[tRows+cRows[i]][tCol+cColumns[i]] = false;
}
}
}
return false;
}
public static void main(String[] args) {
int[] incRows = {-1,1,0,0,-1,-1,1,1};
int[] incColumns = {0,0,1,-1,-1,1,-1,1};
char[][] m = {{'A','C','P','P','E'},
{'X','S','O','R','C'},
{'V','O','V','N','I'},
{'W','G','F','M','N'},
{'Q','A','T','I','T'}};
String pattern = "MICROSOFT";
System.out.println(findPattern(m,incRows,incColumns,m.length,m.length,pattern.toCharArray()));
}
}
#include <stdio.h>
char board[8][8] = {
{'R', 'N', 'B', 'Q', 'K', 'B', 'N', 'R'},
{'P', 'P', 'P', 'P', 'P', 'P', 'P', 'P'},
{' ', '.', ' ', '.', ' ', '.', ' ', '.'},
{'.', ' ', '.', ' ', '.', ' ', '.', ' '},
{' ', '.', ' ', '.', ' ', '.', ' ', '.'},
{'.', ' ', '.', ' ', '.', ' ', '.', ' '},
{'p', 'p', 'p', 'p', 'p', 'p', 'p', 'p'},
{'r', 'n', 'b', 'q', 'k', 'b', 'n', 'r'}
};
int turn = 0;
void print_board() {
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
printf("%c ", board[i][j]);
}
printf("\n");
}
}
void make_move() {
// TODO: implement move logic
}
void check_win() {
// TODO: implement win condition logic
}
void check_assassin_move() {
// TODO: implement assassin move logic
}
int main() {
printf("Welcome to Assassin Chess!\n");
print_board();
while (!check_win()) {
printf("Player %d's turn:\n", turn + 1);
make_move();
check_assassin_move();
print_board();
turn = (turn + 1) % 2;
}
printf("Game over! Player %d wins!\n", turn + 1);
return 0;
}
This is an iterative approach.
for(i=0 to ROW_LENGTH){
for(j=0 to COL_LENGTH){
if(pattern contains MATRIX[i][j])
remove MATRIX[i][j] from pattern
}
}
if pattern length=0 return 1
else return 0
public int found (char[][]s, String p,int row,int column){
for(int i=0;i<row;i++){
for(int j=0;j<column;j++){
if( p.indexOf(Character.toLowerCase(s[i][j]))!=-1){
p=p.replace(Character.toString(Character.toLowerCase(s[i][j])),"");
System.out.println(p);
}
}
}
if(p.length()==0) return 1;
else return 0;
}
Here is the recursive brute force solution:
public class PatternSearch {
public static boolean patternFind(char[][] array, String pattern, int rowLen, int colLen, int[][] matrix, int prevMatchIndex_i, int prevMatchIndex_j){
boolean result = false;
//Nothing to match
if(pattern == null || pattern.length() == 0){
return true;
}
int i = prevMatchIndex_i;
int j = prevMatchIndex_j;
char charToMatch = pattern.charAt(0);
if(i > 0) {
//check upper character
if(matrix[i-1][j] == 0 && array[i-1][j] == charToMatch){
matrix[i-1][j] = 1;
result = patternFind(array, pattern.substring(1), rowLen, colLen, matrix, i-1, j);
if(result == true){
return result;
}
matrix[i-1][j] = 0;
}
if(j > 0){
//Check left upper corner
if(matrix[i-1][j-1] == 0 && array[i-1][j-1] == charToMatch){
matrix[i-1][j-1] = 1;
result = patternFind(array, pattern.substring(1), rowLen, colLen, matrix, i-1, j-1);
if(result == true){
return result;
}
matrix[i-1][j-1] = 0;
}
}
}
if(j > 0){
//check left character
if(matrix[i][j-1] == 0 && array[i][j-1] == charToMatch){
matrix[i][j-1] = 1;
result = patternFind(array, pattern.substring(1), rowLen, colLen, matrix, i, j-1);
if(result == true){
return result;
}
matrix[i][j-1] = 0;
}
}
if(i+1 < rowLen) {
//check bottom character
if(matrix[i+1][j] == 0 && array[i+1][j] == charToMatch){
matrix[i+1][j] = 1;
result = patternFind(array, pattern.substring(1), rowLen, colLen, matrix, i+1, j);
if(result == true){
return result;
}
matrix[i+1][j] = 0;
}
if(j > 0) {
//check left bottom corner
if(matrix[i+1][j-1] == 0 && array[i+1][j-1] == charToMatch){
matrix[i+1][j-1] = 1;
result = patternFind(array, pattern.substring(1), rowLen, colLen, matrix, i+1, j-1);
if(result == true){
return result;
}
matrix[i+1][j-1] = 0;
}
}
}
if(j+1 < colLen) {
if(i > 0){
//check right upper corner
if(matrix[i-1][j+1] == 0 && array[i-1][j+1] == charToMatch){
matrix[i-1][j+1] = 1;
result = patternFind(array, pattern.substring(1), rowLen, colLen, matrix, i-1, j+1);
if(result == true){
return result;
}
matrix[i-1][j+1] = 0;
}
}
//check right character
if(matrix[i][j+1] == 0 && array[i][j+1] == charToMatch){
matrix[i][j+1] = 1;
result = patternFind(array, pattern.substring(1), rowLen, colLen, matrix, i, j+1);
if(result == true){
return result;
}
matrix[i][j+1] = 0;
}
if(i+1 < rowLen) {
//check right bottom corner
if(matrix[i+1][j+1] == 0 && array[i+1][j+1] == charToMatch){
matrix[i+1][j+1] = 1;
result = patternFind(array, pattern.substring(1), rowLen, colLen, matrix, i+1, j+1);
if(result == true){
return result;
}
matrix[i+1][j+1] = 0;
}
}
}
return result;
}
public static void main(String[] argv){
char[][] array = { {'A', 'C', 'P', 'R', 'C'},
{'X', 'S', 'O', 'P', 'C'},
{'V', 'O', 'V', 'N', 'I'},
{'W', 'G', 'F', 'M', 'N'},
{'Q', 'A', 'T', 'I', 'T'} };
String pattern = "MICROSOFT";
char chToMatch = pattern.charAt(0);
int rowLen = 5;
int colLen = 5;
int[][] matrix = new int[rowLen][colLen];
boolean result = false;
for(int i=0; i<rowLen; i++){
for(int j=0; j<colLen; j++){
if(array[i][j] == chToMatch){
matrix[i][j] = 1;
result = patternFind(array, pattern.substring(1), rowLen, colLen, matrix, i, j);
if(result == true){
break;
}
matrix[i][j] = 0;
}
}
if(result == true){
break;
}
}
System.out.println("Pattern FOUND: " + result);
}
}
- jzhu May 19, 2012boolean pattern_match(char **martix, int m, int n, char *pattern) { boolean **visited = new boolean*[n]; boolean found=false; int i, j; for(i=0; i<m; i++) { visited = new boolean[n]; for(j=0; j<n; j++) visited[i][j]=false; } for(i=0; i<m; i++) for(j=0; j<n; j++) { if(find_pattern(matrix, i, j, m, n, pattern, visited)==true) { found = true; break; } } if(found) break; } for(i=0; i<m; i++) delete visited[i]; delete visited; return found; } boolean find_pattern(char **matrix, int i, int j, int m, int n, char *pattern, boolean visited) { static int delta_i[8]={-1, -1, -1, 0, 1, 1, 1, 0}; static int delta_j[8]={1, 0, -1, -1, -1, 0, 1, 1}; int k; char *p=pattern; if(*p == '\0') return true; if(i<0 || i>=m-1 || j<0 || j>=n-1) return false; if(matrix[i][j] != *p || visited[i][j]==true) return false; visited[i][j]=true; for(k=0; k<8; k++) { if(find_pattern(matrix, i+delta_i[k], j+delta_j[k], m, n, p+1, visited)==true) return true; } return (visited[i][j]=false); }