PHPで「人材獲得作戦・４ 試験問題」をやってみた

人生を書き換える者すらいた。: 人材獲得作戦・４　試験問題ほか
http://okajima.air-nifty.com/b/2010/01/post-abc6.html
　
昨日、会社に面接来た人がいて、その人にやらせたらしく。
で社長に、その人は何分で出来たかを告げられて、やる？って聞かれて、これが出来なかったらニートになるんじゃないかと思ってとりあえず必死でやってみた。
その人はC++でやったらしいけど、1番得意なはずのPHPでやってみた。
↓こんな感じでやってみようかと思ったけどやった事ないからやめといた。今回使った方法もほぼ初めての書き方だったけど。

class Route {
	public y;
	public x;
	public next; // Route
}

総当り版

アルゴリズムなんて解らないからまずは総当たり。
作るのは1時間ちょっと(構文エラーのみ確認)で、プログラム実行時間は計ってないけど確か20分とか30分とかそれ位かかった。
行き止まりかゴールにたどり着いてから次のルートを探すから、めちゃくちゃ遅い。
苦し紛れに、過去の最短ゴール歩数を越えたらそこで終了、ってしてるけど遅い事には変わりない。
それにしても行き当たりばったりなコードで汚い。
最近PHPから離れててforeachの書き方忘れちゃったから使えなかった。

<?php
ini_set("memory_limit", "1024M");

$txt = file_get_contents(dirname(__FILE__).'/input.txt');
$txt = trim($txt);
$txt = str_replace("\r\n", "\n", $txt);
$txt = str_replace("\r", "\n", $txt);

$map = array();
$line = explode("\n", $txt);

for ($i=0; $i<count($line); $i++) {
	$map[] = str_split($line[$i]);
}

// S
for ($i=0; $i<count($map); $i++) {
	for ($j=0; $j<count($map[$i]); $j++) {
		if ($map[$i][$j]=='S') {
			break 2;
		}
	}
}

echo "S = y:$i x:$j\n";
$s_y = $i;
$s_x = $j;

// G
for ($i=0; $i<count($map); $i++) {
	for ($j=0; $j<count($map[$i]); $j++) {
		if ($map[$i][$j]=='G') {
			break 2;
		}
	}
}

echo "G = y:$i x:$j\n";
$g_y = $i;
$g_x = $j;


class Route
{
	public static $map;
	public static $goal;

	public function __construct($y, $x, $route = array())
	{
		$route[] = array($y, $x);
//		echo "goal:".count(Route::$goal)." route:".count($route)." y:{$y} x:{$x}"."\n";
		// ゴール
		if (isset(Route::$map[$y][$x]) && Route::$map[$y][$x]=='G') {
			Route::$goal = $route;
			return;
		}
		// 最短は出せない
		if (isset(Route::$goal) && count(Route::$goal)<=count($route)) {
			return;
		}
		// 次へ進む
		if (Route::checkMap($y+1, $x) && Route::checkFix($y+1, $x, $route)) {
			new Route($y+1, $x, $route);
		}
		if (Route::checkMap($y-1, $x) && Route::checkFix($y-1, $x, $route)) {
			new Route($y-1, $x, $route);
		}
		if (Route::checkMap($y, $x+1) && Route::checkFix($y, $x+1, $route)) {
			new Route($y, $x+1, $route);
		}
		if (Route::checkMap($y, $x-1) && Route::checkFix($y, $x-1, $route)) {
			new Route($y, $x-1, $route);
		}
	}

	public static function checkMap($y, $x)
	{
		if (isset(Route::$map[$y][$x])) {
			if (Route::$map[$y][$x]==' ' || Route::$map[$y][$x]=='G') {
				return true;
			}
		}
		return false;
	}

	public static function checkFix($y, $x, $route)
	{
		for ($i=0; $i<count($route); $i++) {
			if ($route[$i][0]==$y && $route[$i][1]==$x) {
				return false;
			}
		}
		return true;
	}
}

// all route
Route::$map = $map;
new Route($s_y, $s_x);
print_r(Route::$goal);

// 道筋
for ($i=0; $i<count(Route::$goal); $i++) {
	$map[Route::$goal[$i][0]][Route::$goal[$i][1]] = '$';
}

// 出力
$result = '';
for ($i=0; $i<count($map); $i++) {
	for ($j=0; $j<count($map[$i]); $j++) {
		$result .= $map[$i][$j];
	}
	$result .="\n";
}
echo $result;

先人がいたら諦める版

流石に遅いと思って全員1マスずつ進んで、そのマスにもっと早くたどり着くルートがある場合はそこで中断するようにした。
時間は定かじゃないけど、総当りのプログラムが結果を出すより前には打ち終わって結果も出た位の時間。
今回は最短ルートをすべて調べるようにした。
すべてのルートを最後まで保持するから、メモリ使用量は総当たりverよりも遥かに多い。
count($route)<=Route::$saitan[$y][$x] を count($route)

<?php
ini_set("memory_limit", "1024M");

$txt = file_get_contents(dirname(__FILE__).'/input.txt');
$txt = trim($txt);
$txt = str_replace("\r\n", "\n", $txt);
$txt = str_replace("\r", "\n", $txt);

$map = array();
$line = explode("\n", $txt);

