Well done, whitypig!

Programming Lisp

よく焼けました，whitypig さん。
って，わしゃ肉か!
ハッピーボ〜イズッ! ワオッ!!
そんな感じでよく冷えました。

Project Euler Problem 1 から 50 のうちで，はまったところ。

なんだかんだで，50問目まで正解できました。
できたんですが，2カ所，はまったところ，そのうち1つは不思議状態，
があったので，メモるでござる。

Problem 45

その不思議状態。
最初は，力業というかパソコンのチカラで解決。
たしか結構時間がかかった気がする。
その後，他の人のポストを見ていて，なるほどなと。
よく考えてからコードを書きましょうとの教訓をゲット。


んで，下記のコードを試してみたのよ。

(defun euler45 ()
  (loop for h from 144
        for hn = (* h (- (* 2 h) 1))
        for pn = (/ (+ 1 (sqrt (+ 1 (* 24 hn)))) 6)
        when (integerp pn)
          return hn))

ワタシの環境は，Windows XPSP3，Cygwin，NTEmacs23.2，SBCL 1.0.51.36.mswinmt.961-3f3df1b
です。


Emacs 内から，C-cC-c してコンパイルすると，unreachable なコードを削除したよ的な
メッセージが出る。むぅ。
ほいで C-cC-y して(これ便利だから覚えようね) 実行するとオワラネェ。
ならばと，Cygwin から，sbcl --script ./e45.lisp とかしてみるも，オワラネェ。
Cygwin についてきた，clisp で，clisp ./e45.lisp すると正解が出る。


sqrt ってるので，integerp が t になり得ないから，終わらないと。
repl で確かめると，

CL-USER> (integerp (sqrt 1))
NIL

となる。ならばと，

(= 1.0 (round 1.0)) ;=> T
(= 1.1 (round 1.1)) ;=> NIL

であることを利用してみることに。

(defun euler45c ()
  (loop for h from 144
        for hn = (* h (- (* 2 h) 1))
        for pn = (/ (+ 1 (sqrt (+ 1 (* 24 hn)))) 6)
        when (= pn (round pn))
          return hn))

(euler45c) ;=> 29395278

Oh, what!? No way...


ほいだらばと，この euler45c を clisp で実行してみる。

% clisp ./e45.lisp
53763265

ぎょぎょぎょ。


なんか触れてはならんものに触れた気がするので，
これ以上追求するのをやめたのです。
テクねーし。
ちなみに，rem とか，floor とかも使ってみたけど
結果は同じでした。

Problem 49。permutation にはまる。

結果からいうと，数字のリストをもらって，permutation を返す関数が
バグっていたというオチ。
得た教訓は，remove には，keyword 引数で count があるということ。
テストは大事だということ。cl-test-more をしっかり使いましょうということでしょうかね。
あと，quicklisp バンザイ。asdf なんとかというのは，ワタシの環境では動作せずでした。
でで，その permutation 関数と実行結果は，以下。

(defun permutaion (nlst)
  (labels ((f (lst)
             (if (null (cdr lst))
                 (list lst)
                 (loop for i in lst
                       nconc (mapcar (lambda (l)
                                       (append (list i) l))
                                     (permutaion (remove i lst :count 1)))))))
    (remove-duplicates (f nlst)
                       :test #'equal)))
(mapcar #'list-to-num (permutaion (num-to-list 1234))) ;=>
(1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214
 3241 3412 3421 4123 4132 4213 4231 4312 4321)

(mapcar #'list-to-num (permutaion (num-to-list 7777))) ;=> (7777)

(mapcar #'list-to-num (permutaion (num-to-list 7979))) ;=>
(7799 7979 7997 9779 9797 9977)


ま，順列すべてを求める必要はないよね〜とかなんとか。

まとめ

  • 紙とペン大事。
  • テスト大事。
  • Problem 51 でさっそく心が折れそう。