いつになったら実践的なコードを書くんだか
Grassで脳がパズルゲーモードになってるところで、100問到達してからしばらく放置してたProject Eulerを再開してみる。
いつの間にやら随分カラフル、というか多機能になってるなー
とりあえず最近の問題からサービス問題っぽいとこを。
Problem 203 - Project Euler
(defun squarefree? (n) (if (= (mod n 4) 0) nil (do ((root (sqrt n)) (a n) (b 3 (+ b 2))) ((< root b) t) (when (= (mod a b) 0) (if (= (mod a (* b b)) 0) (return nil) (setf a (/ a b))))))) (defun pe203 (n) (let ((dn '(1))) (labels ((rec (nums lim) (when (< lim n) (let ((next '(0))) (mapl #'(lambda (l) (pushnew #1=(+ (car l) (or (cadr l) 0)) dn) (push #1# next)) nums) (rec (reverse next) (1+ lim)))))) (rec '(0 1) 1) (apply #'+ (remove-if-not #'squarefree? dn)))))
maplを使ってみた。最初はなんだこれって思ったけど結構使いどころありそうだなあ。
squarefree?は最初再帰で書いたんだけど、xyzzyでスタックが足らんと怒られたので書き直した。
(defun pe207 (border) (do* ((l 1 (1+ l)) (k 2 (* (1+ l) l)) (u 1 (log (/ (1+ (sqrt (1+ (* 4d0 k)))) 2) 2d0)) (p 1 (+ (if (= (floor u) u) 1 0) p))) ((< (/ p l) border) (list k p l))))
短く書けたしxyzzyでも1秒前後で結果が出たのでよしよしと思ったのだけど、フォーラム見たらもっとずっと短かった、というかコードを書くまでもなく紙と鉛筆で解いてる人が一杯いて悲しくなった。
コード色々いじってる内に気づいた点。
logの第2引数を2d0と倍精度浮動少数にしてあるけど、ここを2にした時に
xyzzy, clisp (2.44) → 結果変わらず
sbcl (1.0.20), ecl (0.9l) → 誤答
と処理系によって精度に差が出た。注意しよう。