content: {- 
   - Solution to Project Euler problem 164
   - Copyright (c) Project Nayuki. All rights reserved.
   - 
   - https://www.nayuki.io/page/project-euler-solutions
   - https://github.com/nayuki/Project-Euler-solutions
   -}
  
  import qualified EulerLib
  
  
  base = 10
  digits = 20
  consecutive = 3
  maxSum = 9
  
  {- 
   - Let ways[d][p] be the number of ways that a d-digit number (with possible leading zeros)
   - whose first 'consecutive' (i.e. 3) digits are the same as the digits of p (padding with
   - leading zeros up to 'consecutive' digits) and where each of the ways does not have
   - 'consecutive' consecutive digits whose sum exceeds 'maxSum'.
   - 
   - For example, ways[5][27] is the number of ways that a 5-digit number starts with 027 and has
   - no 3 consecutive digits summing to more than 9. This set of ways includes only {02700, 02701, 02702}
   - and not {02703, 02710, 02799, etc}.
   - 
   - For each d (from 0 to anything) and p (from 0 to (10^consecutive - 1)), ways[d][p] is equal
   - to the sum of ways[d-1][p'] for 10 choices of p'. To explain by example, suppose p = 555.
   - Clearly these 3 digits sum to more than 9, so ways[d][555] = 0. To give another example,
   - suppose p = 421. We strip off the first digit and try all possibilities for the last digit,
   - giving the set {210, 211, ..., 219}. Now we add up the ways with one fewer digit with these
   - prefixes: ways[d][421] = ways[d-1][210] + ways[d-1][211] + ... + ways[d-1][219].
   - 
   - The final number of ways wanted is for strict 20-digit numbers (i.e. with no leading zeros),
   - which is equal to the number of ways for non-strict 23-digit numbers that start with 000 minus
   - the number of non-strict 22-digit numbers that start with 000, leaving only 22-digit numbers
   - that start with 001 to 009, which are exactly the 20-digit numbers that start with 1 to 9.
   -}
  
  main = putStrLn (show ans)
  ans = (ways (digits + consecutive) 0) - (ways (digits + consecutive - 1) 0)
  
  ways :: Int -> Int -> Integer
  ways 0 0 = 1
  ways 0 _ = 0
  ways d p = if (EulerLib.digitSum p) > maxSum then 0
  	else sum [waysMemo !! (d - 1) !! ((mod p (base^(consecutive - 1))) * base + i) | i <- [0..9]]
  waysMemo = [[ways d p | p <- [0..]] | d <- [0..]]
  