おびなたのはてな日記 - C++ テンプレートでLisp
一昨日のエントリー（d:id:earth2001y:20060929:p2）でC++のテンプレートがチューリング完全性を備えているということを、見つけた論文から言及した。で、C++テンプレートだけでBrainfuckインタプリタを書こうとして一旦挫折したが、テンプレートの記述が宣言的、関数的な点を考えて、純Lispを書いてみることにした。 純Lispについては、 はてなキーワードの純Lisp 純Lisp - Wikipedia あたりを、ご参考あれ。ようは、McCarthyがLispを発明したときのオリジナルで、最小のLisp関数セット。 PL.CT - Pure Lisp on C++ Template とりあえず、テンプレートの実装。 // cat purelisp.h class NIL { public: typedef NIL eval; }; class T { public:
組み合わせ最適化問題とぷよぷよ - おびなたん☆
先月の電子情報通信学会論文誌の「組合せ最適化問題としてのぷよぷよの連鎖数判定問題」を読むことができた。過去にぷよぷよというゲームそれ自体についての論文が無い*1ので、その数理モデルの定義から議論を始めている。で、結論として4色以上のぷよぷよでは、ある盤面と落ちてきたピース列から連鎖数を判定することはNP完全であることを証明している。以後の課題としては、4色以下のときに、NP完全となるかどうか。さらに関連研究で、与えられたぷよが全て落ちたときに、全消しできるかどうかはNP完全であることも分かっているらしい。 ぐぐってみると、第一著者の松金輝久さんは「第２回ぷよマスターズ」決勝戦進出者。趣味が功奏しての論文ということか。 *1:ゲームのWebサイトをリファレンスしている
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
