Project Euler Problem 9

問題9: a+b+c=1000 かつ a^2+b^2=c^2 (a<b<c) を満たす唯一の a b c の積を求めよ。[=>問題文]

問題9の解答

(defun problem009 (N)
  (let ((a 0) (ans nil))
    (while (and (null ans)
                (< (incf a) N))
      (let* ((a2 (* a a))
             (n (- N a))
             (b (1+ a)) (c 0))
        (while (and (null ans)
                    (< b (setq c (- n b))))
          (if (= (+ a2 (* b b)) (* c c))
              (setq ans (* a b c))
            (incf b)))))
    ans))

(problem009 1000)

　a<b<c の不等式が崩れたらすぐに内側のループを抜け a を更新するのがポイント。明らかに当てはまらない部分の枝刈りです。内側のループでは変化しない値 (a2 や n) をあらかじめ計算しておくのも基本ですね。
　whileループはカウンタ変数のインクリメント位置にいつも迷います。

問題9の別解(?)

　問題4で書いた while と progn を組み合わせる方式を突き詰めたらこんなものができてしまいました。

(defun problem009-2 (N)
  (let ((a 0) (ans nil))
    (while (progn
             (incf a)
             (let* ((a2 (* a a))
                    (n (- N a))
                    (b a))
               (while (progn
                        (incf b)
                        (let* ((c (- n b))
                               (c2 (* c c)))
                          (if (not (= c2 (+ a2 (* b b))))
                              (< b c)
                            (progn
                              (setq ans (* a b c))
                              nil))))))
             (and (null ans) (< a N))))
    ans))

(problem009-2 1000)

　2つの while はどちらもボディ部が空っぽです。条件部にすべての処理を詰め込んであります。ネスとした二つ目の while 式も一つ目の whileのボディ部ではなく条件式の中に書かれています。

式変形で高速化（別解)

　ツムジさんのところで紹介されている方法です。出題の2式を連立方程式として、変数 c を除去すると最終的に次のような式に変形されます。

b = n - n^2 / (2 * (n - a))

　a に順に値を代入し計算結果 b が整数ならその a b の組が求める答えとなります。nは定数です。

(defun problem009-3 (N)
  (let* ((n (float N))
         (n2 (* n n))
         (a 0.0) (ans nil))
    (while (and (null ans)
                (< (incf a) N))
      (let ((b (- n (/ n2 (* 2 (- n a))))))
        (if (not (< 0 (- b (floor b))))
            (setq ans (* a b (- n (+ a b)))))))
    ans))
(problem009-3 1000)

　計算結果 b が整数かどうかを判定する述語がわからなかったので、(- b (floor b)) がゼロ以上のとき非整数と判定しました。これは私の前2つの解答と違い、ループが１つしかないため相当な高速化が期待できます。

プロファイル

　比べてみました

Function       Calls  Total time (sec)  Avg time per call
============  ======  ================  =================
problem009       200         38.565000           0.192825
problem009-3     200          0.232000           0.001160

　まさに桁違い。めんどくさがらずに出題の式を変形する心、大事ですね。