092.scm 1003 B

1234567891011121314151617181920212223242526272829303132333435363738
  1. ;; Square digit-chains
  2. (use-modules (srfi srfi-1)
  3. (euler utils))
  4. (define chain-cache #f)
  5. (define (digit-square-sum n)
  6. (reduce + 0
  7. (map (lambda (digit)
  8. (expt digit 2))
  9. (number->digits n))))
  10. (define (get-chain->loop-val n)
  11. (let while-loop ([curr-val n])
  12. (let ([cached-val? (vector-ref chain-cache curr-val)])
  13. (cond
  14. [cached-val? cached-val?]
  15. [(memq curr-val '(1 89)) curr-val]
  16. [else
  17. (while-loop (digit-square-sum curr-val))]))))
  18. ;; Note: this procedure only works when end > 600
  19. (define (get-chain->loop-vals end)
  20. (set! chain-cache (make-vector (1+ end) #f))
  21. (let for-loop ([i 1] [acc '()])
  22. (when (zero? (modulo i 100000)) (display i) (newline))
  23. (if (>= i end) acc
  24. (for-loop (1+ i)
  25. (let ([end-val (get-chain->loop-val i)])
  26. (vector-set! chain-cache i end-val)
  27. (cons (get-chain->loop-val i)
  28. acc))))))
  29. (define (solve)
  30. (fold (lambda (val acc) (+ (if (= val 89) 1 0) acc))
  31. 0
  32. (get-chain->loop-vals (expt 10 7))))