2
\$\begingroup\$

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)  
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Quentin Pradet Apr 30 '12 at 9:12
  • \$\begingroup\$ @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 \$\endgroup\$ – Luigi Plinge Apr 30 '12 at 18:37
  • \$\begingroup\$ I think their "point" is that they run concurrently in separate threads although that's of little use in this problem \$\endgroup\$ – Luigi Plinge Apr 30 '12 at 18:43
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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)
    }
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.