例の話題の試験の解答

とりあえず、ざっくりとこんな感じか。

#!/usr/bin/perl

use strict;
use warnings;

my @map;
my @start;
my @goal;
my $i = 0;
while (<>) {
    chomp;
    my @map_line = split(//, $_);
    my $j = 0;
    foreach (@map_line) {
        @start = ($i, $j) if $_ eq 'S';
        @goal  = ($i, $j) if $_ eq 'G';
        $j++;
    }
    push @map, \@map_line;
    $i++;
}
$map[$start[0]][$start[1]] = ' ';
$map[$goal[0]][$goal[1]] = ' ';

my @queue;

my ($x, $y) = @start;
$map[$x][$y] = 0;
until ($x == $goal[0] and $y == $goal[1]) {
    my $last = 0;
    foreach ([$x-1, $y], [$x+1, $y], [$x, $y-1], [$x, $y+1]) {
        my ($nx, $ny) = @$_;
        if ($map[$nx][$ny] eq ' ') {
            $map[$nx][$ny] = $map[$x][$y] + 1;
            push @queue, $_;
        }
    }

    ($x, $y) = @{shift @queue};
}

($x, $y) = @goal;
until ($x == $start[0] and $y == $start[1]) {
    $map[$x][$y] = '$';
    my $last = 0;
    my ($minx, $miny);
    my $min;
    foreach ([$x-1, $y], [$x+1, $y], [$x, $y-1], [$x, $y+1]) {
        my ($nx, $ny) = @$_;
        if ($map[$nx][$ny] !~ /[\$\* ]/ and (not defined $min or $min > $map[$nx][$ny])) {
            $min = $map[$nx][$ny];
            ($minx, $miny) = @$_;
        }
    }
    ($x, $y) = ($minx, $miny);
}

$map[$start[0]][$start[1]] = 'S';
$map[$goal[0]][$goal[1]] = 'G';
foreach (@map) {
    print join('', map { $_ =~ /[\*\$SG]/ ? $_ : ' ' } @$_) . "\n";
}

結果

mkataigi:~$ cat sample
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************
mkataigi:~$ ./route.pl < sample
**************************
*S* * $$$$               *
*$* *$$* $*************  *
*$* $$*  $$************  *
*$$$$*    $$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$$$* $$$$$$$$$$$$$G  *
*  *  $$$$*********** *  *
*    *        ******* *  *
*       *                *
**************************

基本的なダイクストラで実装。

他のことやりながらでしたが、だいたい1時間半位だったかな。

表面保護シートを交換したら、入力感度がよくなった

先日iPhoneにつけているソフトカバーが、破けてしまったため、別のカバーに交換しました。そのとき、表面保護シートの方もずいぶん汚れていたので、一緒に交換。そうしたら、入力感度が劇的に向上しました。


もともと、コピペの範囲選択をするときとか、漢字変換の変換候補を選ぶときとか、タッチする部分が小さいものだと、思ったようにタッチできなくていらいらしてました。みんなどうやってうまく入力してるんだろうなー、なんぞと考えてましたが、表面保護シートを交換したら、普通に反応するようになりました。


まあ、当たり前といっちゃ当たり前なのですが、うまく反応してくれていない原因は表面保護シートだったようです。自分でそういうもんだと思い込んでると気づかないもんなんですよね。


iPhoneを使うようなら、表面保護シートはちゃんとしたのを選んで、定期的に交換した方が良さそうですね。

福島(3日目)

福島最終日です。今日は昨日とは打って変わって快晴でいい感じです。昨日は結局全くみられなかったので、今日は昨日と同じ道を引き返して観光です。

最初は有料道路のスカイラインです。昨日はほとんど見えなかったのですが、かなり景色のいい道です。途中で鉄橋があるのですが、そこを眺められる展望台があるのでそこからみてみます。
P1070704

スカイラインをさらに上っていくと、最後は荒涼とした場所に出てきます。壮大な景色でいい感じです。スカイラインの最後に近い場所にある浄土平に行ってみます。駐車場に止めて、吾妻小富士に登ってみます。頂上までは歩いて10分くらいでつきます。
P1070732
P1070748
火は出ていないですが、火山のため、頂上からは火口が見えます。ここではこの火口に沿って一周歩くことができます。かなり細い道で両側が切り立っているため、結構怖いのですが、景色はかなりよいです。所々で止まって周りを見渡すといい感じです。
P1070754

吾妻小富士を下りたら次は五色沼に向かいます。ここは沼と言っても実際はきれいな湖という感じの場所で、名前の通りおもしろい色をしています。湖沿いを歩けるようになっていて、犬の散歩なんかをしている人もいます。相変わらず人が多い。歩いて1時間くらいの散策路を行きます。
P1070816
反対側に抜けると、桧原湖があります。観光船なんかも出て居るみたいですね。久々にがっつり歩いて、かなり疲れてしまったので、ちょっと休憩。散策路を通って五色沼の反対側まできてしまったので、帰りはバスです。ここに来て満員バスです。
P1070874

この後どこに行こうかと考えたのですが、会津若松側はすでに昨日見てしまったので、戻って安達太良方面に行ってみます。安達太良側も走りやすい道が続きます。途中の道の駅に止まって、次にどこに行くか考えたのですが、安達太良山といったら智恵子抄ということで、近くに智恵子の生家なるものがあるらしいのでそっちに行ってみます。

智恵子の生家は普通の資料館の様です。周りをざっと眺めて、次に行きます。
P1070906

こっち側は完全に福島市街地なので、これって言うような観光地は無い様です。ざっと市内を走っていたら、いい感じの時間になってしまったので、食事をして帰宅です。

帰りは時間を遅めにしたこともあって、そんなに混んではいなかったのですが、時間も遅いことですし疲れもあるのでゆっくり帰ります。結局帰りも7時間くらいかかってます。

天気は微妙ですが、まあ東北らしく涼しかったかな、という感じでした。

200907福島 - a set on Flickr

福島(2日目)

福島2日目です。今日は若干天気が悪そうなので、室内で観光できそうなところを優先的に回ります。

最初は鶴ヶ城です。戊辰戦争の会津戦でも出てくる城です。中は資料館になってます。頂上からは会津若松市内が一望できるようになってます。大河ドラマの影響もあってか、結構人が多い。
P1070556

城を出たら、きれいに晴れていたので、ちょっと屋外の観光地を回ってみよう、ということで猪苗代湖に行ってみます。猪苗代湖は湖岸が整備されていて、海水浴なんかもできるようになってます。車で一周ぐるっと回ったのですが、軽く1時間はかかるような広さです。
P1070598

せっかく晴れているので山側の磐梯山の方に行ってみます。ここはいくつかの有料道路でつながっている、ドライブするとおもしろい道です。ただ、運悪く、最初の有料道路のゴールドラインに入ってちょっとした急に豪雨です。ちょっと観光できるような雨ではなかったので、有料道路を越えた後の道の駅でしばし休憩です。

しばらくたってもやむ気配がないので、しょうがなく今日の宿の福島方面へ向かいます。走っている途中で雨は小降りになったのですが、相変わらず風は強いままだったため、結局観光はできず。途中で浄土平に寄ったのですが、全く空いてないのでそそくさとあきらめて、福島へ行きます。

結局温泉でしばらく休んで、宿に行きます。

200907福島 - a set on Flickr

福島(1日目)

連休に福島にドライブに行ってきました。いまいち印象の薄い県ですが、一応東北に入る涼しい場所でした。

1日目はほとんど移動で終わります。高速1000円もあって、都内は結構混んでるのですが、東北道入ってしばらく行ったら、そこそこ進む感じでした。とは言っても、さすがに東北だけあって遠いです。東京からだいたい7時間という感じ。

高速を降りてから宿に行くまでに通る場所で軽く観光です。最初は羽鳥湖高原です。雨が上がったばっかだったので、高原はちょっと観光しにくいので、さっとみて次に行きます。
P1070471


次は塔のへつりに行ってみます。ここは変わった形の岩が立ち並ぶところで、岩の溝になっている部分を歩けるようになっています。
P1070492

最後は大内宿です。昔の家屋が建ち並んだ、ちょっと変わった場所です。かなりきれいに整備されてます。ただ、時間が遅かったので、残念ながら店は開いてませんでした。ちゃんと観光したいなら早めの時間に行った方が良さそうですね。
P1070534

ちょっと遅くなりましたが、会津若松市内の宿に向かって1日目終了です。

200907福島 - a set on Flickr

第4回MG勉強会

本日は4回目のMG勉強会でした。今日は2章を一気に終わらせるつもりなので、かなりの長丁場です。


まずは前回積み残しのDynamic Markov Compressionです。この手法では有限状態機械を適応的に作りつつ、符号語を構成していくという方法で、この有限状態機械により文脈を判断するようになっています。また、有限状態機械を構築していくときに、入出力が多くなってしまうノード(=文脈が判断しづらいノード)はcloneすることにより文脈を分けます。


次はDictionary modelsです。これは今まで出てきた語の辞書を作りつつ、既に前に出てきた語はその辞書の番号で置き換えていくことにより、文章を圧縮していく手法になります。この本ではLZ77とLZ78という手法が紹介されています。


まずはLZ77です。この手法ではある語が何文字前に出現したかとそこから何文字コピーするか、という情報を保持しておくことにより、後ろの語を前に出てきた語の位置で置き換える手法になります。
もう一つのLZ78は前に出てきた単語を辞書に登録しておいて、後で出てきた単語はその辞書の番号で代替させる方法になります。


次の部分はSynchronizationです。これは今までの手法だと、単語を前から順に復号していかないと中身がとれないのですが、検索のようにランダムアクセスを行いたい場合、どうしても途中から一部分だけ復号したいということがあります。そのときにちょっと工夫して構成することにより、途中からでも復元できるようにする方法がSynchronizationです。


また符号語には、適当な場所から復号を始めても、最初はもちろん一致しないのですが、復号を続けていくうちに、元の語に戻っているというSelf-synchronizationなる性質を持った符号語もあるそうです。まあここら辺はこういうのもありますよ、程度のお話なのでさらっと。


最後は性能比較です。筆者が自分たちで作ったであろうプログラムと、バリバリチューニングされたプログラムを比較してたり、環境によって異なってくるといいつつ、1種類の環境でしか比較してなかったりするので、厳密な結果とはいいがたいですが、参考としては面白い感じです。順当に圧縮率が高いものは符合化復号化に時間がかかる、という感じですね。


次回はIndexingということで、バリバリの検索関連の話題に戻ります。

Hack部合宿

もう2週間も前で今更な感じですが、某Hack部で伊東まで開発合宿に行ってきました。
余裕を持って行ったら予定の集合時間の1時間前くらいに着いてしまったので、軽く周りを散策してました。
そのときの写真。

P1070401

P1070418

宿自体は古くてお世辞にもきれいとは言い難いところでしたが、それっぽい風格があって、何より無線LANつなぎ放題です。
なんやら合宿プランみたいのがあるらしいので、開発合宿御用達の宿になっているらしいです。

P1070413

P1070444

合宿そのものはあまり動きもないので写真撮ってない。
合宿で作ったものは、ちゃんとできたら公開するかも?

200906開発合宿伊東 - a set on Flickr