document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. #lang racket
  2. ;Find a 10-digit number, with all digits unique, such that the
  3. ;first n digits of the number are divisible by n. For instance,
  4. ;in the 3-digit number 345, the 1-digit prefix, 3, is divisible by 1,
  5. ;the 2-digit prefix, 34, is divisible by 2, and the 3-digit prefix,
  6. ;345, is divisible by 3.
  7.  
  8. (define (unique-digits? n)
  9.   (define (loop n digits)
  10.     ;;exit condition 1 n = 0
  11.     (if (= n 0)
  12.         #t
  13.         (let [(x (modulo n 10))]
  14.           ;;exit-condition 2 we\'ve seen this digit
  15.           (if (set-member? digits x)
  16.               #f
  17.               (loop (quotient n 10) (set-add digits x))))))
  18.   (loop n (set)))
  19.  
  20.  
  21. (define (gen-candidates current n)
  22.   "Generate a list of candidates from the current value"
  23.   ;;find values using (current % n)
  24.   ;;and iterating by n.
  25.   (define next (* current 10))
  26.   (define start
  27.     (cond
  28.       ;;catch leading zeros
  29.       [(= n 1)
  30.        1]
  31.       [(= 0 (modulo next n))
  32.        next]
  33.       [else
  34.         (+ next (- n (modulo next n)))]))
  35.   ;;generate our list from start to (current * 10) + 10
  36.   ;;step by n
  37.   ;;filter for unique digits.
  38.   (filter unique-digits? (range start (+ 10 (* 10 current)) n)))
  39.  
  40. (define (solutions max-length)
  41.   (define results (list))
  42.   (define (loop curr n)
  43.     (if (> n max-length)
  44.         (set! results (cons curr results))
  45.         (for [(x (gen-candidates curr n))]
  46.           (loop x (+ n 1)) results)))
  47.   (loop 0 1)
  48.   (reverse results))
  49.        
  50. (time (solutions 10))
');