for ($i=0; $i<count($line); $i++) {
	$map[] = str_split($line[$i]);
}

// S
for ($i=0; $i<count($map); $i++) {
	for ($j=0; $j<count($map[$i]); $j++) {
		if ($map[$i][$j]=='S') {
			break 2;
		}
	}
}

echo "S = y:$i x:$j\n";
$s_y = $i;
$s_x = $j;

// G
for ($i=0; $i<count($map); $i++) {
	for ($j=0; $j<count($map[$i]); $j++) {
		if ($map[$i][$j]=='G') {
			break 2;
		}
	}
}

echo "G = y:$i x:$j\n";
$g_y = $i;
$g_x = $j;


class Route
{
	public static $map;
	public static $goal = array();
	public static $all = array();
	public static $saitan = array();
	public $y;
	public $x;
	public $route = array();

	public function __construct($y, $x, $route = array())
	{
		$this->y = $y;
		$this->x = $x;
		$route[] = array($y, $x);
		$this->route = $route;
		// goal
		if (isset(Route::$map[$y][$x]) && Route::$map[$y][$x]=='G') {
			Route::$goal[] = $this->route;
			return;
		}
		Route::$all[] = $this;
	}

	public static function start($y, $x, $route = array())
	{
		new Route($y, $x);
		while (count(Route::$goal)==0) {
			Route::next();
		}
	}

	public static function next()
	{
		$next = 0;
		for ($i=0; $i<count(Route::$all); $i++) {
			$r = Route::$all[$i];
			if (Route::checkMap($r->y+1, $r->x, $r->route)) {
				$next++;
				new Route($r->y+1, $r->x, $r->route);
			}
			if (Route::checkMap($r->y-1, $r->x, $r->route)) {
				$next++;
				new Route($r->y-1, $r->x, $r->route);
			}
			if (Route::checkMap($r->y, $r->x+1, $r->route)) {
				$next++;
				new Route($r->y, $r->x+1, $r->route);
			}
			if (Route::checkMap($r->y, $r->x-1, $r->route)) {
				$next++;
				new Route($r->y, $r->x-1, $r->route);
			}
		}
		return $next;
	}

	public static function checkMap($y, $x, $route)
	{
		if (isset(Route::$map[$y][$x])) {
			if (Route::$map[$y][$x]==' ' || Route::$map[$y][$x]=='G') {
				if (!isset(Route::$saitan[$y][$x])) {
					Route::$saitan[$y][$x] = count($route);
					return true;
				} elseif (isset(Route::$saitan[$y][$x]) && count($route)<=Route::$saitan[$y][$x]) {
					Route::$saitan[$y][$x] = count($route);
					return true;
				}
			}
		}
		return false;
	}
}

// all route
Route::$map = $map;
Route::start($s_y, $s_x);
//print_r(Route::$goal);

for ($k=0; $k<count(Route::$goal); $k++) {
	$map2 = $map;

	// 道筋
	for ($i=1; $i<count(Route::$goal[$k])-1; $i++) {
		$map2[Route::$goal[$k][$i][0]][Route::$goal[$k][$i][1]] = '$';
	}

	// 出力
	$result = '';
	for ($i=0; $i<count($map2); $i++) {
		for ($j=0; $j<count($map2[$i]); $j++) {
			$result .= $map2[$i][$j];
		}
		$result .="\n";
	}
	echo $result."\n";
}

アルゴリズム

ダイクストラ法だか幅優先探索だかを解説してる記事を見ても、結局アルゴリズムのやり方はよく解らず。
というか難しそうでまったく読む気にならなかった。
元記事にトラックバックを送ってる人たちの中で解りそうな言語でやってるのを探したけど特になく。
文法的にはJavaかC言語が読みやすいかと思ったけど、型が解らないから結局読めなかった。
　

char

システム移行で、データベースをOracleからMySQLにテキスト経由で移動させたのを思い出した。
カラムは、文字列左寄せスペース詰めの固定幅、数字右寄せスペース詰めの固定幅で出力されたテキスト。
なんでテキストだったのかは知らないけど。
行をループして、スペースじゃない文字がある列にフラグを立てて、フラグが0から1に変化したインデックスをカラムの開始箇所として記録して、また最初からループして開始箇所で分割して、trimして、絵文字を文字列に置き換えて、SJISからUTF-8に変換して、insert分を作る、っていうやつ。
そういえばこれもめちゃくちゃ遅かった。
　

最短ルート168パターン

貼り付けようとしたら長すぎて駄目だった…。
とりあえず最初の1つだけ…。

S = y:1 x:1
G = y:8 x:22
**************************
*S* *$$$$                *
*$* *$ *$ *************  *
*$*$$$* $  ************  *
*$$$ *  $$$$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$  *$$$$$$$$$$$$$$G  *
*  *$$$$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************

　
今日はご飯とトイレ以外ベッドから降りず、居眠りして起きたら添い寝してるMacBookをちょっといじってまた寝るってのをずっと繰り返してる。
こんな廃人生活、何年ぶりだろう。
なんでか知らないけど、今週は始まって以来の勢いで疲れた。
ずっとヒザが痛い。
果たしてこの日記を書くのに何回の居眠りを挟んでいるのか。
朝だか夜だか解らないけどお腹すいた。