Einstein meets F# Part 2

In part 1, I described a riddle Einstein had come up with, and a proposed algorithm for programmatically finding the solution.  In this post, we will take the next steps of  writing our F# program, including defining the domain objects, creating a list of all the possibilities of homes, and begin filtering down this list to find the answer.

First I wanted to define a set of the distinct types for each of the houses properties as described in the riddle, e.g. colors, nationalities, beverages, smokes, and pets.  An enum seemed like the most natural fit:

type ColorHouse = Red = 1 | Green = 2 | White = 3 | Yellow = 4 | Blue = 5

This was my first conceptual change from the C# world. I had originally (unintentionally) created a discriminated union such as this…

type ColorHouse = Red | Green | White | Yellow | Blue //discriminated union

So what’s the difference between an enum and discriminated union?  You can read about discriminated unions here as well as some of the differences with enums here.  For our purposes we need something easy to enumerate over, which .NET provides many utilities for enumerating over enums but not discriminated unions.

Next, I defined a House type with members for each of our enum types.  This is a little verbose, and there may be more concise way to define a simple type in F# but it suits our purposes for now:

type House(number:int, color:ColorHouse, nationality: Nationality, beverages:Beverages, smoke:Smoke, pet:Pet) =

member this.Number = number

member this.Color = color

member this.Nationality = nationality

member this.Beverages = beverages

member this.Smoke = smoke

member this.Pet = pet

Next, we iterate through each of the available values of each property type, and create a home with a distinct set of property values.  Now we have created a set homes with all combinations of property values represented.

let houses = [for i in [1..5] do

for color in colors do

for nationality in nationalities do

for beverage in beverages do

for smoke in smokes do

for pet in pets do

yield new House(i, color, nationality, beverage, smoke, pet)]

Now that we have all possibilities of house values (15625!) we are going to filter out the houses that do not pass the rules applicable to a single home given to us in the riddle.  Lets create the set of functions that determine a valid home…

let rule1(house:House) =  exnor((house.Nationality = Nationality.Brit), (house.Color = ColorHouse.Red))

let rule10(house:House) = exnor((house.Nationality = Nationality.German), (house.Smoke = Smoke.Prince))

Great, now lets create a list of those rules and apply them to all the house combinations.

let singleRuleSet = [rule1;rule2;rule3;rule4;rule5;rule6;rule7;rule8;rule9;rule10;]

let rulesPredicate(house:House) = singleRuleSet |> List.forall(fun rule -> rule(house))

let housesPassedRules = houses |> List.filter rulesPredicate

We now have the set of homes that pass the ‘single home’ rules. For the final part of this blog series, we will create sets of  sets of homes and a list of ‘multi home’ rules, and apply this last rule filtering.   This should leave a single set of 5 homes, and reveal the answer to the riddle!

To be continued…part 3.

Download the source code for this post.


3 thoughts on “Einstein meets F# Part 2

  1. Pingback: Einstein meets F# part 1 « The Code Nose

  2. BinaryStar

    No need to use member variables in the House type. It can be simplified to …

    type House (number: int, color: ColorHouse, nationality: Nationality, beverages: Beverages, smoke: Smoke, pet: Pet) =
    member this.Number = number
    member this.Color = color
    member this.Nationality = nationality
    member this.Beverages = beverages
    member this.Smoke = smoke
    member this.Pet = pet

    1. Jace Rhea Post author

      Thanks! I mistakenly thought that type of syntax was equivalent to C# auto properties and I did not want to expose a public setter. I should have known it would be immutable by default.


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