ゼロからはじめるスクリプト言語製作: プログラミング課題に挑戦する③（１８日目）

前回につづき、スクリプト言語製作の仕上げとして、やや実践的なプログラミング課題を解きながら、現状で欠けている機能の追加に取り組んでいこう。

今日は、プロジェクト・オイラーの第３問に挑戦だ。

Largest prime factor
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

（訳）
最大の素因数
13195 の素因数は 5, 7, 13, 29 である。
では 600851475143 の素因数のうち最大のものはいくつか？

Project Euler の Problem 3 より

繰り返しになるが、プロジェクト・オイラーのようなプログラミングによる回答タスクに対して、製作中のスクリプト言語が充分に機能を備えているかを確認することが真の目的である。

いま足りてない機能を求めて

製作中のスクリプト言語を駆使して、この問題を解いてみた。
あったら便利な機能、というものが無いだろうか。

($ 'make-list (lambda (' x y) (' let ($ 'arr (list x)) (cdr= arr y) arr)))
($ 'prime-factors
  (let
    ($ 'prime-factors2
      (lambda (' v d)
        (' if (>= v d)
          (which
            (writeln "prime-factors2" v d)
            (if (== (% v d) 0) (make-list d (prime-factors2 (/ v d) d)))
            (for 'i (range (if (== d 2) 3 (+ d 2)) (/ v 2) 2)
              (if (== (% v i) 0)
                (do
                  ($= 'for:value (make-list i (prime-factors2 (/ v i) i)))
                  ($= 'for:break true)
                )
              )
            )
            (list v)
          )
        )
      )
    )
    (lambda (' v) (' prime-factors2 v 2))
  )
)

関数 prime-factors は引数に指定された整数を素因数分解して、リストで返すことができる。内部関数 prime-factors2 の２つめの引数 d は、１つめの引数 v を割り切れる値を探すときの初期値となっていて、２から始めて割り切れなければ３、５、７、…と増加していくようになっている。

試しに、問題文に例として挙がっている 13195 を prime-factors に渡してみよう。

13195 を素因数分解できた！（600851475143 の答えは公表しません）

このスクリプトは、新たな仕様や実装を追加することなく、そのまま実行できてしまった。全体をざっと眺めてみて、コーディングする上で著しく冗長な部分も無いようだ。
不足機能が見当たらなかったので、続けて第４問に挑戦してみよう。

Largest palindrome product
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.

（訳）
積で表せる最大の回文数
回文数とは、上位の桁から読んでも下位の桁から読んでも同じになる数のことである。２桁の数を２つ掛けて回文数になるもののうち、最大のものは９００９＝９１×９９である。
では３桁の数を２つ掛けて回文数になるもののうち、最大のものはいくつか？

Project Euler の Problem 4 より

この問題を解いてみる。

($ 'digit-of (lambda (' v at-place) (' % (/ v at-place) 10)))
($ 'make-palindrome (lambda (' v) (' + (* 1000 v) (* 100 (digit-of v 1)) (* 10 (digit-of v 10)) (* 1 (digit-of v 100)))))
(for 'a (range 999 99 -1)
  (let
    ($ 'p (make-palindrome a))
    ($= 'for:value p)
    ($= 'for:break
      (!= null
        (for 'b (range (+ a 1) 1000)
          (if (== (% p b) 0)
            (do
              ($= 'for:break true)
              ($= 'for:value true)
              (writeln p b (/ p b))
            )
          )
        )
      )
    )
  )
)

この問題は２重の for ループで回答できた。外側の for ループ（ループ変数は a）と内側の for ループ（ループ変数は b）があり、a は 999 からデクリメントされつつ、b は a+1 からインクリメントされている。a から回文数 p を生成して、b で割り切れるかをチェックしている。

このスクリプトも、新たな仕様や実装を追加することなく、そのまま実行できてしまった。
不足機能が見当たらなかったので、続けて第５問に挑戦してみた。

Smallest multiple
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

（訳）
最小公倍数
2520 は、１から１０までのどの数字でも割り切れる、最小の数である。
では１から２０までのどの数字でも割り切れる最小の正数はいくつか？

Project Euler の Problem 5 より

この問題を解いてみる。
なお↓このスクリプトでは、第３問で定義した関数 prime-factors を再利用した。

($ 'prime-factors-data (list null))
(for 'i (range 2 21)
  (cdr= (@last prime-factors-data) (list (prime-factors i)))
)
(writeln prime-factors-data)
($ 'get-next-factor
  (lambda (' factors-data)
    (' for 'data factors-data
      (if (!= null data)
        (do
          ($ 'for:break true)
          ($ 'for:value (car data))
        )
      )
    )
  )
)
(let
  ($ 'factors (list *))
  ($ 'next-factor (get-next-factor prime-factors-data))
  (while (!= null next-factor)
    (cdr= (@last factors) (list next-factor))
    (for 'i (range (# prime-factors-data))
      (if (&& (!= null (car (@ i prime-factors-data))) (== (car (car (@ i prime-factors-data))) next-factor))
        (car= (@ i prime-factors-data) (cdr (car (@ i prime-factors-data))))
      )
    )
    (writeln "find" (car (@last factors)))
    (writeln prime-factors-data)
    ($ 'next-factor (get-next-factor prime-factors-data))
  )
  (writeln factors)
  ((lambda (') factors))
)

まず１から２０までのそれぞれの数を素因数分解したリストを、リスト prime-factors-data に格納する。

prime-factors-data の中身は２０個のリスト

関数 get-next-factor は、prime-factors-data から素因数の１つを取得する。その後 while ループでは get-next-factor を繰り返し実行し、リスト factors に素因数を格納しながら、prime-factors-data の各リストの先頭から一致する素因数を削除する。prime-factors-data が空になるまでこの while を繰り返すことによって、prime-factors-data に格納されていた素因数の和集合を factors に構築できる。

while の１週目では素因数２を見つけて、prime-factors-data の各リストから２を１つずつ削除する。２週目では素因数３を見つけて、各リストから３を１つずつ削除する。これを繰り返す

あとは factors に格納された数値をすべて掛け合わせることで、答えが求まる。

ということで、またもや不足機能が見当たらなかった。製作してきたスクリプトには、コーティングに必要な機能や概念が充分備わっている、そう考えて良いのだろうか。
次回はもっと意図的に課題を選択することにして、今日はここまでとした。おつかれさま。

こっそり実装を改良したところ

↓以下に第５問のスクリプト例の一部を引用した。

    (for 'i (range (# prime-factors-data))
      (if (&& (!= null (car (@ i prime-factors-data))) (== (car (car (@ i prime-factors-data))) next-factor))
        (car= (@ i prime-factors-data) (cdr (car (@ i prime-factors-data))))
      )
    )

シンボル if の箇所で論理演算子 && を使っていて、prime-factors-data のｉ番目が空でなければ、その要素（素因数のリスト）にアクセスするというロジックになっている。
実はこの部分、以前のスクリプト実装では、この if ブロックは２つに分割して記述する必要があった。ショートサーキット評価と呼ばれる機構が実装されていなかったからである。

ショートサーキット評価（あるいは短絡評価）とは、論理式の真偽を演算する過程で明らかに評価しなくてよい式を評価せず省略することを指すのだそうだ。一般的なプログラミング言語において真偽値 a と b（あるいは論理式 a と b）が与えられ、a && b という論理式全体を評価したいとき、a の評価が false の場合は b を評価しない、というふるまいになる。

ショートサーキット評価には、無駄な評価を省き処理性能を稼ぐだけの効果しかない、という思い込みで実装を後回しにしていたが、実はガード処理を記述するときのコードの冗長性を減らす効果があるということを今回学ぶことができた（ささやかな収穫）。

次回も乞うご期待。