逆FizzBuzz問題 (Inverse FizzBuzz)

inverse-fizz-buzz.clj

(require '[clojure.test :refer :all])

;; fizz-buzz
;; 連続整数列をリストとして与えると各要素に対して
;; 3 の倍数は "fizz" を
;; 5 の倍数は "buzz" を
;; 3 と 5 の両方の倍数の場合は "fizzbuzz" を出力し,
;; それ以外は何も出力しない, という法則で出力される文字列の順序集合を
;; リストとして返す.
(defn fizz-buzz [coll]
  (letfn [(is-fizz-buzz? [x] (or (zero? (mod x 3)) (zero? (mod x 5))))
          (to-fizz-buzz [x] (cond (zero? (mod x 15)) "fizzbuzz"
                                  (zero? (mod x  5)) "buzz"
                                  (zero? (mod x  3)) "fizz"))]
    (for [x coll :when (is-fizz-buzz? x)] (to-fizz-buzz x))))

(deftest test-fizz-buzz
  (is (= (fizz-buzz (range 1 101))
         '("fizz" "buzz" "fizz" "fizz" "buzz" "fizz" "fizzbuzz"
           "fizz" "buzz" "fizz" "fizz" "buzz" "fizz" "fizzbuzz"
           "fizz" "buzz" "fizz" "fizz" "buzz" "fizz" "fizzbuzz"
           "fizz" "buzz" "fizz" "fizz" "buzz" "fizz" "fizzbuzz"
           "fizz" "buzz" "fizz" "fizz" "buzz" "fizz" "fizzbuzz"
           "fizz" "buzz" "fizz" "fizz" "buzz" "fizz" "fizzbuzz"
           "fizz" "buzz" "fizz" "fizz" "buzz"))))

;; inverse-fizz-buzz
;; 要素 "fizz", "buzz" および "fizzbuzz" からなるリストを与えると
;; fizz-buzz を実行した時にそのリストを出力するようなリストのうち
;; 最短で且つ最も小さな要素から始まる連続した整数からなるリストを返す.
;; 与えられたリストが fizz-buzz の出力に成り得ない場合は nil を返す.
(defn inverse-fizz-buzz [coll]
  (let [n (count coll) ; 与えられたリストの長さを n としておく
        ;; candidates
        ;;   与えられたリストが fizz-buzz の出力であり得る場合
        ;;   それを出力する整数列になりえるものの開始整数 s と
        ;;   長さ l のペアのリストを得る.
        ;;   fizz-buzz の出力であり得ない場合, 空リスト.
        candidates
          (for [;; 0 以上 7 未満の整数 offset のいずれかに対して
                ;; '("fizzbuzz" "fizz" "buzz" "fizz" "fizz" "buzz" "fizz")
                ;; を繰り返したリストの先頭から offset 個の要素を
                ;; 捨てたリストの先頭から coll の長さ n だけ取り出したリスト
                ;; が coll と一致すれば
                ;; それらは fizz-buzz の出力になりうる.
                ;; 条件を満たす offset は複数あり得るので全て候補とする.
                offset (range 7)
                :when (= coll (take n (drop offset (cycle
                  '("fizzbuzz" "fizz" "buzz" "fizz" "fizz" "buzz" "fizz")))))]
             (let [;; offset に対して, 与えられた出力を生成する整数列の
                   ;; 開始整数のうち 0 以上 14 以下の範囲で最大のものを
                   ;; s とする
                   s (nth '(0 3 5 6 9 10 12) offset)
                   ;; offset に対して, 与えられた出力を生成する整数列の
                   ;; 最小の長さを l とする
                   l (-
                       (+ 
                         ;; offset に対して, 与えられた出力を生成する整数列の
                         ;; 最後の整数のうち 0 以上 14 以下の範囲で最小のもの
                         ;; は
                         (nth '(0 3 5 6 9 10 12) (mod (- (+ n offset) 1) 7))
                         ;; である. これに
                         (* 15 (quot (- (+ n offset) 1) 7))
                         ;; を加えると, 上記のように s を選んだときの
                         ;; 最後の整数として最小のものになる.
                         ;; 数列の長さを与えるためさらに 1 を足して
                         ;; s を引く
                         1) s)
                 ]
               ;; 開始整数候補 s と, それに対して求めた最小の長さ l を
               ;; ペアにして返す.
               ;; ただし s は 1 以上 15以下に変換する.
               [(if (= s 0) 15 s) l]))]
    (if (seq candidates)
        ;; 候補がある場合
        (let [;; minl
              ;; 開始整数 s と長さ l のペアとして与えられる候補のリストから
              ;; l の最小値を求む
              minl (apply min (map (fn [[s l]] l) candidates))
              ;; 長さが minl である候補のうち最初のものから
              ;; あらためて開始整数 s と長さ l を取り出す.
              [s l] (first (filter (fn [[s l]] (= l minl)) candidates))]
          ;; s で始まる長さ l の整数列を返す
          (range s (+ s l)))
        ;; 候補が無い場合は nil を返す
        )))

(deftest test-inverse-fizz-buzz
  (is (= (inverse-fizz-buzz '("fizz")) '(3)))
  (is (= (inverse-fizz-buzz '("buzz")) '(5)))
  (is (= (inverse-fizz-buzz '("fizz" "buzz")) '(9 10)))
  (is (= (inverse-fizz-buzz '("buzz" "fizz")) '(5 6)))
  (is (= (inverse-fizz-buzz '("fizz" "buzz" "fizz")) '(3 4 5 6)))
  (is (= (inverse-fizz-buzz '("fizz" "fizz")) '(6 7 8 9)))
  (is (= (inverse-fizz-buzz '("fizz" "fizz" "buzz")) '(6 7 8 9 10)))
  (is (= (inverse-fizz-buzz '("buzz" "fizz" "buzz")) nil))
  (is (= (inverse-fizz-buzz '("fizzbuzz" "fizz")) '(15 16 17 18))))

逆FizzBuzz問題 (Inverse FizzBuzz)
というエントリを読み, 自分なりに解いてみました. in Clojure