Project Firehose teasers

cycle_detection.rb

#
# I didn't take the time to implement floyd's algorithm, I just used a dirty "has this been visited before" scheme.
#
# It felt like cheating anyway since Floyd's (allegedly Floyd's?) algorithm is on the 
# page in Python and this isn't really just a "can you convert python to ruby" challenge
#
# But I also hadn't read about that algorithm before, so thanks for the interesting read!!
#


class LinkedListNode
  attr_accessor :value, :next_node

  def initialize(value, next_node=nil)
    @value = value
    @next_node = next_node
  end
end

VISITED = 'visited'

def is_list_infinite(head, objects_visited_so_far = {})
  # if we reach the end, there was no cycle, so report that it's not infinite
  return false if head.next_node.nil?;

  # if head has been visited before, report that yes, there is a loop
  return true if objects_visited_so_far[head.object_id] == VISITED;

  objects_visited_so_far[head.object_id] = VISITED;
  return is_list_infinite(head.next_node, objects_visited_so_far)
end

node1 = LinkedListNode.new(37)
node2 = LinkedListNode.new(99, node1)
node3 = LinkedListNode.new(12, node2)

raise "is_list_infinite not working" if is_list_infinite(node3) != false

nodeA = LinkedListNode.new(37)
nodeB = LinkedListNode.new(99, nodeA)
nodeC = LinkedListNode.new(12, nodeB)
nodeD = LinkedListNode.new(12, nodeC)
nodeE = LinkedListNode.new(8, nodeD)
nodeA.next_node = nodeE

is_list_infinite(nodeD)
raise "is_list_infinite not working" if is_list_infinite(nodeE) != true

reverse_linked_list_in_place.rb

def print_values(list_node)
  print "#{list_node.value} --> "
  if list_node.next_node.nil?
    print "nil\n"
    return
  else
    print_values(list_node.next_node)
  end
end

class LinkedListNode
  attr_accessor :value, :next_node

  def initialize(value, next_node=nil)
    @value = value
    @next_node = next_node
  end
end


def reverse_list(head, previous = nil)
  nextNode = head.next_node
  head.next_node = previous
  return head if nextNode.nil?
  return reverse_list(nextNode, head)
end

node1 = LinkedListNode.new(37)
node2 = LinkedListNode.new(99, node1)
node3 = LinkedListNode.new(12, node2)

print_values(node3)

nodeA = LinkedListNode.new(37)
nodeB = LinkedListNode.new(99, nodeA)
nodeC = LinkedListNode.new(12, nodeB)

print_values(reverse_list nodeC)

reverse_linked_list_with_stack.rb

def print_values(list_node)
  print "#{list_node.value} --> "
  if list_node.next_node.nil?
    print "nil\n"
    return
  else
    print_values(list_node.next_node)
  end
end

class LinkedListNode
  attr_accessor :value, :next_node

  def initialize(value, next_node=nil)
    @value = value
    @next_node = next_node
  end
end

class Stack
  attr_reader :data

  def initialize
    @data = nil
  end

  # Push an item onto the stack
  def push(element)
    @data = LinkedListNode.new(element, @data)
  end

  # Pop an item off the stack.
  # Remove the last item that was pushed onto the
  # stack and return it to the user
  def pop
    return nil if @data.nil?
    temp = @data.value
    @data = @data.next_node
    return temp
  end
end

# test the stack
stack = Stack.new
stack.push(4)
stack.push(5)
stack.push(6)
raise "Stack is broken" unless 6 == stack.pop()
raise "Stack is broken" unless 5 == stack.pop()
raise "Stack is broken" unless 4 == stack.pop()
raise "Stack is broken" unless nil == stack.pop()



def reverse_list(list)
  stack = Stack.new

  while list
    stack.push(list.value)
    list = list.next_node
  end

  stack.data
end

node1 = LinkedListNode.new(37)
node2 = LinkedListNode.new(99, node1)
node3 = LinkedListNode.new(12, node2)

print_values(node3)

nodeA = LinkedListNode.new(37)
nodeB = LinkedListNode.new(99, nodeA)
nodeC = LinkedListNode.new(12, nodeB)

print_values(reverse_list nodeC)