水島雄太のブログ

個人的かつ雑多なブログです。

迷路自動生成

先日リリースしたアプリで迷路自動生成を実装してみたので、 まとめてみます。

迷路自動生成の仕様としては、

  • 2次元平面の対角をスタートとゴールとする
  • スタートは必ず一つ
  • ゴールは必ずしも、一本の道で終わってなくても良い

以上の3点となります。

これらを踏まえた上で以下のようにステップ実行してみました。

ステップ実行してみると、1ステップごとに以下の点を考えるだけで、 全ての処理が終了するように思いました。

  1. 行き止まりではない場合、ランダムで分岐を選択
  2. 行き止まりだった場合、選択していない分岐まで戻る
  3. もし全ての点を走査したら処理を終了

データ構造としては、

  • X座標、Y座標、前の点、探索済みフラグを保持しておく
  • 再帰を使って前の点への参照を作っていく

以上で、迷路を単純な木構造として表現出来そうです。

このよう方針にてPythonで実装してみました。

実際の動作としては、既にiPhoneで実装したものをリリースしていますので、 それで確認してみてください。

minosound

このアルゴリズムの問題点としては、

  • ゴールの深さが迷路が生成されるたびに変わる。
  • 分岐が浅くなりやすい。

といったことがあるため、 今後何かしらのアルゴリズムの修正が入るかもしれません。

Homebrewでインストールしたleiningen1.xからleiningen2.xへのUpgrade

2013/04/04現在、Homebrewでインストールされる leiningenが1.x系列なので2.x系列にUpgradeしてみました。

ほぼleiningen/wiki/Upgradingの手順通りです。

直接Cellarいじくっていいのかよくわかりませんので、こうした方が良いよというのがあれば指摘していただけるとありがたいです。

$mkdir /usr/local/Cellar/leiningen/2.1.2/bin
$brew install wget
$wget -O /usr/local/Cellar/leiningen/2.1.2/bin/lein https://raw.github.com/technomancy/leiningen/stable/bin/lein
$ln -s /usr/local/Cellar/leiningen/2.1.2/bin/lein /usr/local/bin/lein
$chmod 755 /usr/local/bin/lein

ここから ~/.lein/plugins/ にあるプラグインを ~/.lein/profiles.clj に追加していきます。

~/.lein/bin/ が以下のようになっていたので、 compojure-lein-template-0.2.0.jar lein-newnew-0.2.6.jar swank-clojure-1.4.2.jar

~/.lein/profiles.clj に以下のように記述します。

{:user {:plugins [
    [lein-immutant "0.18.0"]
    [compojure/lein-template "0.2.0"]
    [lein-newnew "0.2.6"]
    [swank-clojure "1.4.2"]]}}

これで完了です。

今回immutantというアプリケーションサーバをインストールするために leiningen2.x系列にupgradeしたので、

$lein install immutant

で問題なくインストール出来ました。

ちなみに、~/.lein/profiles.cljは今後編集していくと思いますので、 dotfilesに組み込みました。

設定したい方は以下のリポジトリの.gitignore、.lein/profiles.clj、参考にしていただければと思います。

ymizushi/dotfiles

zshでgit checkoutを叩いた時のリモート補完を無効

最近bashからzshに移行したが、 zshではデフォルトでリモート補完が有効になっているので、 git checkout でブランチ名補完を行おうとした際に、 リモートのブランチ名を探しに行ってしまう。 そのため補完が完了するまで入力を受け付けないという事が頻発するので、 無効にする方法を探してみた。

StackOverflowで見つけた記事によると、

.zshrcに compdef -d git checkout

を追記するだけで補完を無効に出来る事はわかったが、 こうするとローカルブランチも補完が無効になってしまう。

誰しもが無効にしたくなると思ったんだが、なんでぱっと情報出てこないんだろうか。

参考: http://stackoverflow.com/questions/12175277/disable-auto-completion-of-remote-branches-in-zsh

Vimでカレント列から行末までをヤンク

Vimではノーマルモードで Dでカレント列から行末までを削除してヤンク、 Cでカレント列から行末までを削除してヤンクして挿入モード に入るのに、 カレント列から行末までをヤンクするコマンドが y$ でしか出来ないので、 nnoremap Y y$ しておけばいいと思います。

Pythonのitems()とiteritems()の違い

Python2.xの辞書オブジェクトに対する組み込みメソッド、 items()はkeyとvalueをtupleに格納したlistを生成して返すのに対して、 iteritems()はイテレータを返す。

items()はいちいちリストを生成する分、オーバーヘッドがかかるので、 基本的にiteritemsを使ったほうが良いっぽい。

一方、イテレータはスライスが使えないので、 スライスで要素の範囲指定をしたいときは、items()で取ってこないといけない。

ただ、3.xではitems()もイテレータを返すようになり、iteritems()は廃止になったそうです。

参考: http://stackoverflow.com/questions/10458437/python-what-is-the-difference-between-dict-items-and-dict-iteritems

パーフェクトPython
パーフェクトPythonPythonサポーターズ

技術評論社 2014-10-31
売り上げランキング : 15928


Amazonで詳しく見る
by G-Tools
Pythonプロフェッショナルプログラミング 第2版
Pythonプロフェッショナルプログラミング 第2版株式会社ビープラウ

秀和システム 2015-02-28
売り上げランキング : 4750


Amazonで詳しく見る
by G-Tools

git rebase

  • git rebaseするときの注意点

git rebaseはbranchを切ってからのcommitを全て書き換えてしまう(ハッシュも違うものになる)ので、リモートブランチにpushしてから、git rebaseを行うと、そのままではpush出来ず、
間違えてpull してしまうと、同じ内容のコミットが別のコミットとして扱われ、同一の内容が重複してマージされてしまう。
とりあえず、

  1. 公開ブランチでは絶対にgit rebaseしない。
  2. pushに失敗したら、リモートとローカルのコミット履歴を確認した上で、git push -fを行う(確認をせずにpush -fを行わない。もし他の人がそのブランチにcommitしていた場合、最悪そのcommitが失われる。)
  3. git rebaseした後は、pushするまで絶対にpullは行わない

この位守っておけば、大失敗はしないかな?

何にせよ、git rebaseはgitの仕組みをちゃんと理解してないと危険だよな。