1description =<<-DOC
  2Given two words, beginWord and endWord, and a wordList of approved words, find the length of the shortest transformation sequence from beginWord to endWord such that:
  3
  4Only one letter can be changed at a time
  5Each transformed word must exist in the wordList.
  6Return the length of the shortest transformation sequence, or 0 if no such transformation sequence exists.
  7
  8Note: beginWord does not count as a transformed word. You can assume that beginWord and endWord are not empty and are not the same.
  9
 10Example
 11
 12For beginWord = "hit", endWord = "cog", and wordList = ["hot", "dot", "dog", "lot", "log", "cog"], the output should be
 13wordLadder(beginWord, endWord, wordList) = 5.
 14
 15The shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog" with a length of 5.
 16
 17Input/Output
 18
 19[time limit] 4000ms (rb)
 20[input] string beginWord
 21
 22Guaranteed constraints:
 231 ≤ beginWord.length ≤ 5.
 24
 25[input] string endWord
 26
 27Guaranteed constraints:
 28endWord.length = beginWord.length.
 29
 30[input] array.string wordList
 31
 32An array containing all of the approved words. All words in the array are the same length and contain only lowercase English letters. You can assume that there are no duplicates in wordList.
 33
 34Guaranteed constraints:
 352 ≤ wordList.length ≤ 600,
 36wordList[i].length = beginWord.length.
 37
 38[output] integer
 39
 40An integer representing the length of the shortest transformation sequence from beginWord to endWord using only words from wordList as described above.
 41DOC
 42
 43describe "word_ladder" do
 44  def match?(word, other)
 45    failures = 0
 46    word.size.times do |n|
 47      if word[n] != other[n]
 48        failures += 1
 49        return false if failures > 1
 50      end
 51    end
 52    true
 53  end
 54
 55  # use a queue to do a breadth (level) first search.
 56  def word_ladder(words, begin_word:, end_word:)
 57    queue = [word: begin_word, level: 1]
 58    words.delete(begin_word)
 59    until queue.empty?
 60      top = queue.shift
 61      return top[:level] if top[:word] == end_word
 62
 63      words.dup.each do |word|
 64        if match?(top[:word], word)
 65          queue.push(word: word, level: top[:level] + 1)
 66          words.delete(word)
 67        end
 68      end
 69    end
 70    0
 71  end
 72
 73  it do
 74    words = ["hot", "dot", "dog", "lot", "log"]
 75    expect(word_ladder(words, begin_word: "hit", end_word: "cog")).to eql(0)
 76  end
 77
 78  it do
 79    words = ["hot", "dot", "dog", "lot", "log", "cog"]
 80    expect(word_ladder(words, begin_word: "hit", end_word: "cog")).to eql(5)
 81  end
 82
 83  it do
 84    expect(word_ladder(["a", "b", "c"], begin_word: "a", end_word: "c")).to eql(2)
 85  end
 86
 87  it do
 88    expect(word_ladder(["hot", "dog"], begin_word: "hot", end_word: "dog")).to eql(0)
 89  end
 90
 91  it do
 92    words = ["hot", "dog", "cog", "pot", "dot"]
 93    expect(word_ladder(words, begin_word: "hot", end_word: "dog")).to eql(3)
 94  end
 95
 96  it do
 97    words = ["hot", "cog", "dot", "dog", "hit", "lot", "log"]
 98    expect(word_ladder(words, begin_word: "hit", end_word: "cog")).to eql(5)
 99  end
100
101  it do
102    words = ["most", "fist", "lost", "cost", "fish"]
103    expect(word_ladder(words, begin_word: "lost", end_word: "cost")).to eql(2)
104  end
105
106  it do
107    words = ["talk", "tons", "fall", "tail", "gale", "hall", "negs"]
108    expect(word_ladder(words, begin_word: "talk", end_word: "tail")).to eql(0)
109  end
110
111  it do
112    words = ["peale", "wilts", "place", "fetch", "purer", "pooch", "peace", "poach", "berra", "teach", "rheum", "peach"]
113    expect(word_ladder(words, begin_word: "teach", end_word: "place")).to eql(4)
114  end
115
116  it do
117    words = ['chai', 'chat', 'coat', 'cost', 'cast', 'case', 'came', 'tame']
118    expect(word_ladder(words, begin_word: "chai", end_word: "tame")).to eql(8)
119  end
120end