Daniel Carrera

The Josephus problem in Perl 6, Python and Ruby

In today’s post, I would like to compare the OOP syntax of Perl 6, Python and Ruby. To this effect, I decided to show you an implementation of the Josephus problem in each language. Wikipedia describes the Josephus problem:

There are people standing in a circle waiting to be executed. After the first man is executed, certain number of people are skipped and one man is executed. Then again, people are skipped and a man is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last man remains, who is given freedom. The task is to choose the place in the initial circle so that you survive (are the last one remaining).

The problem is named after Flavius Josephus, a Jewish historian living in the 1st century. As the legend goes, he and his 40 comrade soldiers were trapped in a cave, surrounded by Romans. They chose suicide over capture and decided that they would form a circle and start killing themselves using a step of three. As Josephus did not want to die, he was able to find the safe place, and stayed alive.

Acknowledgement

The idea to use the Josephus problem to compare these languages is not my own. The idea comes from danvk.org who used it to compare Perl 5, Python and Ruby. I have copied his Python and Ruby code and I added the Perl 6 code of my own.

A quick note

I have tried to normalize the code as much as possible, so that you can get a better impression of the OOP syntax in each language. I will not benchmark the code, and I will keep my commentary to a minimum. The idea is that you see the OOP syntax of each language, with minimum influence from me.

Writing the class

Perl 6 (tested with Rakudo)

class Person {
	# $. means "public", "is rw" means it is writable.
	has ($.position, $.succ is rw);
	has $.alive is rw = True;

	# Stringify
	method Str() {
		"Person $.position, " ~ ($.alive ?? "alive" !! "dead")
	}
	# Create a linked chain of people.
	method createChain($n) {
		return self unless $n > 0;
		$.succ = Person.new(position => $.position + 1);
		$.succ.createChain($n-1);
	}
	# Kill every nth person. Stop killing if I'm the last one.
	method kill($pos is rw, $n, $remaining is rw) {
		return $.succ.kill($pos, $n, $remaining) if !$.alive;
		return self if $remaining == 1;

		if $pos == $n {
			$.alive = False;
			$pos = 0;
			$remaining -= 1;
		}
		$.succ.kill($pos+1,$n, $remaining);
	}
}

Python (tested with 2.5.2)

class Person:
	# Initialize
	def __init__(self,pos):
		self.position = pos
		self.alive = True

	# Stringify
	def __str__(self):
		status = "alive" if self.alive else "dead"
		return "Person #%d, %s" % (self.position, status)

	# Create a linked chain of people.
	def createChain(self,n):
		if n > 0:
			self.succ = Person(self.position+1)
			return self.succ.createChain(n-1)
		else:
			return self

	# Kill every nth person. Stop killing if I'm the last one.
	def kill(self,pos,n,remaining):
		if not self.alive:
			return self.succ.kill(pos,n,remaining)
		if remaining == 1:
			return self
		if pos == n:
			self.alive = False
			pos = 0
			remaining -= 1
		return self.succ.kill(pos+1,n,remaining)

Ruby (tested with 1.8.7)

class Person
	# Accessor and mutator methods
	attr_reader :position, :succ, :alive
	attr_writer :position, :succ, :alive

	# Initialize
	def initialize(pos)
		@position = pos
		@alive = true
	end
	# Stringify
	def to_s
		"Person \##@position, #{@alive ? 'alive' : 'dead'}"
	end
	# Create 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. Stop killing if I'm the last one.
	def kill(pos,n,remaining)
		return @succ.kill(pos,n,remaining) if !@alive
		return self if (remaining == 1)

		if pos == n
			@alive = false
			pos = 0
			remaining -= 1
		end
		@succ.kill(pos+1,n,remaining)
	end
end

Comments

All three classes are straight forward, and almost exactly the same size. Perl 6 is a bit shorter, but the differences are insignificant:

* Not including comments.

There are things I could have done to make each language shorter, but my goal was to make each code sample clear and legible. Besides, you shouldn’t pick a language because you can save 3 lines of code. It makes more sense to see if you like the syntax and the over-all “feel” of the language, and that is a much more personal decision.

On a personal note, I don’t like the Python syntax as much… passing “self” explicitly, double underscores… it feels a bit hackish, but that’s just me. In turn, I like the Ruby and Perl 6 syntax. I can’t decide which I like better. Both look very clean and very clear.

Using the classes

Finally, this is how you would use these classes:

Perl 6

my $orig = 40;
my $nth = 3;

my $first = Person.new(position => 1);
my $last = $first.createChain($orig-1);
$last.succ = $first;

my $winner = $first.kill(1,$nth,$orig);
say "Winner: ", $winner;

Python

orig = 40
nth = 3

first = Person(1)
last = first.createChain(orig-1)
last.succ = first

winner = first.kill(1,nth,orig)
print "Winner: ", winner

Ruby

orig = 40
nth = 3

first = Person.new(1)
last  = first.createChain(orig-1)
last.succ = first

winner = first.kill(1,nth,orig)
puts "Winner: " + winner.to_s