2010年1月アーカイブ

2010年1月13日

スタート地点からゴール地点に至る最短経路を求めよ

とくに理解できないのはLv0,1の人たちが開発現場でどんな仕事をしてるのかだな。ぶっちゃけ、3時間かけてこれということはコードを書く能力は0でしょ? なのに経歴書にはいろいろなプロジェクトにプログラマとして関わった経験があるようだし、こんな人でも何とか使わないといけない状況に置かれた彼らの上司がかわいそうでならない。

岡島氏のプログラマ採用の試験問題をやってみました。

試行錯誤しながら2時間半かけて一応完成しました。
時間制限のある緊張化だと、制限時間内の3時間で完成したかどうかは疑問です。
私はアルゴリズムの基礎力が無いから、力業で解決しようとする傾向があるように思いました。
あと寝る前にすると頭に血が回って寝付けないよ!

ちなみに今まで一緒に仕事をしてきた実際の職場のプログラマの方々の中で、
この問題を3時間で解ける人は、10人に1人いるかいないかだと思います。

2時間半で簡易動作の確認まではしたコード。
リファクタリングなし、見直しなし

#!/usr/local/bin/perl --
use strict;
use warnings;

my @map;
my @root;

# マップ読み込み
my $y = 0;
my $x = 0;
my $goalY = 0;
my $goalX = 0;
my $maxY = 0;
my $maxX = 0;
open(FILE,"< map.txt") || die $!;
while (){
my @line = split(//,$_);
$x = 0;
foreach my $c (@line){
$map[$y][$x] = $c;
if($c eq 'S'){
$root[$y][$x] = 0;
}
elsif($c eq 'G'){
$root[$y][$x] = -1;
$goalY = $y;
$goalX = $x;
}
$x++;
$maxX = $x if($x > $maxX);
}
$y++;
$maxY = $y if($y > $maxY);
}
close(FILE);

# スタートからゴールまでの全探索
my $point = 0;
END_START:while(){
foreach my $y(0 .. $maxY-1){
foreach my $x(0 .. $maxX-1){
if(defined($root[$y][$x])){
if($root[$y][$x] == $point){
last END_START if(checkStoG($y-1,$x)); #上
last END_START if(checkStoG($y+1,$x)); #下
last END_START if(checkStoG($y,$x-1)); #左
last END_START if(checkStoG($y,$x+1)); #右
}
}
}
}
$point++;
last END_START if($point > 1000);
}

# ゴールからスタートまでの最短ルートを逆引き
$point++;
END_GOAL:while(){
$point--;
next if(checkGtoS($goalY-1,$goalX)); #上
next if(checkGtoS($goalY+1,$goalX)); #下
next if(checkGtoS($goalY,$goalX-1)); #左
next if(checkGtoS($goalY,$goalX+1)); #右
last END_GOAL if($point < 0);
}

# 回答表示
foreach my $y(0 .. $maxY-1){
foreach my $x(0 .. $maxX-1){
next if(!defined($map[$y][$x]));
if($map[$y][$x] eq ' ' && defined($root[$y][$x]) && $root[$y][$x] == -1){
print '$';
}
else{
print $map[$y][$x];
}
}
}

sub checkStoG{
my $y = $_[0];
my $x = $_[1];

if($map[$y][$x] eq 'G'){
# ゴールに到達
return 1;
}

if(defined($root[$y][$x])){
# 既出ルート
}
elsif($map[$y][$x] eq ' '){
# ルート候補
$root[$y][$x] = $point + 1;
}

return 0;
}


sub checkGtoS{
my $y = $_[0];
my $x = $_[1];

if(defined($root[$y][$x])){
if($root[$y][$x] == $point){
$root[$y][$x] = -1;
$goalY = $y;
$goalX = $x;
return 1;
}
}

return 0;
}


実行結果


**************************
*S* * *
* * * * ************* *
* * * ************ *
* * *
************** ***********
* *
** ***********************
* * G *
* * *********** * *
* * ******* * *
* * *
**************************

**************************
*S* * $$$$ *
*$* *$$* $************* *
*$* $$* $$************ *
*$$$$* $$$$$ *
**************$***********
* $$$$$$$$$$$$$ *
**$***********************
* $$$$$* $$$$$$$$$$$$$G *
* * $$$$*********** * *
* * ******* * *
* * *
**************************

**************************
*S                       *
*                        *
*                        *
*                        *
*                        *
*                        *
*                        *
*                     G  *
*                        *
*                        *
*                        *
**************************

**************************
*S$$$$$$$$$$$$$$$$$$$$$ *
* $ *
* $ *
* $ *
* $ *
* $ *
* $ *
* G *
* *
* *
* *
**************************


2010年1月11日

闘う時に必要なのは中島みゆきの歌だ


暗闇の中から指さすみゆきさんの手、その先には、スポットライトの光に照らされる宮下さん
伸びやかな宮下さんの声が、宙船のサビを歌い上げる。
その様子をカラカラと楽しそうに笑うみゆきさん、こんなカッコイイ男前みたことがない!
その笑いを受けて少し照れたような宮下さん、こんなカワイイ男前みたことがない!
出だしから終わりまで何もかもがかっこいい。
心地良い。




歌旅-中島みゆきコンサートツアー2007-






宙歌はこの2007年コンサートバージョンが一番好きだなぁ。
2007年コンサートは、この宙歌をはじめファイトやら誕生やら糸やら地上の星やら、
何度聞いてもすり切れない名曲ばかり。
やる気やテンションがとてもあがります。
ただ唯一の欠点は見始めると止まらないから、見終わるまで2時間かかるんだよね。

2010年1月 4日

スタンドアローン年末年始

年末年始は、一週間ほどネットが繋がらない環境で過ごしました。
意図的にネットから断線していたわけではなく物理的に繋がらない環境でした。

運営サイトで困ったことが起きてないかな、と少しだけ心配でしたが、
そのほかに大きな不便はありませんでした。

今のネット利用は暇つぶしに特化していて、積極的に参加しているコミュニティもなければ、
IRCやメールで頻繁に連絡しあう必要も相手もいないからさして困らないのでしょうね。

そしてネットの暇つぶしができなかったことによる他の暇つぶしは以下を楽しんでました。


  • HEROESのシーズン1・2(34話)をみた

    …正義だと思っていたものが悪だった、といった演出も好きだけど、
    それぞれのヒーロが自分が一番譲れないもの(家族だったり娘だったり)だけが唯一ぶれないといったところが面白いです。
    キャラクタの中ではノアが好き。
  • 本を7冊よんだ

    …西尾維新を初めて読んだけど有害図書ものじゃないの?といった表現に吹きました
  • Civ4をあそんだ

    …相変わらず奇跡的にバランスがすばらしいゲームです。
    騎士がでてくる中世あたりまではユニット一つ一つの動きにすべての注意を払ってたのしく遊ぶのだけど、
    その後の都市が10都市以上になったりと多くなってきたときは思考が雑になって作業プレイになりがち。