Ruby Code Example: Boggle Board Solver
The September 2007 meeting of the Southeast Michigan Ruby Users' Group posed a Boggle Board Solver as the monthly challenge. Here is my solution. It is comprised of a number of components.
trie.rb
The first component is a class that implements the trie data structure.
# File trie.rb
# Copyright 2007 J. Eric Ivancich, all rights reserved.
# Licensed under the Creative Commons Attribution Non-commercial Share
# Alike license (see: http://creativecommons.org/licenses/by-nc-sa/3.0/).
require 'yaml'
# Implements the trie data structure.
class Trie
def initialize(level = 0)
@level = level
@hash = Hash.new
end
# Adds the string parameter to the trie.
def add(string)
letter = this_letter(string)
if letter.nil?
@hash[letter] = string
else
trie = @hash[letter]
if trie.nil?
trie = @hash[letter] = Trie.new(@level + 1)
end
trie.add(string)
end
end
# Tests whether the string parameter is a whole word present within
# the trie.
def include?(string)
letter = this_letter(string)
if letter.nil?
@hash[nil] == string
else
trie = @hash[letter]
trie && trie.include?(string)
end
end
# Tests whether there are any words in the trie that *begin* with
# the string parameter.
def begin?(string)
letter = this_letter(string)
if letter.nil?
@hash
else
trie = @hash[letter]
trie && trie.begin?(string)
end
end
# From the current trie, returns the sub-trie where the string
# parameter is the next letter.
def subtrie(letter)
trie = @hash[letter]
if trie.nil?
trie = @hash[letter] = Trie.new(@level + 1)
end
trie
end
# Returns true if there are any words in the current trie.
def any?
@hash.size > 0
end
# Saves this trie into a YAML file with the filename passed in.
def save(filename)
File.open(filename, "w") { |f| YAML.dump(self, f) }
end
# Loads in a trie from a YAML file, as determined by the filename
# passed in.
def self.load(filename)
YAML.load_file(filename)
end
# Loads in the text file passed in by filename, treating each line
# as a word to load into the trie.
def self.from_dictionary(filename)
trie = Trie.new
IO::foreach(filename) { |line| trie.add(line.chomp) }
trie
end
protected
# Returns the letter of the string passed in corresponding ot the
# level of this trie (or sub-trie).
def this_letter(string)
letter = string[@level, 1]
letter && letter.empty? ? nil : letter
end
end
boggle_solver.rb
The second component is the actual solver. It uses a recursive search through the board.
# File boggle_solver.rb
# Copyright 2007 J. Eric Ivancich, all rights reserved.
# Licensed under the Creative Commons Attribution Non-commercial Share
# Alike license (see: http://creativecommons.org/licenses/by-nc-sa/3.0/).
require 'trie'
require 'set'
# The BoggleSolver class is used to solve Boggle boards. It has
# nested classes to represent individual letter blocks (e.g., "a" or
# "qu"), Boggle boards, and a class that can load in a dictionary and
# then solve multiple boards.
class BoggleSolver
# Represents a letter blocks on the Boggle board. Generally a
# letter block will be a single letter (e.g., "a"). However, it can
# handle letter blocks that can contain sequences (e.g., "qu"). It
# knows who is neighboring letters are. It also knows whether it's
# been used (consumed) yet or not. Can return a list of all
# neighboring letters that are not yet used.
class Letter
attr_reader :letter, :neighbors
attr_accessor :used
def initialize(letter)
@letter = letter
@neighbors = Set.new
@used = false
end
# Adds a neighbor to the given letter.
def add_neighbor(other_letter)
@neighbors << other_letter
end
# Returns an array of neighboring letters that are not yet used.
def unused_neighbors
@neighbors.reject { |n| n.used }
end
end
# Represents a Boggle board as a two-dimensional array of Letters.
# The letters themselves keep track of the structure of the board
# (i.e., which letters neighbor which other letters), although the
# initialize method of this class sets up those links.
class Board
# Creates a board from a two-dimensional array of letters. Note,
# a letter can actually be a letter sequence (e.g., "qu").
def initialize(contents)
@size = contents.size
raise "non-rectangular" unless @size == contents.first.size
@letters = contents.map do |row|
row.map { |letter| Letter.new(letter) }
end
# set up neighbors
@letters.each_with_index do |row, row_index|
row.each_with_index do |letter, col_index|
(-1..1).each do |row_offset|
r = row_index + row_offset
next unless (0...@size) === r
(-1..1).each do |col_offset|
next if row_offset == 0 && col_offset == 0
c = col_index + col_offset
next unless (0...@size) === c
letter.add_neighbor @letters[r][c]
end
end
end
end
end
# Processes each letter on the board with the block provided.
def process
@letters.flatten.each { |l| yield l }
end
end
# Loads a dictionary and solves multiple boards using that dictionary.
class Solver
# Provide a dictioary file used to solve the Boggle boards.
def initialize(dictionary_file)
@dictionary = Trie.from_dictionary dictionary_file
end
# Solves the board passed in, returning an array of words, sorted
# from longest to shortest.
def solve(board_config)
board = Board.new(board_config)
results = Set.new
board.process do |l|
find_words(l, "", @dictionary, results)
end
results.to_a.sort_by { |w| [-w.size, w] }
end
protected
# Recursively try to find words by adding this letter to word,
# looking for it in our dictionary trie, and adding found words to
# results.
def find_words(letter, word, dict, results)
letter.used = true # open block by making letter used
word = word + letter.letter # make new word w/ letter
# march down dictionary trie; note: because one die contains a
# side w/ "qu", we use generalize to allow a die to contain any
# number of letters and march through *all* of them using a loop
0.upto(letter.letter.size - 1) do |index|
dict = dict.subtrie(letter.letter[index, 1])
end
# if there are any possible words once we get here...
if dict.any?
# if this specific word so far is in the dictionary
# add it to the results
results << word if word.size >= 3 && dict.include?(word)
# try to extend with all unused neighboring letters
letter.unused_neighbors.each do |l|
find_words(l, word, dict, results)
end
end
letter.used = false # close block by making letter available
end
end # class Solver
end # module BoggleSolver
boggle_server.rb
Because it took a while for the boggle solver to load the dictionary into the trie, I decided that it should only be done once by a "boggle server" and that the client could then just ask the existing solver to solve a given Boggle board.
So, the server is launched via a call to "fork", and it listens by default on port #32972 (0x80cc, which looks like "BOGG"). If it doesn't get any requests for 10 minutes, it shuts down automatically.
Note: all the server code is placed into a single module, so it can be used or not used.
# File boggle_server.rb
# Copyright 2007 J. Eric Ivancich, all rights reserved.
# Licensed under the Creative Commons Attribution Non-commercial Share
# Alike license (see: http://creativecommons.org/licenses/by-nc-sa/3.0/).
require 'boggle_solver'
require 'socket'
# This module has the methods to implement a Boggle server.
module BoggleServer
ServerHost = 'localhost'
ServerPort = 0x80cc
ServerTimeout = 60 * 10 # 10 minutes
DictFile = 'boggle.dict'
# Returns true if the server is running, false if not.
def self.server_running?
socket = TCPSocket.new(ServerHost, ServerPort)
YAML.dump("hello", socket)
socket.close_write
response = YAML.load(socket)
socket.close_read
response == "hello back"
rescue Errno::ECONNREFUSED => e
return false
end
# Forks off a process to run the server. The server loops, wating
# for connections and processing them. The server stops when it
# gets a shutdown message or when the timeout expires without any
# connections. All incoming messages are in YAML as are the
# responses.
def self.spawn(dict_file = DictFile)
solver = BoggleSolver::Solver.new(dict_file)
fork do
connection = TCPServer.new(ServerHost, ServerPort)
loop do
# if no connections before timeout, shutdown server
break unless select([connection], nil, nil, ServerTimeout)
socket = connection.accept
message = YAML.load(socket)
case message
when 'hello'
YAML.dump('hello back', socket)
when 'shutdown'
break
when Array
t1 = Time.now
result = solver.solve(message)
t2 = Time.now
YAML.dump(result, socket)
else
YAML.dump('error: unknown message', socket)
end
socket.shutdown
end # loop
connection.shutdown
end # fork
rescue Errno::EADDRINUSE
raise "could not start server"
end
# Returns immediately if server is running, or launches server and
# verifies that it is running before returning.
def self.server_assure
unless BoggleServer::server_running?
BoggleServer::spawn
50.times do |count|
break if BoggleServer::server_running?
sleep 0.1
end
unless BoggleServer::server_running?
raise 'could not start server'
end
end
end
# Requests that the server closes down.
def self.server_shutdown
socket = TCPSocket.new(ServerHost, ServerPort)
YAML.dump('shutdown', socket)
socket.shutdown
return true
rescue Errno::ECONNREFUSED => e
return false
end
# Takes a board and sends it to the server for solving. Returns the
# result.
def self.server_solve(board)
socket = TCPSocket.new(ServerHost, ServerPort)
YAML.dump(board, socket)
socket.close_write
result = YAML.load(socket)
socket.shutdown
result
end
end
# If this script is run on its own, shuts down the server if it's
# running.
if $0 == __FILE__
BoggleServer::server_shutdown
end
boggle_board_generator.rb
This class creates Boggle boards by rolling a set of Boggle dice and placing them in the grid randomly.
# Represents and generates Boggle Boards. It randomly rolls simulated
# Boggle Dice and places them randomly in a 4x4 grid. Note: one die
# has a side that shows 'qu'.
require 'enumerator'
class BoggleBoardGenerator
BoggleDie = [
['f', 'o', 'r', 'i', 'x', 'b'],
['m', 'o', 'qu', 'a', 'b', 'j'],
['g', 'u', 'r', 'i', 'l', 'w'],
['s', 'e', 't', 'u', 'p', 'l'],
['c', 'm', 'p', 'd', 'a', 'e'],
['a', 'c', 'i', 't', 'a', 'o'],
['s', 'l', 'c', 'r', 'a', 'e'],
['r', 'o', 'm', 'a', 's', 'h'],
['n', 'o', 'd', 'e', 's', 'w'],
['h', 'e', 'f', 'i', 'y', 'e'],
['o', 'n', 'u', 'd', 't', 'k'],
['t', 'e', 'v', 'i', 'g', 'n'],
['a', 'n', 'e', 'd', 'v', 'z'],
['p', 'i', 'n', 'e', 's', 'h'],
['a', 'b', 'i', 'l', 'y', 't'],
['g', 'k', 'y', 'l', 'e', 'u']]
@@random_seed = 10202007 # default initial seed
attr_reader :board
def initialize()
srand @@random_seed # to insure repeatabilty set seed now
indices = (0...BoggleDie.size).to_a.sort_by { rand }
@@random_seed = rand 2**31 # pick next random seed based on previous
# creates an array with the dice randomly re-ordered and then
# rolls each of the dice
@board = BoggleDie.values_at(*indices).map { |die| die[rand(die.size)] }
end
def self.seed=(new_seed)
@@random_seed = new_seed
end
# Returns an array of arrays, where outer arrays contains the rows
# on the board, and each row is an array that contains the letters
# on a given row.
def board_2d
# slice the array into groups of 4 to create 2d-array
@board.enum_slice(4).to_a
end
def to_input_s
board.join('').gsub('qu', 'q')
end
# Returns a string that displays the rows on separate lines.
def to_s
board_2d.map do |row|
row.map { |letter| '%-3s' % letter }.join(' ')
end.join("\n")
end
end
if $0 == __FILE__
BoggleBoardGenerator.seed = 555
5.times do
b = BoggleBoardGenerator.new
p b.board # 1-dimensional array
p b.board_2d # 2-dimensional array
puts b # 4-line string
puts b.to_input_s
end
end
boggle.rb
This is the entry point into the software. If a Boggle board is provided as a string of sixteen letters as a command-line argument, it solves taht board. If no argument is provided, it creates a randomly generated board and solves it.
#!/usr/bin/env ruby
# File boggle.rb
# Copyright 2007 J. Eric Ivancich, all rights reserved.
# Licensed under the Creative Commons Attribution Non-commercial Share
# Alike license (see: http://creativecommons.org/licenses/by-nc-sa/3.0/).
require 'enumerator'
require 'boggle_solver'
require 'boggle_server'
# if a Boggle server is not running, start it.
BoggleServer::server_assure
# If there's a command-line argument use it as the Boggle board.
# Otherwise create a random Boggle board.
if ARGV.size >= 1
board_string = ARGV[0]
else
require 'boggle_board_generator'
BoggleBoardGenerator.seed = rand(2 ** 32)
random_board = BoggleBoardGenerator.new
board_string = random_board.to_input_s
puts "Random board is:"
puts random_board
end
# convert the board string into nested arrays representing a 4-by-4
# Boggle board
board =
board_string.split(//).map { |l| l == 'q' ? 'qu' : l }.enum_slice(4).to_a
t1 = Time.now
# solve the board
results = BoggleServer::server_solve(board)
t2 = Time.now
puts "\nResults:"
puts results
puts "\nStats:"
puts "Time to solve: %0.4f seconds" % (t2 - t1)
boggle.dict
Finally, here is the dictionary used by this program. It contains full words, one per line. Download boggle.dict.
