久々のプログラミングネタ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