Cedric Beust has posted a programming challenge on his blog. Seeing as I have nothing better to do, I thought I’d give it a go in Haskell. Here is a naive brute-force solution that I came up with. I’m sure there are many optimisations that can be made.
import List(nub) -- Predicate that returns True if a number contains no duplicate digits. noDuplicateDigits :: Int -> Bool noDuplicateDigits n = length (nub (digits)) == length digits where digits = show n values :: Int -> [Int] values n = [x | x <- [1..n], noDuplicateDigits x] -- Given a positive integer n, return the number of values between 1 and n that -- contain no duplicate digits, and the largest gap between two consecutive -- values in that sequence. answer :: Int -> (Int, Int) answer n = (length sequence, gap) where sequence = values n gap = maximum (zipWith subtract sequence (tail sequence)) |