Created
September 8, 2018 07:05
-
-
Save mydoghasworms/e31a723c114f760942aed11bb0fe3d95 to your computer and use it in GitHub Desktop.
Boggle Solver in Ruby
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Trie < Hash | |
def initialize | |
super | |
end | |
def build(string) | |
string << '.' #Terminator indicating end of a complete word | |
string.chars.inject(self) do |h, char| | |
h[char] ||= { } | |
end | |
end | |
end | |
# Build the trie from all the words in the list | |
@trie = Trie.new | |
File.foreach('wordlist.txt') {|w| @trie.build(w.chomp) } | |
# Possible directions from a space and their x/y deltas: | |
DIRS = { n: [0, -1], ne: [1, -1], e: [1, 0], se: [1, 1], s: [0, 1], sw: [-1, 1], w: [-1, 0], nw: [-1, -1] }.freeze | |
# Sample board we want to solve; we could create a random board with | |
# the known configuration of the cubes. | |
# For 'Qu' on the Boggle board, only 'Q' is entered in @board, because the traversion routine | |
# has special handling for 'Q' by adding a 'U' each time | |
@board = [ | |
%w[ N P E R ], | |
%w[ P L R O ], | |
%w[ I U N T ], | |
%w[ J E G V ] | |
] | |
# This method determines the next position based on the currend position | |
# and direction. If the position is out of bounds, it returns nil | |
def next_pos(position, direction) | |
npos = [ | |
position[0] + DIRS[direction][0], | |
position[1] + DIRS[direction][1] | |
] | |
return nil if (npos[0] < 0) || (npos[1] < 0) || | |
(npos[0] > 3) || (npos[1] > 3) | |
npos | |
end | |
@stack = [] # Stack containing the positions traversed | |
@found_words = [] # Words found | |
def traverse(cpos, trie) | |
# If the subsection of the trie has no children, return | |
#return if trie.keys.empty? | |
# Push current position and letters collected so far on the respective stacks | |
@stack << cpos | |
letters = @stack.map{|p|@board[p[0]][p[1]]} | |
letters << "U" if letters.last == "Q" | |
# From 3 letters onwards, check if the word is in the dictionary | |
if @stack.length >= 3 | |
word = letters.join | |
@found_words << word if trie.keys.include?('.') and !@found_words.include?(word) | |
end | |
# If the trie node has no further children, abandon further search | |
if trie.keys.empty? | |
@stack.pop | |
return | |
end | |
# Try each direction in succession from the current position | |
DIRS.keys.each do |dir| | |
npos = next_pos(cpos, dir) # Calculate next pos from current pos | |
next unless npos # Check it is not out of bounds | |
next if @stack.include?(npos) # Skip the new position if it had been visited | |
ntrie = trie[@board[npos[0]][npos[1]]] # Child node of trie based on next letter | |
next unless ntrie # Skip if the trie node has no such child with such a letter | |
traverse(npos, ntrie) # Continue looking from next position | |
end | |
# Take the last position off the stack before returning | |
@stack.pop | |
end | |
# Traverse from every square on the board | |
4.times.map do |x| | |
4.times.map do |y| | |
pos = [x,y] | |
traverse(pos, @trie[@board[x][y]]) | |
end | |
end | |
puts @found_words.sort |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment