LearnRuby.com

Ruby Training and Ruby on Rails Training exclusively

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.