My first Tail Recursive Ruby script

path_finder.rb

# Tail Recursive
# A to Z path finder

def path_finder(arr, n = nil)
  arr = arr.dup
  n ||= Array(arr.shift)
  val = arr.shift
  if n.last.last == val.first
    path_finder(arr, n << val)
  elsif arr.any? {|b| n.last.last == b.first}
    path_finder(arr.push(val), n)
  else
    n
  end
end

y = ["AB", "BC", "BZ", "DG", "AZ", "CG", "GZ", "DG", "DK", "AH", "EH"]

path_finder(y)
#  => ["AB", "BC", "CG", "GZ"] 

Here are some optimizations I found while playing with your script:

def self.path_finder(arr, n = nil)
  # If we can rely on #path_finder only being called with an n argument in the
  # recursive case (AKA no library user will be calling this method with a given
  # n argument), then we only need to dupe arr when no n is given, otherwise we
  # already own the arr Array and don't need to dupe it and can save a lot of time.
  arr = arr.dup unless n

  # Over 10M trials, I found Array#slice! to be ever so slightly faster
  # than Kernel#Array.
  n ||= arr.slice!(0, 1)
  val = arr.shift

  # Switched from ActiveSupport provided String#last to simple Array element
  # reference. This reduces the external dependencies of this library, but also
  # reduces semantic readability. I didn't test it, but I also suspect that
  # normal Array element reference is faster than String#last, if only very
  # slightly.
  #
  # Also, I pulled out the final character of the last link in the chain into a
  # temporary variable. Because this value could be referenced n times, this
  # saves us a lot of unnecessary look ups.
  tail = n[-1][-1]
  if tail == val[0]
    # Switched from n << val to n.push(val) for consistency
    path_finder(arr, n.push(val))
  elsif arr.any? {|b| tail == b[0]}
    path_finder(arr.push(val), n)
  else
    n
  end
end

You are likely already aware of this, though it may be worth adding to the gist for the benefit of other readers, but tail recursion is not enabled in the RubyVM by default and must be explicitly turned on:

RubyVM::InstructionSequence.compile_option = {
  :tailcall_optimization => true,
}

You can read more about Tail Call Optimization in Ruby here. I didn't find enabling tail call optimization to make a significant difference with the given sample data, though it certainly improved things much more than swapping Kernel#Array with Array#slice!.

I hope this helps!

I really like your arr.dup unless n. And the use of tail is nice.

I wonder about possibly implementing more functionality with this method. For example all possible paths from A to Z, or shortest. Since "AZ" is one option that would be a simple test case to implement. But I wonder if that would be overkill for this.