David Tran’s blog

/*
 * 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

# Author : David Tran
# Date   : 2008-04-02
# Quiz   : http://davidtran.doublegifts.com/blog/?p=139
# File   : quiz.rb

class Quiz

  def initialize(grid_file, goal_file)
    grid_data = IO.readlines(grid_file).map {|e| e.chomp}.map {|e| e.split(/\s+/)}
    goal = IO.read(goal_file).chomp
  
    @rows = grid_data.size
    @cols = grid_data[0].size
    cell_size = grid_data[0][0].size
  
    # split goal string to build up dictionary
    dictionary = Hash.new {|h, e| h[e] = []}
    index = 0
    goal.scan(/#{'.' * cell_size}/).each do |w|
      dictionary[w] << index
      index += 1
    end
  
    @last_nb = (goal.size / cell_size) - 1
    @grid = Array.new(@rows) { Array.new(@cols) { Hash.new } }
    starts = []
  
    @rows.times do |r|
      @cols.times do |c|
        dictionary[grid_data[r][c]].each do |v|
          @grid[r][c][v] = -1
          starts << [r,c] if v == 0
        end
      end
    end

    solutions = starts.inject(0) { |s, (i,j)| s += find_solution(i, j, 0) }
    puts "Total Solution = #{solutions}"
  end
  
  def find_solution(i, j, nb)
    return 1 if nb == @last_nb
    return @grid[i][j][nb] if @grid[i][j][nb] >= 0
    @grid[i][j][nb] = get_neighbors(i, j, nb).inject(0) { |s, (x, y)| s += find_solution(x, y, nb+1) }
  end
  
  def get_neighbors(i, j, nb)
    [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]].inject([]) do |a, (x,y)|
      a << neighbor(i+x, j+y, nb+1)
    end.compact
  end
  
  def neighbor(i, j, nb)
    (i >= 0 && i < @rows && j >= 0 && j < @cols && @grid[i][j].key?(nb)) ? [i, j] : nil
  end
  
end

if $0 == __FILE__
  (puts "Usage: ruby quiz.rb  grid_file  goal_file"; exit) if ARGV.size < 2
  Quiz.new(ARGV[0], ARGV[1])
end

# ============================== #

# Author : David Tran
# Date   : 2008-04-02
# File   : test.rb
# Object : find the maximum solutions

open('grid.txt', 'w') {|f| 50.times { f << 'A ' * 50 << "\n"}}
max = 0
index = -1
50.times do |i|
  i += 1
  open('goal.txt', 'w') { |f| f << 'A' * i }
  result = %x{ ruby quiz.rb grid.txt goal.txt }
  if result =~ /Solution = (\d+)/
    solutions = $1.to_i
    puts "#{i.to_s.rjust(2, '0')} => #{solutions}"
    if (solutions > max)
      max = solutions
      index = i
    end
  end
end

puts
puts "Maximum => #{index} => #{max}"


__END__
Result:

01 => 2500
02 => 19404
03 => 152292
04 => 1198512
05 => 9453300
06 => 74662104
07 => 590305088
08 => 4670864544
09 => 36982919796
10 => 292979734056
11 => 2322050158968
12 => 18410909224368
13 => 146024921567904
14 => 1158535320863088
15 => 9194071282628352
16 => 72981174038164224
17 => 579439667561976564
18 => 4601415854638476552
19 => 36547133286285125864
20 => 290326968106929048336
21 => 2306684143572560961624
22 => 18329503368942296048880
23 => 145670217447616179975600
24 => 1157829208250036601664992
25 => 9203827271760017849641312
26 => 73171094997928920840845904
27 => 581774919929278927886179248
28 => 4626070561470449649010421664
29 => 36788241251602079481574654656
30 => 292579041503607826263355150176
31 => 2327088439774693588696558829376
32 => 18510420519854069350331486524800
33 => 147248802959429409354656962751220
34 => 1171434060031010511872752993856328
35 => 9319939961558447074697552088702600
36 => 74154290207123230340766878367722064
37 => 590046376097012157795995971369959624
38 => 4695281006073221324094307242033576432
39 => 37364705320671553187068052340260719824
40 => 297361737077320616265561468778248253728
41 => 2366634780471229416464762512469663693592
42 => 18836455040472517436022242181973614080112
43 => 149929836577708085403038515575864523777776
44 => 1193430584532300786500980677298194867380832
45 => 9500046751158181070821773471417360223448304
46 => 75626347587870791654047249972768528120486752
47 => 602058474789522292652482399670191674941123040
48 => 4793158368431771829259255859223541964804203200
49 => 38161186114402617099716572074367083097283018976
50 => 303835410591851117616135618108340196903254429200

Maximum => 50 => 303835410591851117616135618108340196903254429200