Skip to content

Project Euler Problem 84

June 20, 2012

Project Euler Problem 84 is fun. Took some time to choose the approach to solve. After some amount of consideration I decided to go with straightforward MonteCarlo simulation.

The only mutable piece of information in the solution below is board array of counters, the rest is pure functional. The state is passed around as a 4-member tuple (boardPosition, chestCard, chanceCard, doubles) containing current main board position, community chest deck card position, chance deck card position, and subsequent double rolls.

Dices are rolled at rollDice function. If it anything, but triple double in row, the state is passed to ifChance function. There if the current position is on a chance square, chance is processed by processChanceCard, and then passed to ifChest, otherwise goes there directly. Similar approach is implemented for community chest squares with ifChest and processChestCard functions.

let [<Literal>]BOARDSIZE = 40
let [<Literal>]CCSIZE = 16
let [<Literal>]CHANCESIZE = 16
let [<Literal>]DICESIDES = 4

let [<Literal>]GO = 0
let [<Literal>]CC1 = 2
let [<Literal>]R1 = 5
let [<Literal>]CH1 = 7
let [<Literal>]JAIL = 10
let [<Literal>]C1 = 11
let [<Literal>]U1 = 12
let [<Literal>]R2 = 15
let [<Literal>]CC2 = 17
let [<Literal>]CH2 = 22
let [<Literal>]E3 = 24
let [<Literal>]R3 = 25
let [<Literal>]U2 = 28
let [<Literal>]G2J = 30
let [<Literal>]CC3 = 34
let [<Literal>]CH3 = 36
let [<Literal>]H2 = 39

let rand = System.Random()
let board = Array.zeroCreate<int> BOARDSIZE

type Doubles = ZeroDouble | OnceDouble | TwiceDouble

let nextRoll() = (rand.Next(DICESIDES) + 1, rand.Next(DICESIDES) + 1)

let (|Double|Ordinary|) roll =
    let sum = fst roll + snd roll in
    if fst roll = snd roll then Double sum else Ordinary sum

let forward boardPosition score = (boardPosition + score) % BOARDSIZE
    
let inc square =
    board.[square] <- board.[square] + 1

let processChestCard (boardPosition, chestCard, chanceCard, doubles) =
    let newChestCard = (chestCard + 1) % CCSIZE
    match newChestCard with
    | 0 -> inc GO; (GO, newChestCard, chanceCard, doubles)
    | 1 -> inc JAIL; (JAIL, newChestCard, chanceCard, doubles)
    | _ -> inc boardPosition; (boardPosition, newChestCard, chanceCard, doubles)

let ifChest (boardPosition, chestCard, chanceCard, doubles) =
    match boardPosition with
    | CC1 | CC2 | CC3 -> processChestCard (boardPosition, chestCard, chanceCard, doubles)
    | G2J -> inc JAIL; (JAIL, chestCard, chanceCard, doubles)
    | _ -> inc boardPosition; (boardPosition, chestCard, chanceCard, doubles)

let processChanceCard (boardPosition, chestCard, chanceCard, doubles) =
    let newChanceCard = (chanceCard + 1) % CHANCESIZE
    match newChanceCard with
    | 0 -> ifChest (GO, chestCard, newChanceCard, doubles)
    | 1 -> ifChest (JAIL, chestCard, newChanceCard, doubles)
    | 2 -> ifChest (C1, chestCard, newChanceCard, doubles)
    | 3 -> ifChest (E3, chestCard, newChanceCard, doubles)
    | 4 -> ifChest (H2, chestCard, newChanceCard, doubles)
    | 5 -> ifChest (R1, chestCard, newChanceCard, doubles)
    | 6 | 7 -> if boardPosition = CH1 then ifChest (R2, chestCard, newChanceCard, doubles)
               elif boardPosition = CH2 then ifChest (R3, chestCard, newChanceCard, doubles)
               elif boardPosition = CH3 then ifChest (R1, chestCard, newChanceCard, doubles)
               else ifChest (boardPosition, chestCard, newChanceCard, doubles)
    | 8 -> if boardPosition = CH2 then ifChest (U2, chestCard, newChanceCard, doubles)
           else ifChest (U1, chestCard, newChanceCard, doubles)
    | 9 -> ifChest (boardPosition - 3, chestCard, newChanceCard, doubles)
    | _ -> ifChest (boardPosition, chestCard, newChanceCard, doubles)

let ifChance (boardPosition, chestCard, chanceCard, doubles) =
    match boardPosition with
    | CH1 | CH2 | CH3 -> processChanceCard (boardPosition, chestCard, chanceCard, doubles)
    | _ -> ifChest (boardPosition, chestCard, chanceCard, doubles)

let rollDice (boardPosition, chestCard, chanceCard, doubles) =
    match nextRoll() with
    | Double score -> match doubles with
                      | ZeroDouble -> ifChance ((forward boardPosition score), chestCard, chanceCard, OnceDouble)
                      | OnceDouble -> ifChance ((forward boardPosition score), chestCard, chanceCard, TwiceDouble)
                      | TwiceDouble -> inc JAIL; (JAIL, chestCard, chanceCard, ZeroDouble)
    | Ordinary score -> ifChance ((forward boardPosition score), chestCard, chanceCard, ZeroDouble)
    
let problem084() =
    let _ = Seq.initInfinite id
            |> Seq.scan (fun (boardPosition, chestCard, chanceCard, doubles) x ->
                rollDice (boardPosition, chestCard, chanceCard, doubles)) (0,0,0,ZeroDouble)
            |> Seq.nth 1000000
    board
    |> Array.mapi (fun i x -> (-x,i))
    |> Array.sortBy(fun (x,y) -> x)
    |> Array.map (fun (x,y) -> y)
    |> Array.toSeq |> Seq.take 3
    |> Seq.fold (fun a x -> a + string x) ""

Few interesting F# features used are: active patterns for handling dice rolls, state passing thru arguments, literals for use in pattern matching. Also an interesting technique is applied with generation of potentially infinite sequence of states using Seq.scan function driven by simply infinite sequence of integers. Evaluating this state sequence to desired length yields the sought frequences for board squares.

Advertisements

From → F#, Project Euler

One Comment

Trackbacks & Pingbacks

  1. Project Euler Problem 85 « In F# Major

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: