GridGame Algorithm Code – Finding a String from Characters in a 2D Grid

Problem Definition – Assume you are given a 2 dimension grid – with each cell in the grid as a character from the ASCII set. Find out an Algorithm and code to find out if a String is present in the Grid by starting from any point in the Grid and moving along any direction in the grid – Up/Down/Left/Right/Diagonally. Loop Around – at the edges is not allowed

Example

If the input matrix is

[a, b, c]

[d, e, f]
[g, h, i]
[j, k, l]
[m, n, o]

and the Input string is – cbdhln

The given string is Present in the grid

While the string – cej

is NOT present in the Grid

Approach

Recursive and brute force keeping the path list of all available paths ( list of coordinates – which are neighbours)

Create a HashMap of each Char in the Grid and the locations it is present in.

So the Key for the HashMap is the Character and the Value – List of all Coordinates(Point) where the char occurs in the grid

Take each char from the input string and compute if this char can be a neighbour of the prev char and if so – keep a list of all such paths – where each path is a list of all Coordinates.

If the string exhausts and we get a path – we return true

If any char from the input string is not present in the HashMap means – the string cannot be formed from the Grid characters.

Otherwise we continue to the next character in the string and keep looking if the current character from the string is neighbour of the last element in each Path.

I am sure there are better algorithms for this – which I will think of more and code as I get more insights.

I have used Point DataStructure from awt java library.

Input to the code is like this

java GridGame 5 3 a b c d e f g h i j k l m n o cbdhln

1st Param – Number of Rows in Grid

2nd Param – Number of Columns in the Grid

3rd Param….(2nd to last Param ) — all the characters in the Grid

The last parameter – is the string to be found

Here is the code in Java

* I have done no argument level parameter testing in the code – since the code assumes that the inputs are all correct.

import java.util.*;
import java.awt.Point;

public class GridGame
{
public static void main(String[] args)
{
System.out.println(args[0]);
System.out.println(args[1]);
GridGame game = new GridGame(Integer.valueOf(args[0]), Integer.valueOf(args[1]), args);
System.out.println(“The given string is ”  + game.isPresent() + ” in the grid”);
}

char[][] inputGrid;
int row, width;
String matchString;

private String isPresent()
{
if (findMatch())
return “Present”;
else
return ” NOT Present”;
}

public GridGame(int r, int w, String[] data)
{
row = r; width = w;
inputGrid = new char[row][];
for(int i=0;i<row;i++)
inputGrid[i] = new char[width];

int index = 2;
for(int i=0;i<row;i++)
for(int j=0;j<width;j++)
inputGrid[i][j] = data[index++].charAt(0);

for(int i=0;i<row;i++)
System.out.println(Arrays.toString(inputGrid[i]));

matchString = data[index];

System.out.println(matchString);
}

HashMap<Character, List<Point>> inverseMap = new LinkedHashMap<Character, List<Point>>();
int currentIndex = 0;
public boolean findMatch()
{
populateInverseMap();
//        printInverseMap();
return findMatch(matchString, currentIndex);
}

private List<Point> lookupHashMap(char x)
{
return inverseMap.get(x);
}

List<List<Point>> currentNeighbourList = new ArrayList<List<Point>>();

private void showCurrentNeighbourList()
{
System.out.println(“Size of currentNeighbourList = ” + currentNeighbourList.size());
for(List<Point> p : currentNeighbourList)
System.out.println(Arrays.toString(p.toArray()));
}

private boolean findMatch(String s, int index)
{
//        System.out.println(index);
//        showCurrentNeighbourList();
if ( index == (s.length()))    return true;
List<Point> currentPoints = lookupHashMap(s.charAt(index));
if (currentPoints == null)        return false;
if (index == 0 )
{
for(Point p : currentPoints)
{
List<Point> l = new ArrayList<Point>();
l.add(p);
currentNeighbourList.add(l);
}
}
else
{
List<List<Point>> updatedNeighbourList = new ArrayList<List<Point>>();
updateNeighbourPoints(updatedNeighbourList, currentPoints);
if (updatedNeighbourList.size() == 0)    // no new neighbours added means no path
return false;
currentNeighbourList = updatedNeighbourList;
}

return findMatch(s, ++index);
}

private void updateNeighbourPoints(List<List<Point>> updateList, List<Point> p)
{
for(List<Point> pList : currentNeighbourList)
{
// Get Last Point in the List
Point p1 = pList.get(pList.size()-1);
for(Point pTest : p)
{
if ( isNeighbour(p1, pTest))
{
List<Point> newList = deepClone(pList);
newList.add(pTest);
updateList.add(newList);
}
}
}

}

private List<Point> deepClone(List<Point> pList)
{
List<Point> newList = new ArrayList<Point>();
for(Point p : pList)
newList.add(new Point(p.x, p.y));
return newList;
}

private void populateInverseMap()
{
for(int i=0;i<row;i++)
{
for(int j=0;j<width;j++)
{
Point p = new Point(i,j);
Character current = inputGrid[i][j];
List<Point> currentLookUpValue = inverseMap.get(current);
if ( currentLookUpValue == null )
{
List<Point> lPoint = new ArrayList<Point>();
lPoint.add(p);
inverseMap.put(current, lPoint);
}
else
{
currentLookUpValue.add(p);
}
}
}
}

private void printInverseMap()
{
for(Character c : inverseMap.keySet())
{
List<Point> p = inverseMap.get(c);
System.out.print(c + ”  “);
printPointList(p);
}
}

private void printPointList(List<Point> pointList)
{
for(Point p : pointList)
System.out.print(p + “,  “);
System.out.println();
}

private boolean isNeighbour(Point p1, Point p2)
{
int p1X = p1.x;
int p1Y = p1.y;

int p2X = p2.x;
int p2Y = p2.y;

if (( Math.abs(p1X-p2X) == 1) && ( Math.abs(p1Y-p2Y) == 1)) return true;    // diagonal test
if (( Math.abs(p1X-p2X) == 1) && ( Math.abs(p1Y-p2Y) == 0)) return true;    // adjacent
if (( Math.abs(p1X-p2X) == 0) && ( Math.abs(p1Y-p2Y) == 1)) return true;    // adjacent

return false;
}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s