Created
February 5, 2013 10:29
-
-
Save Davidslv/4713582 to your computer and use it in GitHub Desktop.
The Josephus Problem source: http://danvk.org/josephus.html Problem: "problem.rb:23:in `kill': stack level too deep (SystemStackError)"
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Person | |
attr_reader :position, :succ, :alive | |
attr_writer :position, :succ, :alive | |
# Everyone is alive, initially | |
def initialize(pos) | |
@position = pos | |
@alive = true | |
end | |
# For creating a linked chain of people | |
def createChain(n) | |
return self unless n>0 | |
@succ = Person.new(@position + 1) | |
@succ.createChain(n-1) | |
end | |
# Kill every nth person | |
# Current position in the cycle is pos | |
# there are remaining people remaining | |
# Stop killing if we're the last one. | |
def kill(pos,nth,remaining) | |
return @succ.kill(pos,nth,remaining) if !@alive | |
return self if (remaining == 1) | |
if pos == nth | |
@alive = false | |
puts self | |
pos = 0 | |
remaining-=1 | |
end | |
@succ.kill(pos+1,nth,remaining) | |
end | |
# Information about this person | |
def to_s | |
"Person \##@position, #{@alive ? 'alive' : 'dead'}" | |
end | |
end | |
# Set n to anything much higher (like 10, say) | |
# And the program hangs, or has an "Illegal Instruction" | |
n = 150 | |
first = Person.new(1) | |
last = first.createChain(n-1) | |
last.succ = first | |
winner = first.kill(1,3,n) | |
# If I use puts "Winner: " + winner, I get an error: | |
# in `+': failed to convert Person into String (TypeError) | |
#puts "Winner: " + winner | |
puts "Winner: ", winner |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment