逆FizzBuzz

http://www.jasq.org/2/post/2012/05/inverse-fizzbuzz.html
http://d.hatena.ne.jp/matarillo/20120515/p1
より。

入力を正規表現に変換してしまえばとても簡単になる。
https://gist.github.com/2708823

けれど、cl-ppcreだと上記のコードのままじゃちょっと長めの入力を渡すと死んでしまう。
バックトラックが爆発してるんだろうけど、正しい書き方あるのかな。

CL-USER(10): (defun test (n) (time (inverse-fizzbuzz (loop repeat n append '(fizz buzz fizz fizz buzz fizz fizzbuzz)))))

TEST
CL-USER(11): (test 5)

Evaluation took:
  0.091 seconds of real time
  0.093601 seconds of total run time (0.093601 user, 0.000000 system)
  103.30% CPU
  225,231,803 processor cycles
  65,520 bytes consed
  
(3 75)
CL-USER(12): (test 6)

Evaluation took:
  8.923 seconds of real time
  8.907657 seconds of total run time (8.907657 user, 0.000000 system)
  99.83% CPU
  22,234,078,381 processor cycles
  98,296 bytes consed
  
(3 90)
CL-USER(13): (test 7)
;; 返って来ない…

7個以上渡された時は最初の7個の繰り返しになってるか確認してから最初の7個をチェック、で終点は入力の長さから計算って形にしないといけなさそう。

ちなみにxyzzyの正規表現検索だと全く問題なし。

user> (defun scan-all (re str &optional (start 0))
	(let ((s (string-match re str start)))
	  (when s (cons (list (1+ s) (match-end 0)) (scan-all re str (1+ s))))))

scan-all
user> (defun inverse-fizzbuzz (fb)
	(let ((re (format nil "~{~A~^_*?~}" (mapcar #'(lambda (s) (case s (fizz "f") (buzz "b") (t "z"))) fb)))
	      (pattern (format nil "~V@{__f_bf__fb_f__z~}" (+ 2 (floor (length fb) 7)) t)))
	  (car (sort (scan-all re pattern) #'> :key (lambda (p) (apply #'- p))))))
inverse-fizzbuzz
user> (defun test (n)
	(inverse-fizzbuzz
	 (loop repeat n append '(fizz buzz fizz fizz buzz fizz fizzbuzz))))

test
user> :time (test 5)
(3 75)
----------
0.000 sec.
user> :time (test 10)
(3 150)
----------
0.000 sec.
user> :time (test 1000)
(3 15000)
----------
0.484 sec.

7000個渡しても大丈夫。