Stack level too deep (SystemStackError) on recursive condition

Ruby
1

Hi guys,

I am new to Ruby and try to learn it. I have problem that I am stuck with on one of the conditions. This is my code:

def check_trip(start, target, stations, station_links, result = "Impossible" )
  station_links.each_pair do |key, value| 
    if value.include?(target) 
       return "Possible" if key == start    #why return don't work?  
       result = check_trip(start, key, stations, station_links)
    end
  end
  result
end



stations = ["ADL", "MEL", "SYD", "BRI"]
links = {"ADL" => ["MEL"], "MEL" => ["ADL", "SYD"],  "SYD" => ["BRI"]}
links.default = []
check_trip( "ADL", "BRI", stations, links )
check_trip( "MEL", "BRI", stations, links )
check_trip( "SYD", "ADL", stations, links )

The first 2 conditions are returning OK but the last one gets in stuck level too deep. Sorry if this is a dumb question for you guys.

Thanks!

2

Hi,
I’m looking this over and first want to be sure I understand:
All 3 of the test cases you ran should return “Impossible”, is that right?

check_trip( "ADL", "BRI", stations, links )
check_trip( "MEL", "BRI", stations, links )
check_trip( "SYD", "ADL", stations, links )
3

looks like you need a check for the stations you’ve visited, there’s a cycle in last run of check_trip

4 
def check_trip(start, target, path, station_links, result = "Impossible" )
  station_links.each_pair do |key, value| 
    if  value.include?(target) 
       return "Possible" if key == start    #why return don't work?  
        unless path.include?(key) 
           result = check_trip(start, key, path+[key],station_links)
	end
    end
  end
  result
end
check_trip( "SYD", "ADL",  [] , links )

Here, a Djiskra-like algo :

def check_trip2(start, target, station_links)
  mark={start => true}
  begin 
	  touch=false
	  station_links.each {|beg,aend| aend.each {|e|
		 if mark[beg] && ! mark[e]
		   return("possible") if e==target
		   mark[e]=true
		   touch=true
		 end
	  }}
      return("impossible") unless touch
  end while true
end

and some benchmark :

links = {"ADL" => ["MEL"], "MEL" => ["ADL", "SYD"],  "SYD" => ["BRI"]}
links.default = []
p    check_trip( "ADL", "BRI",  [], links )
p	check_trip( "MEL", "BRI",  [],links )
p	check_trip( "SYD", "ADL",  [],links )
puts ""
p	check_trip2( "ADL", "BRI",  links )
p	check_trip2( "MEL", "BRI",  links )
p	check_trip2( "SYD", "ADL",  links )	
p Benchmark.realtime {
  1000_000.times {
    check_trip( "ADL", "BRI",  [], links )
	check_trip( "MEL", "BRI",  [],links )
	check_trip( "SYD", "ADL",  [],links )
}}
puts ""
p Benchmark.realtime {
  1000_000.times {
	check_trip2( "ADL", "BRI",  links )
	check_trip2( "MEL", "BRI",  links )
	check_trip2( "SYD", "ADL",  links )
}}

ruby w.rb
“Possible”
“Possible”
“Impossible”

“possible”
“possible”
“imposssible”

10.47125145001337
14.99042987904977

5

You can use this for optimize ruby tail recursion :

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,
  trace_instruction: false
}

I try your code with optimize, for big graph :

links= {}
def sn(r,c) "#{r}/#{c}" end
N=350
N.times.each_cons(2) {|_r,r| N.times.each_cons(2) {|_c,c| 
 ns=sn(_r,_c)
 ne=sn(r,c)
 n2=sn(_r,c)
 n3=sn(r,_c)
 links[ns]=  ((links[ns]||[])+[n2,n3]).shuffle
 links[n2]=  ((links[n2]||[])+[ne]).shuffle
}} 

NN=N-1
p check_trip( sn(0,0), sn(NN,NN),  [sn(NN,NN)], links )

that’s work !