ProjectEuler#84 : monopoly game in Scala

In the last weeks, I slowed down my completion rate of Project Euler's problems a lot. But yesterday, looking for something to do for the last days of Christmas's holidays, I found the #84 problem which seemed quite fun: the goal is to find what are the 3 most visited squares in the game if we played with 4 sided dices in place of the common 6 sided ones.

It's interesting, because it's a probabilistic problem, and I'm lame in proba. So, as the problem does not require too much precision (at contrary to problem #213...), I could solve it in a monte-carlo way. This is the kind of proba solving method that suits me the best, because no proba are used...

As always, it was really simple to express the solution I imagine in Scala, and that's the result.

Be careful ! If you play at Project Euler, the following contains a solution that you may prefer to find by yourself !

/*
 * This is the companion object of our Monopoly class, it's the
 * place where we put all the common and side stuff, 
 * the board definition and our Random number generator
 * definition, for example. 
 */
object Monopoly {
  /*
   * The monopoly board 
   * (yes, we could have just use the square numbers,
   * but I found that clearer at the begining, and the overhead is
   * really small)
   */
  val board = Array(
    "GO"  , "A1", "CC1", "A2" , "T1", "R1", "B1" , "CH1", "B2", "B3", 
    "JAIL", "C1", "U1" , "C2" , "C3", "R2", "D1" , "CC2", "D2", "D3",
    "FP"  , "E1", "CH2", "E2" , "E3", "R3", "F1" , "F2" , "U2", "F3",
    "G2J" , "G1", "G2" , "CC3", "G3", "R4", "CH3", "H1" , "T2", "H2"   
  )

  /*
   * Match a case name to it's number
   */
  val reverseBoard = {
    var m = Map[String,Int]()
    for(i <- 0 until board.size) m = m.+((board(i) , i))
    m
  }

  abstract class Random {
    def next : Int
  }

  /*
   * A simple homothetie from int's range to a new one range,
   * used to transform Random to dice roll
   */
  def randomInRange(start:Int,end:Int, random: Random) : Int = {
    //that was funny to set up, there was some intersting
    //overflow and int division to take care of ;)
    val i = start +
      ((random.next.toFloat - Int.MinValue) * (end+1 - start) / 
         (Int.MaxValue.toFloat - Int.MinValue) ).toInt 
    if(i > end) end else if(i  }

  /*
   * Utility methods that sends three square back 
   */
  def goBack3(square:String) : String = {
    val i =  reverseBoard(square)
    if(i>2)board(i-3) else board(board.size+i-4)
  }

  /*
   * Utility method that given a square, 
   * return the next Railway Company square
   */
  def gotoNextR(square:String) : String = {
    val i =  reverseBoard(square)
    if(i>5 && i <= 15) "R2"
    else if(i>15 && i <= 25) "R3"
    else if(i>25 && i <= 35) "R4"
    else "R1"
  }

  /*
   * Utility method that given a square, 
   * return the next Utility company square
   */
  def gotoNextU(square:String) : String = {
    val i =  reverseBoard(square)
    if(i > 12 && i <= 28) "U2"
    else "U1"
  }
  
  /*
   * Represent a stack of cards, used for Communty cards and
   * Chance. 
   * We cycle throught an array to convey the idea that cards
   * are put back on the stack after use. 
   * 
   * Each "card" is a function that is awaiting for the real
   * square name to return the resulting square move. Most of
   * the card does nothing for us, so the function is identity
   * (return the square itself)
   */
  class CardStack(random: Random, private val size:Int) {
    protected val cards = new Array[String=>String](size)
    for(i <- 0 until size) cards(i) =  (square:String) => square
    private var index = 0
    private def rand = random

    def next(square:String) : String = {
      index = (index+1)%size
      cards(index)(square)
    }
  }

  /*
   * The class that represents the chance card heap.
   * Fairly random card distribution, 
   * see http://xkcd.com/221/ for more details
   */
  class CH(random: Random) extends CardStack(random,16) {
    cards(1) = gotoNextR _
    cards(2) = goBack3 _
    cards(4) = _ => "GO"
    cards(5) = _ => "R1"
    cards(7) = _ => "C1"
    cards(9) = _ => "H2"
    cards(10) = gotoNextR _
    cards(12) = _ => "JAIL"
    cards(14) = gotoNextU _
    cards(15) = _ => "E3"
  }

  /*
   * The class that represent the community chest card heap. 
   * Fairly random card distribution, 
   * see http://xkcd.com/221/ for more details (again)
   */
  class CC(random: Random) extends CardStack(random,16) {
    cards(4)  = _ => "GO"
    cards(10) = _ => "JAIL"
  }

  /*
   * A class that represents a pair of dices 
   * with a given number of faces
   * 
   * The only intersting thing to do with
   * is of course to roll them 
   * (with cards, dices and money involved, I can't 
   * understand where The Monopoly failed to be attractive).
   */
  class Dices(faces:Int,random: Random) {
    def roll = (
      randomInRange(1,faces,random),
      randomInRange(1,faces,random)
    )
  }
}  
  
/*
 * That's the actuall Monopoly representation. 
 * In our simplification of the Game, a
 * Monopoly has a pair of dices, a Community Chest
 * and a Chance heap of cards, a log of the number
 * of consecutive doubles, and a marker for the 
 * current position of the player (notice that as
 * there is only one player, the game should be
 * even less attractive than the real Mo,opoly...)
 * 
 * Nonetheless, we want to play to our game, so
 * we have a "turn" method that roll the dices and
 * move the player thanks to a "next square" method
 * processor. 
 * 
 * And that's all, our monopoly really looks like 
 * the real !
 */  
class Monopoly(faces:Int,random: Monopoly.Random) {
  import Monopoly.{CC,CH,Dices}
  import Monopoly.{board=>B,reverseBoard=>RB}
  
  val dices = new Dices(faces,random)
  val cc = new CC(random)
  val ch = new CH(random)
  var doubles = 0
  var currentPosition = 0

  private def next(square:String) : String = {
    val s = square match {
      case "CC1" => cc.next(square)
      case "CC2" => cc.next(square)
      case "CC3" => cc.next(square)
      case "CH1" => ch.next(square)
      case "CH2" => ch.next(square)
      case "CH3" => ch.next(square)
      case "G2J" => "JAIL"
      case  _    => square
    }

    if(s == square) s
    else next(s)
  }
    
  /*
   * A turn starts at one square and end on another,
   * perhaps passing on several other squares
   */
  def turn() : String = {
    val d = dices.roll
    
    var newSquare = next(
      B((currentPosition+d._1+d._2)%B.size ))
    
    //3 consecutive double send to Jail
    if(d._1 == d._2) {
      doubles = doubles+1
      if (doubles >= 3) {
        doubles = 0
        newSquare = "JAIL"
      }
    } else doubles = 0
    
    currentPosition = RB(newSquare)      
    newSquare
  }
}
  
/*
 * Now that we can have a Monopoly, 
 * we game play a party ! 
 * In Scala, party are called "application", 
 * but it's because software developper are
 * known to be dull people. 
 */  
object Problem85 extends Application {
  import Monopoly.{reverseBoard=>RB}

  /*
   * We want to observe the evolution of
   * the game, so we define a Logger
   * (I'm sooooo unsurprising)
   */
  abstract class Logger {
    def register(square:String)
  }

  /*
   * A looger that just output to console,
   * used at the begining, to see the player
   * evolves...
   */
  trait ConsoleLogger extends Logger {
    override def register(s:String) = println(s)
  }

  /*
   * ... and was quickly replaced by a logger that
   * just keep everything in a map, not that
   * it was boring... Well, actually, it was.
   */
  trait MapLogger extends Logger {
    var map = new HashMap[String,Int]()
    override def register(s:String) { 
      /*
       * ** Note to Java developpers **
       * look how it's easy to say 
       * "I want to retrieve a key value
       * from my map, but if the key does 
       * not exists, defined it with the 
       * given default value" in Scala. 
       * Just think to the number of if, and
       * brackets and the like in Java...
       */
      map(s) = map.getOrElse(s,0) + 1
    }
  }

  /*
   * Aaaaaahhhhhhh ! At last, there is our Game !
   * It's defined with a random generator, the number
   * of face we want our dices to have (remember, 
   * that's actually the point of the problem...), and
   * a limit number.
   * 
   * The limit number is the number of turn that our 
   * game will play before stoping (and we, look to
   * the results). As we are in a Monte Carlo similution,
   * this number will have to be HUGE. Say ONE MILLION !
   * Ok, that's ridiculously small, but thanks to the
   * kindness of project Euler team, the number converge 
   * quickly, and my PC is not as fast as clusters used
   * for real Monte Carlo simulation, 
   * so it will have to do ;)
   */
  abstract class Game(
    faces:Int, 
    random: Monopoly.Random, 
    limit:Int) extends Logger {
    
    val monopoly = new Monopoly(faces,random)
    var square = ""
    var turn = 0
    
    def start = {
      while(turn < limit) {
        this.register(monopoly.turn())
        turn = turn + 1
      }
    }
  }

  /*
   * Oups, don't forget to actually get a random
   * generator. As explained for the Game, we don't
   * need something too sophisticated for this
   * simple example. We may have taken 
   * http://www.honeylocust.com/RngPack/ for a
   * better pseudo-random generator (for example).
   */
  class JavaSimpleRandom extends Monopoly.Random {
    val r = new scala.util.Random()
    override def next = r.nextInt
  }
  
  /* ============================= */
  /*        Actual test            */
  /* ============================= */
  
  val r = new JavaSimpleRandom()
  val rounds = 1000000
  val test = new Game(4,r,rounds) with MapLogger

  print("begins... ")
  test.start
  println("results:")
  val a = test.map.toList.sort( 
    ( x:(String,Int), y:(String,Int) ) => x._2 > y._2)
  for(i <- 0 until 5) {
    println("%5s (%02d): %s".
      format(
        a(i)._1,
        RB(a(i)._1), 
        a(i)._2.toFloat/rounds)
    )
  }
}

Voilà !