FizzBuzzというニッチな市場*1において更にニッチな「剰余を使わない」分野ではあるものの、どうも需要があるようなので*2書いておく。
ひとまず既存ネタから幾つか再録して解説する。それから新作を出そうと思う。
既存ネタ：「事前に答えを用意しておく」アルゴリズム
最初に剰余無しのFizzBuzzを書いたのは id:eel3:20100531:1275307408 の/bin/sh（シェルスクリプト）編だ。
/bin/shによるシェルスクリプトでは剰余演算に expr(1) を使うしかないのだが、expr(1) はシェルの組み込みコマンドではなく外部コマンドである為、実行する度にプロセスが生成される。
これがWindowsだとアンチウイルスソフトの類がプロセスの生成を監視していたりする訳で、その結果としてプロセス生成の時間的コストが高くなってしまう。つまり毎回 expr(1) を呼び出すと無茶苦茶遅いFizzBuzzになってしまうのだ。
そこで expr(1) を使わず且つ極力シェル組み込みのコマンドを使うように頑張った結果、こんなFizzBuzzが出来上がった。
#!/bin/sh FIZVAL=`seq -s ' ' 3 3 100` isfizz() { for i in $FIZVAL; do if [ $i = $1 ]; then FIZVAL=`echo $FIZVAL | sed -e 's/^[0-9]*[ ]*//'` return 0 fi break done return 1 } BUZVAL=`seq -s ' ' 5 5 100` isbuzz() { for i in $BUZVAL; do if [ $i = $1 ]; then BUZVAL=`echo $BUZVAL | sed -e 's/^[0-9]*[ ]*//'` return 0 fi break done return 1 } isfizbuz() { for i in $BUZVAL; do if [ $i = $1 ]; then for j in $FIZVAL; do if [ $j = $1 ]; then FIZVAL=`echo $FIZVAL | sed -e 's/^[0-9]*[ ]*//'` BUZVAL=`echo $BUZVAL | sed -e 's/^[0-9]*[ ]*//'` return 0 fi break done fi break done return 1 } pfizbuz() { if isfizbuz $1; then echo FizzBuzz elif isfizz $1; then echo Fizz elif isbuzz $1; then echo Buzz else echo $1 fi } for i in `seq 1 100`; do pfizbuz $i done
ここで考え出した方法は「事前に答えを用意しておく」とでもいうべき発想に基づくものだ。この後に書いた剰余無しFizzBuzzも同じようなアルゴリズムだったりする。
例えば id:eel3:20111031:1319989854 のbash編で書いた以下のFizzBuzzは、上記の方法をよりスッキリさせた実装だと言える。
#!/bin/bash readonly MAXVAL=100 eval " pfizbuz() { case \$1 in `seq -s " | " 15 15 $MAXVAL` ) echo FizzBuzz ;; `seq -s " | " 3 3 $MAXVAL` ) echo Fizz ;; `seq -s " | " 5 5 $MAXVAL` ) echo Buzz ;; * ) echo \$1 esac } for i in {1..$MAXVAL}; do pfizbuz \$i; done "
ちなみにこのアルゴリズム、多分データ量が増えると無茶苦茶遅くなるはず。/bin/shで書いたパターンでは頻繁に文字列操作（とそれに伴うメモリ操作）が発生する可能性がある。bashで書いたパターンではパターンマッチングに古いパターン（もう2度と一致することがないパターン）が残ってしまう為、毎回膨大な数のパターンとのマッチングが発生する。100回程度ならともかく10000回のオーダーでは極端に遅くなるだろう。
既存ネタ：言語機能的に剰余無しでいけるもの
使用する言語によっては手軽に剰余無しでFizzBuzzできる言語機能を持っていたりする。最も顕著なのが id:eel3:20110924:1316791928 のmake編だろう。
# fizzbuzz2.mak # Ubuntu 8.04.4 LTS (server) GNU Make 3.81-3build1 MAXVAL ?= 100 all: $(shell seq 1 1 $(MAXVAL)) $(shell seq 3 3 $(MAXVAL)): @echo 'Fizz' $(shell seq 5 5 $(MAXVAL)): @echo 'Buzz' $(shell seq 15 15 $(MAXVAL)): @echo 'FizzBuzz' .DEFAULT: @echo $@
gmake（GNU make）用の実装。実行する際は標準エラーを読み捨てること。
make編で書いたFizzBuzzは全て剰余演算を使っていない。というか剰余を使う方が面倒ではないだろうか？ ついでに言えばifやswitchなどの条件判定の構文もfor文のようなループ構文も使用していない。まあmakeですから。
Fortranも充実した配列操作機能のおかげで剰余無しでFizzBuzzできる。id:eel3:20111008:1318049202 のFortran 90〜95編より。
program fizzbuzz implicit none integer i integer :: tmp(100) = (/ (i, i = 1, 100) /) tmp( 3:size(tmp): 3) = -1 tmp( 5:size(tmp): 5) = -2 tmp(15:size(tmp):15) = -3 do i = 1, size(tmp) call pfizbuz(tmp(i)) end do contains subroutine pfizbuz(n) integer, intent(in) :: n select case (n) case (-1) print '(A)', 'Fizz' case (-2) print '(A)', 'Buzz' case (-3) print '(A)', 'FizzBuzz' case default print '(I0)', n end select end subroutine pfizbuz end program fizzbuzz
Fortranの仕様で1つの配列に複数のデータ型を含めることができないのだが、もしそれが可能で且つデータ型を気にせずにprintできるのなら、サブルーチンpfizbuzのようなまどろっこしい工夫が不要になってコードがスッキリするように思う。
新作ネタ：恐らく真っ当なアルゴリズム
剰余を使わないFizzBuzzのアルゴリズムは他にも幾つか考えられるが、真っ当な方法としては「3の倍数や5の倍数を判定する為のカウンタを別途用意する」というものが考えられる。
#!/usr/bin/ruby -w $fizz = 0 $buzz = 0 def fizzbuzz(n) val = '' $fizz = $fizz.next if $fizz == 3 val << 'Fizz' $fizz = 0 end $buzz = $buzz.next if $buzz == 5 val << 'Buzz' $buzz = 0 end val == '' ? n : val end (1..100).each {|n| puts fizzbuzz(n) }
この方法は「固定配列でリングバッファを作ったけど剰余演算でインデックスを計算したくない。だけど大きさが2のべき乗じゃないorz」という時に仕方なくif文を使う時の方法に似ている*3。
カウンタではなく判定値を用意する方法もある。
#!/usr/bin/ruby -w $fizz = 3 $buzz = 5 def fizzbuzz(n) val = '' if n == $fizz val << 'Fizz' $fizz += 3 end if n == $buzz val << 'Buzz' $buzz += 5 end val == '' ? n : val end (1..100).each {|n| puts fizzbuzz(n) }
アルゴリズムはカウンタを用意する方法と異なるが、この方法に至る発想自体は両者とも似通っているように思う。
ちなみに上記2つの実装は共に「1から開始する」という暗黙の前提がある。
新作ネタ：アフォコード
まあしかし真っ当に剰余無しでFizzBuzzしていても面白くないので一ひねりしてみた。
#!/usr/bin/ruby -w $fizzmagic = ['3' ,'6', '9', '2', '5', '8', '1', '4', '7', '0'] $buzzmagic = ['5', '0'] def fizzbuzz(s) val = '' [ {magic: $fizzmagic, value: 'Fizz'}, {magic: $buzzmagic, value: 'Buzz'} ].each do |prm| if s[-1] == prm[:magic][0] val << prm[:value] prm[:magic].rotate! end end val == '' ? s : val end (1..100).each {|n| puts fizzbuzz(n.to_s) }
何というか、うん、アフォコードだなあ。コード自体は比較的シンプルだけど、アルゴリズム自体が真っ当とは言えない。
