Project Euler(with Scheme) Problem 16,17,18

続けています。

Problem 16

(define (power a n)
  (if (= n 0) 1
      (* a (power a (- n 1)))))
(define (ketawa n)
  (if (= n 0) 0
      (+ (modulo n 10) (ketawa (quotient n 10)))))

(display (ketawa (power 2 1000)))
(newline)

でかい数字、かかってこいよでおなじみScheme。余裕でした。

Problem 17

(define (tex1 n);0-9 1の位
  (cond ((or (= n 1) (= n 2) (= n 6)) 3)
        ((or (= n 3) (= n 7) (= n 8)) 5)
        ((or (= n 4) (= n 5) (= n 9)) 4)
        (#t 0)))

(define (tex2 n);10-19
  (cond ((or (= n 11) (= n 12)) 6)
        ((or (= n 15) (= n 16)) 7)
        ((or (= n 13) (= n 14) (= n 18) (= n 19)) 8)
        ((= n 17) 9)
        ((= n 10) 3)
        (#t (tex1 n))))

(define (tex3 n);20,30,,,90
  (cond ((or (= n 40) (= n 50) (= n 60)) 5)
        ((or (= n 20) (= n 30) (= n 80) (= n 90)) 6)
        (#t 7)))

(define (tex4 n)
  (if (<= n 19) (tex2 n)
      (+ (tex3 (- n (modulo n 10))) (tex1 (modulo n 10)))))

(define (numtotex n);for all 0 <= n <= 999
  (cond ((= 0 (modulo n 100)) (+ (tex1 (quotient n 100)) 7))
        ((> n 100)
         (+ (tex1 (quotient n 100)) (tex4 (modulo n 100)) 10))
        ((>= n 10) (tex4 n))
        (#t (tex1 n))))

(define (ans n)
  (if (= n 0) 0
      (+ (numtotex n) (ans (- n 1)))))

(display (+ (ans 999) 11));one thousand = 11characters
(newline)

本当につまらない問題。
つまらないし、めっちゃ手間取った。
もうこんなの出さないでほしい。

Problem 18

(define (tri-num n) (quotient (* n (+ n 1)) 2))
(define (input-tri n)
  (define (nlistinp i)
    (if (= i 0) '()
        (let* ((num (read)))
          (cons num (nlistinp (- i 1))))))
  (define (listlistinp i)
    (if (> i n) '()
        (let* ((nlist (nlistinp i)))
          (cons nlist (listlistinp (+ i 1))))))
  (reverse (listlistinp 1)))


(define (bigger list)
  (if (null? (cdr list)) '()
      (cons (max (car list) (car (cdr list))) (bigger (cdr list)))))
(define (sumlist list1 list2)
  (if (null? list1) '()
      (cons (+ (car list1) (car list2)) (sumlist (cdr list1) (cdr list2)))))

(define (solve tri-list)
  (if (null? (cdr tri-list)) (car (car tri-list))
      (solve (cons (sumlist (bigger (car tri-list)) (car (cdr tri-list))) (cdr (cdr tri-list))))))

(display (solve (input-tri 15)))
(newline)

我ながら、キレイに解けた！！！！！！！！！
下から貪欲法的な感じで見ていくのですが、配列でなくリストでデータを持ち上がっていきました。

・一番下の列について、隣合う2つのうち大きい方を残す
ex) (3 5 9 2) → (5 9 9)
・一個上の列とこの"大きい方配列"を対応する場所ごとに足す
ex) (4 9 1) + (5 9 9) → (9 18 10)

この2手順の繰り返しです。そして一番上まで来たら出力。

上がって行き方も我ながらキレイ。
最後の方はこんな感じ。

((666 614 636 684 660 717) (20 4 82 47 65) (18 35 87 10) (17 47 82) (95 64) (75))
((686 640 766 731 782) (18 35 87 10) (17 47 82) (95 64) (75))
((704 801 853 792) (17 47 82) (95 64) (75))
((818 900 935) (95 64) (75))
((995 999) (75))
1074

ちなみに、これの入力が大きい版のProblem 67もこのアルゴリズムだと一瞬で解けます。O(n^2)ですね。

少しScheme力がアップしている気がする。
ちなみに自分が学生のとき(もう6年くらい前か)にJavaで解いたのはProblem 31までのよう。見えてきた感があるぞ。
続けていくぞー！