Commit a75d60b

@@ -13,6 +13,7 @@
 # it.
 #
 # See http://rubydoc.info/gems/rspec-core/RSpec/Core/Configuration
+require 'byebug'
 RSpec.configure do |config|
   # rspec-expectations config goes here. You can use an alternate
   # assertion/expectation library such as wrong or the stdlib/minitest

@@ -48,18 +48,16 @@ describe "word_ladder" do
     matching >= length - 1
   end
 
+  # use a queue to do a breadth (level) first search.
   def word_ladder(words, begin_word:, end_word:)
-    return 0 if words.empty?
-    return 0 if begin_word == end_word
-
-    words.each do |word|
-      if begin_word == word
-        remaining = words - [begin_word]
-        return word_ladder(remaining, begin_word: word, end_word: end_word)
-      end
-      if match?(begin_word, word)
-        remaining = words - [begin_word]
-        return word_ladder(remaining, begin_word: word, end_word: end_word) + 1
+    queue = [word: begin_word, level: 1]
+    words.delete(begin_word)
+    until queue.empty?
+      top = queue.shift
+      return top[:level] if top[:word] == end_word
+
+      words.each do |word|
+        queue.push(word: word, level: top[:level] + 1) if match?(top[:word], word)
       end
     end
     0

@@ -2,3 +2,4 @@
 source "https://rubygems.org"
 
 gem 'rspec'
+gem 'byebug'

@@ -1,6 +1,7 @@
 GEM
   remote: https://rubygems.org/
   specs:
+    byebug (9.0.6)
     diff-lcs (1.3)
     rspec (3.6.0)
       rspec-core (~> 3.6.0)
@@ -20,6 +21,7 @@ PLATFORMS
   ruby
 
 DEPENDENCIES
+  byebug
   rspec
 
 BUNDLED WITH