# Project Euler Problem 90

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