problem 29

scheme euler

Problem 29 - Project Euler

2 ≤ a ≤ 100 かつ 2 ≤ b ≤ 100 を満たす a,b から作られる a^b はいくつあるかという問題。

  1. 2 から 100 までの 2 つの集合を用意し、
  2. その 2 つの集合の直積を求め、
  3. その直積に対する a^b の写像を作り、
  4. 重複を削除し、
  5. リストの長さ数える

という方法で解いてみました。

(use srfi-1)
(use util.combinations)

(define (p29)
  (let1 list2to100 (list-tabulate 99 (lambda (x) (+ x 2)))
        (length                                         ; 5
          (delete-duplicates                            ; 4
            (map (lambda (x) (expt (car x) (cadr x)))   ; 3
                 (cartesian-product                     ; 2
                   (make-list 2 list2to100)))))))       ; 1

(print (p29))

scheme で書いておいていうのもおかしな話ですが、関数型言語的な解き方です。手続き型言語しかやってなかったらループ使って解いてたと思います。
こういう解き方をすると遅延評価の必要性に迫られる感じがします。

素数の問題を飛ばしてますが、遅延評価、ストリームを理解した上でチャレンジする予定です。

分かったこと

  • 直積集合は cartesian-product (要 util.combinations)
  • 要素の重複をなくすのは delete-duplicates
  • リストを作るのは make-list もしくは list-tabulate で良い感じに作れる。list-tabulate の第二引数にはインデックスが渡る。