逆FizzBuzz問題をTrieでトライ

なにやら巷で逆FizzBuzz(Inverse FizzBuzz)問題というのが流行ってるらしい。

Shipper: すみませんが問題をもう一度教えてもらえますか？
Google: あるリストが与えられたときに、FizzBuzzを実行するとそのリストを出力するような最短の連続数列を求めよ。

逆FizzBuzz問題 (Inverse FizzBuzz) - 猫とC#について書くmatarilloの雑記

「ここまで短く書けるよ！」という向きは他でもいろいろとやられているのでよそに譲るとして、ここではTrie(トライ)を使った方法でやってみた。

こんな考え方

Fizz, Buzz, FizzBuzzの出現の仕方には周期性があって、3つの並びとして許されるのは「その周期のうちのどこから始めるか」という7パターンのバリエーションしかない。


なので、その7パターンに対してTrieを作ってやって、並びを先頭から調べていけば、7つのパターンのうちのどのパターンかが判別できる。


あとは、並びを末尾まで調べて、許されない順序でFizz, Buzz, FizzBuzzが並んでいないかを調べればいい。任意の長さの並びを調べるためには、上の図で緑色で示したノードの先にも無限に伸びたTrieが必要になるので、今回は遅延評価で無限に伸ばせるようなTrieを作った。

コード

(ns inverse-fizzbuzz
  (:refer-clojure :exclude [range extend])
  (:use [clojure.test :only [deftest are]]))

(defprotocol Node
  (range [this])
  (children [this]))

(extend-type clojure.lang.PersistentVector
  Node
  (range [this] (first this))
  (children [this] (second this)))

(defn min-next [word n]
  (let [m ({:fizz 3, :buzz 5, :fizzbuzz 15} word)]
    (* m (+ 1 (quot n m)))))

(defn extend [[word & words] start end]
  (reify Node
    (range [this] [start end])
    (children [this] {word (extend words start (min-next word end))})))

(def trie
  (let [words (cycle [:fizz :buzz :fizz :fizz :buzz :fizz :fizzbuzz])]
    [nil {:fizz [[3 3] {:fizz (extend (nthrest words 4) 6 9)
                        :buzz [[9 10] {:fizz [[3 6] {:fizz (extend (nthrest words 4) 3 9)
                                                     :fizzbuzz (extend words 9 15)}]}]
                        :fizzbuzz (extend words 12 15)}]
          :buzz [[5 5] {:fizz [[5 6] {:fizz (extend (nthrest words 4) 5 9)
                                      :fizzbuzz (extend words 10 15)}]}]
          :fizzbuzz (extend words 15 15)}]))

(defn solve
  ([words] (solve words trie))
  ([[word & words' :as words] trie]
   (if (empty? words)
     (range trie)
     (when-let [trie' ((children trie) word)]
       (recur words' trie')))))

(deftest test-solve
  (are [x y] (= (solve x) y)
    [:fizz] [3 3]
    [:fizz :buzz] [9 10]
    [:buzz :fizz :fizz] [5 9]
    [:fizz :fizz :buzz] [6 10]
    [:fizzbuzz :fizz] [15 18]))

おわりに

他と比べるとコードが長いのがアレだけど、Trieを使ってるので

  • 入力のリストを1回舐めれば結果が出せる
  • 変な順序の入力は即座に弾くことができる

あたりが利点になるかなぁと思う。