1#!/usr/bin/env ruby
  2
  3def assert_equal(expected, actual)
  4  raise "expected: #{expected.inspect}, actual: #{actual.inspect}" unless expected == actual
  5end
  6
  7LETTER_DIGIT_MAPPING = {
  8  'a' => 2,
  9  'b' => 2,
 10  'c' => 2,
 11  'd' => 3,
 12  'e' => 3,
 13  'f' => 3,
 14  'g' => 4,
 15  'h' => 4,
 16  'i' => 4,
 17  'j' => 5,
 18  'k' => 5,
 19  'l' => 5,
 20  'm' => 6,
 21  'n' => 6,
 22  'o' => 6,
 23  'p' => 7,
 24  'q' => 7,
 25  'r' => 7,
 26  's' => 7,
 27  't' => 8,
 28  'u' => 8,
 29  'v' => 8,
 30  'w' => 9,
 31  'x' => 9,
 32  'y' => 9,
 33  'z' => 9,
 34}
 35
 36DIGIT_TO_LETTER = {
 37  2 => 'abc',
 38  3 => 'def',
 39  4 => 'ghi', 
 40  5 => 'jkl', 
 41  6 => 'mno', 
 42  7 => 'pqrs', 
 43  8 => 'tuv', 
 44  9 => 'wxyz',
 45}
 46
 47class Node
 48  attr_reader :value, :children
 49
 50  def initialize(value, children = [])
 51    @value = value
 52    @children = children
 53  end
 54
 55  def inspect
 56    "(#{value},#{children.map(&:inspect).join(",")})"
 57  end
 58end
 59
 60def trie_from(words)
 61  trie = {}
 62  words.each do |word|
 63    current = trie
 64    word.chars.each do |char|
 65      current[LETTER_DIGIT_MAPPING[char]] ||= {}
 66      current = current[LETTER_DIGIT_MAPPING[char]]
 67    end
 68    if !current.key?(-1)
 69      current[-1] = [word]
 70    else
 71      current[-1] << word
 72    end
 73  end
 74  return trie
 75end
 76
 77def words_from(trie, digits)
 78  return [] if digits.empty?
 79  current = trie[digits.shift]
 80  return [] if current.nil?
 81
 82  matches = []
 83  until digits.empty?
 84    digit = digits.shift
 85    current = current[digit]
 86    break if current.nil?
 87
 88    if current.key?(-1)
 89      matches << current[-1]
 90    end
 91  end
 92  return matches.flatten
 93end
 94
 95def solution(input_digits, valid_words)
 96  trie = trie_from(valid_words)
 97  matches = []
 98
 99  tail = 0
100  until tail == input_digits.length do
101    window = input_digits[0..tail]
102    words = words_from(trie, window)
103    matches << words unless words.empty?
104    tail += 1
105  end
106  return matches.compact
107end
108
109assert_equal [["act"], ["bat"], ["cat"]], solution([2, 2, 8], ["act", "bat", "cat", "acd", "test"])