#!/usr/bin/env ruby

def assert_equal(expected, actual)
  raise "expected: #{expected.inspect}, actual: #{actual.inspect}" unless expected == actual
end

LETTER_DIGIT_MAPPING = {
  'a' => 2,
  'b' => 2,
  'c' => 2,
  'd' => 3,
  'e' => 3,
  'f' => 3,
  'g' => 4,
  'h' => 4,
  'i' => 4,
  'j' => 5,
  'k' => 5,
  'l' => 5,
  'm' => 6,
  'n' => 6,
  'o' => 6,
  'p' => 7,
  'q' => 7,
  'r' => 7,
  's' => 7,
  't' => 8,
  'u' => 8,
  'v' => 8,
  'w' => 9,
  'x' => 9,
  'y' => 9,
  'z' => 9,
}

DIGIT_TO_LETTER = {
  2 => 'abc',
  3 => 'def',
  4 => 'ghi', 
  5 => 'jkl', 
  6 => 'mno', 
  7 => 'pqrs', 
  8 => 'tuv', 
  9 => 'wxyz',
}

class Node
  attr_reader :value, :children

  def initialize(value, children = [])
    @value = value
    @children = children
  end

  def inspect
    "(#{value},#{children.map(&:inspect).join(",")})"
  end
end

def trie_from(words)
  trie = {}
  words.each do |word|
    current = trie
    word.chars.each do |char|
      current[LETTER_DIGIT_MAPPING[char]] ||= {}
      current = current[LETTER_DIGIT_MAPPING[char]]
    end
    if !current.key?(-1)
      current[-1] = [word]
    else
      current[-1] << word
    end
  end
  return trie
end

def words_from(trie, digits)
  return [] if digits.empty?
  current = trie[digits.shift]
  return [] if current.nil?

  matches = []
  until digits.empty?
    digit = digits.shift
    current = current[digit]
    break if current.nil?

    if current.key?(-1)
      matches << current[-1]
    end
  end
  return matches.flatten
end

def solution(input_digits, valid_words)
  trie = trie_from(valid_words)
  matches = []

  tail = 0
  until tail == input_digits.length do
    window = input_digits[0..tail]
    words = words_from(trie, window)
    matches << words unless words.empty?
    tail += 1
  end
  return matches.compact
end

assert_equal [["act"], ["bat"], ["cat"]], solution([2, 2, 8], ["act", "bat", "cat", "acd", "test"])