pla.log

Vim Advent Calendarがなかなか電子書籍化しないのは、もしかして私がanimated gifなんか貼ったせいなんじゃないかと微かに罪悪感を感じる今日この頃の plaster です。 ごぶさたでした。

さて、 ちょっと前に話題になった「『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！」というすばらしい動画があります。

おねえさんが命をかけて組み合わせ爆発のすごさをつたえてくれる壮絶なストーリーなのですが、 おねえさんのコンピュータを作ってみた方までいらっしゃって、ほんとにみなさんすごいですね。

ところで、この記事を読んでいて、ひとつ気づいたことがありました。

小さいなサイズなら単純な深さ優先検索(DFS)で解けます

なるほど……たしかに解けますね。Vimで。

レギュレーション

• たとえば 2×2 の道があったら

  #####
  #   #
  #   #
  #  G#
  #####
  0

  こういうテキストで表すことにします。ゴールは「G」にします。
  • 3×3 の場合は

    ######
    #    #
    #    #
    #    #
    #   G#
    ######
    0

    となります。
• 空白は歩ける場所で、「#」が通れない、壁です。空白のうち、いちばん左上にあるところがスタートです。
  • 見た目はちょっとちがいますが、こう決めると、もとの道とまったく同じグラフになりますよね。
• 一番下に書かれてる「0」は大体想像つくかと思いますが、ここに答えがでてきます。

みんな、Vimおねえさんといっしょに数えてみよう！

まずバッファに次のようなテキストを1行、書いておきます。

• yl@=@0=="G"?"maGD\"=@-+1\rP`a":@0==" "?"r.l@1hj@1kh@1lk@1jr ":""

この行でddして、スタート地点にカーソルを持って行って、@1すれば Vimおねえさんががんばって数えてくれます。

以下に、Vimおねえさんの勇姿を貼っておきます。

この通り、184だね！

たった1行で解けるVimおねえさん、すご〜い！

みんなのVimでも、かぞえてみよう！

同じように、あなたのお手元のVimでももちろん、数えることができます。ぜひ試してみましょう。

コピペするのもめんどいひとのために、すぐ試せるファイルを用意しておきました。

まずはこのファイルをダウンロードして、おもむろにお手元のVimで開いて、1行目にカーソルがある状態で ddjl@1 すれば 3×3 の道順の数が出てきます。

地形を適当にいじれば、4×4 も数えられますし、3×5 みたいな変則的な場合にも対応できます。スタートとゴールの場所を左上や右下以外にしても大丈夫です。 ただし、全体を「#」で囲うことと、最下行が「0」なのだけは変えないでくださいね。

補足

• 枝刈りを一切やっていません。「どうあがいてもゴールに辿りつけない」状況がよほど明らかであっても、延々と探索を続けてしまいます。つまり、ほかのひとの大抵の実装より遅いはずです。
• Vimおねえさんに組み合わせ爆発のすごさを教えてもらいたいみんなに残念なお知らせです。この方法で正確に数えられるのは 2,147,483,647 通りまでのようです。つまり、7×7 はむりです……
• それでも、どーしても試したいという皆さんのために、Vimおねえさんロボットが数えてくれる 7×7 のファイルを用意しておきました。使い方は 3×3 のときと同じで、1行目にカーソルがある状態で ddjl@1 するだけです。
  • え、いつまでたっても終わらない？だいじょうぶ、きっとおわります。いつかは。
• 前回のネタとかわりばえしてなくてごめんなさい