Scala: Josephus problem with Actors

Another stab at the Josephus problem, this time using Actors. N people stand in a circle and every stepth person is eliminated until one is remaining.

The way I solve it here is to give each actor a reference to their successor, and the actors send their successor a count of places since the last elimination. If an actor is eliminated, it replies with a reference to its successor so that the previous actor now links the one after.

I've hardly used Actors before. I'd like general comments, but in particular I'm wondering:

• is using Actors appropriate for this problem?
• are the messages I used sensible?
• is the wait for reply necessary?
• how would you do it differently?

btw I'm going to try this with Akka as well - if that will make any major difference to the solution that you know of, please mention!

object Josephus_Actors extends App {
import actors._

val N = 40
val step = 3

case class Person(id: Int) extends Actor { Self =>
// would like to make next private[this], but it's then very tricky to set up
var next: Person = _
private[this] var alive = true
def act {
while (alive) {
// Messages consist of (count, sender) where count is distance from last man out
// last man standing
case (_, Self) => {
println("Winner: "+id)
sys.exit(0)
}
// kill self
case (x: Int, _) if x == step => {
alive = false
}
// kill next
case (x: Int, _) if x == step - 1 => {
// wait until we have received our next value
next !? ((step, Self)) match {
case a: Person => next = a
case _ =>
}
next ! (1, Self)
}
/* pass on message */
case (x: Int, _) => {
next ! (x + 1, Self)
}
case other => println(id + " unrecognized message: " + other)
}
}
}
}

val acts = 1 to N map Person
acts foreach { p =>
p.next = p.id match {
case N => acts(0)
case x => acts(x)
}
p.start()
}
acts(0) ! (1, null)
}

• It's a fun way to model the problem, sure. But it's probably more efficient to simply use a linked list for a naive implementation. Your wikipedia pages shows that the best solution uses dynamic programming and executes in O(n) time. So it's probably not appropriate, but a nice way to learn about actors. – Quentin Pradet Apr 30 '12 at 9:12
• @Cygal this should be O(n) too and acts very much like a linked list. Actors are quite lightweight although prob not so much as a collection node. To me sending messages seems like just an un-typesafe form of method invocation but it may just be that I don't understand them properly yet – Luigi Plinge Apr 30 '12 at 18:37
• I think their "point" is that they run concurrently in separate threads although that's of little use in this problem – Luigi Plinge Apr 30 '12 at 18:43

would like to make next private[this], but it's then very tricky to set up

To achieve that, you can define the initial next person as a lazy val field, and then define a var locally in the act method:

case class Person(id: Int) extends Actor { Self =>
private[this] lazy val initialNext: Person = acts((id + 1) % N)
...
def act {
var next = initialNext


The initialization then simplifies to

val acts = 1 to N map Person
acts foreach { _.start }
acts(0) ! (1, null)


You use in your solution a synchronous call (!?) which prevents the actor from doing something else while waiting (in this example, this is not a problem). You could easily implement a true asynchronous solution by reacting on persons sent back in case that a person killed itself. The act method then looks as follows:

def act {
var next = initialNext
while (alive) {
// last man standing
case (_, Self) => println("Winner: "+id); sys.exit(0)

// kill self
case (step, _) => alive = false; reply {next}