Quiz: Count the ways to find a word by walking on a grid (4)
# 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