読者です 読者をやめる 読者になる 読者になる

Arantium Maestum

プログラミング、囲碁、読書の話題

SICPの勉強 問題1.36

SICP1.3.3の問題1.36を解いてみる。 と、その前にまずfixed-pointをClojureっぽく書いてみる。 シーケンス[a0 a1 ... an-1 an]から[a0 a1 ... ai-2 ai-1] [a1 a2 ... ai-1 ai] [a2 a3 ... ai ai+1]と続くベクトルのシーケンスを作成する関数: (defn conseq …

SICPの勉強 問題1.33

SICP1.3.1の問題1.33を解いてみる。 filtered-accumulateのiterative process版: (defn filtered-accumulate [combiner null-value filt f a next b] (loop [a a result null-value] (cond (> a b) result (filt a) (recur (next a) (combiner (f a) result…

SICPの勉強 問題1.32

SICP1.3.1の問題1.32を解いてみる。 accumulateのrecursive process版: (defn accumulate [combiner null-value f a next b] (if (> a b) null-value (combiner (f a) (accumulate combiner null-value f (next a) next b)))) iterative process版: (defn …

SICPの勉強 問題1.31

SICP1.3.1の問題1.31を解いてみる。 productのrecursive process版: (defn product [f a next b] (if (> a b) 1 (* (f a) (product f (next a) next b)))) iterative process版: (defn product [f a next b] (loop [a a result 1] (if (> a b) result (rec…

SICPの勉強 問題1.30

SICP1.3.1の問題1.30を解いてみる。 末尾再帰にするのがポイント。問いの中のコードをできるだけ利用するなら: (defn sum [f a next b] (letfn [(iter [a result] (if (> a b) result (recur (next a) (+ (f a) result))))] (iter a 0))) これで先ほどの(in…

SICPの勉強 問題1.29

SICP1.3.1の問題1.29を解いてみる。 とりあえずSimpson Ruleを使わない積分法: (defn sum [f a next b] (if (> a b) 0 (+ (f a) (sum f (next a) next b)))) (defn integral [f a b dx] (letfn [(add-dx [x] (+ x dx))] (* (sum f (+ a (/ dx 2.0)) add-dx …

SICPの勉強 問題1.17~18

SICP1.2.4の問題1.17と1.18を解いてみる。 とりあえずdoubleとhalveを定義: (defn double [x] (* 2 x)) (defn halve [x] (/ x 2)) linear recursiveに書くとこんな感じ: (defn mul [a b] (cond (zero? b) 0 (even? b) (double (mul a (halve b))) :else (+…

SICPの勉強 問題1.16

SICP1.2.4の問題1.16を解いてみる。 (defn fast-exp-iter [b n] (loop [n n x 1 y b z 1] (cond (zero? n) z (< n (* 2 x)) (recur (- n x) 1 b (* y z)) :else (recur n (* 2 x) (* y y) z)))) 引数名が考えつかなかった、というのはいつもの弁。 n = 2a1 +…

Clojureで農夫と狼とヤギとキャベツ問題

これも「関数型オブジェクト指向AIプログラミング」から。 宣教師と食人鬼に続き、同じような川渡りロジック問題の農夫と狼とヤギとキャベツを解いてみる。 前回のコードをほぼ流用。元の本では差分プログラミング的にWolfGoatCabbageクラスをMissionariesAn…

ClojureでMissionary & Cannibal問題

「関数型オブジェクト指向AIプログラミング」からMissionaries and Cannibals問題のコーディング。 まずは状態を表すデータの定義。 [{:missionary 3 :cannibal 3} {:missionary 0 :cannibal 0} :left] 左岸にいる宣教師と食人鬼の数のマップ、右岸にいる数…

Quilでランダムな線を引く

ジェネラティブ・アート Processingによる実践ガイドという本を買ってみた。 Processingでコンピュータを使って図形にランダム性を持たせるとすごく複雑かつ美しい結果が出る(かもしれない)という話。 まずは基礎中の基礎である、ランダム性を持たせた線を…

Quilでフラクタル Mandelbrot

「関数型オブジェクト指向AIプログラミング」に載っていなかったのでやっていなかったが、フラクタルで一番有名なものは多分マンデルブロだろう。 というわけでこれもClojure&Quilで書いてみる。 今まで書いてきたフラクタルに比べてかなり複雑な概念である…

Clojureで騎士の巡回問題を解いてみる

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 (…

ClojureでN-Queen問題を解いてみる

「関数型オブジェクト指向AIプログラミング」もちまちま読んでいきたい。 有名な8-Queen問題を一般化したN-Queen問題。本では再帰的に解いているので、まずはそれをなぞってみる。 とりあえずデータの定義。4x4のグリッドに以下のような配置の場合: X-Q-X-X…

SICPの勉強 Lecture 1A-2

レクチャービデオの頭の方でHarold Abelsonの紹介テキストがちょこっと出るのだが、Assoc. Prof. EE & CSとある。 「電気工学と計算機科学の准教授」というわけだ。実際ちょくちょく電磁信号処理の話題が出てくる。そして信号処理はLisp(あるいは関数型言語…

SICPの勉強 Lecture 1A-1

というわけで本命のStructure and Interpretation of Computer Programs読解。 作者二人がヒューレット・パッカード社員向けにやったレクチャービデオと合わせて読んでいきたい。 www.youtube.com Computer Science is a terrible nameというのはまさにその…

Rich HickeyのAnt Simulationを調べてみる1

recordsやらschemaやらspecterやらSTMやらの勉強に、小さめのプロジェクトをやってみたいなーと思っていたらRich Hickeyの古いプレゼンで良さげなものがあったので調べている。 www.youtube.com サムネの画像は非常に有名というかRich Hickeyの教祖ちっくな…

Clojure入門 - Project Eulerを解いてみる 問17続

この記事の続き。 @_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さんとあやぴーさ…

Clojure/QuilでGame of Lifeを表示してみた

前回はn時点での生きたセルの集合からn+1時点での生きたセルの集合を算出する関数を定義した。 はっきり言ってGame of Life的なところはそれで終わりなのだが、やはりアニメーションで見てみたい、ということでQuilで表示してみる。 atomなどで状態を管理し…

ClojureでGame of Lifeを書いてみた

Conway's Game of LifeをClojureで実装してみる。 何となく簡単そうだったので試してみたら、やっぱり簡単だった。 主要なロジックはnext-round関数にほぼ収まりきっている。個人的にはかなり宣言的にゲームのルールを記述するところが大部分を占めているよ…

簡単な硬貨問題 from IT速報4

前回からの続き 「随分とダサいコードを書いてるのね」と某IQ145の女子高生*1に言われた気がしたので考え直してみたら、こうなった。 (def coins [500 100 50 10 5 1]) (defn coin-divide [n] (map quot (reductions rem n coins) coins)) 一つの直線で全部…

勉強したいもの

Clojureを書き散らかしてきて、何となく文法や好きな書き方、どんなエコシステムになっているのかなどがわかってきた。 しかし、汎用性のあるライブラリを含めて、まだClojureの基本的なところさえ使いきれていない。 忘備録的な意味合いも含めて、近いうち…

Quilでフラクタル Tree

「関数型オブジェクト指向AIプログラミング」のフラクタルをscalaからclojureに書き直す続き。 ツリー状の図形をフラクタルで描画してみる。 (defn tree [n length angle switch] (q/push-matrix) (if (= 1 n) (forward length angle) (let [l (/ length (/ …

Quilでフラクタル Szierpinski

「関数型オブジェクト指向AIプログラミング」のフラクタルをscalaからclojureに書き直す続き。 フラクタルといえばマンデルブロかシェルピンスキー、というくらいにメジャーなフラクタルであるシェルピンスキー三角を描いてみる。 (defn szierpinski ([n len…

Quilでフラクタル Dragon

「関数型オブジェクト指向AIプログラミング」のフラクタルをscalaからclojureに書き直す続き。 ドラゴン曲線を描いてみる。 namespaceやらdefsketchやらはkochのものを流用して、図形のためのdragon関数とそれに引数入れて呼ぶdrawだけ再定義: (defn dragon…

Quilでフラクタル Koch

積読中だった「関数型オブジェクト指向AIプログラミング」にフラクタルの話が出ていたのを思い出したのでQuilでやってみる。 ちなみにこの本はScalaで、フラクタルに関して出てくるコードはどこをどう見ても相当オブジェクト指向なのが少し不思議。パッと見…

Quil覚書 Clojureで視覚的デザイン

昔からProcessingがやりたかったのだけど、なかなかいい機会がなく放置していた。 しかし、ClojureでもProcessingをベースにしたQuilというライブラリがあることを知り、どうせClojureを勉強しているのだから、と早速使ってみた。 基本中の基本だとこんな感…

Clojureで動的計画法を使ってKnapsack Problemを解いてみる

Project Eulerの31問と同じような動的計画法を使ったナップサック問題の解き方。 m kgまで入るカバンと、n個のモノがある。 モノiはx-i kgでy-i円の価値がある。 カバンに入り、価値の合計が最大になるモノの組み合わせは何か。 まずはデータ構造の定義。 (d…

Clojureでアルゴリズムまとめ

ソート selection sort insertion sort bubble sort 1/ 2/ 3 merge sort 1 2 quick sort bucket sort radix sort

Clojureで基数ソート

Radix Sortとも。 バケツソートのバケツ数を制限して、そのかわり複数回走らせることで すでにバケツソートを書いたので実装は比較的楽。 (defn radix-sort [xs] (let [bucket-count 100 buckets (into [] (repeat bucket-count [])) max-item (apply max xs…

Clojureとマルコフ連鎖で自動文章生成

自動文章生成の手法の一つとして昔から有名なのが、マルコフ連鎖でn-gramから次の単語を確率的に決めて行くやり方である。 元となる文章データから、n語の連なり(prefixと呼ばれる)の後に来る単語の確率分布を作る。 起点としてn語を用意し、確率分布に従…

Clojureでバケツソート

正の整数のシーケンスxsをO(n+m)時間でソートする方法としてBucket Sortがある。 0からxsの最大値mまで番号が付けられているvector of vectorを作成して、xsの全要素を一つずつ対応するvectorに入れていく。あとはconcatするだけ。 (defn bucket-sort [xs] (…

clojureでバブルソート3

あやぴーさんのご指摘を参考に、バブルソートをいろいろ(主に名前を)いじってみる。 最終的にはremainingのdestructuringを後に遅らせた方が、実際に使うところの近くで定義されるのでわかりやすいんじゃないか、ということに。 (def max-min (juxt max mi…

Clojure入門 - Project Eulerを解いてみる 問31 続々

前回からの続き。

Clojureでバブルソート2

そういえばClojureのsequenceはvectorじゃない場合は大抵countがO(n)だった。 bubble-sortでO(n)回bubbleを呼び、bubble内でO(n)回再帰して、その中でO(1)の作業だったはずが、(cond (>= i (count xs)))でもう一回O(n)の作業を入れていたのでO(n3)になる。 …

Clojureでバブルソート

とりあえず書きなぐったもの。 (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…

Clojureでインサーションソート

例によってソート実装。これは面白かった。 とりあえず書いてみたのは以下のコード: (defn insert [x sorted] (let [[heads tails] (split-with #(<= % x) sorted)] (concat heads [x] tails))) (defn insertion-sort [xs] (loop [[head & tail :as unsorte…

Clojureでセレクションソート

まあとりあえず。 (defn selection-sort [xs] (loop [unsorted xs, sorted []] (if (empty? unsorted) sorted (let [unsorted-indexed (map vector (range) unsorted) [min-i min-v] (apply min-key second unsorted-indexed) [heads [_ & tails]] (split-at…

Clojureでクイックソート

書いてみる。 まずはletの中にベタ書き。 (defn quick-sort [col] (if (>= 1 (count col)) col (let [i (rand-int (count col)) pivot (nth col i) heads (take i col) tails (drop (inc i) col) col2 (concat heads tails) lesser (filter #(< % pivot) col…

簡単な硬貨問題 from IT速報3

前回 まあこれもありかも。 (def coins [500 100 50 10 5 1]) (defn f [[remainder & count-list] coin] (concat ((juxt rem quot) remainder coin) count-list)) (defn coin-count2 [n] (->> coins (reduce f (list n)) next reverse)) reduceの戻り値を、…

簡単な硬貨問題 from IT速報2

前回 ふと気づいたのだが、この問題ってreduceじゃなくてreductionsで書けば、「fの中でvectorを作成してそれを戻り値のvectorに入れて・・・」というvector入れ子状態を避けられる。 (def coins [500 100 50 10 5 1]) (defn f [[last-count remain] coin] (…

Clojureでマージソート2

とりあえずiterate版も貼っておく。 (defn merge ([col] col) ([[head1 & rest1 :as col1] [head2 & rest2 :as col2]] (cond (some empty? [col1 col2]) (concat col1 col2) (< head1 head2) (lazy-seq (cons head1 (merge rest1 col2))) :else (lazy-seq (c…

Clojureでマージソート

なんとなくやってみた。 (defn merge ([col] col) ([[head1 & rest1 :as col1] [head2 & rest2 :as col2]] (cond (some empty? [col1 col2]) (concat col1 col2) (< head1 head2) (lazy-seq (cons head1 (merge rest1 col2))) :else (lazy-seq (cons head2 (…

簡単な硬貨問題 from IT速報

Project Eulerをブログ用に解いていると、 答えを出す 2.高速化 3.コードの美化 の順番でかなり書き直しが必要なので、ただ単に解き散らかすのに比べてべらぼうに時間がかかる。 息抜きにIT速報を見ていたら、タイムリーなことに硬貨関連の問題が出ていた。 …

Clojure入門 - Project Eulerを解いてみる 問31 続

前回からの続き。

Clojure入門 - Project Eulerを解いてみる 問31 序

第三十一問 合計で200p(200ペンス=2ポンド)になるコインの組み合わせが何通りあるかを計算する。

Clojure入門 - Project Eulerを解いてみる 問30

第三十問 二桁以上の整数で、その数の各桁の5乗の和と等しいものを選んで足し合わせる。

Clojure入門 - Project Eulerを解いてみる 問29

第二十九問 a=2...100、b=2...100でabの取り得る個別の値の総数を求める。

Clojure入門 - Project Eulerを解いてみる 問28

第二十八問 数字の渦の角の和。

Clojure入門 - Project Eulerを解いてみる 問27

第二十七問 x=0..nで、 x2 + a*x + b がすべて素数となるnの値が最大となるaとbを求める。