駄日記 (未完結間欠日記)

> 書くことないな～。
というのはウソでいっぱいたまってるんだけど (書く“べき”ことが、ではない)、 量をためすぎて一度に全部ぶちまけると大変なことになるのでやらない。
まァ時機もほとんど逸しまくってるし、 ためといても特に何も支障がなかった程度の内容だし。 とりあえず未来の自分 (のヒマツブシ) 用にぼちぼち小出しに。

> 今月頭から半ばにかけて、 「非実在青少年」という珍造語が印象的な東京都条例改悪案が実質的に何ら審議らしい審議もされないまま可決されそうになっちゃって、 大変だった。 ワシほとんど Twitter でヒトのつぶやきを RT してただけであと何もしてないけど。 結局“継続審議”ということで結論は 6月に持ち越しになったらしいが、 この“継続審議”ってのは即ち修正・変更は加わるにしても廃案になることはまずないという意味なんだそうで。 ウツクシイ日本語の意味をイビツに歪めて内輪用の汚いジャーゴンぼこすか量産しやがって。
それにしても…。

> メモ。 ImageMagick (convert) で色味補正しつつノーマライズ。 これがベストかどうかは分からない。 (テキトーに試行錯誤した結果)

> 自転車の積算走行距離がいつの間にか 1000km を (10000km をではなく) 超えていた。 現在 1300km くらい。 以前距離計の電池を完全に切らして内容を揮発させてしまい、 積算距離は記憶を頼りにテキトーに入れ直したので、 あんまし正確ではないけど。(*27-1)
自転車購入から 2年半で 1300km って少ないんだろうなァ。 まァ滅多に外出しないからな。

> 「抱き枕のアナグラムで倉田真希」 という自分のメモを発見。 意味不明。

> どうでもいい話。
TV CM で、他人の (架空の) アイテムを“盗める”っつーのがウリらしい携帯用ゲームを宣伝してるんだけど (DeNA のモバゲーのなんとかいうやつ) CM をボーッと見ていて受けた印象では、 ゲーム内のキャラクタではなく現実世界の相手 (ゲームプレーヤ) を特定できてるように見える。 そんな訳ないよなァ…と思って検索してみたが、 やはりリアルな相手を (少なくともゲーム内から) 特定できるような仕掛けはなさそうだ。 ボーッと見てるのが悪いと言われればそれまでだが、 なんか紛らわしいよーな気がするんだよなあの CM…。
まァしかし実世界の誰かであっても架空世界のキャラクタであっても、 互いの (架空の) “持ち物”を窃盗しあうゲームって、面白いのかなあ。 そのセンスがよく理解できないなァ…と CM を見る度に思うんだった。 どっちみち携帯端末持ってないんで実際どういうシステムなのか確認もできないが。 Willcom の PHS はいわゆる“携帯”向けサービスからほぼ完全にハブられてるからな。 (それ以前に Willcom 自体風前の灯っぽいけど。 PHS は出力弱いところとその弱点をカバーするように高出力の基地局をたくさん作った旧 DDI ポケットの方針が好きなんで (ヘンな理由)、 細々でもいいから続いて欲しいんだけど、どうなることやら)

> どーでもいい話。
もう 2ヶ月も前のことだが、 生まれて初めて幅優先探索のコードを書いた。 これまでは深さ優先探索 (バックトラック法) のコードしか書く機会がなかったんだった。
↓これなんですがな。とある会社の中途採用の入社試験。 (応募した訳ではない)

> 文中の「可能な全経路を列挙した上で最短を求める、というアルゴリズム」というのは、 深さ優先探索 (バックトラック法) のことのようだ。
しかし迷路をたどる系プログラムというと深さ優先探索のコードしか書いたことがない。 まァこのくらいの迷路なら比較的単純な枝刈りだけでもそんなに時間もかからん気がするし、 どのくらいかかるかとりあえず書いて動かしみてダメそうだったらまた考えよう、という戦略で、 まずは深さ優先探索で (いつものように Perl で) 書いてみた。 所要時間約 30～40分 (うろ覚え)。 Cygwin 上で走らせたところ、数分程度で解が出た。

use strict;

# 深さ優先探索

# マップ：
# '*' 壁
# 'S' スタート地点
# 'G' ゴール地点
# '$' 足跡
# ' ' 道

my @map;
while (<DATA>) {
    chomp;
    push @map, [split '', $_];
}

# 何歩進んだかのカウンタ
my $step = 0;
# ゴールまでの歩数の過去最小値
my $minstep = 0;
# 座標(スタート地点で初期化)
my ($x, $y) = get_start();

search_next_and_go();

sub search_next_and_go {
    # 上
    go_d(0, -1);
    # 右
    go_d(1, 0);
    # 下
    go_d(0, 1);
    # 左
    go_d(-1, 0);
}

sub go_d {
    my ($dx, $dy) = @_;
    # 進めるか判定
    my $c = $map[$y + $dy][$x + $dx];
    return if $c ne ' ' and $c ne 'G';
    # よし行け
    $step++;
    # 単純な枝刈り
    if ($minstep and ($minstep <= $step)) {
        $step--;
        return;
    }
    $x += $dx;
    $y += $dy;
    if ($map[$y][$x] eq 'G') {
        goal();
    } else {
        $map[$y][$x] = '$';
        search_next_and_go();
        $map[$y][$x] = ' ';
    }
    $x -= $dx;
    $y -= $dy;
    $step--;
}

