Monday, March 14, 2011

Word in a Maze

Q: Given a puzzle of letters/ characters e.g.

a e r o p s
b h a r l s
w r i s l o
a s n k t q

Write a function to which this puzzle and a word will be passed to test whether that word exists in the puzzle or not.
e.g. rain and slow will return true. rain is present in the third column and slow in the third row wrapped around.

Algorithm:

Idea is for each element in matrix find if it matches the first character, if it matches then we have to look in 4 directions. If there is match in that direction proceed till we are end of the string. If match return true if not return false. We have to look in all the directions because the string can be in any of 4 directions. Also Math.abs takes care of wrap around (this was my big bug)

Working Java Code:

public class StringFinder {

    enum Direction {
        up, down, left, right
    };

    public static void main(String args[]) {
        char[][] ar = new char[][] { { 'a', 'e', 'r', 'o','p','s' },
                                     { 'b', 'h', 'a', 'r','l','s' },
                                     { 'w', 'r', 'i', 's','l','o' },
                                     { 'a', 's', 'n', 'k','t','q' },
                                     { 'a', 'e', 'r', 'o','p','s' },
                                     { 'b', 'h', 'a', 'r','l','s' },};
        String str = "rain";
        StringFinder sf = new StringFinder();
        System.out.print(sf.stringFinder(ar, str));
    }

    private boolean stringFinder(char[][] ar, String str) {
        int size = ar.length;
        if (str.length() > size + 1)
            return false;
        int k = 0;
        char[] charArray = str.toCharArray();
        for (int i = 0; i < size; i++)
            for (int j = 0; j < size; j++)
                if (ar[i][j] == charArray[k])
                    return isMatch(ar, charArray, i, Math.abs((j + 1) % size),
                            k + 1, Direction.right)
                            || isMatch(ar, charArray, Math.abs((i + 1) % size),
                                    j, k + 1, Direction.down)
                            || isMatch(ar, charArray, Math.abs((i - 1) % size),
                                    j, k + 1, Direction.up)
                            || isMatch(ar, charArray, i,
                                    Math.abs((j - 1) % size), k + 1,
                                    Direction.left);
        return false;
    }

    private boolean isMatch(char[][] ar, char[] charArray, int i, int j, int k,
            Direction dir) {
        int size = ar.length;
        if (k == charArray.length - 1) {
            if (ar[i][j] == charArray[k])
                return true;
            else
                return false;
        }
        if (ar[i][j] == charArray[k]) {
            if (dir == Direction.down)
                i = Math.abs((i + 1) % size);
            else if (dir == Direction.right)
                j = Math.abs((j + 1) % size);
            else if (dir == Direction.left)
                j = Math.abs((j - 1) % size);
            else
                // dir==Direction.up
                i = Math.abs((i - 1) % size);

            return isMatch(ar, charArray, i, j, k + 1, dir);
        }

        return false;
    }

}

No comments: