A Boggle-style word search done for a coding interview

word_search.rb

require 'set'

$test_board = [['i', 'b', 't'],
              ['m', 'e', 's'],
              ['r', 'o', 'e']]


def valid_words_on_board(board, trie = Trie.new(word_list()))
  valid_words = []
  board = Board.new(board)
  

  starting_position = board.position(0,0)
  while !starting_position.nil?
    
    paths = [Path.new(starting_position)]

    until paths.empty?
      path = paths.shift

      is_valid = trie.valid_as_prefix_or_word? path.word_so_far
 
      next if !is_valid

      if is_valid == :word or is_valid == :both
        valid_words << path.word_so_far.join
      end

      if is_valid == :prefix or is_valid == :both
        paths.concat path.continued_paths
      end
    end

    starting_position = starting_position.next
  end
  valid_words
end

class Path
    attr_reader :word_so_far

    def initialize(pos)
      @word_so_far = [pos.value]
      @visited = Set.new
      @visited.add pos
      @current = pos
    end

    def continued_paths
      neighbors = @current.neighbors
      neighbors.reject! { |pos| @visited.include? pos }

      neighbors.collect {|n| self.dup.add_position(n) }
    end

    protected
      def add_position(pos)
        @word_so_far<< pos.value
        @visited << pos
        @current = pos

        self
      end

      def initialize_copy(old)
        @word_so_far = @word_so_far.dup
        @visited = @visited.dup
      end 
end

class Board
  attr_reader :height, :width

  def initialize(char_array)
    @height = char_array.length
    @width = char_array[0].length

    char_array.each do |row| 
      raise ArgumentError, "board must be rectangular" if row.length != @width 
    end

    @positions = {}

    char_array.each_with_index do |row, x|
      row.each_with_index do |value, y|
        @positions[:"#{x},#{y}"] = Position.new(x, y, value, self)
      end
    end
  end

  def position(x,y)
    @positions[:"#{x},#{y}"]
  end

  class Position
    attr_reader :x, :y, :value

    def initialize(x, y, value, board)
      @x = x
      @y = y
      @value = value
      @board = board
    end

    def next
      if @x == @board.height - 1 and @y == @board.width - 1
          nil
      elsif @y == @board.width - 1
          @board.position(@x + 1, 0)
      else
          @board.position(@x, @y+1)
      end
    end

    def neighbors
      [@board.position(@x - 1, @y), 
       @board.position(@x + 1, @y),
       @board.position(@x, @y - 1),
       @board.position(@x, @y + 1)].reject {|p| p.nil? }
    end

    def inspect
      "(#{@x}, #{@y}): #{@value}"
    end
  end
end

class Trie
  def initialize(words)
    @root = {}

    words.each do |word|
      current_level = @root

      word.each_char do |c|
        current_level[c] ||= {}
        current_level = current_level[c]
      end

      current_level[:end] = true
    end
  end

  def valid_as_prefix_or_word?(chars)
    current_level = @root

    if !chars.respond_to? :each and chars.respond_to? :each_char
      chars = chars.each_char #allow strings in 1.9+
    end

    chars.each do |c| 
      return false if current_level.nil?
      current_level = current_level[c]
    end

    if current_level.nil?
      false
    elsif current_level.has_key? :end
      if current_level.size == 1
        :word 
      else
        :both
      end
    else
      :prefix
    end
  end
end

def word_list
  words = `cat /usr/share/dict/words`
  words.split("\n")
end