WebCrawler RSSフィード

2010-03-06

グレイコード

プログラミング

先日某勉強会で出たグレイコードについて、一応概念的には知っていたのですが、実装とかをよく知らなかったため調査。

グレイコードについてはWikipediaに結構詳しく書いてあります。

グレイコード - Wikipedia


このグレイコード、何がいいかというと、数字的な近さがそのままグレイコード表現でも近くなることです。

普通の２進数の場合だと、例えば、

7 => 0111
8 => 1000

となって、数字上ではとなりの数字なのに、２進数では４ビットも違う表現になってしまいます。

しかし、グレイコードの場合は、

7 => 0100
8 => 1100

のようになって、数字上のとなりの数字が、グレイコード表現でも１ビット違いで表現されます。


このグレイコードの構成方法ですが、いろいろとあるのですが、ひとつの簡単な方法としては「反射２進グレイコード」というものがあります。

これは前半部分のグレイコードを反転して、先頭に0,1をつけることによってグレイコードの続きを作っていく方法です。


説明だとよくわからないので、実例で。

 0          0            00
 1   反転   1  0,1付与   01
---  ===>  ---  ======> ----
            1            11
            0            10

この数字 => グレイコード変換は単純な２進演算で実装できます。

この変換を実装するとこんな感じ。

#!/usr/bin/perl

use strict;
use warnings;

for (0 .. 15) {
    my $gray = $_ ^ ($_ >> 1);
    print sprintf("%2d => %04b\n", $_,  $gray);
}

結果

$ ./graycode.pl
 0 => 0000
 1 => 0001
 2 => 0011
 3 => 0010
 4 => 0110
 5 => 0111
 6 => 0101
 7 => 0100
 8 => 1100
 9 => 1101
10 => 1111
11 => 1110
12 => 1010
13 => 1011
14 => 1001
15 => 1000

こんな感じで数字からグレイコードへの変換は簡単にできます。

ただ、逆のグレイコードから数字への変換はちょっと難しいようです。

ここら辺は後でもうちょっと詳しく調ベる。



ハッカーのたのしみ—本物のプログラマはいかにして問題を解くか

Permalink | コメント(0) | トラックバック(0) | 17:51 グレイコード - WebCrawler を含むブックマーク はてなブックマーク - グレイコード - WebCrawler

2010-03-01

MacPortsのソフトウェアを一括でインストールするスクリプト書いた

プログラミング, mac

先日、mac portsのソフトウェアの依存関係がどうにもおかしくなってしまっていたので、一念発起してまっさらにして入れなおしました。

アンインストールする方は結構簡単にいくんですが、アンインストールした物を再度インストールしなおすのが大変。

mac portsではローカルでコンパイルしてるらしいので、一個一個が結構時間かかるんですね。


どうにも面倒になってきたので、一括でインストールするスクリプト書きました。

とりあえず一回動けばいいので、エラー処理もテストもろくにしてないです。

自分で動かしたときにはうまくいきました。


一応依存関係には配慮して、自動でインストール順を決めるようにはしています。

ただ、ガッツリmac portsの出力依存なので、バージョン変わると動かないかも。

使うときには、インストールしたいportのソフトをvariant付きでひとつのファイルにズラズラ書き出して、それを引数に与えてスクリプトを実行すればOK。

$ port version
Version: 1.8.2
$ cat install_list.txt
gcc43
perl5 +perl5_10
#sqlite3
$ sudo ./port_install.pl install_list.txt

なかでport installを回しているだけなので、相当時間がかかるので、夜中に実行して、朝起きたら終わってる、位の感覚で実行するといいかも。


以下スクリプト本体。

#!/usr/bin/perl

use strict;
use warnings;
use IO::File;


if (scalar(@ARGV) < 1) {
    exit(1);
}

my $filename = $ARGV[0];

my $file = IO::File->new($filename, 'r');
my @not_install = ();
my %variants = ();
while (my $line = $file->getline) {
    chomp $line;
    if ($line ne "" and $line !~ /^\s*#/) {
        my ($cmd, @variant) = split(/\s+/, $line);
        $variants{$cmd} = \@variant;
        push @not_install, $cmd;
    }
}

my %dependencies = ();
for my $cmd (@not_install) {
    my ($name, @deps);
    my $out = `port deps $cmd @{$variants{$cmd}}`;
    for my $l (split(/\n/, $out)) {
        if ($l =~ /Full Name:\s([^ ]*)\s/) {
            $name = $1;
        } elsif ($l =~ /has no Build Dependencies/) {
        } elsif ($l =~ /Build Dependencies:\s+(.*)$/) {
            foreach my $dline (split(/,\s/, $1)) {
                if ($dline ne "" and $dline ne ",") {
                    chomp $dline;
                    push @deps, $dline;
                }
            }
       } elsif ($l =~ /Library Dependencies:\s+(.*)$/) {
            foreach my $dline (split(/,\s/, $1)) {
                chomp $dline;
                if ($dline ne "" and $dline ne ",") {
                    push @deps, $dline;
                }
            }
        }
    }
    $dependencies{$name} = \@deps;
}

