Count numbers whose digits are only increasing or decreasing

Question

The goal is described here: basically, it is to compute the number of numbers below \$10^n\$ such that its digits are either increasing or decreasing (like 112 or 211, but not like 121).

The original version:

-- f computes the number of numbers with increasing digits.
-- digits >= k and the number of digits is n

f :: (Num t1, Num t, Eq t1, Eq t, Enum t) => t -> t1 -> t
f k 0 = 1
f k 1 = 10 - k
f 9 n = 1
f k n = foldl (\sum i -> sum + f i (n-1)) 0 $ enumFromTo k 9

-- h computes the number of numbers with decreasing digits.
-- digits <= k and the number of digits is n

h :: (Num t1, Num t, Eq t1, Eq t, Enum t) => t -> t1 -> t
h k 0 = 1
h 0 n = 1
h k 1 = k + 1
h k n = foldl (\sum i -> sum + h i (n-1)) 0 $ enumFromTo 0 k

-- The main function is g

g :: (Num t1, Num t, Eq t1, Eq t, Enum t) => t1 -> t
g 0 = 1   
g 1 = 10
g n = g (n-1) + foldl (\sum i -> sum + g1 i (n-1)) 0 (enumFromTo 1 9)

-- g1 computes the number of numbers with either increasing or decreasing digits. 

g1 :: (Num t1, Num t, Eq t1, Eq t, Enum t) => t -> t1 -> t
g1 0 n = f 0 n -- only increasing
g1 9 n = h 9 n -- only decreasing
g1 k 0 = 1     -- necessary for recursion
g1 k n = g1 k (n-1) + s1 + s2
  where
  s1 = foldl (\sum i -> sum + f i (n-1)) 0 $ enumFromTo (k+1) 9
  s2 = foldl (\sum i -> sum + h i (n-1)) 0 $ enumFromTo 0 (k-1)

The problem is it is too slow, and basically g n needs two times of the time needed by g (n-1).

I think maybe I need to memorize the functions, but don't know how to achieve this. Perhaps a list of lists?

The version using a list of lists follows:

total n  = case n of
  0 -> 1
  _ -> foldl (\sum k -> (sum + incg k n + decg k n) - 1) 0 [1..9] + total (n - 1)

incg k n = incgs !! n !! k
decg k n = decgs !! n !! k

incgs :: [[Integer]]
incgs =  [] : take 10 (repeat 1) : rest
  where
  rest = map (reverse . scanl1 (+) . reverse) $ tail incgs

decgs :: [[Integer]]
decgs =  [] : take 10 (repeat 1) : rest
  where
  rest = map (scanl1 (+)) $ tail decgs

Answer 1

Here's a version of your list of lists version using list comprehension and no !! and no explicit recursion:

total 0 = 1
total n = sum
  [ sum (init decgn) + sum (tail decgn) - 9
  | decgn <- take n $ iterate (scanl1 (+)) $ replicate 10 1
  ] + 1

This can probably be reduced further because either of us introduced some unneeded numerical operation somewhere.

Answer 2

When doing these sorts of programming challenges, it very often pays to start off by digging into the problem mathematically.

Let's simplify the problem by considering only increasing digit sequences. We can multiply by two and subtract out constant sequence quite easily to get the final answer. With this simplification, the question is now simple enough to approach. We know the exact order the digits will occur in, but we don't know how how many of each digit we have. This is a classic combinatorial problem:

How many ways are there to distribute n identical items into k bins, where some bins are allowed to be empty?

or, equivalently,

How many k-tuples of non-negative integers sum to n?

Wikipedia tells us the answer:

(n + k - 1) `choose` (k - 1)

This is

factorial (n + k - 1) `quot` (factorial (k - 1) * factorial (n - 1))

which is just

product [(n+1)..(n+k-1)] `quot` product [1..(k-1)]

For ascending digits, k = 10; we simply have to put the digits from 0 to 9 in order.

For descending digits, it's a little more complicated, because we start of with an arbitrary number of 0 digits. So for this, we let k=11, but then we subtract out the different ways to represent 0.

Once we add the ascending and descending digits, we have to subtract out the digit sequences that show up in both.

I didn't perform a terribly careful analysis of the fussy little edge cases; I just roughed it out and fiddled to match the results of Gurkenglas's code. My final result:

nineUp :: Num a => a -> a
nineUp n = product [(n+1)..(n+9)]

tenFactorial :: Num a => a
tenFactorial = 3628800

total :: Num a => a -> a
total n = (nineUp n * (n+20)) `quot` tenFactorial - 10*n - 1

To deal with truly absurdly large n (e.g., when n has hundreds or thousands of digits), you can pull a few more tricks to reduce the number of operations and make each of them cheaper. But this should probably be fast enough already to avoid running out of time.

---

The most obvious way to make the calculations cheaper is to improve nineUp:

nineUp n = ((n+5)^2-16)*((n+5)^2-9)*((n+5)^2-4)*(n+5)

This suggests

nineUp n = ((n52-16)*(n52-9))*((n52-4)*n5)
   where
     n5 = n + 5
     n52 = n5*n5

This reduces the number of pricy bignum multiplications, and (I think) also performs them in a more advantageous order.