Snow Leopardがリリースされてから早くも2ヶ月が経過しましたが、CVS先端のCocoa Emacsのビルドが通るようになっていました。勿論、嬉しいことに、64ビットバイナリです。ビルド方法は以前と変わっていないようです。私の環境ではlibtiffとlibungifを入れる…
Mac OS X 10.6 Snow Leopardの雑感をつらつらと書き留めています。 Mac OS X 10.6にバンドルされているPythonのヴァージョンは2.6.1でした。流石のAppleもPython 3.x系の採用には踏み切れなかったのでしょうか。何れにせよ、itertools.(permutations|combina…
Snow Leopardと呼ばれているMac OS X 10.6をインストールしました。今回のリリースはLeopard、Mac OS X 10.5から大きく変更されることはないだろうという予想の元、アップグレードインストールをしようかと考えていたのですが、結局スクラッチからインストー…
Snow LeopardをインストールしようとしているEmacsユーザーは少々気を付けたほうがよいかもしれません - Snow Leopardリリース直後現在において、Cocoa EmacsおよびCarbon Emacsの双方ともにビルドすることが出来ません。ただし、LeopardにてビルドしたCocoa…
先日のエントリでは射影を用いた矩形の交差判定について記載しました。その際の実装は以下のようなものでした。 def intersect(A, B): for a, b in zip(zip(*A), zip(*B)): if max(b) < min(a) or max(a) < min(b): return False return True 実装にはベクト…
さて、先日までのエントリにて矩形と射影について各々解説しました。今回のエントリでは、射影を応用した矩形の交差判定について記載したいと思います。早速、以下のようなAとBの二つの矩形の交差判定について考えてみましょう。先日のエントリにて解説した…
先日のエントリでは、射影(Projection)を用いた領域検索について解説し、簡単な実装を行いました。今回はその実装をリファクタリングしてみます。 では、早速始めましょう。先日のコードをジェネレータとしてsequential_search()関数にまとめたコードから開…
先日のエントリでは、矩形の交差判定を行う際の用語の紹介を行いました。今回のエントリでは、射影(Projection)という技法を紹介します。一見、射影は単純なことを難しく表現しているだけに感じられるかもしれません。しかし、計算幾何や領域検索を考えるに…
先日のエントリではマンハッタン幾何を紹介し、総当たりによる実装を行いました。その際、水平と垂直の線分を縮退した矩形とみなし、交差判定を行いました。今回のエントリでは、矩形の交差判定アルゴリズムを考えるための用語の解説を行います。また、次回…
先日kd-treeについてのエントリを記載したことは、自分にとって計算幾何の面白さを再認識する良い機会となりました。計算幾何で用いられる幾何学的アルゴリズムは比較的若く、今でも進化の過程にあります。また、人間には単純に見える問題も計算機にとっては…
先日のエントリに引き続き、Quick Selectアルゴリズムについて考えてみたいと思います。Quick Selectアルゴリズムを考えるに至った動機は、メディアンを選択することでした。今回は以下の9個の要素を持つ配列を使って考えてみましょう。ここでは、配列のイン…
先日のエントリではメディアンの選択にsort()を用い、より効率のよいメディアンの選択方法を課題としました。さて、今回そのアイデアの一つとして紹介するのはQuick Selectというアルゴリズムです。Quick Selectというアルゴリズム名は一般的ではないかもし…
さて、先日のエントリにて、メディアンを加味した2d木の構築を紹介しました。コードの見通しを簡潔にする目的もあり、メディアンの選択にはsort()を用いました。 #!/usr/bin/python -t from operator import itemgetter from random import seed, randint de…
先日のエントリにて、kd木を紹介しました。前回はアルゴリズム Cに倣って、要素の追加のみでkd木を構築してみました。繰り返しになりますが、一般的に要素の追加のみでkd木を構築するとバランスの悪い木となることが知られています。先日のエントリで作成し…
前回のエントリに引き続き、連続したビット群の総数を求めるアルゴリズムを考える予定でしたが、今回は空間分割データ構造に関するエントリにしました。人力検索はてなに以下のような問題が提示されていたのがきっかけでした。 二次元の値(x, y)をもつ集合P …
先日のエントリにて掲載した問題の回答を検証するに当たり、コードを書いてみました。問題は以下のようなものでした。 さて、この問題には「壊してもよいブロック」と「必ず残るブロック(確定のブロック)」が一つずつあるようです。それは一体どれでしょうか…
任天堂から発売された立体ピクロスにはまっています。これは面白い。ピクロスDS等の平面でのピクロスとは異なった趣を持ち、また全く異なる要素を持ったパズルであるよう感じます。任天堂 ++ 細かいルールは任天堂の立体ピクロスのページを参照して頂くとし…
この問題が面白そうだなと思い、私もPythonで挑戦してみました。目的は、数字にコンマを振ることです。 「Python のジェネレータ (2)」に引き続き、ジェネレータに慣れるための練習。o(+_+)o どかにまた例題はないかと散策していたら、「数字にコンマを振る…
和田栄一先生のブログが大好きです。淡々とした静かな文章の間々に、計算機への愛情が見え隠れする様はたまりません。そんな和田先生が、節分に関するエントリにて、以下のような問題を取り上げていました。 年の数が多いと, 10の桁の数と1の桁の数を足した…
先日のエントリにてCocoa Emacsをインストールしました。Cocoa Emacsではバンドルという形式が取られたため、site-lispのパスがドラスティックに変更され、Emacs Museが動作しなくなってしまいました。良い機会であるので、最新版のEmacs Museをインストール…
