Stack Overflow on OJ for Ruby implementation, works locally


  • 0
    D

    I wrote dfs abstract answer to work for any graph and any way of finding edges. The algorithm is the same as other dfs searches that have passed (or at least it's supposed to be), and it works locally, but OJ is giving me a stack level too deep error for the n = 2000 case. Algorithm problem or problem with OJ?

    require 'set'
    def can_finish(num_courses = 0, prerequisites = [])
      graph = calculate_prerequisites(num_courses, prerequisites)
      !CycleFinder.new((0...num_courses), Proc.new { |num| graph[num] }).has_cycle?
    end
    
    def calculate_prerequisites(num_courses, prerequisites)
      Array.new(num_courses).map { [] }.tap do |graph| #OJ seems to be finnicky with Array.new(n) { [] }
        prerequisites.uniq.each { |course, pre| graph[pre] << course }
      end
    end
    
    class CycleFinder
      attr_reader :nodes
      def initialize(nodes, calculate_children_proc)
        @nodes = nodes
        @calculate_children = calculate_children_proc
      end
    
      def calculate_children(node)
        @calculate_children.call(node)
      end
    
      def has_cycle?
        visited = Set.new
        complete = Set.new
        recur = generate_find_cycle_proc(visited, complete)
        nodes.each do |node|
          if !visited.include?(node)
            visited << node
            return true if recur.call(node)
          end
          complete << node
        end
        false
      end
    
      def generate_find_cycle_proc(visited, complete)
        recur = lambda do |start_node|
          calculate_children(start_node).each do |child|
            if visited.include?(child)
              return true unless complete.include?(child)
            else
              visited << child
              return true if recur.call(child)
              complete << child
            end
          end
          false
        end
      end
    end

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.