Re: 人材獲得作戦・４　試験問題ほか

人材獲得作戦・４　試験問題ほか
　さて試験問題です。内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。

　とりあえず Perl で書いてみました。正確な時間は測っていないけれど(途中で熱中して時間のことを完全に忘れていた)、多分１時間くらいかな？　最後の20分は見栄えの調整だったような気がしますが(汗)　せっかく Perl を使ったのに Perl っぽくないというか C 言語っぽい香りがします。何故だろう。

ソースコード
コードの解説

ソースコード

#!/usr/bin/perl

my ($maze);

my ($startX, $startY);  # Start position
my ($mazeSX, $mazeSY);  # Size of maze

sub {
    $mazeSY = 0;
    foreach (<DATA>) {
        $x = 0;
        foreach (split //) {
            ($startX, $startY) = ($x, $mazeSY) if /S/;
            $maze->{$x}->{$mazeSY} = $_;
            $x++;
        }
        $mazeSY++;
    }
    $mazeSX = $x;
}->('Initialize maze field from __DATA__');

my ($goalX, $goalY);    # Goal position

sub {
    $maze->{$startX}->{$startY} = $step = 1;
    while (1) {
        for my $y (0..$mazeSY) {
            for my $x (0..$mazeSX) {
                next if $maze->{$x}->{$y} != $step;
                for (0..3) {
                    my $xx = $x + ( 0,+1, 0,-1)[$_];
                    my $yy = $y + (-1, 0,+1, 0)[$_];
                    $_ = $maze->{$xx}->{$yy};
                    if (/G/) {
                        ($goalX, $goalY) = ($xx, $yy);
                        return; # Finish searching
                    }
                    elsif (/ / || $step < $_) {
                        $maze->{$xx}->{$yy} = $step + 1; # Fill with step count
                    }
                }
            }
        }
        $step++;
    }
}->('Find the shortest route to each point');

sub {
    while ($startX != $goalX || $startY != $goalY) {
        for (0..3) {
            my $xx = $goalX + ( 0,+1, 0,-1)[$_];
            my $yy = $goalY + (-1, 0,+1, 0)[$_];
            if ($maze->{$xx}->{$yy} == $step) {
                $maze->{$xx}->{$yy} = '$';
                ($goalX, $goalY) = ($xx, $yy);
                last;
            }
        }
        $step--;
    }
    $maze->{$startX}->{$startY} = 'S';
}->('Fill the shortest route to goal');

sub {
    for my $y (0..$mazeSY) {
        for my $x (0..$mazeSX) {
            print int $maze->{$x}->{$y} ? ' ' : $maze->{$x}->{$y};
        }
    }
}->('Print maze');

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

コードの解説

　処理ごとに関数で括っています。迷路を初期化→各マスまでの最短到達距離を求める→ゴールからスタートまでマーキング→画面に出す、という感じ。アルゴリズムの肝は最短到達距離を求める部分で、A*(エースター)だとかαβ枝狩りだとか色々テクニックはあるらしいんですが、多分、使っていません。普通にゼロからロジックを考えて実装しました。なので、アルゴリズムを知っている方が有利だとか、というのは多分無い。理論的に考える能力があって、時間をかければ誰でも解ける問題ですね。というわけで、ぐだぐだ言ってる奴はコード書けよハゲ。なかなか面白かった。
　えーっと、話を戻して最短到達距離の求め方は、1) 隣のマスに移動すると歩数+1、2) 既に到達したマスでも、到達距離が今の方が短ければ、その値でアップデート、というルールだけで、これを盤面全体でぐるーっと回してやれば、盤面上の各点に移動するための最短距離が得られます。ゴールに関係なく、盤面全体で処理しているので効率悪いけど。
　グローバル変数と変数の使いまわしはexcuse。

コメントを投稿する

返信先
コメント	お気軽にコメントをお寄せくださいませ・コメントを投稿するにはブラウザの JavaScript を有効にしてください・入力された通りに改行位置で改行されます・HTML タグは使用できませんが、文中の URL は自動的にリンクされます・"<" は "<"、">" は ">" と書いてください　・MovableType関係の質問でテンプレートタグをそのまま書かれると見えません
名前	(匿名可/必須/公開)
メール	(匿名可/必須/非公開)
投稿確認	(必須) コメントスパム防止のため投稿前にを入力してから投稿してください。お手数ですがご協力のほど宜しくお願いいたします。

ヘッダメニュー

Re: 人材獲得作戦・４　試験問題ほか

ソースコード

コードの解説

この記事を読んだ人はこんな記事も読んでいます

この記事のアーカイブ

関連記事/トラックバック

この記事にトラックバックを送るには？

コメントを投稿する

リファレンス

ブロガープロフィール

ツール

関連する商品

モバイル

ナビゲーション

記事検索

勝手におすすめ

最近のコメント/関連記事

最近の人気記事

フッタメニュー

ヘッダメニュー

Re: 人材獲得作戦・４ 試験問題ほか

ソースコード

コードの解説

この記事を読んだ人はこんな記事も読んでいます

その他の関連する記事

この記事のアーカイブ

関連記事/トラックバック

この記事にトラックバックを送るには？

コメントを投稿する

リファレンス

ブロガープロフィール

ツール

関連する商品

モバイル

ナビゲーション

記事検索

勝手におすすめ

最近のコメント/関連記事

最近の人気記事

フッタメニュー

Re: 人材獲得作戦・４　試験問題ほか