Quiz: Count the ways to find a word by walking on a grid (5)
Thursday, April 3rd, 2008/*
* Author : David Tran
* Date : 2008-04-03
* Quiz : CountPaths
*/
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Quiz4 {
public static void main(String[] args) throws Exception {
new Quiz4().solve();
}
public void solve() {
long start = System.currentTimeMillis();
loadProblem();
BigInteger solutions = BigInteger.ZERO;
for (int index : starts) {
solutions = solutions.add(findSolution(index / cols, index % cols, 0));
}
System.out.println("Total Solution = " + solutions);
System.out.println("Total time (msec) to solve = " + (System.currentTimeMillis() - start));
}
public Quiz4() throws Exception {
rows = 50;
cols = 50;
cellLength = 1;
goal = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"; // 50x"A"
gridData = new String[rows][cols]; // 50×50x"A"
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
gridData[i][j] = "A";
}
}
}
private int rows;
private int cols;
private int lastNumber;
private List<Integer> starts;
private Map<Integer, BigInteger>[][] grid;
private int cellLength;
private String goal;
private String[][] gridData;
@SuppressWarnings("unchecked")
private void loadProblem() {
// split goal string to build up dictionary
Map<String, List<Integer>> dictionary = new HashMap<String, List<Integer>>();
for (int nb = 0, position = 0, length = goal.length(); position < length; nb++, position += cellLength) {
String substring = goal.substring(position, position + cellLength);
if (dictionary.containsKey(substring)) {
dictionary.get(substring).add(nb);
} else {
List<Integer> values = new ArrayList<Integer>();
values.add(nb);
dictionary.put(substring, values);
}
}
if (dictionary.size() <= 0) {
throw new IllegalArgumentException("No input data ?!");
}
lastNumber = (goal.length() / cellLength) - 1;
starts = new ArrayList<Integer>();
grid = (Map<Integer, BigInteger> [][]) new Map[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
String key = gridData[i][j];
if (dictionary.containsKey(key)) {
Map<Integer, BigInteger> map = new HashMap<Integer, BigInteger>();
for (int nb : dictionary.get(key)) {
map.put(nb, null);
if (nb == 0) {
starts.add(i * cols + j);
}
}
grid[i][j] = map;
}
}
}
}
private BigInteger findSolution(int i, int j, int nb) {
if (nb == lastNumber) {
return BigInteger.ONE;
} else {
BigInteger solutions = grid[i][j].get(nb);
if (solutions == null) {
solutions = BigInteger.ZERO;
for (int index : findNeighbors(i, j, nb)) {
solutions = solutions.add(findSolution(index / cols, index % cols, nb + 1));
}
grid[i][j].put(nb, solutions);
}
return solutions;
}
}
private List<Integer> findNeighbors(int i, int j, int nb) {
int nextNb = nb + 1;
List<Integer> neighbors = new ArrayList<Integer>();
addNeighbor(i - 1, j - 1, nextNb, neighbors);
addNeighbor(i - 1, j , nextNb, neighbors);
addNeighbor(i - 1, j + 1, nextNb, neighbors);
addNeighbor(i , j - 1, nextNb, neighbors);
addNeighbor(i , j + 1, nextNb, neighbors);
addNeighbor(i + 1, j - 1, nextNb, neighbors);
addNeighbor(i + 1, j , nextNb, neighbors);
addNeighbor(i + 1, j + 1, nextNb, neighbors);
return neighbors;
}
private void addNeighbor(int i, int j, int nb, List<Integer> list) {
if (i >= 0 && i < rows && j >= 0 && j < cols &&
grid[i][j] != null && grid[i][j].containsKey(nb)) {
list.add(i * cols + j);
}
}
}
Result on my machine:
A:>java Quiz4
Total Solution = 303835410591851117616135618108340196903254429200
Total time (msec) to solve = 562