Skip to content

Project Euler Problem 90

November 25, 2012

Solving Project Euler Problem 90 in a pure functional manner is fun. First and foremost, when picking an approach, we may notice that there are only “6 of 10” different combinations exist for dices with numbers 0 to 9 on sides, which equals to 210. In turn, this gives only 44100 combinations for a pair of dices, so simple brute forcing the solution is feasible.

Let’s begin with the list of target squares. We represent it as a list squares of tuples (tens, ones) for all digit squares; also there is no need to differentiate 9 from 6, so the final list is

[(0, 1); (0, 4); (0, 6); (1, 6); (2, 5); (3, 6); (4, 6); (6, 4); (8, 1)]. This list is the key piece of function isValidArrangement that for two sets of digits representing a dice sides each determines if all elements of squares list can be represented by pair of sides given as arguments.

Then, function combinations yields all combinations of the given size from the given list ls, i.e. all possible dice side lists allDices would be contained in combinations 6 [0..9]. Finally, as we want to represent a dice as a set of its sides with the help of function asSetofSides we would turn 9 to 6 unless both these digits are present on the same dice.

The rest is trivial: build a sequence of all dice pairs allDicePairs where each pair is a tuple of side sets and count number of elements that are recognized as isValidArrangement. As each valid arrangement is duplicated by dice switch, the solution would be this number divided by 2.

let squares =
    [ for i in 1..9 -> i*i ]
    |> List.map (fun square -> let tens, ones = square/10, square%10 in
                                (tens, if ones = 9 then 6 else ones))

let isValidArrangement dice1 dice2 = 
    let rec scan = function
    | [] -> true
    | (tens,ones)::t -> if (Set.contains tens dice1 && Set.contains ones dice2) ||
                           (Set.contains tens dice2 && Set.contains ones dice1) then scan t
                        else false
    scan squares

let rec combinations size ls =
    let rec bead = function
    | [] -> []
    | h::t -> (h,t) :: [ for (l, ls) in bead t -> (l, ls) ]
    [match size with
     | 0 -> yield []
     | _ -> for (first, rest) in bead ls do
              for tail in combinations (size - 1) rest do
                  yield first::tail]                

let allDices = combinations 6 [0..9]

let asSetofSides dice =
    let sides = Set.ofList dice in
        if sides.Contains 9 && not (sides.Contains 6)
        then (sides.Remove 9).Add 6
        else sides

let allDicePairs = seq {
    for dice1 in allDices do
        for dice2 in allDices do
            yield (asSetofSides dice1, asSetofSides dice2)
    }

let problem090() =
    allDicePairs
    |> Seq.sumBy (fun (dice1, dice2) -> if isValidArrangement dice1 dice2 then 1 else 0)
    |> (/) <| 2
Advertisements

From → Project Euler

Leave a Comment

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: