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à !
