Who Owns The Zebra Reloaded

For the Who Owns the Zebra problem I initially tried a solution based on a list comprehension. I was, however, unable to get it to work in any reasonable time. Today Rofl_Waffler posted a solution on reddit that showed me why: I put all the conditions at the end, which meant that all possible solutions had to be generated. By interleaving the options and the conditions, Haskell does do the smart filtering you would expect. Although it does require careful ordering of the code, the resulting solution is a lot shorter. Rofl_Waffler’s solution uses a do statement with guards, but I figured I could make it even better using a list comprehension and some other minor adjustments.

Our import:

import Data.List

In this approach all permutations of the five properties are generated. To figure out the position of a specific option we use the following function:

indexOf :: (Eq a) => [a] -> a -> Int
indexOf xs x = head $ elemIndices x xs

We also need to be able to tell if an option is next to or to the right of another option:

nextTo :: Int -> Int -> Bool
nextTo a b = abs (a - b) == 1

rightOf :: Int -> Int -> Bool
rightOf a b = a == b + 1

A small convenience function to generate the different permutations:

options :: String -> [[String]]
options = permutations . words

And the solution to the problem itself.

solution :: [[String]]
solution = head [transpose [cs, os, ds, ss, ps] |
    cs <- options "red green ivory yellow blue",
    let color = indexOf cs,
    color "green" `rightOf` color "ivory",
    os <- options "english spaniard ukranian norwegian japanese",
    let owner = indexOf os,
    owner "norwegian" == 0,
    owner "english" == color "red",
    owner "norwegian" `nextTo` color "blue",
    ds <- options "coffee tea milk juice water",
    let drinks = indexOf ds,
    drinks "milk" == 2,
    drinks "coffee" == color "green",
    owner "ukranian" == drinks "tea",
    ss <- options "old_gold kools chesterfields parliaments lucky_strike",
    let smokes = indexOf ss,
    smokes "kools" == color "yellow",
    smokes "lucky_strike" == drinks "juice",
    owner "japanese" == smokes "parliaments",
    ps <- options "dog snails fox horse zebra",
    let pet = indexOf ps,
    owner "spaniard" == pet "dog",
    smokes "old_gold" == pet "snails",
    smokes "chesterfields" `nextTo` pet "fox",
    smokes "kools" `nextTo` pet "horse"]

A quick test shows that we still get the correct answer.

main :: IO ()
main = mapM_ print solution

Now we only need 30 lines, which is a reduction of just under 50%. The lesson here: put conditions in list comprehensions as close to the generators as possible.

About these ads

Tags: , , , , , , , , , ,

2 Responses to “Who Owns The Zebra Reloaded”

  1. brian Says:

    Wow, I’m not getting it too well. You know that the colors of the houses are some permutation of the possible colors, and furthermore that the green house is to the right of the ivory house, so the colors are one of [ig???, ?ig??, ??ig?, ???ig]. What I don’t get is how ‘cs’ gets winnowed down any further. You go on in that list comprehension to make other generators and to filter them in different ways, but I don’t see how any of that affects ‘cs’.

  2. Remco Niemeijer Says:

    The colors get filtered further through the other conditions. For instance, after filtering to [ig???, ?ig??, ??ig?, ???ig] (which in reality is a list with 24 elements) we generate the permutations for the owners. The next condition restricts those to [n????] (also 24 elements). All combinations of cs and os are now possible (24*24). The Englishman in the red house condition eliminates some of those. The next one eliminates the ig??? and ?ig??? patterns, since cs !! 1 must be blue. Thus we now have less than 12*24 options. If you do this for the other generators and conditions as well, you will get only one option each for cs, os, ds, ss and ps.

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


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: