2016-05-01から1ヶ月間の記事一覧
Twitterを見ていたらDavid Beazleyがこんなつぶやきをしていた。 Curio abides. https://t.co/cPqEfr6dOD— David Beazley (@dabeaz) 2016年5月30日 Curioってなんだ?とリンクを辿って読んでみたら去年のブラジルPyconで話した内容をさらに進化させたライブ…
これも「関数型オブジェクト指向AIプログラミング」から。 宣教師と食人鬼に続き、同じような川渡りロジック問題の農夫と狼とヤギとキャベツを解いてみる。 前回のコードをほぼ流用。元の本では差分プログラミング的にWolfGoatCabbageクラスをMissionariesAn…
「関数型オブジェクト指向AIプログラミング」からMissionaries and Cannibals問題のコーディング。 まずは状態を表すデータの定義。 [{:missionary 3 :cannibal 3} {:missionary 0 :cannibal 0} :left] 左岸にいる宣教師と食人鬼の数のマップ、右岸にいる数…
ジェネラティブ・アート Processingによる実践ガイドという本を買ってみた。 Processingでコンピュータを使って図形にランダム性を持たせるとすごく複雑かつ美しい結果が出る(かもしれない)という話。 まずは基礎中の基礎である、ランダム性を持たせた線を…
「関数型オブジェクト指向AIプログラミング」に載っていなかったのでやっていなかったが、フラクタルで一番有名なものは多分マンデルブロだろう。 というわけでこれもClojure&Quilで書いてみる。 今まで書いてきたフラクタルに比べてかなり複雑な概念である…
N-Queen問題に続いて騎士の巡回。 (defn knight-tour [n] (let [board (set (for [i (range n) j (range n)] [i j])) dirs (for [a [1 2] i [-1 1] j [-1 1]] (let [b (- 3 a)] [(* i a) (* j b)])) tour (fn f [pos visited i] (if (= (* n n) i) visited (…
「関数型オブジェクト指向AIプログラミング」もちまちま読んでいきたい。 有名な8-Queen問題を一般化したN-Queen問題。本では再帰的に解いているので、まずはそれをなぞってみる。 とりあえずデータの定義。4x4のグリッドに以下のような配置の場合: X-Q-X-X…
レクチャービデオの頭の方でHarold Abelsonの紹介テキストがちょこっと出るのだが、Assoc. Prof. EE & CSとある。 「電気工学と計算機科学の准教授」というわけだ。実際ちょくちょく電磁信号処理の話題が出てくる。そして信号処理はLisp(あるいは関数型言語…
というわけで本命のStructure and Interpretation of Computer Programs読解。 作者二人がヒューレット・パッカード社員向けにやったレクチャービデオと合わせて読んでいきたい。 www.youtube.com Computer Science is a terrible nameというのはまさにその…
recordsやらschemaやらspecterやらSTMやらの勉強に、小さめのプロジェクトをやってみたいなーと思っていたらRich Hickeyの古いプレゼンで良さげなものがあったので調べている。 www.youtube.com サムネの画像は非常に有名というかRich Hickeyの教祖ちっくな…
この記事の続き。 @_ayato_p "cl-format ... is *fully* compatible with the format function in Common Lisp (https://t.co/GriobfPdtw)." とは凄いですね!~RがUS綴りなのが惜しい :)— Nobuhiko FUNATO (@nfunato) 2016年3月27日 nfunatoさんとあやぴーさ…
前回はn時点での生きたセルの集合からn+1時点での生きたセルの集合を算出する関数を定義した。 はっきり言ってGame of Life的なところはそれで終わりなのだが、やはりアニメーションで見てみたい、ということでQuilで表示してみる。 atomなどで状態を管理し…
stackoverflow.com a, b = a[b] = {}, 5 Raymond Hettingerの過去ツイートを追っていたら、これってどうなるんだ?とわからなかった式があった。 結果はa = {5:(a, 5)}、b=5と再帰的なディクショナリーができる。 肝は代入式の評価順で、a = b = c = dの場合…
Conway's Game of LifeをClojureで実装してみる。 何となく簡単そうだったので試してみたら、やっぱり簡単だった。 主要なロジックはnext-round関数にほぼ収まりきっている。個人的にはかなり宣言的にゲームのルールを記述するところが大部分を占めているよ…
前回からの続き 「随分とダサいコードを書いてるのね」と某IQ145の女子高生*1に言われた気がしたので考え直してみたら、こうなった。 (def coins [500 100 50 10 5 1]) (defn coin-divide [n] (map quot (reductions rem n coins) coins)) 一つの直線で全部…
Clojureを書き散らかしてきて、何となく文法や好きな書き方、どんなエコシステムになっているのかなどがわかってきた。 しかし、汎用性のあるライブラリを含めて、まだClojureの基本的なところさえ使いきれていない。 忘備録的な意味合いも含めて、近いうち…
「関数型オブジェクト指向AIプログラミング」のフラクタルをscalaからclojureに書き直す続き。 ツリー状の図形をフラクタルで描画してみる。 (defn tree [n length angle switch] (q/push-matrix) (if (= 1 n) (forward length angle) (let [l (/ length (/ …
「関数型オブジェクト指向AIプログラミング」のフラクタルをscalaからclojureに書き直す続き。 フラクタルといえばマンデルブロかシェルピンスキー、というくらいにメジャーなフラクタルであるシェルピンスキー三角を描いてみる。 (defn szierpinski ([n len…
「関数型オブジェクト指向AIプログラミング」のフラクタルをscalaからclojureに書き直す続き。 ドラゴン曲線を描いてみる。 namespaceやらdefsketchやらはkochのものを流用して、図形のためのdragon関数とそれに引数入れて呼ぶdrawだけ再定義: (defn dragon…
積読中だった「関数型オブジェクト指向AIプログラミング」にフラクタルの話が出ていたのを思い出したのでQuilでやってみる。 ちなみにこの本はScalaで、フラクタルに関して出てくるコードはどこをどう見ても相当オブジェクト指向なのが少し不思議。パッと見…
昔からProcessingがやりたかったのだけど、なかなかいい機会がなく放置していた。 しかし、ClojureでもProcessingをベースにしたQuilというライブラリがあることを知り、どうせClojureを勉強しているのだから、と早速使ってみた。 基本中の基本だとこんな感…
Project Eulerの31問と同じような動的計画法を使ったナップサック問題の解き方。 m kgまで入るカバンと、n個のモノがある。 モノiはx-i kgでy-i円の価値がある。 カバンに入り、価値の合計が最大になるモノの組み合わせは何か。 まずはデータ構造の定義。 (d…
ソート selection sort insertion sort bubble sort 1/ 2/ 3 merge sort 1 2 quick sort bucket sort radix sort
Radix Sortとも。 バケツソートのバケツ数を制限して、そのかわり複数回走らせることで すでにバケツソートを書いたので実装は比較的楽。 (defn radix-sort [xs] (let [bucket-count 100 buckets (into [] (repeat bucket-count [])) max-item (apply max xs…
自動文章生成の手法の一つとして昔から有名なのが、マルコフ連鎖でn-gramから次の単語を確率的に決めて行くやり方である。 元となる文章データから、n語の連なり(prefixと呼ばれる)の後に来る単語の確率分布を作る。 起点としてn語を用意し、確率分布に従…
正の整数のシーケンスxsをO(n+m)時間でソートする方法としてBucket Sortがある。 0からxsの最大値mまで番号が付けられているvector of vectorを作成して、xsの全要素を一つずつ対応するvectorに入れていく。あとはconcatするだけ。 (defn bucket-sort [xs] (…
あやぴーさんのご指摘を参考に、バブルソートをいろいろ(主に名前を)いじってみる。 最終的にはremainingのdestructuringを後に遅らせた方が、実際に使うところの近くで定義されるのでわかりやすいんじゃないか、ということに。 (def max-min (juxt max mi…
前回からの続き。
そういえばClojureのsequenceはvectorじゃない場合は大抵countがO(n)だった。 bubble-sortでO(n)回bubbleを呼び、bubble内でO(n)回再帰して、その中でO(1)の作業だったはずが、(cond (>= i (count xs)))でもう一回O(n)の作業を入れていたのでO(n3)になる。 …
とりあえず書きなぐったもの。 (defn bubble [xs i] (loop [left [] x1 (first xs) [x2 & right :as xs] (rest xs)] (cond (>= i (count xs)) (doall (concat left [x1] xs)) :else (let [[maxx minx] ((juxt max min) x1 x2)] (recur (conj left minx) maxx…