word_challenge.rb

class Grid
  def initialize(grid, dict)
    @grid = grid
    raise "size of #{grid} isn't 4x4" if @grid.size != 4 || @grid[0].size != 4

    @dict = dict
    @result = []
  end

  def dfs(i, j, cur)
    @visited[i][j] = true

    @result << cur if @dict.contains? cur

    dirs.each do |dir|
      x = i + dir[0]
      y = j + dir[1]

      next if x < 0 || x > 3 || y < 0 || y > 3 || @visited[x][y]

      word = cur + @grid[x][y]
      dfs(x, y, word) if @dict.prefix?(word)
    end
    @visited[i][j] = false
  end

  def search
    4.times do |i|
      4.times do |j|
        @visited = Array.new(4) { Array.new(4, false) }
        dfs(i, j, @grid[i][j])
      end
    end

    @result.uniq
  end

  def dirs
    [
      [1, 0],
      [-1, 0],
      [0, 1],
      [0, -1],
      [1, 1],
      [1, -1],
      [-1, 1],
      [-1, -1],
    ]
  end
end

class Dict
  class Node
    def initialize
      @end = false
      @children = {}
    end

    def insert(word)
      if word == ""
        @end = true
        return
      end

      letter, rest = word[0], word[1..word.length-1]

      @children[letter] = Node.new unless @children[letter]
      @children[letter].insert(rest)
    end

    def prefix?(word)
      return true if word == ""
      letter, rest = word[0], word[1..word.length-1]

      return false unless @children[letter]

      @children[letter].prefix?(rest)
    end

    def contains?(word)
      if word == ""
        @end
      else
        letter, rest = word[0], word[1..word.length-1]

        return false unless @children[letter]

        @children[letter].contains?(rest)
      end
    end
  end

  def initialize(wf="/usr/share/dict/words")
    @wf = wf
    @root = Node.new
  end

  def parse
    File.open(@wf).each_line do |word|
      @root.insert(word.downcase.chomp)
    end
  end

  def contains?(word)
    @root.contains?(word)
  end

  def prefix?(word)
    @root.prefix?(word)
  end

  def root
    @root
  end
end

class NaiveDict
  require "set"

  def initialize(wf="/usr/share/dict/words")
    @wf = wf
    @lines = Set.new
  end

  def parse
    File.open(@wf).each_line do |word|
      @lines.add word.downcase.chomp
    end

    puts @lines.size
  end

  def contains?(word)
    @lines.include?(word)
  end

  def prefix?(word)
    @lines.each do |l|
      return true if l.start_with?(word)
    end
    false
  end
end

test_set_1 = [
  %w{c z w f},
  %w{r a m p},
  %w{s u t e},
  %w{q c s z},
]

test_set_2 = [
  %w{q b c t},
  %w{b c t n},
  %w{s u k q},
  %w{b x o l},
]

def time(action)
  puts "Start #{action}..."
  start = Time.now
  yield

  puts "Time take to #{action}: #{Time.now - start}s"
end

dict = Dict.new
time("create tire tree") do
  dict.parse
end

time("Trie test 1") do
  puts Grid.new(test_set_1, dict).search.inspect
end

time("Trie test 2") do
  puts Grid.new(test_set_2, dict).search.inspect
end

naive_dict = NaiveDict.new
time("create tire tree") do
  naive_dict.parse
end

time("Naive test 1") do
  puts Grid.new(test_set_1, naive_dict).search.inspect
end

time("Naive test 2") do
  puts Grid.new(test_set_2, naive_dict).search.inspect
end