Google Code Jam - WordPath

Spirit — Mon, 19 Dec 2005 08:36:00 GMT

- Implementation

public class WordPath {
    public int countPaths(String[] grid, String find) {
        int length = grid.length + 2;

        //convert "grid" from String to char matrix
        char[][] charGrid = new char[length][length];
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (i == 0 || i == length - 1 || j == 0 || j == length - 1)
                    charGrid[i][j] = '0';
                else
                    charGrid[i][j] = grid[i - 1].charAt(j - 1);
            }
        }

        //convert "find" from String to char array
        char[] charFind = new char[find.length()];
        for (int k = 0; k < find.length(); k++)
            charFind[k] = find.charAt(k);

        //use three dimensions "degree" to hold the in-degree of the vertex of graph
        int[][][] degree = new int[length][length][find.length()];

        // k=0
        for (int i = 0; i < length; i++)
            for (int j = 0; j < length; j++) {
                degree[i][j][0] = ((charGrid[i][j] == charFind[0]) ? 1 : 0);
            }

        // fill the degree
        for (int k = 1; k < find.length(); k++) {
            for (int i = 0; i < length; i++)
                for (int j = 0; j < length; j++) {
                    if (charGrid[i][j] != charFind[k])
                        degree[i][j][k] = 0;
                    else {
                        degree[i][j][k] = degree[i - 1][j - 1][k - 1] + degree[i - 1][j][k - 1]
                                + degree[i - 1][j + 1][k - 1] + degree[i + 1][j - 1][k - 1]
                                + degree[i + 1][j][k - 1] + degree[i + 1][j + 1][k - 1]
                                + degree[i][j - 1][k - 1] + degree[i][j + 1][k - 1];

                    }

                }
        }

        //calculate the sum
        int sum = 0;
        for (int i = 0; i < length; i++)
            for (int j = 0; j < length; j++) {
                sum += degree[i][j][find.length() - 1];
                if (sum > 1000000000) {
                    return -1;
                }
            }
        return sum;
    }
}

- TestCase

public class WordPathTest extends TestCase {
    public void testCountPaths() {
        WordPath wordPath = new WordPath();
        assertEquals(2, wordPath.countPaths(new String[] { "ABC", "FED", "GAI" }, "ABCDEA"));
        assertEquals(0, wordPath.countPaths(new String[] { "ABC", "DEF", "GHI" }, "ABCD"));
        assertEquals(108, wordPath.countPaths(new String[] { "AA", "AA" }, "AAAA"));
        assertEquals(56448, wordPath.countPaths(new String[] { "ABABA", "BABAB", "ABABA", "BABAB", "ABABA" },
                "ABABABBA"));
        assertEquals(-1, wordPath.countPaths(new String[] { "AAAAA", "AAAAA", "AAAAA", "AAAAA", "AAAAA" },
                "AAAAAAAAAAA"));
        assertEquals(0, wordPath.countPaths(new String[] { "AB", "CD" }, "AA"));
    }
}

This testcase finished after 0.015 seconds on my pc.

http://forum.javaeye.com/viewtopic.php?p=106316#106316

Spirit 2005-12-19 16:36 发表评论

Google Code Jam - SkipStones的一种递归算法

Spirit — Thu, 15 Dec 2005 05:29:00 GMT

public class SkipStones {
    private String water = "X";

    public int maxDistance(String water) {
        this.water = water;
        int max = 0;
        int sum = 0;
        for (int initial = 1; initial < water.length() + 1; initial++) {
            sum = bounce(0, initial);
            max = (sum > max ? sum : max);
        }
        return max;
    }

    private int bounce(int startDistance, int bounceDistance) {
        if (bounceDistance == 0)
            return startDistance;

        if ((startDistance + bounceDistance) > water.length())
            return -1;

        if (water.charAt(startDistance + bounceDistance - 1) == 'X')
            return startDistance;

        return bounce(startDistance + bounceDistance, bounceDistance / 2);
    }

    public static void main(String[] args) {
        SkipStones skipStones = new SkipStones();
        System.out.println(skipStones.maxDistance(args[0]));
    }
}

Spirit 2005-12-15 13:29 发表评论

语源科技BlogJava-Spirit

Google Code Jam - WordPath

Google Code Jam - SkipStones的一种递归算法