I chose to show a small example of the Zebra Puzzle and an implementation of the solution to it in F#.
The implementation is rather basic as it uses simple integers to assign the attributes to the house. A more type safe implementation using a discriminated union for each attribute type is a good idea, more to follow on that in a later blog post with an improved example. Please find the code below.
Credits to Tomas Petricek, whose implementation of the permutations of a list I used from Stack Overflow.
The solution is shown below or under this link.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //http://en.wikipedia.org/wiki/Zebra_Puzzle | |
| // Zebra Puzzle | |
| // | |
| //1 There are five houses. | |
| // | |
| //2 The Englishman lives in the red house. | |
| // | |
| //3 The Spaniard owns the dog. | |
| // | |
| //4 Coffee is drunk in the green house. | |
| // | |
| //5 The Ukrainian drinks tea. | |
| // | |
| //6 The green house is immediately to the right of the ivory house. | |
| // | |
| //7 The Old Gold smoker owns snails. | |
| // | |
| //8 Kools are smoked in the yellow house. | |
| // | |
| //9 Milk is drunk in the middle house. | |
| // | |
| //10 The Norwegian lives in the first house. | |
| // | |
| //11 The man who smokes Chesterfields lives in the house next to the man with the fox. | |
| // | |
| //12 Kools are smoked in a house next to the house where the horse is kept. | |
| // | |
| //13 The Lucky Strike smoker drinks orange juice. | |
| // | |
| //14 The Japanese smokes Parliaments. | |
| // | |
| //15 The Norwegian lives next to the blue house. | |
| // | |
| //Who drinks water? Who owns the zebra? | |
| // | |
| //Each house is painted a different color, and their inhabitants are of different nationalities, own different pets, drink different beverages and smoke different brands of American cigarettes. | |
| namespace ZebraDemo | |
| module programOrdered = | |
| let rec permutations inputlist taken = | |
| seq { if Set.count taken = List.length inputlist then yield [] else | |
| for l in inputlist do | |
| if not (Set.contains l taken) then | |
| for perm in permutations inputlist (Set.add l taken) do | |
| yield l::perm } | |
| let myperms = permutations [1;2;3] Set.empty | |
| Seq.length myperms | |
| Seq.toList myperms | |
| let splitToTuple = function | |
| | [fst; sec; thrd; fth; ffth] -> (fst, sec, thrd, fth, ffth) | |
| | _ -> failwith "wrong list format" | |
| let nextTo (frst, sec) = | |
| frst - 1 = sec || frst + 1 = sec | |
| let myHouses = [1..5] | |
| let myHousePerms = permutations myHouses Set.empty | |
| Seq.length myHousePerms | |
| let myOrderedAnswer = | |
| [for myCountryList in myHousePerms do | |
| let (England, Spain, Ukraine, Japan, Norway) = splitToTuple myCountryList | |
| if Norway = 1 then | |
| for myColorList in myHousePerms do | |
| let (red, green, ivory, yellow, blue) = splitToTuple myColorList | |
| if England = red && | |
| green - 1 = ivory && | |
| nextTo (Norway, blue) then | |
| for myDrinkList in myHousePerms do | |
| let (coffee, tea, milk, oj, WATER) = splitToTuple myDrinkList | |
| if Ukraine = tea && | |
| green = coffee && | |
| milk = 3 then | |
| for mySmokeList in myHousePerms do | |
| let (oldGold, kools, chesterfields, luckyStrike, parliaments) = splitToTuple mySmokeList | |
| if yellow = kools && | |
| luckyStrike = oj && | |
| Japan = parliaments then | |
| for myPetList in myHousePerms do | |
| let (dog, snail, horse, fox, ZEBRA) = splitToTuple myPetList | |
| if Spain = dog && | |
| oldGold = snail && | |
| nextTo(chesterfields, fox) && | |
| nextTo(kools, horse) then | |
| yield [("red", red); ("green", green); ("ivory", ivory); ("yellow", yellow); ("blue", blue); | |
| ("England", England); ("Spain", Spain); ("Ukraine", Ukraine); ("Japan", Japan); ("Norway", Norway); | |
| ("coffee", coffee); ("tea", tea); ("milk", milk); ("oj", oj); ("WATER", WATER); | |
| ("dog", dog); ("snail", snail); ("horse", horse); ("fox", fox); ("ZEBRA", ZEBRA); | |
| ("oldGold", oldGold); ("kools", kools); ("chesterfields", chesterfields); ("luckyStrike", luckyStrike); ("parliaments", parliaments)] ] | |
| let ans = List.head myOrderedAnswer | |
| let selectFromList houseNum = | |
| List.filter (fun (fst, snd) -> snd = houseNum) ans | |
| |> List.map (fun (fst, snd) -> fst) | |
| printfn "house 1:" | |
| printfn "%A" (selectFromList 1) | |
| printfn "house 2:" | |
| printfn "%A" (selectFromList 2) | |
| printfn "house 3:" | |
| printfn "%A" (selectFromList 3) | |
| printfn "house 4:" | |
| printfn "%A" (selectFromList 4) | |
| printfn "house 5:" | |
| printfn "%A" (selectFromList 5) |
.
