Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
My first Tail Recursive Ruby script
# 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"]
@tdg5

This comment has been minimized.

Copy link

@tdg5 tdg5 commented Jan 1, 2015

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!

@danielpclark

This comment has been minimized.

Copy link
Owner Author

@danielpclark danielpclark commented Jan 3, 2015

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.