my @installed = ();
while (scalar @not_install) {
    my $cmd = shift @not_install;
    my $dep_flag = 0;
    for my $dep (@{$dependencies{$cmd}}) {
        for my $not_install_cmd (@not_install) {
            if ($dep eq $not_install_cmd) {
                $dep_flag= 1;
                last;
            }
        }
        last if $dep_flag;
    }
    if ($dep_flag) {
        push @not_install, $cmd;
    } else {
        push @installed, $cmd;
    }
}

my @install_ok = ();
my @install_ng = ();
for my $cmd (@installed) {
    eval {
        system("port",  "install",  $cmd, @{$variants{$cmd}});
    };
    if ($@) {
        push @install_ng, "$cmd @{$variants{$cmd}}";
        eval {
            system("port",  "clean",  $cmd);
        };
    } else {
        push @install_ok, "$cmd @{$variants{$cmd}}";
    }
}

print "install OK\n" . join("\n", @install_ok) . "\n\n";
print "install NG\n" . join("\n", @install_ng) . "\n\n";

Permalink | コメント(0) | トラックバック(0) | 23:17 MacPortsのソフトウェアを一括でインストールするスクリプト書いた - WebCrawler を含むブックマーク はてなブックマーク - MacPortsのソフトウェアを一括でインストールするスクリプト書いた - WebCrawler

2010-01-17

例の話題の試験の解答

プログラミング

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

#!/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  *
*  *  $$$$*********** *  *
*    *        ******* *  *
*       *                *
**************************

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

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

Permalink | コメント(0) | トラックバック(0) | 18:47 例の話題の試験の解答 - WebCrawler を含むブックマーク はてなブックマーク - 例の話題の試験の解答 - WebCrawler

2009-08-23

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

iPhone

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


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


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


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

Permalink | コメント(1) | トラックバック(0) | 21:49 表面保護シートを交換したら、入力感度がよくなった - WebCrawler を含むブックマーク はてなブックマーク - 表面保護シートを交換したら、入力感度がよくなった - WebCrawler

2009-07-25

福島(3日目)

旅行

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

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

P1070704

スカイラインをさらに上っていくと、最後は荒涼とした場所に出てきます。壮大な景色でいい感じです。スカイラインの最後に近い場所にある浄土平に行ってみます。駐車場に止めて、吾妻小富士に登ってみます。頂上までは歩いて10分くらいでつきます。

P1070732

P1070748

火は出ていないですが、火山のため、頂上からは火口が見えます。ここではこの火口に沿って一周歩くことができます。かなり細い道で両側が切り立っているため、結構怖いのですが、景色はかなりよいです。所々で止まって周りを見渡すといい感じです。

P1070754

吾妻小富士を下りたら次は五色沼に向かいます。ここは沼と言っても実際はきれいな湖という感じの場所で、名前の通りおもしろい色をしています。湖沿いを歩けるようになっていて、犬の散歩なんかをしている人もいます。相変わらず人が多い。歩いて1時間くらいの散策路を行きます。

P1070816

反対側に抜けると、桧原湖があります。観光船なんかも出て居るみたいですね。久々にがっつり歩いて、かなり疲れてしまったので、ちょっと休憩。散策路を通って五色沼の反対側まできてしまったので、帰りはバスです。ここに来て満員バスです。

P1070874

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

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

P1070906

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

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

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

福島 - a set on Flickr

Permalink | コメント(3) | トラックバック(0) | 23:05 福島(3日目) - WebCrawler を含むブックマーク はてなブックマーク - 福島(3日目) - WebCrawler

福島(２日目)

旅行

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

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

P1070556

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

P1070598

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

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

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

福島 - a set on Flickr

Permalink | コメント(0) | トラックバック(0) | 22:36 福島(２日目) - WebCrawler を含むブックマーク はてなブックマーク - 福島(２日目) - WebCrawler

福島(1日目)

旅行

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

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

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

P1070471


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

P1070492

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

P1070534

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

福島 - a set on Flickr

Permalink | コメント(0) | トラックバック(0) | 22:20 福島(1日目) - WebCrawler を含むブックマーク はてなブックマーク - 福島(1日目) - WebCrawler

プロフィール

mkataigi

mkataigi

サービス
Twitter
Frickr
カレンダー
<< 2010/03 >>
日 月 火 水 木 金 土
1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31
カテゴリー
最新タイトル
最近のコメント
最近のトラックバック
プロフィール

mkataigi

mkataigi

mkataigiのブックマーク
日記の検索