| Am Freitag 26 Februar 2010 00:57:48 schrieb Rafael Gustavo da Cunha Pereira | Pinto: | |> There is a single 10 digit number that: |> |> 1) uses all ten digits [0..9], with no repetitions |> 2) the number formed by the first digit (right to left, most |> significant) is divisible by one |> 3) the number formed by the first 2 digits (again right to left) is |> divisible by two |> 4) the number formed by the first 3 digits is divisible by three |> and so on, until: |> 11) the number formed by the first 10 digits (all!) is by 10
Since Ishaaq Chandy just posted about how to generalize nested list comprehensions, I thought this was an interesting way to approach this. First a couple of simple helper functions: > val = foldl (\x y -> x*10+y) 0 > divides d n = n `mod` d == 0 So you could solve it using a set of list comprehensions: > solutions = [[x1,x2,x3,x4,x5,x6,x7,x8,x9,x10] > | x1 <- [0..9] > , x2 <- [0..9], divides 2 $ val [x1,x2] > , x3 <- [0..9], divides 3 $ val [x1,x2,x3] > , x4 <- [0..9], divides 4 $ val [x1,x2,x3,x4] > , x5 <- [0..9], divides 5 $ val [x1,x2,x3,x4,x5] > , x6 <- [0..9], divides 6 $ val [x1,x2,x3,x4,x5,x6] > , x7 <- [0..9], divides 7 $ val [x1,x2,x3,x4,x5,x6,x7] > , x8 <- [0..9], divides 8 $ val [x1,x2,x3,x4,x5,x6,x7,x8] > , x9 <- [0..9], divides 9 $ val [x1,x2,x3,x4,x5,x6,x7,x8,x9] > , x10 <- [0] > , length (nub [x1,x2,x3,x4,x5,x6,x7,x8,x9,x10]) == 10 > ] This is a nicely declarative way to do it, and a pretty clear way to formulate the original problem statement. But it's a bit tedious with all the repetitions, so you would rather recurse to make it more general. Since list comprehensions are just a different way to work in the list monad (where | becomes 'guard'), I managed to come up with this: > solve :: [Int] -> [[Int]] > solve prefix = do > let l = length prefix > if l == 10 > then return prefix > else do > x <- [0..9] > let r = prefix++[x] > guard (divides (l+1) (val r) && nub r == r) > solve r -k (PS: I'm happy to hear any comments regarding style or other issues) -- If I haven't seen further, it is by standing in the footprints of giants _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
