Pizza Hut math problem #1 in Haskell

I'm currently attempting to learn Haskell after a fair history of imperative programming. When I saw the Pizza Hut Pi Day math problems, I thought the first one would be a good candidate for my Haskell experimenting. The question is:


I’m thinking of a ten-digit integer whose digits are all distinct. It happens that the number formed by the first n of them is divisible by n for each n from 1 to 10. What is my number?

And I came up with the following code:

module Main where                               
import System.Environment                       

import Data.List                                

pizza2 = [ x | x <- [1000000000..9999999999],   
            (x `div` (10 ^ 0)) `mod` (10) == 0, 
            (x `div` (10 ^ 1)) `mod` (9) == 0,  
            (x `div` (10 ^ 2)) `mod` (8) == 0,  
            (x `div` (10 ^ 3)) `mod` (7) == 0,  
            (x `div` (10 ^ 4)) `mod` (6) == 0,  
            (x `div` (10 ^ 5)) `mod` (5) == 0,  
            (x `div` (10 ^ 6)) `mod` (4) == 0,  
            (x `div` (10 ^ 7)) `mod` (3) == 0,   
            (x `div` (10 ^ 8)) `mod` (2) == 0,  
            (x `div` (10 ^ 9)) `mod` (1) == 0,  
            nub ( show x ) == show x]           

main :: IO ()                                   
main = do                                       
putStrLn (show (nub (pizza2)))

To my suprise, this actually compiles, runs, and returns the correct result. However, due to my inexperience (I think), it takes about 9 minutes to run and I feel like it should take less than a minute on the long side and just a couple seconds on the short side.

Two questions:

• Why does this take so long?

• I really feel like all those extra conditions I wrote should be able to be abstracted into one condition, but I couldn't figure it out on my own. Any ideas on how to condense that into one, more abstract condition?

Basically, you're testing a lot of paths you don't have to. It would probably be more efficient to find a 1-digit number that is divisible by 1, then use that digit to find a 2-digit number that is divisible by 2, then use those two digits to find a 3-digit number that is divisible by 3, then recursively backtrack if you run out of options at one level.

Here's some code to illustrate. It returns essentially instantly in my REPL. You call it by pizza 1 0 initially.

import Data.List ((\\))
import Data.Char (digitToInt, intToDigit)
import Data.Maybe (listToMaybe, mapMaybe)

pizza :: Integer -> Integer -> Maybe Integer

pizza 10 accum = Just (accum * 10)

pizza n accum =
  let usedDigits = map digitToInt $ show accum
      unusedDigits = map toInteger $ [1..9] \\ usedDigits
      previous = accum * 10
      divisibleDigits = filter (\digit -> (previous + digit) `mod` n == 0) unusedDigits
  in listToMaybe $ mapMaybe (\digit -> pizza (n + 1) (previous + digit)) divisibleDigits

However, for one-shot problems like these, your solution is fine. If you can't write a faster algorithm in less than 9 minutes (of your programmer time), you haven't actually saved any time.

StackExchange Code Review Q#123265, answer score: 9