人間万事塞翁が馬

2016年5月19日木曜日

RUST でファイル入力処理

迷路のレイアウトをコードにベタ書きで埋め込むのは骨が折れるので、下のようなテキストで作成した迷路を読み込めるようにした。

だいぶ長くなってきたので、アルゴリズム以外を別ファイルに移した上で、ファイルから迷路を構築する処理を追加。
メインからはモジュールとして読み込んで利用する。
ファイル入力自体は比較的簡単だったが、エラー処理にだいぶ嵌められた。
エラー処理の仕様をきちんと理解しないままサンプルを見よう見まねでコピペしても全然コンパイルできなかった。
その分ちゃんと理解すれば柔軟なエラー処理ができるんだが、正直かなりとっかかりにくいと思う。

2016年5月14日土曜日

RUST 勉強中

環境構築

インストール

Ubuntu16.04 だと apt-get から入手できるようになった。

エディタ設定

Emacs 使いなので、melpa から lang-rust を導入

お勉強

何は無くとも RUST のドキュメントを熟読。

どうやらメモリ参照の透過性の高いプログラミング言語らしい。
なので、マルチスレッドとかに向いているそうだ。

一応オブジェクトっぽいこともできそうだが、オブジェクト指向言語ではないようだ。

実践

試しに単純な右手の法則で迷路を解くプログラムを書いてみた。

どうしても関数の引数が borrow ばっかりになってしまうが、これでいいんだろうか。

オブジェクト指向のようにポリモーフィズムばりばりで抽象化すると言うよりも、テンプレートで抽象化するが、テンプレートだとなんでもありになってしまうので、Trait で期待するテンプレートを指定するという感じか。
なんとなく、Cのマクロでこうできれば便利なんだけどなー、ってもどかしかったのができるようになっている感じで使っていて気持ちいい。

2016年1月18日月曜日

Kinect + Raspberry Pi 2 で監視カメラを作る(8)

運用の自動化

前回からだいぶ間が開いてしまったが、再起動のたびに手動でプログラムを起動するのはアホらしいので、Kinect プログラムを自動で起動するようにしていく。

自動起動の設定

まずは、camtest を適当にそれっぽいディレクトリにコピーしてついでにファイル名も kinect に変えておく。

> sudo install camtest /usr/local/sbin/kinect

で、/etc/init.d の下に起動/終了用スクリプトを作成
------------------------------
#! /bin/sh
### BEGIN INIT INFO
# Provides:             kinect
# Required-Start:       $remote_fs $syslog
# Required-Stop:        $remote_fs $syslog
# Default-Start:        2 3 4 5
# Default-Stop:
# Short-Description:    Kinect remote webcam system
### END INIT INFO
set -e
test -x /usr/local/sbin/kinect || exit 0
. /lib/lsb/init-functions
case "$1" in
start)
        log_daemon_msg "Starting Kinect webcam system" "kinect" || true
        if start-stop-daemon --background --start --quiet --oknodo --pidfile /var/run/kinect.pid --make-pidfile --exec /usr/local/sbin/kinect; then
            log_end_msg 0 || true
        else
            log_end_msg 1 || true
        fi
        ;;
stop)
        log_daemon_msg "Stopping Kinect webcam system" "kinect" || true
        if start-stop-daemon --stop --quiet --oknodo --pidfile /var/run/kinect.pid; then
            log_end_msg 0 || true
        else
            log_end_msg 1 || true
        fi
        ;;
*)
        log_action_msg "Usage: /etc/init.d/kinect {start|stop}" || true
        exit 1
esac
exit 0
------------------------------
sshd のスクリプトをベースに見よう見まねで改造しただけ。
本当は restart や status も作ったが、スペースの都合で割愛した。

出来上がったら、
> /etc/init.d/kinect start

などして動くのを確認したら
> sudo init q

でスクリプトのリストを更新（Ubuntu だと要らなかったのだが、よくわからん）

最後に
> update-rc.d kinect defaults

で、自動起動に登録。

ラズパイを一度再起動して自動で立ち上がるか確認しておく。

自動終了

Kinect の深度センサーは赤外線レーザーを使っている。

人体に影響があるとは思えないが、一晩中我が子に照射し続けるのも気が引けるため、深夜になったら自動で切れるようにする。

入手したラズパイはタイムゾーンが違っていたので、まずはそれを合わせておく。

> cp /etc/localtime /etc/localtime.org #念のためバックアップ
> cp /usr/share/zoneinfo/Asia/Tokyo /etc/localtime

色々と試行錯誤したのだが、Kinect の深度センサーの照射を止めるには USB から切り離す方法でしか止められなかった。
ちと乱暴だが、以下のコマンドで大本のポートから止めることで深度センサーの照射を止めることが出来るようだった。
> echo -n '1-1' > /sys/bus/usb/drivers/usb/unbind
（止まっているかどうかは、肉眼で深度センサーからうっすら出ている赤い光をみて確認した）

しかしながら、これをやると無線 LAN まで止まってしまうので、子供を寝かせる時間になったら自動で再起動するようにしたい。

というわけで、cron を使って以下のように自動で Kinect センサーの停止とラズパイの再起動を行うように設定した。

> sudo crontab -u root -e
※エディタが起動するので以下の行を追加
0 23 * * * /etc/init.d/kinect stop
5 23 * * * echo -n '1-1' > /sys/bus/usb/drivers/usb/unbind
0 18 * * * /sbin/reboot

これで、毎晩 23 時に Kinect プログラムが終了。その 5 分後にセンサーを停止し、翌日の 18 時になったら自動で再起動するようになる。

2015年12月27日日曜日

Kinect + Raspberry Pi 2 で監視カメラを作る(7)

ブラウザから Kinect を操作する（後編）

html の作成

とりあえず、以前作成した自動画像リロードのページをベースに制御コマンドを送信するためのフォームとボタンを追加する。

<body onload="loadimage()">
<form id="cntlform" action="/cgi-bin/control.pl" method="post"">
<div class="tcontrol">
<div class="tilt_up">
<input type="submit" class="tilt" name="cntl" value="UP">
<input type="submit" class="tilt" name="cntl" value="up">
</div>
<div class="tilt_down">
<input type="submit" class="tilt" name="cntl" value="dn">
<input type="submit" class="tilt" name="cntl" value="DN">
</div>
</div>
<div style="float:left;">
<canvas id="cv" width="640" height="480"></canvas>
<div class="vcontrol">
<input type="submit" class="video" name="cntl" value="RGB">
<input type="submit" class="video" name="cntl" value="IR">
<input type="submit" class="video" name="cntl" value="DEPTH">
</div>
</div>
</form>
</body>

正直 html はいまいち不慣れなので、divの構造などは適当。

POST と GET はどちらが良いのか毎度悩むが、POST は純粋にサーバーにデータを送信する場合（サーバーの状態を変更する）、GET はサーバーから情報を取得する時のパラメータとして送る情報（サーバーの状態は変わらない）と覚えている。
なぜそうなるかは、submit の挙動ではなく、submit 後に遷移したページをリロードしたり URL をコピペしたときにどうなる考えると想像が付くと思う。
当然今回は POST を使っている。

css をよしなに設定してあげればこんな感じで画面が表示される。

ボタンを押すたびにリロードされるのが嫌なら iframe を使うなどすれば回避できるそうだが、そんなに頻繁に押さなければ気にならないので放置。

