Vimで逆FizzBuzz問題を解いてみた

  • Author: MURAOKA Taro
  • Date: 2012/05/20

Vimで逆FizzBuzz問題を解いてみたわけですが、比較的まじめに手を抜いた感じで解説します。

Vimで逆FizzBuzz問題を解いてみました。ソースはコチラ。きっかけと基本的な方針はまっつんさんと同じですが、検索対象とパターンそれぞれを変換しているところが違うので、ちょっと面白いかなと思ったので解説記事を書いておきます。

問題の定義

はじめに逆FizzBuzz問題の定義はこうします。

あるリストが与えられたときに、FizzBuzzを実行するとそのリストを出力するような最短の連続数列を求めよ。

逆FizzBuzz問題 (Inverse FizzBuzz)よりまっつんさんの解では実は太字の部分が守られておらず「最初に発見した連続数列」が求まります。このあたりまっつんさんに問い合わせたところ、彼が採用した方法だと最短を求めるのに無限の時間が掛かるので妥協したとのこと(参照1,参照2)。

なので私の版は「最短の連続数列」がでるようにしました。そのせいでちょっとソースが長くなりました。この長くなった部分をすっきり書く方法があった気がするんですが、すぐには思い出せないのでそのままとしました。

問題の分析

まず、この問題の入力はFizzBuzz列で、出力は数列です。ある数列内に特定のFizzBuzz列があるか探し、その位置を求める典型的な正規表現向けの問題です。検索対象と検索パターンを決めてしまえば、あとは正規表現エンジンが勝手に答えを見つけてくれるはずです。ですから問題はいかに検索対象とパターンを決めるか、その点に絞られます。私は検索対象を「3の倍数をFに、5の倍数をBに、3と5の倍数をZに、それ以外をAに置き換えた数列を文字列化したもの」とし、検索パターンを「FizzBuzz列」を「fizzをF、buzzをB、fizzbuzzをZに変換したVimの正規表現」としました。

検索対象の決定

難しいところがあるとすれば、検索対象となる数列の定義が(一見)自然数列で無限であるところです。無限の数列から任意のパターンにマッチする最小区間を探すのは現実上できません。任意のパターンにマッチする理論上の最小区間の長さ(短さ)が予めわかっていれば別ですが。

しかし待ってください。そもそも無限の数列から探す必要があるのでしょうか? FizzBuzz(3と5の倍数判定)での判定なんですから、最小公約数である15で一周するはずです。試しに1～15の数列を、3の倍数をFに、5の倍数をBに、3と5の倍数をZに、それ以外をAに置き換えてみましょう。

AAFABFAAFBAFAAZ

これを1ユニットとすれば、あとはユニットの繰り返しなわけですから90までの数列はこのコピペで求まります。

AAFABFAAFBAFAAZAAFABFAAFBAFAAZAAFABFAAFBAFAAZAAFABFAAFBAFAAZAAFABFAAFBAFAAZAAFABFAAFBAFAAZ

ここで問題は次のように変わります。実際の検索対象として使う際、いったい何回繰り返せば良いのか? これへの解答は上の数列を眺めていると気がつくでしょう…繰り返すたびにZが増えていますよね。

つまり、検索パターンにZがいくつ含まれているか、入力のFizzBuzz列にfizzbuzzがいくつ含まれているかで、何回繰り返すべきかが決められます。逆に言うと「もともとのFizzBuzz列に1個もfizzbuzzが含まれていないのに1～15の範囲の外を探すのは無駄」と、こういうわけです。正確には「1～14の」というべきですが。

以上を踏まえて検索対象を決めるコードを示すとこうなります。

let s:unit = 'AAFABFAAFBAFAAZ'

function! s:CountFizzbuzz(inList)
  return len(filter(copy(a:inList), 'v:val ==# "fizzbuzz"'))
endfunction

let field = repeat(s:unit, s:CountFizzbuzz(a:inList) + 1)

検索パターンの生成

さて、検索対象が無限ではなくなったのでいよいよ検索パターンの生成です。とは言っても簡単ですね。「fizzをF、buzzをB、fizzbuzzをZに変換したVimの正規表現」を生成します。ただ間に「それ以外」を示すAが入ることに注意しましょう。

実際に変換の例を見たほうが速いでしょう。FizzBuzz列:[ ‘fizz’, ‘buzz’ ]に対して生成される検索パターンはFA*Bです。簡単ですね。

変換部分のソースを抜粋するとこうなります。

let s:map = { 'fizz': 'F', 'buzz': 'B', 'fizzbuzz': 'Z' }

function! s:GetPattern(inList)
   return join(map(copy(a:inList), 'get(s:map, v:val)'), 'A*')
endfunction

let pattern = s:GetPattern(a:inList) 

検索の実行

検索対象とパターンが決まればあとは実行するだけです。例によって該当箇所を抜粋します。

let m = matchstr(field, pattern, 0)

let start = stridx(field, m, 0)
let length = strlen(m)

return [start + 1, start + length]

ここではmatchstrでマッチする文字列を探してから、その開始位置を特定するために再度stridxで検索しています。あとは数列の開始位置と終了位置を作るだけ。

その他

ソースコードのその他の部分は最短パターンを探すための典型的なループと、簡単な自動テスト用のコードです。なので上記のポイントを抑えておけば読むのは難しくないでしょう。

終わりに

まっつんさんと同じく正規表現エンジンに頼っていますが、ほら違うでしょ? そのあたりに面白さを感じてもらえると嬉しいです。