連続する整数の「7」の個数を数える

久々のプログラミングネタw!
暇だったので解いてみました。

まずは、愚直なコードで傾向と対策を考えますw

#;(define (test limit)
  (define (iter n c)
    (if (> n limit)
	c
	(iter (+ n 1)
	      (+ c (length (filter (lambda (x) (= x 55)) (map x->integer (string->list (number->string n)))))))))
  (iter 1 0))

これは遅いwww

改良しました。
ポイントは計算で求めて計算量を O(N) にする事です。

(define nil '())

(define (number->list num)
  (define (iter n lst)
    (if (= n 0)
	lst
	(iter (quotient n 10) (cons (remainder n 10) lst))))
  (iter num nil))

(define (count-seven n)
  (let ((zk (- (length (number->list n)) 1)))
    (if (< zk 1)
	0
	(* (quotient n (expt 10 zk)) zk (expt 10 (- zk 1))))))

(define (seven num)
  (define (iter n q r s k cnt)
    (if (= n 0)
	cnt
	(cond ((= r 7)
	       (iter (quotient n 10)
		     (quotient q 10)
		     (remainder q 10)
		     (+ s (* r (expt 10 k)))
		     (+ k 1)
		     (+ cnt (count-seven (* r (expt 10 k))) 1 s)))
	      ((< r 7)
	       (iter (quotient n 10)
		     (quotient q 10)
		     (remainder q 10)
		     (+ s (* r (expt 10 k)))
		     (+ k 1)
		     (+ cnt (count-seven (* r (expt 10 k))))))
	      (else
	       (iter (quotient n 10)
		     (quotient q 10)
		     (remainder q 10)
		     (+ s (* r (expt 10 k)))
		     (+ k 1)
		     (+ cnt (count-seven (* r (expt 10 k))) (expt 10 k)))))))
  (iter num (quotient num 10) (remainder num 10) 0 0 0))

ロジックの解説は暇な時にでも書きます。たぶん。

実行結果

gosh> (time (map seven '(99 77777 23678947 732465890 1912478368)))
;(time (map seven '(99 77777 23678947 732465890 1912478368)))
; real   0.000
; user   0.000
; sys    0.000
(20 38890 16140633 614891670 1728439836)

1秒かかってないので合格です。

計算量は O(N) ですから、

gosh> (time (seven 1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890))
;(time (seven 1234567890123456789012345678901234567890123456789012345678 ...
; real   0.218
; user   0.218
; sys    0.000
97379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972768

巨大な数でも楽々計算できます。
この答えで合ってるのか不明ですが。たぶん合ってるのだと思いますw