Number Puzzle: Racket Solution

A Number Puzzle | Programming Praxis Racket Solution

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