CGI の作成

CGI自体は POST で送られてきたデータを解釈して FIFO に送るだけの非常にシンプルなもの。
一瞬 bash でも十分かと思ったが、そういえばシェルショックなる話があったなーと思い出して念のため perl で作成した。

#!/usr/bin/perl
use Fcntl;
print "Location: /kinect\n\n";
sysopen(FIFO, "/tmp/kinect", O_NONBLOCK | O_WRONLY) or die "Failef to open FIFO: $!\n";
read(STDIN, $data, $ENV{'CONTENT_LENGTH'});
foreach $item (split(/&/, $data)) {
        ($key, $value) = split(/=/,$item);
        if($key eq "cntl") {
                print $value;
                if($value eq "UP") {
                        $cmd = "P";
                } elsif($value eq "up") {
                        $cmd = "p";
                } elsif($value eq "dn") {
                        $cmd = "m";
                } elsif($value eq "DN") {
                        $cmd = "M";
                } elsif($value eq "RGB") {
                        $cmd = "R";
                } elsif($value eq "IR") {
                        $cmd = "I";
                } elsif($value eq "DEPTH") {
                        $cmd = "D";
                }

                $r = syswrite(FIFO, $cmd);
                if(!defined($r)) {
                        die "Write failed\n";
                }
        }
}
close(FIFO);

久々に perl 書いたけど、そういえば標準だと switch 文使えなかったのね。
正直ノンブロックにする必要はないのだが、後からFIFOが開いた時に溜まっていたコマンドが送られるケースがあり得るのがなんとなく嫌だったのでノンブロックにした。

CGIのテストと有効化

職業柄プログラムを作ったら単体で動かして見ないと落ち着かないので、一旦単体で動かして見る。

とは言え、POST に相当するものをブラウザ以外から与えるのはなかなか面倒なようで、以下のように長ったらしい呪文を追加してあげる必要がある。

echo cntl=p | env REQUEST_METHOD='POST' CONTENT_LENGTH=6 HTTP_REFERER='http://localhost/index.html' perl -d control.cgi

無事に動くのが確認できたら、cgi-bin に配置する。

ラズパイの場合は /usr/lib/cgi-bin になるが、一つトラップがあって以下のように apache の設定を変えてあげないとたとえ cgi-bin に配置しても動いてくれなかった。（apache のドキュメントを読んでもそんなことどこにも書いていないので、正直かなり苦戦した・・・）

> sudo ln -s /etc/apache2/mods-available/cgi.load /etc/apache2/mods-enabled/
> sudo service apache2 restart

これで無事にブラウザから Kinect の制御が可能になった。

どうしてもブログだとソースを全てかけないので細切れになってしまうが、需要があればそのうち GitHub なり何なりに上げようと思う。

2015年12月14日月曜日

Kinect + Raspberry Pi 2 で監視カメラを作る(6)

ブラウザから Kinect を操作する(前編)

前回で libfreenect を利用した Kinect の操作方法は大体わかったので、今度はWebカメラらしくブラウザから仰角や表示モードを操作できるようにする。

やり方は色々あるが今回は古典的だが一番簡単そうなネームドパイプ(FIFO)を使って cgi から camtest にコマンドを送る。

概念的にはこんな感じになる。

　　camtest ← FIFO ← CGI ← ブラウザ

双方向の情報伝達も出来なくはないが、ちゃんとやろうとすると非常に面倒なので今回は一方通行にする。

まずは、camtest.c に以下の行を追加してFIFOの生成とオープンを行う。
マルチスレッドにするならブロックモードでも良いが、~~それはそれでめんどい~~ありがたいことにイベントループ方式で Kinect から画像データを取得してくれているので、それに乗っかって今回はノンブロックモードを利用してシングルスレッドで運用する。

#include <string.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
...
char fifoname[] = "/tmp/kinect";
...

int main(int argc, char** argv)
{
       ...
        int fifo;
        if(mkfifo(fifoname, 0666) == 0) { // FIFOの作成
                chmod(fifoname, 0777);
        } // すでにFIFOがある場合は失敗するだけなので気にしない
        if((fifo = open(fifoname, O_RDONLY | O_NONBLOCK)) < 0) { // オープン
                printf("Failed to open fifo\n");
                return 1;
        }

ルート権限で実行すると mkfifo で0777を指定しても umask の影響で一般ユーザーの書き込み権限がなくなってしまうので、わざわざ作った後に chmod で権限を変更している。
この辺もう少し賢く出来ないもんか・・・

んでもってあとはイベントループの中でFIFOからコマンドをリードしてそれに応じて仰角とカメラモードを変更するようにすればよい。

        enum video_mode { KINECT_RGB, KINECT_IR, KINECT_DEPTH };

        // とりあえず最初はRGBモードでカメラだけ起動しておく
        current_mode = KINECT_RGB;
        ret = freenect_set_video_mode(fn_dev, freenect_find_video_mode(FREENECT_RESOLUTION_MEDIUM, FREENECT_VIDEO_RGB));
        ret = freenect_start_video(fn_dev);

        // 起動時の仰角を取得
        freenect_update_tilt_state(fn_dev);
        p_raw_tilt_state = freenect_get_tilt_state(fn_dev);
        current_tilt = freenect_get_tilt_degs(p_raw_tilt_state);
        next_tilt = current_tilt;

        while (running && freenect_process_events(fn_ctx) >= 0)
        {
                char cmd;
                enum video_mode next_mode = current_mode;
                ...
                while(read(fifo, &cmd, sizeof(cmd)) == sizeof(cmd)) {
                        switch(cmd) {
                        case 'p':
                                next_tilt += 1.0;
                                if(next_tilt > 30.0)
                                        next_tilt = 30.0;
                                break;
                        ...
                        case 'D':
                                next_mode = KINECT_DEPTH;
                                break;
                        }
                }
                if(current_tilt != next_tilt) {
                        freenect_update_tilt_state(fn_dev);
                        p_raw_tilt_state = freenect_get_tilt_state(fn_dev);
                        tilt_status = freenect_get_tilt_status(p_raw_tilt_state);
                        if(tilt_status != TILT_STATUS_MOVING) {
                                freenect_set_tilt_degs(fn_dev, next_tilt);
                                current_tilt = next_tilt;
                        }
                }
                if(current_mode != next_mode) {
                        set_mode(fn_dev, next_mode);
                }
        }

コマンドは複数文字にすると送信オーバーフロー時のバッファの処理や終端コードなど色々考える必要が出てくるので、単純化のため今回は全て1文字で p が仰角+1度、P が+5度、m が-1度、M が-5度、R がRGBモード、I が赤外線モード、D が深度モードとした。

set_mode 関数では以下のようにビデオモードの切り替えを行う。
貧乏性なので律儀に使わないモードを止めているが、どれだけ性能に影響するかは不明。

void set_mode(freenect_device* fn_dev, enum video_mode next_mode) {
        switch(current_mode) {
        case KINECT_RGB:
        case KINECT_IR:
                freenect_stop_video(fn_dev);
                break;
        case KINECT_DEPTH:
                freenect_stop_depth(fn_dev);
                break;
        }
        switch(next_mode) {
        case KINECT_IR:
                freenect_set_video_mode(fn_dev, freenect_find_video_mode(FREENECT_RESOLUTION_MEDIUM, FREENECT_VIDEO_IR_10BIT));
                freenect_start_video(fn_dev);
                current_mode = KINECT_IR;
                break;
        case KINECT_DEPTH:
                freenect_start_depth(fn_dev);
                current_mode = KINECT_DEPTH;
                break;
        case KINECT_RGB:
                freenect_set_video_mode(fn_dev, freenect_find_video_mode(FREENECT_RESOLUTION_MEDIUM, FREENECT_VIDEO_RGB));
                freenect_start_video(fn_dev);
                current_mode = KINECT_RGB;
                break;
        }
}

無事に出来たところで動作確認を行う。
camtest を実行すると、"/tmp/kinect”というファイルが生成されるので、試しにリダイレクトなどでコマンドを書き込んで動作確認を行う。

# echo p > /tmp/kinect

camtest の方はこれで出来たので、あとは CGI と html を作成する。

2015年12月5日土曜日

Kinect + Raspberry Pi 2 で監視カメラを作る(5)

Depth と　IR 画像の取得

Depth は depth_cb の data 引数から取得できる。
ただし、データは 11bit 形式なので、8bit のグレイスケールに変換する必要がある。
最初は律儀に RGB 各色に同じ値を入れていたが、JPEG のオプションを調べたら 1byte のグレイスケールでも出力できるようだった。

    JSAMPLE jpg_line[640];
    ・・・
    jpg_cinfo.input_components = 1;
    jpg_cinfo.in_color_space = JCS_GRAYSCALE;
    ・・・
    for(i = 0; i < 480; i++) {
        int j;
        for(j = 0; j < 640; j++) {
                unsigned short tmp;
                tmp = ((unsigned short)buf[i * 640 * 2 + j * 2 + 1] << 8)
                          + ((unsigned short)buf[i * 640 * 2 + j * 2] & 0xff);
                jpg_line[j] = (tmp >> 3) & 0xff;
        }
        jpg_row[0] = jpg_line;
        jpeg_write_scanlines(&jpg_cinfo, jpg_row, 1);
    }

IR の方は、最初に freenect_set_video_mode で FREENECT_VIDEO_RGB の代わりに FREENECT_VIDEO_IR_8BIT を指定する必要がある。
10BIT精度にも出来るが、どうせグレイスケールに変換するのでここでは 8bit で十分。こうすれば切り出したバッファをそのまま JPEG のライブラリに食わせられる。
このあたりからあまりまとまった解説が見当たらくなってきたので、わからなかったらlibfreenect のヘッダのコメントを見て解決している。

    freenect_set_video_mode(fn_dev, freenect_find_video_mode(FREENECT_RESOLUTION_MEDIUM, FREENECT_VIDEO_IR_8BIT));
    ・・・

    ・・・
    for(i = 0; i < 480; i++) {
        jpg_row[0] = (JSAMPROW)&buf[i * 640];
        jpeg_write_scanlines(&jpg_cinfo, jpg_row, 1);
    }

動作中の RGB と IR の切り替え方法については、正式なドキュメントは見当たらなかったが、とりあえず以下のように一旦止めてから、モードを変更して再度スタートしたら無事に動いたので、とりあえずはこのやり方で行くことにした。

    freenect_stop_video(fn_dev);
    freenect_set_video_mode(fn_dev, freenect_find_video_mode(FREENECT_RESOLUTION_MEDIUM, FREENECT_VIDEO_IR_8BIT));
    freenect_start_video(fn_dev);

もしかしたら止めなくても良いのかもしれないが、なんとなく気分的にやってしまう。

Tilt（傾き）の操作

Tilt の操作は freenect_set_tilt_degs を呼べば良いはずなのだが、ベースとした camtest.c にこれを組み込んでもさっぱり反応してくれない。
コードを読み返したら一カ所怪しいところがあったので、ヘッダのコメントをみたら案の定これが悪さをしていた。というわけで、以下の一行をコメントアウト。

    //freenect_select_subdevices(fn_ctx, FREENECT_DEVICE_CAMERA);

これは、アプリで使用するキネクトのデバイスを指定するオプション。キネクトは、カメラ、モーター、LEDの3つのデバイスから構成されており、この関数を利用することで個別に指定して開くことが出来る。
例えば、アプリ A でカメラを操作し、アプリ B でチルトの制御を行うときなどはこれを使うと便利だが、今回はアプリを分けるつもりは無い。指定なしの場合は全部のデバイスをオープンするそうなので、コメントアウトしてしまうのが手っ取り早い。

傾きの角度は浮動小数点で自由に指定できるが、サンプルを見た限りだと ±30度の範囲がデバイスとしての限界っぽい。(API 側で制限かけていないのは、将来的に新型 Kinect が出たときに動作範囲が変わることを想定してるんだろうな)
角度の指定は動いているときでも出来るようだが、気分的に以下のように止まっていることを確認してから行うようにする。

    freenect_raw_tilt_state* p_raw_tilt_state;
    freenect_tilt_status_code tilt_status;
    double tilt_deg = 10.0;

    freenect_update_tilt_state(fn_dev);
    p_raw_tilt_state = freenect_get_tilt_state(fn_dev);
    tilt_status = freenect_get_tilt_status(p_raw_tilt_state);
    if(tilt_status != TILT_STATUS_MOVING) {
        freenect_set_tilt_degs(fn_dev, tilt_deg);
    }

なお、±30度を超える角度を指定した場合は状態は TILT_STATUS_LIMIT になる。なのであえて TILT_STATUS_STOPPED ではなく !TILT_STATUS_MOVING で動作中かどうかを判定している。

これで必要な機能の使い方は一通りわかったので、後はこれをどうやってブラウザから制御するかってことになる。

2015年12月1日火曜日

Kinect + Raspberry Pi 2 で監視カメラを作る(4)

Kinect のカメラ画像を Jpeg ファイルに出力してブラウザで見る

freenect の example には camtest.c が入っている。
ソースを読んだ感じでは、RGB/Depth カメラのデータを繰り返し取得しているようなのだが、そのままではメッセージを出力するだけで画像が取得できないのでこれを改造して画像を出力するようにする。

カメラのデータは video_cb という関数の第二引数であるdata に格納されていると思われるが、どのようなフォーマットで格納されているかいまいちドキュメントが見当たらなかった。仕方なしに先頭数バイトを HEX でダンプして心の目で見た感じだとどうやらRGBの生データぽかったので、これを上手いこと整形して JPEG のライブラリに食わせれば画像ファイルに変換できると考えた。

まずは Jpeg ライブラリのインストール
> sudo apt-get install libjpeg-dev

で、video_cb の中身を以下のように変更

#include <jpeglib.h>

char filename[] = "/var/www/html/kinect/output.jpg";

void video_cb(freenect_device* dev, void* data, uint32_t timestamp)
{
        JSAMPROW jpg_row[1];
        struct jpeg_compress_struct jpg_cinfo;
        struct jpeg_error_mgr jerr;
        FILE *fp;
        int i;
        char* buf = data;

        jpg_cinfo.err = jpeg_std_error(&jerr);
        jpeg_create_compress(&jpg_cinfo);
        fp = fopen(filename, "wb");
        jpeg_stdio_dest(&jpg_cinfo, fp);
        jpg_cinfo.image_width = 640;
        jpg_cinfo.image_height = 480;
        jpg_cinfo.input_components = 3;
        jpg_cinfo.in_color_space = JCS_RGB;
        jpeg_set_defaults(&jpg_cinfo);
        jpeg_set_quality(&jpg_cinfo, 75, TRUE);
        jpeg_start_compress(&jpg_cinfo, TRUE);
        for(i = 0; i < 480; i++) {
                jpg_row[0] = (JSAMPROW)&buf[i * 640 * 3];
                jpeg_write_scanlines(&jpg_cinfo, jpg_row, 1);
        }
        jpeg_finish_compress(&jpg_cinfo);
        jpeg_destroy_compress(&jpg_cinfo);
        fclose(fp);
}

コンパイルは -lfreenect に加えて -ljpeg を追加してコンパイルする。
無事にコンパイルできたら、/var/www/html/kinect ディレクトリを作成してから実行すればここに Kinect カメラで撮影した画像が保存される。
実のところ Jpeg のライブラリを使うのは初めてだったが、思ってた以上にすんなり出来た。なので、細かいパラメータはどっかで拾ったサンプルそのまま。

画像を見るにはPCのブラウザで "http://ラズパイのIP/Kinect/output.jpg" と入れれば撮影した画像が閲覧できる。

ブラウザのリロードボタンをひたすら連打すればアニメーションぽいのも見れるはずである・・・が、

ここで問題が発生した。
一つはそのままだと画像がキャッシュされてしまい更新されない。
これは以下の.httaccesを作成して対処した。

<Files ~ "\.jpg$">
Header set Cache-Control "no-cache"
Header set Pragma "no-cache"
</Files>

もう一つは読み込むタイミングによってはライブラリが書き込んでる途中のデータが読み込まれてしまい、画像の一部が切れてしまうことがあった。

苦肉の策として、一旦テンポラリに吐き出した後で、mv コマンドで移動するようにした。

互換性がだいぶ犠牲になるが、どうせラズパイ専用なので気にしない。

char filename[] = "tmp.jpg";

char postcmd[] = "mv tmp.jpg /var/www/html/kinect/output.jpg";

void video_cb(freenect_device* dev, void* data, uint32_t timestamp)
{
JSAMPROW jpg_row[1];

　　　・・・

fclose(fp);
system(postcmd);
}

蛇足だが、Linux/Unix 系のファイルシステムでは読み込み途中のファイルが mv コマンドで変更されても、読み込んでファイルがクローズされるまでは読み込み側ではもとのファイルを参照し続けるので、このように mv で上書きしてしまってもブラウザで表示されるデータが混ざったり崩れたりする心配は無い。

FATやNTFSの場合は知らんが。

手動でリロードするのも何なので、JavaScriptで自動でリロードするようにしてあげれば、Kinectのカメラで撮った画像をぱらぱら漫画風の動画として見ることが出来る。

/var/www/html/kinect/index.html

このままでも良いのだが、リロードの時のちらつきが気になる。

見栄えの問題なので後回しにしようと思ったが、canvas を使えば意外と簡単に解決できそうなのでやってみた。

同じページでのリロードの場合は画像のキャッシュを無効にしても意味が無いようなので、結局ファイル名の後に"?"と日時を追加してブラウザに違うファイルとして認識させるようにする必要がある。

実態はパラパラ漫画なのだが、この程度でもLAN 環境なら動画と遜色ない感じで表示できる。

setTimeout はもっと短くても良いかもしれない。

とりあえずはこれでスタート地点と同じ RGB の動画(っぽいの)を表示するところまではたどり着いた。

せっかく頑張って libfreenect を導入したのだから、IR/Depth 画像の表示やチルト操作もできるように今後拡張していく。

2015年11月28日土曜日

Kinect + Raspberry Pi 2 で監視カメラを作る(3)

外からラズパイにログインするための準備

前回でライブラリとベースとするソースは決めたのでこれからはごりごりコードを書いていきたいのだが、いかんせん家にいると子守と Fallout4 を並列にこなさなければならないのでその合間にコードを書くのはなかなかヘビーだ。

そこで少しでも作業が進むように外からスマフォなりタブレットなりで SSH でログインしてコーディングやその他の作業が出来る環境を整える。

何はともあれ、ラズパイを外部に公開するので、まずはそれなりにセキュリティを強化していく。

デフォルトユーザーのパスワード変更
> passwd
外部ログイン用グループ(developper)の作成
> sudo groupadd developper
外部ログイン用ユーザー(ruser)の作成
> sudo useradd -c "remote user" -g developper -m -N ruser
作成したユーザーにパスワードを設定
> sudo passwd ruser
デフォルトユーザーの外部ネットワークからのログインを禁止
/etc/security/access.conf に以下の行を追加
- : pi : ALL EXCEPT 192.168.1.

これでWANからは先ほど作成したruserでしかログインできなくなる。
ルートの権限がほしい場合は、ruserでログインした後で、
> su - pi
でユーザーを切り替えるので両方のパスワードを知らないとroot権限を取得できないことになる。

さらに、

pi を先ほど作成したdevelopperグループに追加
> sudo gpasswd -a pi developer
("usermod -G" は罠なので使ってはいけない)
共有ディレクトリの作成
> sudo mkdir /home/developer
> sudo chown pi /home/developer
> sudo chgrp developper /home/developper
共有ディレクトリにSGIDを設定して異なるユーザーがファイルを作成しても同じグループになるようにする。
> sudo chmod 2770 /home/developer/
デフォルトでグループに書き込み権限を与える
/etc/profile に以下の行を追加
umask 002

これで、外からは ruser, 家では pi でログインしても同じように作業が出来る。

そとからラズパイにログイン

グローバルIPをもらえる環境なら DDNS なりなんなり使えば良いが、我が家のマンションネットではそれが難しそうなのでホスティングサービスを利用して踏み台となる公開サーバーを用意して、そこに逆方向トンネルを掘って繋げる作戦で行く。

AmazonECにアカウント作成

この手のサービスは幾つかあるが、やっぱり無料で使えるAmazonECを選択した。

Ubuntuの仮想マシンを作成
現在のサブネットからポート22(SSH)にアクセスできるようにセキュリティルールを追加
ssh でログイン
Ubuntuの場合、初期ユーザー名はUbuntu
Rloginの場合はSSH Identify Keyに仮想マシン作成時に生成したキーファイルを指定
ログインできたら早速 /etc/ssh/sshd_confに以下の一行を追加してトンネルを可能にする
GatewayPorts yes
次にラズパイにキーファイルをコピーしてアクセス権を変更
> chmod 400 KeyFile.pem
キーファイルを使ってトンネルを掘る
> ssh -i KeyFile.pem -f -N -R :10022:localhost:22 user@hostname
ここでは仮想マシンの10022ポートをラズパイの22(ssh)ポートに転送する
EC2 ManagementConsoleに戻って先ほどの10022ポートをグローバルに通すようにセキュリティルールを変更
ポートに10022を指定して仮想マシンにsshをかけると手元のラズパイにログインできる。

設定が確認できたらautosshを利用して起動時に自動で接続させる
> sudo apt-get install autossh

一旦ルートになってSSHで仮想マシンにログイン
> sudu su -
> ssh -i /home/pi/KeyFile.pem user@hostname
※一見無意味な儀式だが、ルートのknown_hostsに登録するために必要となる

/etc/rc.localに以下の行を追加
sleep 10
/usr/bin/autossh -i /home/pi/KeyFile.pem -f -N -R :10022:localhost:22 user@hostname
※起動直後はネットワークの接続が完了していないことがあるので、とりあえず10秒スリープさせる

以降はラズパイを起動すると自動で仮想マシンにトンネルを作成してくれるので、そこからアクセスできるようになる。

スマフォ用のSSHクライアントは色々あるのでご自由に
どちらにしてもスマフォからがっつりコーディングするのは厳しいが、修正や簡単な動作確認用のコードの追加ならなんとか

2015年11月25日水曜日

Kinect + Raspberry Pi 2 で監視カメラを作る(2)

OpenKinect (libfreenect) のインストール

お手軽に使えそうなラズパイ用のアプリを探してみたのだが、さっぱり見つからないので腹を据えて自分でプログラムすることにした。

ラズパイでも使える Kinect 用のAPIとして libfreenect があるので、まずはこれを導入する。
ただし、サンプルプログラムのビルドに難があるようなので（参考）サンプルプログラムをビルドしないように cmake のオプションを指定する必要がある。

> sudo apt-get install libusb-dev
> sudo apt-get install freeglut3-dev ※example をビルドしないなら要らないかも
> git clone https://github.com/OpenKinect/libfreenect
> cd libfreenect
> mkdir build
> cd build
> cmake -L .. -DBUILD_REDIST_PACKAGE=OFF -DBUILD_EXAMPLES=OFF
> make
> sudo make install

※ 参考ページだと CMakeLists.txt を編集しているが、cmake のオプションで指定した方が手っ取り早い。今回は再配布の予定も無いのでついでにそのオプションも追加した。

これでKinect 用のライブラリとドライバがインストールされるので、Kinect を差し直すか、ラズパイを再起動すれば新しいドライバが認識される（はず）。

動作確認その１

動作確認のために先ほどの参考ページにサンプルソースが貼ってあったので、コピペして Make した。
途中、sleep が見つからないと怒られたのでソースに"#include <unistd.h>"を追加したら通った。

ためしに実行してみる。
> sudo env LD_LIBRARRY_PATH=/usr/local/lib ./tiltdemo

libfreenect のビルドとインストールが上手くいっていればこれで Kinect センサーがウィーンと良いながら上下に動いてくれるはず。

毎回環境変数を設定するのも面倒なので/usr/local/lib をパスに追加しておく。
> sudo su - root
> echo /usr/local/lib > /etc/ld.so.conf.d/usr-local.conf
> ldconfig
> exit

動作確認その２

libfreenect の example を眺めてみると幾つか動かせそうなものがあったので先ほど作成したサンプルの Makefile を参考にコンパイルしてみた。

> gcc -o camtest -I/usr/local/include/libfreenect camtest.c -lfreenect
> gcc -o tiltdemo -I/usr/local/include/libfreenect tiltdemo.c -lfreenect -lfreenect_sync

両方とも sudo を付けて動かすと無事に動いてくれた。

なお、'#include "libfreenect.h"' を '#include <libfreenect/libfreenect.h>' に変えると -I... を付けなくてもコンパイルできるようになる。

camtest が Kinect の RGB カメラと Depth センサーのデータを繰り返し読み込むデモのようなので、これをベースに自前のアプリを作っていこうと思う。

2015年11月19日木曜日

Kinect + Raspberry Pi 2 で監視カメラを作る(1)

XBOX360のキネクトが余っていたので、ラズパイと組み合わせて寝ている我が子を見守るための監視カメラを作れないかやってみた。

OSのインストール

ラズパイを触るのは初めてなので、まずはOSをインストールするところから。

公式ページに行って素直にNOOBSをダウンロード
Zipファイルを展開
手持ちのMicroSDカードにコピー
※公式ページにはフォーマットツールをダウンロードしろとあったが、エクスプローラーから普通にFAT32でフォーマットしたら普通に使えた
Raspbianをインストール

かなりお手軽にインストールできた。

いまどきはISO焼き込んだりextでフォーマットしたりしなくて良いのね。

WiFi設定

あまり深く考えずに、ラズパイを購入したときにAmazonでおすすめされたBuffaroのWLI-UC-GNMを一緒に購入
相性が悪ければ最悪ドライバのビルドとか必要かなと思ったが、挿すだけで何もしなくても認識してくれた。ありがとうAmazonさん。

WPAの設定
> sudo su -
> cp /etc/wpa_supplicant/wpa_supplicant.conf /etc/wpa_supplicant/wpa_supplicant.conf.orig
> wpa_passphrase SSID PASS_PHRASE >> /etc/wpa_supplicant/wpa_supplicant.conf
> ifdown wlan0
> ifup wlan0
> exit
無線ルーターで固定アドレスに設定
Windows用のSSHクライアントとしてRLoginを落としてPCから接続

これで電源だけ繋げば後はリモートで作業できる。

RDP設定

基本はSSHで作業するつもりだが、画像確認などで画面飛ばせた方が便利かと思って一応RDPも設定しておく。

> sudo apt-get install xrdp

PC(Windows)側からはリモートデスクトップで繋げればOK

Kinectを繋ぐ

やるまえに色々調べていたが、結局USBに挿したら何もしなくても認識してくれた。
/dev/video0 が出来ているのを確認。

camoramaで表示

念のため、リモートで配信する前にリモートデスクトップで繋いでローカルできちんと見えるか確認。
> sudo apt-get install camorama
> camorama -d /dev/video0

ストリーミング

motionをインストール
> sudo apt-get install motion
/etc/motion/motion.confを編集
daemon off → on
/etc/default/motionを編集
start_motion_daemon=no → yes
自動起動設定
update-rc.d motion defaults

で、再起動してPCのブラウザで先ほど設定したIPアドレス:8080にアクセスするとコマ送り状態だがキネクトカメラの画像が見える。

ただ、Chromeからは見えたが、Edgeではファイルの無限ダウンロードになってしまい正常に見えなかった。

一応これでお手軽に最低限監視カメラとしての機能は実現できたが、現状では

チルトが出来ない
ノーマルカメラでは暗い部屋ではほとんど見えない

と、Kinectの機能を全く生かせていないので、この辺をもうちょっとなんとかしていきたい。

2015年10月15日木曜日

赤城を作る

ハセガワの1/700赤城フルハルモデルをディティールアップパーツと一緒に購入。

武蔵の時のように作りながら記事を書く時間と根性がなかったので完成形だけ。

高い金出してエッチングパーツを買ったけど、結局飛行甲板裏のところまで作り込む根性はなかったので飛行甲板はキット標準の方を利用。

もともとのキットの出来が良いのでエッチングパーツがなくても十分見栄えしそうだけど、やっぱり手すりがあるだけでも近寄って見たときの印象は良い。

やっぱり戦艦に比べて構造がかなり複雑なので、作るのは難しい。

特に後甲板部分は時間と金が腐るほどあるならもう一度やり直したい気分。

2015年8月30日日曜日

C++ で C# の delegate っぽいものも作ってみた

こないだ event 風のものを作ってみたけど、もう一ひねりしたら delegate っぽいものも作れた。

template<typename T>
class Delegate;

template<typename R, typename... A>
class Delegate<R(A...)> {
private:
    std::function<R(A...)> mFunc;
public:
   Delegate(std::function<R(A...)> func) : mFunc(func) {}
   template<typename C, typename T>
   Delegate(C* pObj, T func) {
        mFunc = [=](A... args) { std::mem_fn(func)(pObj, args...); };
   }
public:
   void operator()(A... args) {
        mFunc(std::forward<A>(args)...); // 修正
   }
};

ｅｖｅｎｔと組み合わせるとこんな感じで使える。

class EventManager {
public:
   typedef Delegate<void(const std::string&)> TestEventHndlr;
   Event<TestEventHndlr> TestEvent;
   void InvokeTestEvent() {
        TestEvent("This is TestEvent. > ");
   }
};

class EventHandler {
public:
   void Hndlr(const std::string& msg) {
        std::cout << msg << "I'm a member function." << std::endl;
   }
};

void print_msg(const std::string& msg) {
   std::cout << msg << "I'm a static function." << std::endl;
}

int main()
{
   EventManager manager;
   EventHandler hndlr;
   manager.TestEvent += EventManager::TestEventHndlr([](const std::string& msg) {
        std::cout << msg << "I'm a lambda function." << std::endl;
   });
   manager.TestEvent += EventManager::TestEventHndlr(print_msg);
   manager.TestEvent += EventManager::TestEventHndlr(&hndlr, &EventHandler::Hndlr);
   manager.InvokeTestEvent();
    return 0;
}

※追記
unique_ptr を使おうとしたらハマったので Delegate を一部修正。
Event の方は複数のハンドラを登録できるようにしているのでもともと unique_ptr は適さない。
どうしても使いたければハンドラを一つしか登録できないイベントクラスを別途作る必要があるが、それよりはイベントハンドラ側にメモリ管理をさせないようにデータ構造を見直した方が健全かなぁ。。。

2015年8月23日日曜日

C++0x のラムダ式と可変長テンプレートで C# っぽいイベント処理

世の中便利になったものね～。
これでコールバックを多用した非同期処理がだいぶ書きやすくなりそう。

どうしてもメンバ関数は一旦ラムダ式で包んであげる必要があるので、デリゲートの仕組みも作れると完璧なんだが・・・

#include <iostream>
#include <list>
#include <functional>
#include <string>

template<typename T>
class Event {
private:
   std::list<T> mHndlrs;
public:
   void operator+=(T hndlr) {
        mHndlrs.push_back(hndlr);
   }
   template<typename... A>
   void operator()(A... args) {
        for (auto it = mHndlrs.begin(); it != mHndlrs.end(); it++) {
            (*it)(args...);
        }
   }
};

class EventManager {
public:
   Event<std::function<void(const std::string&)> > TestEvent;
   void InvokeTestEvent() {
       TestEvent("This is TestEvent. > ");
   }
};

class EventHandler {
public:
   void Hndlr(const std::string& msg) {
       std::cout << msg << "I'm a member function." << std::endl;
   }
};

void print_msg(const std::string& msg) {
   std::cout << msg << "I'm a static function." << std::endl;
}

int main()
{
    EventManager manager;
   EventHandler hndlr;
   manager.TestEvent += [](const std::string& msg) {
        std::cout << msg << "I'm a lambda function." << std::endl;
   };
   manager.TestEvent += print_msg;
   manager.TestEvent += [&](const std::string& msg) {
      hndlr.Hndlr(msg);
    };
   manager.InvokeTestEvent();
   return 0;
}

2015年8月2日日曜日

JavaScript で Sudoku を解いてみる (3)

前回までで、問題と条件が記述できたので、後は例によって解けば良い。

今回はモナドを利用したおかげで条件の記述がそのまま条件をチェックするコードになるので、ソルバは非常にシンプルに書ける。

        function solve(question, conditions, iter) {
            var result;
            if(iter === undefined) iter = 0;
            else if(iter >= question.length) return;
            var answer = [];
            question[iter].selectEach(function() {
                result = conditions();
                if(result === undefined)
                    answer = answer.concat(solve(question, conditions, iter+1));
                else if(result === true) {
                    answer.push(question.map(function(tile) { return tile.get(); }));
                }
            });
            return answer;
        }

        var Question = Cells.reduce(function(prev, row) {
            return prev.concat(row);
        }, []);

        var Answer = solve(Question, Condition);

ここまでシンプルに書けると、もはやソルバは要らないんじゃないかと思えてきて、問題に吸収させて、問題生成時に問題に対応するソルバを生成するようにもしてみた。

        function Question(items) {
            this.Solve = items.reduce(function(prev, item) {
                return function(condition) {
                    var answer = [];
                    item.selectEach(function() {
                        result = condition();
                        if(result === undefined)
                            answer = answer.concat(prev(condition));
                        else if(result === true) {
                            answer.push(items.map(function(tile) { return tile.get(); }));
                        }
                    });
                    return answer;
                }
            }, function() { return []; });
        }

        var Answer = (new Question(Cells.reduce(function(prev, row) {
            return prev.concat(row);
        }))).Solve(Condition);

実際に解いてみると、簡単な問題なら一瞬で解けるが、難易度が上がると試行回数が跳ね上がってむちゃくちゃ時間がかかるようになる。
この辺はスクリプトの限界なのか、それとも工夫すればもっと速くなるのか。。。

JavaScript で Sudoku を解いてみる (2)

前回の続きで、塗り分けの時にモナド的に書きたいなと言っていたところを、無い知恵を絞ってモナドもどきを作ってみた。

        var Result = {
            False: {
                bind: function() {
                    return this;
                },
                get: function() {
                    return false;
                }
            },
            True: {
                bind: function(f) {
                    return f();
                },
                get: function() {
                    return true;
                }
            },
            Undefined: {
                bind: function(f) {
                    var result = f();
                    if(result.get() === false) {
                        return result;
                    }
                    return Result.Undefined;
                },
                get: function() {
                    return undefined;
                }
            }
        }

これを使うと、「与えられた要素が全て互いに異なる」という条件はこう書ける。
モナドを使いつつも、あまり関数型っぽくない書き方だが、実行効率を踏まえつつハイブリッドなやり方と言うことで

        function AllNotEqual() {
            return allNotEqual(arguments, arguments.length-2);
        }
        function allNotEqual(items, iter) {
            var result = (function(j) {
                var callee = arguments.callee;
                if(j <= iter + 1) return NotEqual(items[iter], items[j]);
                return NotEqual(items[iter], items[j]).bind(function() { return callee(j-1); });
            })(items.length - 1);
            if(iter <= 0) {
                return result;
            }
            return result.bind(function() { return allNotEqual(items, iter-1); });
        }
        function NotEqual(x, y) {
            var tmp_x = x.get(), tmp_y = y.get();
            if(tmp_x === undefined || tmp_y === undefined)
                return Result.Undefined;
            if(tmp_x != tmp_y)
                return Result.True;
            return Result.False;
        }

Sudoku の条件である、「各行、各列、各3x3のブロックで同じ数字を使わない」は、関数型言語の勉強の時に作った do 記法もどきを利用してこう書ける。
ちとながいが、よく見れば単にルールをべた書きしただけの記述。

        var MonaDo = function(fs) {
            var monado = function(funcs) {
                if(funcs.length > 1) {
                    var inner = monado(funcs.slice(1));
                    return function(a) {
                        return funcs[0](a).bind(inner);
                    }
                }
                return funcs[0];
            }
            return monado(fs)();
        }

        function RowNotEqual(cells, row) {
            return AllNotEqual.apply(this, cells[row]);
        }
        function ColNotEqual(cells, col) {
            return AllNotEqual.apply(this, cells.map(function(row) {
                return row[col];
            }));
        }
        function BlkNotEqual(cells, row, col) {
            return AllNotEqual(
                cells[row][col], cells[row][col+1], cells[row][col+2],
                cells[row+1][col],cells[row+1][col+1],cells[row+1][col+2],
                cells[row+2][col],cells[row+2][col+1],cells[row+2][col+2]);
        }
        var Condition = function() {
            return MonaDo([
                function() {return RowNotEqual(Cells, 0); },
                function() {return RowNotEqual(Cells, 1); },
                function() {return RowNotEqual(Cells, 2); },
                function() {return RowNotEqual(Cells, 3); },
                function() {return RowNotEqual(Cells, 4); },
                function() {return RowNotEqual(Cells, 5); },
                function() {return RowNotEqual(Cells, 6); },
                function() {return RowNotEqual(Cells, 7); },
                function() {return RowNotEqual(Cells, 8); },
                function() {return ColNotEqual(Cells, 0); },
                function() {return ColNotEqual(Cells, 1); },
                function() {return ColNotEqual(Cells, 2); },
                function() {return ColNotEqual(Cells, 3); },
                function() {return ColNotEqual(Cells, 4); },
                function() {return ColNotEqual(Cells, 5); },
                function() {return ColNotEqual(Cells, 6); },
                function() {return ColNotEqual(Cells, 7); },
                function() {return ColNotEqual(Cells, 8); },
                function() {return BlkNotEqual(Cells, 0, 0); },
                function() {return BlkNotEqual(Cells, 0, 3); },
                function() {return BlkNotEqual(Cells, 0, 6); },
                function() {return BlkNotEqual(Cells, 3, 0); },
                function() {return BlkNotEqual(Cells, 3, 3); },
                function() {return BlkNotEqual(Cells, 3, 6); },
                function() {return BlkNotEqual(Cells, 6, 0); },
                function() {return BlkNotEqual(Cells, 6, 3); },
                function() {return BlkNotEqual(Cells, 6, 6); }
            ]).get()
        };

JavaScript で Sudoku を解いてみる (1)

こないだ塗り分け問題を解く JavaScript を書いてみたが、同じ原理で Sudoku も解けるんじゃないかと思ってコードを改良しつつやってみた。

Sudoku の場合は初期状態で値が決まっているセルと決まっていないセルがあるので、これを表現するために、Obvious と Ambiguous という二つのクラスを作成した。

        function Ambiguous(candidates) {
            this.candidates = candidates;
            this.selected = undefined;
        }
        Ambiguous.prototype = {
            get: function() {
                return this.selected;
            },
            selectEach: function(callback) {
                this.candidates.forEach(function(item) {
                    this.selected = item;
                    callback();
                }.bind(this));
                this.selected = undefined;
            },
        }
        function Obvious(value) {
            this.value = value;
        }
        Obvious.prototype = {
            get: function() {
                return this.value;
            },
            selectEach: function(callback) {
                callback();
            }
        }

長くなるのでヘルパーを使いつつ、どっかから探してきた Sudoku の問題を表現するとこうなる。

        var Nine = [1, 2, 3, 4, 5, 6, 7, 8, 9];
        function createRow(args) {
            return args.map(function(item) {
                if(Array.isArray(item)) return new Ambiguous(item);
                return new Obvious(item);
            });
        }
        var Cells = [
            createRow([Nine, Nine,    8, Nine,    9, Nine, Nine, Nine, Nine]),
            createRow([   9, Nine, Nine, Nine,    3, Nine, Nine, Nine,    1]),
            createRow([   6,    2, Nine, Nine,    4,    7, Nine,    8, Nine]),
            createRow([Nine, Nine,    7, Nine, Nine, Nine,    1,    9, Nine]),
            createRow([   1,    3, Nine,    4,    7, Nine,    2,    5,    8]),
            createRow([   5, Nine, Nine,    8,    2, Nine,    3,    6, Nine]),
            createRow([   3,    6,    1,    7, Nine,    4,    8,    2, Nine]),
            createRow([Nine,    5,    2,    9,    1, Nine,    4,    7,    6]),
            createRow([Nine,    9,    4,    6, Nine, Nine,    5, Nine,    3])
        ];

インデントは気にしない

2015年7月16日木曜日

Javascript で塗り分け問題を解いてみる (4)

前回で総当たり方式についてコードを一般化出来たところで、今度はこれに枝刈りを導入して動作の効率化を図る。

枝刈りというのは、要は全てのタイルの色を設定した後で全ての条件に合致するかを判断するのではなく、1枚ずつタイルの色を設定しながら、現時点で条件を満たさないことが判明したらその先の試行をやめて違う組み合わせを試すというものになる。

そのためには、それぞれの条件に対して判断に必要なタイルを明記する必要がある。

        var Colors = ['red', 'blue', 'green', 'yellow'];
        var tile1 = { candidates: Colors, selected: undefined };
        var tile2 = { candidates: Colors, selected: undefined };
        var tile3 = { candidates: Colors, selected: undefined };
        var tile4 = { candidates: Colors, selected: undefined };
        var tile5 = { candidates: Colors, selected: undefined };

        var Conditions = [
            { require: [tile1, tile2], func: function() { return tile1.selected != tile2.selected; } },
            { require: [tile1, tile3], func: function() { return tile1.selected != tile3.selected; } },
            { require: [tile1, tile4], func: function() { return tile1.selected != tile4.selected; } },
            { require: [tile1, tile5], func: function() { return tile1.selected != tile5.selected; } },
            { require: [tile2, tile3], func: function() { return tile2.selected != tile3.selected; } },
            { require: [tile3, tile5], func: function() { return tile3.selected != tile5.selected; } },
            { require: [tile4, tile5], func: function() { return tile4.selected != tile5.selected; } },
            { require: [tile4, tile2], func: function() { return tile4.selected != tile2.selected; } }
        ];

        var Question = [tile1, tile2, tile3, tile4, tile5];

各条件を判定するときには、require で示されたタイルの色が設定されているかをチェックして、設定されていない場合は undefined を返すようにする。

        function checkOne(question, cond) {
            var i;
            for(i = 0; i < cond.require.length; i++) {
                if(cond.require[i].selected === undefined) {
                    return undefined;
                }
            }
            return cond.func();
        }

あとは、
複数の条件のうち、一つでも条件を満たさない場合はその先の試行は行わない。
全ての条件を満たせばそれが回答の一つになる。
それ以外(undefinedが混じる場合)は次のタイルの色を設定してもう一度条件を確認する。
というのを行っていけばよい。

        function solve(question, conditions, iter) {
            var result;
            if(iter === undefined) iter = 0;
            else if(iter >= question.length) return;
            var answer = [];
            question[iter].candidates.forEach(function(item) {
                question[iter].selected = item;
                result = check(question, conditions);
                if(result === undefined)
                    answer = answer.concat(solve(question, conditions, iter+1));
                else if(result === true) {
                    answer.push(question.map(function(tile) { return tile.selected; }));
                }
            });
            question[iter].selected = undefined;
            return answer;
        }

        function check(question, conditions) {
            var i,
                tmp,
                result = true;
            for(i = 0; i < conditions.length; i++) {
                tmp = checkOne(question, conditions[i]);
                if(tmp === false) return false;
                else if(tmp === undefined) result = undefined;
            }
            return result;
        }

こうすれば、メンテナンス性を維持しつつも、枝刈りにより高速に処理が出来る。

check や checkOne の戻り値をチェックして処理内容を変えるところなんかは、関数型言語で勉強したモナド的なやり方を導入するともう少しスマートに書けそうな気がするのだが、一からモナドを設計するのは自分の脳みそじゃ無理そうだ。

塗り分け問題を JavaScript で書いてみた結論としては、

　　prologで良いじゃん

の一言に尽きる。

というか、prolog 向きの問題だと言うことはハナからわかっていたが、JavaScript で書いたらもう少しオブジェクト指向的なアプローチが出来るかなと思って色々試行錯誤してみたのたが、結局は一般化しようとしたら prolog っぽい書き方をするのが一番良いよねということになってしまった。
強いて言えば、require と selected をもう少しスマートに表現できるようにしたかったなぁ。

まあ、こんなことは先人たちがさんざん試してるので今更なんだろうが、勉強には良いよね。

Javascript で塗り分け問題を解いてみる (3)

前回は効率性を重視するあまりメンテナンス性がおろそかになってしまった。
メンテナンス性を良くするために、解き方はもとの総当たりに戻すとして、一旦命題を整理してみる。

今回の命題を言葉で書くと
「タイル1～5までの5枚のタイルがある」
「それぞれのタイルには赤、青、緑、黄のどれかの色が塗られる」
「"条件"に合致するタイルの色の組み合わせは何か」
のということになる。

これをそのままコードで書くとこのように書ける。

        var Colors = ['red', 'blue', 'green', 'yellow'];

        var tile1 = { candidates: Colors, selected: undefined };
        var tile2 = { candidates: Colors, selected: undefined };
        var tile3 = { candidates: Colors, selected: undefined };
        var tile4 = { candidates: Colors, selected: undefined };
        var tile5 = { candidates: Colors, selected: undefined };

        var Conditions = [
            function() { return tile1.selected != tile2.selected; },
            function() { return tile1.selected != tile3.selected; },
            function() { return tile1.selected != tile4.selected; },
            function() { return tile1.selected != tile5.selected; },
            function() { return tile2.selected != tile3.selected; },
            function() { return tile3.selected != tile5.selected; },
            function() { return tile4.selected != tile5.selected; },
            function() { return tile4.selected != tile2.selected; }
        ];

        var Question = [tile1, tile2, tile3, tile4, tile5];

命題をコードで書けるのなら、それをそのまま解けば良い。

        function solve(question, conditions, iter) {
            if(iter === undefined) iter = 0;
            else if(iter >= question.length) {
                if(conditions.every(function(condition) { return condition(); })) {
                    return [question.map(function(tile) { return tile.selected; })];
                }
                return [];
            }
            var answer = [];
            question[iter].candidates.forEach(function(item) {
                question[iter].selected = item;
                answer = answer.concat(solve(question, conditions, iter+1));
            });
            return answer;
        }

        var Answer = solve(Question, Conditions);

さらっと無茶なことをやっているようにも見えるが、実際は question で与えられた tile1 ～ tile5 に対して再起を使って candidate の全ての組み合わせを総当たりで試しているだけ。

こうしてしまえば、タイルの数が増えようが、条件が変わろうが容易に対応できる。

Javascript で塗り分け問題を解いてみる (2)

前回の続き。

さすがに総当たりだと単純すぎるので、いわゆる枝刈りして余計な試行を削っていく。

var colors = ['red', 'blue', 'green', 'yellow'];

colors.forEach(function(tile1) {
    colors.forEach(function(tile2) {
        if(tile1 != tile2) {
            colors.forEach(function(tile3) {
                if(tile1 != tile3 && tile2 != tile3) {
                    colors.forEach(function(tile4) {
                        if(tile1 != tile4 && tile3 != tile4) {
                            colors.forEach(function(tile5) {
                                if(tile1 != tile5 && tile4 != tile5 && tile2 != tile5) {
                                    document.write(tile1+', '
                                        +tile2+', '
                                        +tile3+', '
                                        +tile4+', '
                                        +tile5+'<br>');
                                }
                            });
                        }
                    });
                }
            });
        }
    });
});

たしかにこれで速くはなるのだが、いかんせんメンテナンス性がすこぶる悪い。
タイルを一枚増やしたり、条件を変更しようとするとあっちゃこっちゃ変えなくちゃならない。

Javascript で塗り分け問題を解いてみる (1)

以前なんかで見かけて、暇があったら勉強がてら JavaScript で書いてみようと思っていたプログラム。
いわゆる塗り分け問題で、細かいところは覚えていないが、とりあえず適当に下のような5枚のタイルを同じ色が隣接しないように赤青黄緑の4色で塗り分ける問題を解いてみる。

まずは何も考えずに愚直に書くとこうなる

var colors = ['red', 'blue', 'green', 'yellow'];

var i, j, k, l, m;
var tile1, tile2, tile3, tile4, tile5;
for(i = 0; i < colors.length; i++) {
    tile1 = colors[i];
    for(j = 0; j < colors.length; j++) {
        tile2 = colors[j];
        for(k = 0; k < colors.length; k++) {
            tile3 = colors[k];
            for(l = 0; l < colors.length; l++) {
                tile4 = colors[l];
                for(m = 0; m < colors.length; m++) {
                    tile5 = colors[m];
                    if(tile1 != tile2
                       && tile1 != tile3
                       && tile1 != tile4
                       && tile1 != tile5
                       && tile2 != tile3
                       && tile3 != tile5
                       && tile5 != tile4
                       && tile4 != tile2) {
                        document.write(tile1+', '
                                       +tile2+', '
                                       +tile3+', '
                                       +tile4+', '
                                       +tile5+'<br>');
                    }
                }
            }
        }
    }
}

これでも解けることは解けるが、タイル数(N)が増えると試行回数が4(色数)のN乗で増えていくので、こんなんを大学の専攻のレポートで提出したら確実に赤点食らうだろう。

蛇足だが、forEachを使うと若干シンプルに書ける。

var colors = ['red', 'blue', 'green', 'yellow'];
var begin = Date.now();
colors.forEach(function(tile1) {
    colors.forEach(function(tile2) {
        colors.forEach(function(tile3) {
            colors.forEach(function(tile4) {
                colors.forEach(function(tile5) {
                    if(tile1 != tile2
                       && tile1 != tile3
                       && tile1 != tile4
                       && tile1 != tile5
                       && tile2 != tile3
                       && tile3 != tile5
                       && tile5 != tile4
                       && tile4 != tile2) {
                        document.write(tile1+', '
                                       +tile2+', '
                                       +tile3+', '
                                       +tile4+', '
                                       +tile5+'<br>');
                    }
                });
            });
        });
    });
});

もっとも、シンプルに書けるだけで中身は変わらないので、まともにしようと思ったら工夫が必要になる。

登録: 投稿 (Atom)