読者です 読者をやめる 読者になる 読者になる

迷路を解くプログラムをネットで見つけた

Re: 人材獲得作戦・4 試験問題ほか - まめめも
こんなブログ記事を見つけました。Ruby で迷路を解くプログラムです。僕の能力ではパット見なにが書いてあるかわからないので、勉強のために勝手にほぐしてみました。

迷路はこれ。input.txt

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

結果はこれ。ruby solve_maze.rb input.txt

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


元のコードはたったこれだけ。コピペです。solve_maze.rb

c=""+b=$<.read
x=b.index"G"
$w=b.index"
"
z=b.tr!"SG","4 "
b=b.gsub(/ (.{#$w}\d)/m,'a\1').gsub(/ (\d)/,'b\1').gsub(/(\d) /,'\1c').gsub(/(\d.{#$w}) /m,'\1d').tr"a-d","0-3"until" "!=b[x,1]
c[x]=?$until ?S==c[x+=[$w+1,1,-1,-$w-1][b[x,1].to_i]]
puts c.gsub /\d/,' '

圧縮されていて、これはむずかしいですね。以下は多少整理したもの。ここで、変数 b, c は String、変数 x, w は Integer です。

c = "" + (b = ARGF.read)  #cは回答 bは入力された迷路
x = b.index("G")          #ゴールの位置
w = b.index("\n")         #一行の文字数
b.tr!("SG","4 ")          #スタートを"4"に、ゴールを空白にする
until " " != b[x, 1]      #ゴールの位置が空白でなくなるまで繰り返す
  b = b.gsub(/ (.{#{w}}\d)/m, 'a\1').gsub(/ (\d)/, 'b\1').gsub(/(\d) /, '\1c').gsub(/(\d.{#{w}}) /m, '\1d' ).tr("a-d","0-3")
end
until "S" == c[ x += [w + 1, 1, -1, -w - 1][b[x, 1].to_i] ]    #[下, 右, 左, 上]
  c[x] = "$"
end
puts c.gsub(/\d/, ' ')

これでも自分にはむずかしい。それから、疑問符+一文字は、一文字の文字列リテラルと同じなのですね。つまり、?A"A" は同じことです(参照)。知らなかったなあ。また、正規表現リテラルの中に #{変数} があった場合、もちろん変数が式展開されますが、それがグローバル変数の場合は括弧が省略できるようです。

最初の until ループ。
gsub(/ (.{#{w}}\d)/m, 'a\1') というのは、空白の真下に数字があれば、その空白を "a" に置き換えるということですね(参照)。その次の gsub は、空白の右に数字があれば、空白を "b" に置き換えると。あとは同じで、数字が空白の左ならば、上ならばそれぞれ "c" "d" にすると。で、最後に tr で a から d を 0 から 3 に置き換える。
これを繰り返し、ゴールに着けばお終い。ちなみに下のように数字が入る。

**************************
*4*0*00222222222222222222*
*3*0*02*32*************32*
*3*002*1322************32*
*3222*1132222222222222222*
**************3***********
*111111111111132222222222*
**3***********************
*132222*002222222222222  *
*13*322222***********3*  *
*1322*32222222******* *  *
*1322222*3222222222222   *
**************************

次の until ループ。
ゴールから数字を辿って、最短距離で("$" で道を作りながら)スタートまで行く。スタートには 4 の数字が入っているので、until の条件が nil になってお終い。

最後に解いた迷路を puts で出力。

なるほど、上手くできてますねえ。すごい。