Cedric’s Coding Challenge

Posted in Haskell by Dan on June 28th, 2008

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))