やねう企画2005年入社問題解答と解説(2)
問2.
問2.は、ペイントアルゴリズムを書けるかという問題である。ペイントアルゴリズムとしては、「scanline seedfill」(→http://www2.starcat.ne.jp/~fussy/algo/algo3-1.htm)が有名だが、その根底には、この問題で見たように再帰→非再帰に変換したあと、値(seed)のpushを出来るだけ減らそうという発想のもとに考案されている。
そこで、今回は再帰版と非再帰版とを書かせるという、ちょっと意地悪な出題の仕方をした。再帰版はたいていの人が書けていたが、非再帰は半数ぐらいの人しか書けていなかった。それも、私が求めている答えを書いてきている人は全体の2割以下という低い数字だった。書けなかった人は、解説を読みながら、自分に何が足りないのかを考えてみて欲しい。
※ ところで「再帰」を「再起」とする誤字が目立った。日ごろ再帰を使っていないのだろう。
まず再帰版から。
W(x,y):-if(!a(x,y)) a(x,y)=1,1+W(x-1,y)+W(x+1,y)+W(x,y-1)+W(x,y+1) else 0.
ちょっと見慣れない(?)記法だが、説明のために私が時々用いる記法で、最後に評価した式が関数の値として返る言語だと思っていただきたい。C言語で書くならば、以下のようになる。
int W(int x,int y) {
if (!a[x][y]) {
a[x][y]=1;
return 1+W(x-1,y)+W(x+1,y)+W(x,y-1)+W(x,y+1);
}
else
return 0.
}
少しひねって、
return (a[x][y]=1)+W(x-1,y)+W(x+1,y)+W(x,y-1)+W(x,y+1);
などと書けなくもないが、ここまでする必要はないだろう。*1
またa[x][y]=1を嫌って、
とするのも無くはないのだが、if式が不成立のときは本来インクリメントは不要なので、少し無駄かなぁという気はする。また、a[x][y]=1の代わりにa[x][y]++と書いてきている人が何人か居たが、これだとread-modify-writeになるので、前者より遥かに劣るコードだと思う。
if (!(a[x][y]++))
あと、今回の場合は、外周が1というのは保証されているのでout of rangeのチェックは不要であるが、もし必要ならば、
1 + W(a, max(0,x-1),y) + W(a, min(6,x+1), y)
+ W(a, x, max(0,y-1)) + W(a, x, min(6,y+1))
のようなhackもある。(可読性の点からあまりお勧めはしないが)
プログラムの仕組みについての解説は特にしなくとも良いと思うのだが、a[x][y]=1と迷路自体を塗りつぶしていくのがミソで、これが再帰を停止させるトリガーとなっている。
ちなみに、迷路自体を潰すことが許されていないのならば、事前にコピーしておくか、その塗りつぶした領域をどこかに記憶しておく必要がある。一例をこれまた擬似コードで示せば
W(x,y,map s):-if(!a(x,y) && !s.exist{x,y})
s{x,y}=1,1+W(x-1,y,s)+W(x+1,y,s)+W(x,y-1,s)+W(x,y+1,s) else 0.
のようになる。(上記プログラム中のmapはC++で言うところのstd::mapだと思ってください)
次に、非再帰版である。再帰とは、言うまでも関数が自分自身の関数を呼び出すことである。初心者にとって、そんなことをして、ローカル変数が破壊されたりしないのか、という疑問もあるだろうが、ローカル変数はスタック上に確保されているので、問題は無いのである。
つまり、再帰から非再帰へは本来、仮想スタックを導入してローカル変数と関数呼び出し履歴をその仮想スタックを使って実現すれば良いだけだ。すなわち、再帰型から非再帰型へは仮想スタックさえあれば自動的に変換できるものである。
よって、非再帰版は再帰版から機械的に変換されたような(等価な)プログラムでなければおかしい。非再帰版を書くのに際して、まったく別のアルゴリズムを持ち出したのでは何をやっているのかわからない。(非再帰形に変換したあとにさらなる速度的なチューンをするというのはもちろんわからなくはないのだが、再帰版が本解答のように書けているのに非再帰版として計算オーダーがO(N^4)になるようなプログラムを書くのはちょっと違うのではないかと言う気がする)
(つづく)
