Posts Tagged ‘comprehension’

Who Owns The Zebra Reloaded

June 22, 2009

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.

Programming Praxis – Feynman’s Puzzle

June 12, 2009

Today’s Programming Praxis problem is about a long division puzzle by Richard Feynman. The provided solution is 14 lines of code. Since both his and my solution are little more than a simple list comprehension, there is not going to be much room for improvement, but let’s see what we can do.

We need a way to refer to specific digits of numbers. The provided solution does so by converting the number to a list of digits. This function just returns the nth digit of a number, starting with the least significant one. For instance, digit 1 1234 equals 4.

digit :: Int -> Int -> Int
nth `digit` n = n `mod` 10 ^ nth `div` 10 ^ (nth - 1)

As mentioned, this problem is most naturally solved with a list comprehension, so that is what we will use as well. The actual conditions are of course nearly identical to the scheme version, with the exception that the condition that a * n1 has four digits is unnecessary, and therefore removed in this version.

feinman :: [(Int, Int)]
feinman = [ (n1, n2)
          | b <- [1..9], a <- [0..9], c <- [0..9],
            d <- [1..9], e <- [0..9], f <- [0..9],
            a /= b, a /= c, a /= d, a /= e, a /= f, e < d,
            let n1 = 100 * b + 10 * a + c,
            let n2 = 1000 * d + 100 * e + 10 * a + f,
            n1 * n2 > 999999, n1 * n2 < 10000000,
            digit 3 (n1 * n2) == a,
            digit 1 (d * n1) == a, digit 2 (d * n1) == a,
            digit 1 (e * n1) == a, digit 3 (a * n1) == a]

To test, we just print the list.

main :: IO ()
main = print feinman

As expected, we get the single result of (484, 7289). Runtime is about 8.5 seconds in ghci and 60 ms compiled (You’ve got to love compilers). The end result is 11 lines of code, so a slight improvement over the scheme version.