sub get_start {
    my $len = $#{$map[0]};
    for (my $y = 0; $y <= $#map; $y++) {
        for (my $x = 0; $x <= $len; $x++) {
            return ($x, $y) if $map[$y][$x] eq 'S';
        }
    }
    return (-1, -1);    # MAPが正しければ決して返さない
}

sub goal {
    $minstep = $step;
    print "step: $minstep\n";
    print_map();
}

sub print_map {
    for (@map) {
        print @$_, "\n";
    }
}


__DATA__
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************

ところで説明文にあるような「マップのほとんどがスペースである場合」はどうなるのか。 試しにマップをいじって広場をいくつか作ってみたところ、 今度は何十分待っても終わらない。 探索過程を表示させてみたら、とても数時間やそこらじゃ終わりそうにない感じの進み具合。 なるほど～。
で、 Web で情報漁りつつ幅優先探索のコードも書いてみた。 深さ優先探索がスタックを使って再帰的にたどるのに対し、 幅優先探索ではキューを使って出発点から近い順に処理していくのだが、 最短ルートをどう判別すればいいのかピンと来ず半日ほど悩む。 深さ優先なら処理を進めつつ、たどったノードをスタックに積んでいって (戻る時は値も捨てて)、 ゴールに着いたらスタックを底から読み出せばいいだけなんだけど。 結局、全ノード分のワーク (二次元配列) を用意して、 ノードごとに「どちらから進んできたか」の情報を格納しておき、 ゴールに着いた時点でゴールから経路を遡ってたどればいいと分かるまでずいぶんかかってしまった。 (頭錆びついてけつかる)
そんなこんなでなんとかコードをでっち上げて走らせたところ、 ほぼ一瞬で答えが出てしまった。うほー。 マップを広場だらけに書き換えてもほぼ一瞬。 全部広場にしてもほぼ一瞬。 まァ原理的には確かにそうなんだろうけど、 しかし探索の仕方でこうも劇的に処理速度が変わるんだなァ、と改めて思った次第。

use strict;

# 幅優先探索

# マップ：
# '*' 壁
# 'S' スタート地点
# 'G' ゴール地点
# '$' 足跡
# ' ' 道


my @map;
while (<DATA>) {
    chomp;
    push @map, [split '', $_];
}

# 座標(スタート地点で初期化)
my ($x, $y) = get_start();

my @queue;
my $from;

# スタート地点の目印
$from->[$y][$x] = [-1, -1];
search_next_and_go();

sub search_next_and_go {
    push @queue, [$x, $y];
    while (($x, $y) = @{shift @queue}) {
        if ($map[$y][$x] eq 'G') {
            goal();
            return;
        } else {
            for ([0, -1], [1, 0], [0, 1], [-1, 0]) {
                my ($dx, $dy) = @{$_};
                # 進めるか判定
                my $c = $map[$y + $dy][$x + $dx];
                if (! $from->[$x + $dx][$y + $dy] and ($c eq ' ' or $c eq 'G')) {
                    push @queue, [$x + $dx, $y + $dy];
                    $from->[$x + $dx][$y + $dy] = [$x, $y];
                }
            }
        }
    }
    print "no answer.\n";
}

sub get_start {
    my $len = $#{$map[0]};
    for (my $y = 0; $y <= $#map; $y++) {
        for (my $x = 0; $x <= $len; $x++) {
            return ($x, $y) if $map[$y][$x] eq 'S';
        }
    }
    return (-1, -1);    # MAPが正しければ決して返さない
}

sub goal {
    my $step;
    # mapに足跡を描く
    while (1) {
        my ($nx, $ny) = @{$from->[$x][$y]};
        last if ($nx < 0 or $ny < 0);
        $map[$y][$x] = '$' if $map[$y][$x] eq ' ';
        $step++;
        ($x, $y) = ($nx, $ny);
    }
    print "step: $step\n";
    print_map();
}

sub print_map {
    for (@map) {
        print @$_, "\n";
    }
}


__DATA__
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************

ちなみに他にも探索アルゴリズムとして A* 法だとかダイクストラ法だとかいろいろあるらしいが、 今回はごく普通の幅優先探索で済んだので使ってみてない。
他の人の解も見てみたが、やはり深さ優先探索で解いてる人がいた。 そう、先述サイトの例題 (マップ) に限ればそれで解けちゃうんだよねえ。 出題者の仕掛けたワナかも。 あと OO なコードの人がやっぱし多い。気がする。 ま～ OO な言語を使ってる人が多いから当然なんだろうけど…。 しかし OO かどうか以前にグローバル変数デフォルトな時点でアレだよな。ワシのコードの場合。 (全体がこれくらいの規模ならまァ問題なかろう的な感じで。 でも実は規模に関係なくいつもそんな感じだったりする)

> 今日はホントは何日なんだ?

> メモ。 TMPGEnc (フリー版) で、連番画像ファイルから動画をエンコードする際は、 'img-' + 数字 7桁のファイル名でないとうまくいかない。らしい。 あと「設定」→「環境設定」→「VFAPIプラグイン」で DirectShow Multimedia File Reader を無効にしておくこと、 だったかな? ずっと以前メモったような記憶があるんだが、検索かけてみたけど見つからなかった。へんだな～。