Solving the game Set in F#

Question

I was playing the game Set online, and thought it would be a good exercise to write an F# script to find all of the sets for me.

The rules of set are as follows: A SET is 3 cards for which each feature is either common across all 3 cards or is different on each card. The object is to find all the SETs among the cards.

I started learning F# four days ago, so what I'm looking for are obvious/easy/"no duh" improvements. I've started at a low bar of just writing a function to compare a group of three cards, and tell you if those three cards form a set. You can see my first attempt below. It feels a bit clunky, like I'm not really making use of all that F# has to offer.

// Create a record type to represent each card
type Card =
    { Color: string
      Shape: string
      Pattern: string
      Number: int
    }

// Create some functions for comparing elements of a collection
let allEqual l = l |> Seq.pairwise |> Seq.forall (fun (x, y) -> x = y)
let allDifferent l = (l |> Seq.distinct |> Seq.length) = (Seq.length l)

// Combine them
let isSet l = (allEqual l) || (allDifferent l)

// The meat of this script
let compare card1 card2 card3 =
    // Put the cards together for easy iteration
    let cardList = [card1; card2; card3]

    // Check each field of the record to see if it makes a set
    let colorSet   = cardList |> List.map (fun c -> c.Color  ) |> isSet
    let shapeSet   = cardList |> List.map (fun c -> c.Shape  ) |> isSet
    let patternSet = cardList |> List.map (fun c -> c.Pattern) |> isSet
    let numsSet    = cardList |> List.map (fun c -> c.Number ) |> isSet

    // Check that they all make a set
    colorSet && shapeSet && patternSet && numsSet



// Test the functions out
let c1 = {Color = "blue"; Shape = "oval"; Pattern = "stripes"; Number = 3}
let c2 = {Color = "red";  Shape = "diamond"; Pattern = "solid"; Number = 2}
let c3 = {Color = "green";  Shape = "squiggle"; Pattern = "empty"; Number = 2}

let areCardsSet = compare c1 c2 c3
printfn "The cards c1, c2, and c3 are a set? %b" areCardsSet

Answer 1

Well, you're off to a good start, I think. Only one major thing comes to mind, when I read your code.

Tuples

Instead of operating on seqs or similar, use a tuple. The size of a tuple is fixed and known at compile time. In this game, you know you'll always consider three cards at a time, so it fits the bill. This will also help simplify your allEqual and allDifferent functions. The isSet function still works, as the parameter l is now a tuple instead of a seq.

let allEqual (c1, c2, c3) = c1 = c2 && c2 = c3
let allDifferent (c1, c2, c3) = c1 <> c2 && c2 <> c3 && c1 <> c3

This affects the shape of your compare function as well. The line

let colorSet = cardList |> List.map (fun c -> c.Color  ) |> isSet

now becomes like

let colorSet = isSet (card1.Color, card2.Color, card3.Color)

and similar for shapeSet, patternSet and numsSet. Now the cardList variable may be removed, and the compare function is short and to the point.

Abstracting the isSet function

Suppose you think the way the colorSet, shapeSet, etc. variables are defined looks to clunky. You could abstract away the commonalities, by defining a function for getting the Color property and so on. These could then be supplied as arguments to the isSet, allEqual and allDifferent functions . Like this:

let color c = c.Color
// ...
let allEqual feature (c1, c2, c3) = feature(c1) = feature(c2) && feature(c2) = feature(c3)
// ...
let cards = (card1, card2, card3)
let colorSet = isSet color cards
// ...

I've only shown a couple of the required functions above, but I hope you get the point. In a small example like this, this might be overkill, but had you had many more features, I would probably go that way.

Discriminated unions

One last point is, that it would be obvious to use discriminated unions instead of string and int. I.e. you could define types for each feature, and use them in the Card definition

type Color = Green | Blue | Red
type Number = One | Two | Three
// ...
type Card = { Color: Color; Number: Number; ... }

This will help readability of your code. Furthermore, if this should interact with the outside would, where input comes in the shape of strings, it pushes parsing and validation to the boundary layer.

Answer 2

There isn't much to add to torbondes answer except the following details:

// Check each field of the record to see if it makes a set
let colorSet   = cardList |> List.map (fun c -> c.Color  ) |> isSet
let shapeSet   = cardList |> List.map (fun c -> c.Shape  ) |> isSet
let patternSet = cardList |> List.map (fun c -> c.Pattern) |> isSet
let numsSet    = cardList |> List.map (fun c -> c.Number ) |> isSet

// Check that they all make a set
colorSet && shapeSet && patternSet && numsSet

In the above you actually evaluate all properties of the cards before returning the result by "and-ing" them. The &&-operator evaluates from left to right, so if colorSet = false then the values of the others are skipped and so on. Therefore it would be an optimaization if you only caculate each property if needed. To do that, you could make each of the xxxSet bindings be functions instead as in:

// Check each field of the record to see if it makes a set
let colorSet _ = cardList |> List.map (fun c -> c.Color  ) |> isSet
let shapeSet _ = cardList |> List.map (fun c -> c.Shape  ) |> isSet
let patternSet _ = cardList |> List.map (fun c -> c.Pattern) |> isSet
let numsSet _ = cardList |> List.map (fun c -> c.Number ) |> isSet

// Check that they all make a set
colorSet() && shapeSet() && patternSet() && numsSet()

Here each property set is only called if the preceding set are true.

---

Another optimization would be to put the repeated code cardList |> List.map (fun c -> c.Color ) |> isSet into a function:

let isValid selector = cardList |> List.map selector |> isSet

and then call it as:

// Check each field of the record to see if it makes a set
let checkColors _ = isValid (fun c -> c.Color)
let shapeSet _ = isValid (fun c -> c.Shape)
let patternSet _ = isValid (fun c -> c.Pattern)
let numsSet _ = isValid (fun c -> c.Number)

// Check that they all make a set
checkColors () && shapeSet () && patternSet () && numsSet ()

... or simply just do:

let compare card1 card2 card3 =
    // Put the cards together for easy iteration
    let cardList = [card1; card2; card3]

    let isValid selector = cardList |> List.map selector |> isSet

    // Check each field of the record to see if it makes a set
    isValid (fun c -> c.Color)
    && isValid (fun c -> c.Shape)
    && isValid (fun c -> c.Pattern)
    && isValid (fun c -> c.Number)

---

Yet another optimization could be to only run through the cards once and collect the properties in sets by using List.fold and the Set type instead of a List:

let compare cards =
    let length = cards |> List.length // Optimization because List.length is an O(n) operation

    let isValid s = s |> Set.count = 1 || s |> Set.count = length

    cards 
    |> List.fold (
        fun (clrs, shps, pats, nums) card -> 
            clrs |> Set.add card.Color,
            shps |> Set.add card.Shape,
            pats |> Set.add card.Pattern,
            nums |> Set.add card.Number
            ) (Set.empty, Set.empty, Set.empty, Set.empty)
    |> fun (c, s, p, n) -> isValid c && isValid s && isValid p && isValid n

The benefit of using Set instead of List is that it is distinct by design, so it's sufficient to directly check if the set contains one or three elements.

That said I would prefer torbondes more static approach because the number of cards and properties aren't likely to change.