4
\$\begingroup\$

The following is my attempt at creating a Boggle board solver in Ruby. It's not especially fast. I would love to have input on how the solution can either be sped up, or whether a different algorithm might be applied that is faster.

The solution corresponds to my answer on a related question on the Math Stack Exchange site: https://math.stackexchange.com/a/2908479/30919

require 'set'
# List of words in a file, imported into sorted set for quick lookup:
WORDS = SortedSet.new(open('wordlist.txt').readlines.map(&: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

# Note on "Qu" -- "Qu" should require special handling in the

# 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
# NB: **The letters have their own stack due to the special handling of "Qu"**
@letters = [] # Corresponding letters from the positions in stack
@found_words = SortedSet.new # Words found 
def traverse(cpos)

    # Nested method that handles popping of stack with special 'Qu' handling (because it's used more than once)
    def pop_stack
        @stack.pop
        @letters.pop
        # Special handling for "Qu":
        @letters.pop if @letters.last == "Q"        
    end

  #The longest words in my list are 15 letters - omit this check if you have more
  return if @stack.length == 15 

  # Push current position and letters collected so far on the respective stacks
  @stack << cpos
  @letters << @board[cpos[0]][cpos[1]]
  # Special handling for Qu:
  @letters << "U" if @letters.last == "Q"

  # From 2 letters onwards, check whether this path is worth pursuing
  if @stack.length >= 2
    unless WORDS.grep(/^#{@letters.join}/).any?
      pop_stack
      return
    end
  end

  # From 3 letters onwards, check if the word is in the dictionary
  if @stack.length >= 3
    word = @letters.join
    if WORDS.include?(word)
      @found_words << word
    end
  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
    # Check whether the new position had been visited in current stack
    visited = false
    @stack.reverse_each do |pos|
      if pos == npos
        visited = true
        break 
      end
    end
    next if visited # Skip the new position if it had been visited
    traverse(npos) # Start looking from next position
  end

  # Take the last position/letter off the stack before returning
  pop_stack

end

# Traverse from every square on the board
4.times.map do |x|
  4.times.map do |y|
    traverse([x, y])
  end
end

puts @found_words.sort
\$\endgroup\$
2
\$\begingroup\$

I can't comment on Ruby style, but there are a couple of algorithmic points which don't need Ruby knowledge to identify.


  if @stack.length >= 2
    unless WORDS.grep(/^#{@letters.join}/).any?
      pop_stack
      return
    end
  end

Although you've preprocessed the wordlist into a sorted data structure with logarithmic time lookup, grep seems to be a method from Enumerable and I can't see any indication that there are special cases. In other words, this is (worst case) doing a linear scan of the entire wordlist. There should be a massive speed improvement either by exploiting the SortedSet interface or (more likely) by preprocessing the wordlist into a trie. The latter gives the advantage that you can pass the current node down the stack and not have to run the entire route from the root every time.


    # Check whether the new position had been visited in current stack
    visited = false
    @stack.reverse_each do |pos|
      if pos == npos
        visited = true
        break 
      end
    end

Again, this is doing a linear scan for something which doesn't need to be so slow. The OO way would be to use a Set, which ought to have fast member? checks. The optimisation-over-all approach would be to use an integer as a bitmask. Either approach requires minimal maintenance on the stack.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the suggestions, especially about the Trie. As a result, I have built a Trie from a Ruby Hash, where the current node in the trie tracks along with the traversal through the board. This has not only sped up the script by orders of magnitude, but has significantly simplified the code. How does it work on Code Review? Do I post my updated solution somewhere? Anyway, here it is: gist.github.com/mydoghasworms/e31a723c114f760942aed11bb0fe3d95 \$\endgroup\$ – mydoghasworms Sep 8 '18 at 7:06
  • 1
    \$\begingroup\$ You don't have to post your updated solution anywhere, but if you want to then posting a gist is indeed one suitable solution. If you want further comments then you can post a new question with the revised code: see this meta thread for specifics. The big thing to avoid is editing the question to replace the code, which makes the answers no longer make sense. Also, I would suggest waiting a day or two before posting a follow-up in case other people spot other things worthy of mention. \$\endgroup\$ – Peter Taylor Sep 8 '18 at 7:11
2
\$\begingroup\$

General practices

  • Global variables

    You have a long script, with a lot of free-floating code that interacts in unclear ways. You have some variables, such as @board, @stack, and @found_words, that essentially act as global variables.

    I would consider WORDS (or wordlist.txt) and @board to be the inputs, but they aren't defined next to each other. Since you'll be dealing with a lot of "words" in the code, I suggest calling it the "vocabulary" to be clear about what you mean.

    @found_words contains the outputs after running the script. Since it's a SortedSet, its entries are always alphabetized, but you call @found_words.sort on it anyway.

    It would be better to make the flow of information clear. Also, the global variables should be scoped as instance variables, so I would define a class. In my suggested solution below, see the last line, which gives an overview of how the code fits together:

    Boggle.new(vocabulary, board).search { |word| puts word }
    
  • Backtracking

    Your code performs backtracking, using @stack to store the state of the traversal. Consider using recursion instead, which would simplify the code a bit. The maximum recursion depth is 16, so you wouldn't have to worry about the stack overflowing.

    Your @stack and @letters are kind of redundant. Considering that you could reconstruct @letters from the stack using a one-liner, I wouldn't bother keeping track of both.

  • Coordinates

    Handling coordinate pairs is a bit of a pain. If you could represent each position as a single integer instead of a pair of integers, then the code would be a bit simpler.

  • Path building

    Instead of defining a next_pos function that may return nil, define a neighbors function that returns all valid neighboring positions. The caller can just iterate over the results, and won't have to deal with the nil case.

    Your loop that performs the visited test is just a set difference operation. In my solution below, it's just neighbors(path.last) - path.

  • Opening files

    Avoid calling open without closing the file handle. The best way to do that is to call open with a block, in which case the file handle will be automatically closed when exiting the block.

Efficiency

The simplest way to provide the illusion of performance is to output results as you find them, rather than all at once at the end. In the suggested solution below, the traverse method takes a callback block that handles each result. (You could, of course, adapt the callback to gather all of the results and print them in alphabetical order, if sorting was required.)

The most time-consuming part of the code is WORDS.grep(/^#{@letters.join}/).any?, because it involves a regex test for every word in the vocabulary. One slight improvement would be WORDS.any? { |w| w.start_with? prefix }, which avoid using a regex, and also allows short-circuiting when a match is found.

Unfortunately, Ruby's SortedSet class lacks a #contains_prefix? method, which could accomplish the test efficiently. In that sense, using a SortedSet to store the vocabulary is no better than using a Set. (Java's SortedSet, in contrast, supports a .tailSet() operation. You could test that the tail set is non-empty, and that its first entry is a prefix.) To make your Boggle solver efficient, therefore, requires a better data structure for the vocabulary. I recommend a trie for this purpose. You'll spend more time building the trie when loading the vocabulary, but the Boggle search will be very fast.

Suggested solution

require 'set'

class Boggle
  # Boggle searcher.
  #
  # The vocabulary is a set of all valid words, in uppercase.
  #
  # The board is a 4x4 array of characters, or an array of
  # four 4-character strings, or a string of 16 characters, all
  # uppercase.  'Q' represents 'Qu'.
  def initialize(vocabulary, board)
    @vocabulary = vocabulary
    @board = board.flatten.join
    raise ArgumentError.new('Invalid board size') unless @board.length == 16
  end

  # Search the board, yielding each word that is found.
  def search      # :yields: word
    seen_words = Set.new
    16.times do |pos|
      traverse([pos]) { |word| yield word if seen_words.add? word }
    end
  end

private
  # Neighboring positions of a given index on a linearized 4x4 board
  def neighbors(pos)
    left  = (pos % 4 == 0) ? pos : pos - 1
    right = (pos % 4 == 3) ? pos : pos + 1
    Set[
      left - 4, pos - 4, right + 4,
      left,              right,
      left + 4, pos + 4, right + 4,
    ].delete_if { |p| p < 0 || p >= 16 }
  end

  def traverse(path, &block)
    word = path.map { |pos| @board[pos] == 'Q' ? 'QU' : @board[pos] }.join
    block.call(word) if word.length >= 3 && @vocabulary.include?(word)

    (neighbors(path.last) - path).each do |pos|
      traverse(path + [pos], &block)
    end if @vocabulary.any? { |v| v.start_with? word }
  end
end


vocabulary = open('wordlist.txt') do |f|
  Set.new(f.readlines.map { |line| line.chomp.upcase })
end

board = [
  'NPER',
  'PLRO',
  'IUNT',
  'JEGV',
]

Boggle.new(vocabulary, board).search { |word| puts word }
\$\endgroup\$
  • \$\begingroup\$ Thanks very much for the helpful tips. I have only just finished implementing Peter Taylor's suggestions, including a trie, which has made the biggest difference in terms of performance. The result is here: gist.github.com/mydoghasworms/e31a723c114f760942aed11bb0fe3d95. I would like to implement some of your suggestions as well, especially the way to determine valid neighbours (rather than checking for nil) which makes a lot more logical sense. I ended up reconstructing the letters sequence from the stack (my only worry was the 'U' after 'Q', but that sorted itself out easily). \$\endgroup\$ – mydoghasworms Sep 8 '18 at 7:10
  • \$\begingroup\$ Also, I did at some point have a class-based solution, but up front I struggle to decide how to model the problem with classes, when the problem just seems a sequential one to me. I will retry using a class-based approach though as it lends itself better to packaging of the code for reusability. \$\endgroup\$ – mydoghasworms Sep 8 '18 at 7:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.