Class: BoggleSolver::Board

Inherits:
AdjacencyMatrix show all
Defined in:
lib/boggle_solver/board.rb

Instance Attribute Summary collapse

Attributes inherited from AdjacencyMatrix

#finished, #visited

Instance Method Summary collapse

Methods inherited from AdjacencyMatrix

#add_directed_edge, #add_edge, #adjacent

Constructor Details

#initialize(mode = :default, input, dictionary_file) ⇒ Board

Returns a new instance of Board.



9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
# File 'lib/boggle_solver/board.rb', line 9

def initialize(mode=:default, input, dictionary_file)
  super(25)
  connect
  @board = []
  if mode == :random
    @prng = Random.new
    generate_random_board
  elsif mode == :given
    @board = input.split(//)
  else
    generate_board
  end
  calculate_board_hash
  puts self
  @words = []
  set_dictionary dictionary_file
  load_dictionary
end

Instance Attribute Details

#words ⇒ Object (readonly)

Returns the value of attribute words.



7
8
9
 
# File 'lib/boggle_solver/board.rb', line 7

def words
  @words
end

Instance Method Details

#calculate_board_hash ⇒ Object 



60
61
62
63
 
# File 'lib/boggle_solver/board.rb', line 60

def calculate_board_hash
  @board_hash = Hash.new(0)
  @board.each {|letter| @board_hash[letter]  += 1}
end

#connect ⇒ Object 



32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/boggle_solver/board.rb', line 32

def connect
  j=0;
  while j<25 do
    add_edge(j, j-6) unless j < 6 or j % 5 == 0
    add_edge(j, j-5) unless j < 5
    add_edge(j, j-4) unless j < 4 or j % 5 == 4
    add_edge(j, j-1) unless j % 5 == 0
    add_edge(j, j+1) unless j % 5 == 4
    add_edge(j, j+4) unless j > 19 or j % 5 == 0
    add_edge(j, j+5) unless j > 19
    add_edge(j, j+6) unless j > 18 or j % 5 == 4
    j += 1
  end
end

#depth_first_search(offset = 0) ⇒ Object 



119
120
121
122
123
124
125
126
127
128
 
# File 'lib/boggle_solver/board.rb', line 119

def depth_first_search(offset=0)
  Thread.current[:visited] = Array.new(@n, nil)
  Thread.current[:finished] = Array.new(@n, nil)
  Thread.current[:words] = []
  Thread.current[:visited][offset..-1].each_with_index do |visit_status, u|
    u += offset
    search_string = @board[u]
    depth_first_search_visit(u, search_string) if Thread.current[:finished][u].nil?
  end
end

#depth_first_search_visit(u, search_string) ⇒ Object 



130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
 
# File 'lib/boggle_solver/board.rb', line 130

def depth_first_search_visit(u, search_string)
  Thread.current[:visited][u] = 1
  Thread.current[:words] << search_string if in_dictionary? search_string
  adjacent(u).each do |v|
    if Thread.current[:visited][v].nil?
      s = search_string + @board[v]
      Thread.current[:words].push s if in_dictionary? s
      if part_in_dictionary? s
        depth_first_search_visit(v, s)
      end
    end
  end
  Thread.current[:finished][u] = 1
  Thread.current[:visited][u] = nil
end

#find_words ⇒ Object 



103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
 
# File 'lib/boggle_solver/board.rb', line 103

def find_words
  threads = []
  @board.each_with_index do |letter, index|
    threads << Thread.new { depth_first_search(index) }
  end

  threads.each do |t|
    t.join
    @words.concat t[:words]
  end

  @words.uniq!
  @words.sort_by!{|item| item.length}
  @words = @words.drop_while{|w| w.length < 3}
end

#generate_board ⇒ Object 



47
48
49
 
# File 'lib/boggle_solver/board.rb', line 47

def generate_board
  @board = ["a", "r", "t", "a", "c", "c", "e", "a", "r", "d", "f", "e", "w", "o", "o", "n", "p", "l", "m", "i", "c", "r", "u", "b", "l"]
end

#generate_random_board ⇒ Object 



55
56
57
58
 
# File 'lib/boggle_solver/board.rb', line 55

def generate_random_board
  @board = Array.new(25)
  @board.map!{|item| (65.+rand(25)).chr.downcase!}
end

#in_dictionary?(s) ⇒ Boolean

Returns:

  • (Boolean) 


93
94
95
 
# File 'lib/boggle_solver/board.rb', line 93

def in_dictionary? s
  @dictionary.index s
end

#load_board_from_string(s) ⇒ Object 



51
52
53
 
# File 'lib/boggle_solver/board.rb', line 51

def load_board_from_string s
  @board = s.split(//) if s.length == 25
end

#load_dictionary ⇒ Object 



65
66
67
68
69
70
71
72
 
# File 'lib/boggle_solver/board.rb', line 65

def load_dictionary
  @dictionary = Array.new

  File.foreach(@dictionary_file) do |line|
    next_word = line.chomp
    @dictionary.push next_word if possible? next_word
  end
end

#part_in_dictionary?(s) ⇒ Boolean

Returns:

  • (Boolean) 


97
98
99
100
101
 
# File 'lib/boggle_solver/board.rb', line 97

def part_in_dictionary? s
  s = "\\A" + s + "..*"
  regex = Regexp.new(s)
  !(@dictionary.grep regex).empty?
end

#possible?(word) ⇒ Boolean

Returns:

  • (Boolean) 


74
75
76
77
78
79
80
81
82
 
# File 'lib/boggle_solver/board.rb', line 74

def possible? word
  word_hash = Hash.new(0)
  result = true
  word.each_char {|letter| word_hash[letter] += 1}
  word_hash.each do |letter, count|
    result &&= count <= @board_hash[letter]
  end
  result
end

#score ⇒ Object 



146
147
148
 
# File 'lib/boggle_solver/board.rb', line 146

def score
  @words.inject(0) { |points, w| points + w.length}
end

#set_dictionary(file) ⇒ Object 



28
29
30
 
# File 'lib/boggle_solver/board.rb', line 28

def set_dictionary file
  @dictionary_file = file
end

#to_s ⇒ Object 



84
85
86
87
88
89
90
91
 
# File 'lib/boggle_solver/board.rb', line 84

def to_s
  s = ""
  @board.each_with_index do |letter, index|
    s += letter.to_s + " "
    s += "\n" if index % 5 == 4
  end
  s.chomp
end