Skip to content

Instantly share code, notes, and snippets.

@m0dd3r
Created June 12, 2015 00:23
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save m0dd3r/34ad41886ff58a88b3fe to your computer and use it in GitHub Desktop.
Save m0dd3r/34ad41886ff58a88b3fe to your computer and use it in GitHub Desktop.
monad based floyd cycle detection
require_relative 'linked_list_node'
Maybe = Struct.new(:value) do
def and_then(&block)
if value.nil?
Maybe.new(nil)
else
block.call(value)
end
end
def method_missing(*args, &block)
and_then do |value|
Maybe.new(value.public_send(*args, &block))
end
end
end
def is_infinite?(list_node)
return false unless list_node
tortoise = Maybe.new(list_node)
hare = tortoise.next_node
floyd(tortoise, hare)
end
def floyd(tortoise, hare)
return false if tortoise.value.nil? || hare.value.nil?
return true if tortoise == hare
return floyd(tortoise.next_node, hare.next_node.next_node)
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment