Solving the Dominoes Exercism Problems with Active Patterns in F#

This is my solution implementation of the Dominoes problem on exercism.io using F#.

Edit: There is a slight problem with this solution (that I noticed right after I posted). An edge case that I failed to consider that requires a very quirky rewrite to fix. Leaving this solution up as I feel it still demonstrates a decent approach to solving the problem. Kudos to anyone who can spot the quirk though.

So what's the problem?

The original question is essentially, "Given a list of dominoes, can you determine if they can be matched or chained from end to end?"

We have to provide the interface canChain. canChain is a function that accepts a list of tuples representing a domino and returns true or false

let canChain dominoes : bool =
// to be implemented 

e.g. of chainable set

The dominoes

(2, 4)(2, 5)(3, 4)(3, 5)

can be "chained" to make

(3, 4)(4, 2)(2, 5)(5, 3).

so

canChain [(2, 4); (2, 5); (3, 4); (3, 5)] 
// true

e.g. of non-chainable set

The dominoes (2, 4)(2, 5)(6, 6)(3, 5) cannot be "chained because (6, 6) has no domino it can be paired with.

canChain [(2, 4); (2, 5); (6, 6); (3, 5)] 
// false

Additional stipulations

In additional, the problem imposes the following rules

An empty list is considered a valid chain.

canChain [] 
// true

A single domino is considered a valid chain only if it is a double (has the same number on both sides)

canChain [(3, 3)] 
// true

canChain [(3, 5)] 
// false 

The ends of the list must also be able to be joined

canChain [(3, 3); (3, 5); (5, 2); (2, 3)] 
// true

canChain [(3, 3); (3, 5); (5, 2); (2, 4)] 
// false

You may have multiple copies of the same domino in the list.

canChain [(3, 3); (3, 5); (5, 3); (3, 2); (2, 1); (1, 2); (2, 4)]
// true

Think about our solution

I would love to have the mathematical training to explicitly define my solution, but I don't so I'll attempt to briefly explain my methodology.

Base case: No doubles, no repeats

Let examine the simplest case. A sequence of normal dominoes (no doubles) with no repeats will match if there's an even number of every number represented on a domino. For example

[(3, 5); (2, 5); (2, 3)] resolves to two (3)s, two (2)s, and two (5)s. So we can say with certainty that this can be chained.

Compare this to [(3, 5); (2, 5); (2, 3); (4, 6); (3, 4)] has two (2)s, three (3)s, two (4)s, and one (6). This cannot pass because there will never be a match for the single (6), nor the third (3).

More complexity: Adding Doubles

Doubles presents an interesting case because adding doubles breaks our reasoning above.

[(3, 5); (2, 5); (2, 3); (6, 6)] has an even number of all digits but this clearly won't chain.

Luckily, if we separate doubles from the original normal theory, they actually integrate nicely. You see, doubles would like the right clause in an of function. So long as the number in the double can be found in the normal dominoes, a double can be added in with no effect on the result.

canChain [(3, 5); (1, 4); (4, 3); (1, 5); (5, 5); (4, 4);]
// true

canChain [(3, 5); (1, 4); (4, 3); (1, 5); (0, 0); (3, 3)]
// true

So now we can describe our algorithm as if all the numbers in normal dominoes have an even count, and all numbers in doubles are found in at least one normal, the dominoes are chainable.

Even more complexity, adding repeats

Repeats can cause our current implementation to fail in a similar way to doubles. If the numbers in the repeated dominoes are not represented in the normal dominoes, the sequence won't be chainable.

canChain [(3, 1); (1, 3); (4, 3); (4, 5); (5, 3)]
// true

canChain [(2, 1); (1, 2); (4, 3); (4, 5); (5, 3)]
// false

The answer luckily, is the same as with the double. We have to consider the repeats separately, and check to ensure that at least one of the numbers in a repeat are in the normal dominoes. If they are, the repeat passes.

In fact, it turns out that doubles are valid if they match with either normals or repeats.

Let's update our algorithm again. If all the numbers in normal dominoes have an even count, and all repeats have at least one number represented in normals, and all numbers in doubles are found in at least one normal or repeat, the dominoes are chainable.

Oops, one more edge case.

We've done well so far, but it turns out there's one more case we haven't considered.

What if there are no normals? What if we just have repeats and doubles? In that case, something slightly interesting happens. In the case of no normals, our repeats take the place of the normals as the dominant group. So long as each repeating pair have one matching number with another repeating pair, they are chainable. Double interaction remains the same.

canChain [(3, 1); (1, 3); (4, 3); (3, 4); (4, 4)]
// true

canChain [(2, 1); (1, 2); (4, 3); (4, 3); (4, 4)]
// false

So our final algorithm now becomes (including the smaller one off requirements), a sequence of dominoes is chainable if:

• The sequence is empty.
• The sequence has one Double
• The sequence has a set of pairs where each pair has a number shared by at least one other pair, and a set of doubles where the number in each double is shared by at least one pair.
• The sequence has a set of normal dominoes where every number in the set is represented in an even number of dominoes, a set of pairs where each pair has at least one number represented in the set of normals, and a set of doubles where each double's number is represented at least once in the set of pairs or normals.

Implementation

Finally from here we have everything we need to write the code to solve this problem. I've included a code snippet of the full solution below.

Note the type blob (I couldn't think of a better name at the time) that we've created to keep all the data we need to determine whether a list of tuples is valid.

type Blob = 
    { doubles: int list
      pairs: (int*int) list
      normals: Map<int, int> }

Our strategy will be:

• Sort the incoming tuple list
• Fold the list of tuples into a blob
• Match the blob with the right combination of cases to see if it represents a chainable domino stream.

Here's what the final solution looks like. Unfortunately walking through exactly how this code works is beyind the scope of this article, but I'm hoping that with the little walkthrough above, the intent of the implementation is clear.

// a type representing the data we need to see if a 
// list of dominoes is chainable.
type Blob = 
    { doubles: int list
      pairs: (int*int) list
      normals: Map<int, int> }

// the initial state of our blob
let emptyBlob = { doubles=[]; pairs=[]; normals=Map.empty }

// This is our suite of comparison functions.
// Each returns true or false and we will mix 
// and match them together in our checks for 
// valid chainable dominoes.
let (|EmptyBlob|) = (=) emptyBlob

let (|EmptyDoubles|) blob = blob.doubles = []
let (|EmptyPairs|) blob = blob.pairs = []
let (|EmptyNormals|) blob = Map.isEmpty blob.normals

let (|OneDouble|) blob = List.length blob.doubles = 1

let (|EvenNormals|) blob =
    blob.normals
    |> Map.forall (fun _ num -> num % 2 = 0)
    && Map.count blob.normals > 0

let (|DoublesMatchNormals|) blob =
    List.forall
    <| fun num -> Map.containsKey num blob.normals
    <| blob.doubles

let (|PairsMatchNormals|) blob =
    List.forall (fun (x, y) -> Map.containsKey x blob.normals 
                                || Map.containsKey y blob.normals )
    <| blob.pairs 

let (|PairsCombine|) blob =
    let canMatch (a, b) (c, d) = 
        a = c || a = d || b = c || b = d
    List.forall
    <| fun pair -> List.exists (canMatch pair) blob.pairs 
    <| blob.pairs

let (|DoublesMatchPairs|) blob =
    let canMatch z (x, y) = x = z || y = z
    List.forall 
    <| fun num -> List.exists (canMatch num) blob.pairs
    <| blob.doubles

let (|JustDomino|) =
    function
    | OneDouble true & EmptyPairs true & EmptyNormals true -> 
    | _ -> false

// This is the actual function that checks to see 
// if our blob is the right 'shape' that represents a
// chainable list of dominoes.
let isChain =
    function
    | EmptyBlob true -> true
    | JustDomino true -> true
    | DoublesMatchPairs true
        & PairsCombine true
        & EmptyNormals true -> true
    | EvenNormals true 
        & (DoublesMatchNormals true | DoublesMatchPairs true) 
        & PairsMatchNormals true -> true
    | _ -> false

let addKey blob key =
    let newValue = 
        if blob.normals.ContainsKey key then 
            (blob.normals.Item key) + 1
        else
            1
    Map.add key newValue blob.normals
    |> fun newNorms -> { blob with normals = newNorms }

// These functions update the three attributes of our blob. type correctly
let addNormal =
    List.fold addKey

let addDouble blob double =
    { blob with doubles = List.distinct <| double :: blob.doubles }

let addPair blob pair =
    { blob with pairs = List.distinct <| pair :: blob.pairs }

// We make heave use of active patterns like this
// to make our match statements more readable
let (|EmptyList|Double|Pair|Normal|) =
    function
    | [] -> EmptyList
    | (x, y) :: rest when x = y -> Double (x, rest)
    | a :: b :: rest when a = b -> Pair (a, rest)
    | (x, y) :: rest -> Normal ([x; y], rest)

// Our 'parser'.
// This converts our list of tuples to a single blob.
let rec parse state dominos =
    match dominos with
    | EmptyList -> state
    | Double (num, rest) -> parse (addDouble state num) rest 
    | Pair (domino, rest) -> parse (addPair state domino) rest
    | Normal (entries, rest) -> parse (addNormal state entries) rest

// Aligns all dominoes so their smallest value is on the left.
// This will help up when we need to check if two dominoes
// are the same.
let polarize ((x, y) as domino) =
    if x > y then (y, x) else domino

// The actual function we expose that puts everything
// above together.
let canChain =
    List.map polarize
    >> List.sort
    >> parse emptyBlob
    >> isChain