Project Euler: Problem 9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a^(2) + b^(2) = c^(2)

For example, 3^(2) + 4^(2) = 9 + 16 = 25 = 5^(2).

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

http://projecteuler.net/index.php?section=problems&id=9

a^2 + b^2 = c^2 を満たすピタゴラス数のうち、a + b + c = 1000 を満たすただ一つの組み合せの積を求めよ、でいいかな。

Gauche で実装した。ピタゴラスってこんな風にスペるとは知らなかった (ぱいたごりあん?) くらいのレベルではあったけど、Web で公式を調べたりしてなんとかできた。無駄に継続を使ってみようと思ったら無駄なところでハマってしまって時間を無駄にしてしまったけど、そんな経験も無駄にはならんだろうと無駄なry

#!/usr/bin/env gosh

(use util.queue)

;; キューを初期化
(define (pt-init)
  (make-queue))

;; 呼び出されるごとに次のピタゴラス数を返す
(define (pt-next q)
  (if (queue-empty? q)
    (call/cc (lambda (return)
      (let mloop [(m 1)]
        (let nloop [(n 1)]
          (if (< n m)
            (let [(m^2 (* m m))
                  (n^2 (* n n))
                  (mn2 (* m n 2))]
              (let [(a (- m^2 n^2))
                    (b mn2)
                    (c (+ m^2 n^2))]
                (if (= (+ (* a a) (* b b)) (* c c))
                  (let* [(res (list a b c))
                         (ret (call/cc (lambda (cc)
                                         (enqueue! q cc)
                                         (return res))))] ; return to toplevel
                    (set! return ret)))) ; refresh return address to toplevel
              (nloop (+ n 1)))
            (mloop (+ m 1)))))))
    (call/cc (lambda (ret) ; キューが空でなければ、戻りアドレスを保存して継続を蘇生
      (let [(cc (dequeue! q))]
        (cc ret))))))

(define (main args)

;; (m^2-n^2)^2 + (2mn)^2 = (m^2+n^2)^2
;; ==> a=m^2-n^2, b=2mn, c=m^2+n^2

;; 愚直に main の中に書いてみた版
;    (let mloop [(m 1)]
;      (let nloop [(n 1)]
;        (if (< n m)
;          (let [(m^2 (* m m))
;                (n^2 (* n n))
;                (mn2 (* m n 2))]
;            (let [(a (- m^2 n^2))
;                  (b mn2)
;                  (c (+ m^2 n^2))]
;              (if (= (+ (* a a) (* b b)) (* c c))
;                (if (= (+ a b c) 1000)
;                  [begin
;                    (print #`"a=,a,, b=,b,, c=,c")
;                    (print #`"  a+b+c=,(+ a b c)")
;                    (print #`"  a*b*c=,(* a b c)")]
;                  (nloop (+ n 1)))
;                (nloop (+ n 1)))))
;          (mloop (+ m 1)))))

  (let [(q (pt-init))]
    (let loop [(pt (pt-next q))]
      (if (= (apply + pt) 1000) ; ピタゴラス数の合計が 1000 かどうか
        (let [(a (car pt))
              (b (cadr pt))
              (c (caddr pt))]
          (print #`"a=,a,, b=,b,, c=,c")
          (print #`"  a+b+c=,(+ a b c)")
          (print #`"  a*b*c=,(* a b c)"))
        (loop (pt-next q))))) ; 違ったら次の組をテストする

  0)