Scala: Josephus problem with Actors

Question

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
 receive {
 // last man standing
 case (_, Self) => {
 println("Winner: "+id)
 sys.exit(0)
 } 
 // kill self
 case (x: Int, _) if x == step => {
 alive = false
 reply {next}
 }
 // 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 =>
 // add reference to successor
 p.next = p.id match { 
 case N => acts(0)
 case x => acts(x)
 }
 p.start()
 }
 acts(0) ! (1, null) 
}

• Quentin Pradet: 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.
• Luigi Plinge: @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: I think their "point" is that they run concurrently in separate threads although that's of little use in this problem

Answer 1

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)

Answer 2

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) {
 receive {
 // last man standing
 case (_, Self) => println("Winner: "+id); sys.exit(0)
 // kill self
 case (`step`, _) => alive = false; reply {next}
 // receive killed 
 case p: Person => next = p; next ! (1, Self)
 // pass on message
 case (x: Int, _) => next ! (x + 1, Self)
 case other => println(id + " unrecognized message: " + other)
 }
 }
}