Fizz Buzz 問題
Fizz Buzz 問題はプログラマとしてのベンチマークとして行われることがあるようです。
プログラムのルールは非常に簡単で１から順に数字を表示させ、３の倍数のときは “Fizz” ５の倍数のときは “Buzz” 、そして１５の倍数のときは “FizzBuzz” と表示させます。だいたい１００ほどまで表示させます。
普通にプログラムの手続きを書くとあっけないほど簡単なので、今回は C++ 言語を使い、数値の定義からこの問題を解いてみます。
ソースコードは github にあります。
考え方
まずはゼロがあり、次にイチ、ニ、サンと等間隔で増えていきます。イチがどのぐらいかは本質ではないので、とりあえずゼロの次はイチ、次はニ・・・として考えます。無限にありますが、ゼロからの等間隔な単位量なのでマイナスや少数はありません。
さっそくコードにおこしてみましょう！
struct Null;
template<typename Volume=Null>
struct Number
{
typedef Volume Dec;
typedef Number<Volume> Value;
typedef Number<Number<Volume> > Inc;
};
最初の Null の宣言は、ゼロからイチまでの単位の定義に使いますが、宣言だけして定義はしません。
Volume を与えることによって、まずは Dec が定義できます。与えられた型を取り出すことで、ひとつ前の値とします。つぎの Value はその値そのもので、自分自身の型を別名で定義しているだけになります。最後の Inc により、次の値も定義されています。
再帰により次の値も同じなので無限に存在します。ここで、最初の値の前は未定義なのと、数値のそれぞれの距離は等間隔であることがわかります。今回は最初に現れる数値をゼロとして扱います。
演算
数値の定義は上記だけでおわってしまいますが、 FizzBuzz 問題を解くにはある程度計算できないといけません。 1+2=3 から察するに、演算子は二つの値をとり、合わせたひとつの値を定義します。
template<typename Op1,typename Op2>
struct Add
:public Add<typename Op1::Inc,typename Op2::Dec>{};
template<typename Op1>
struct Add<Op1,Number<Null> >
:public Op1{};
足し算の定義なので引数は二つです。片方の値だけ、もう片方を増やしていけば定義できるので、 Op2 を減らし、 Op1 を増やすことにしました。 Op2 がゼロになったときに、 Op1 がその足し算の定義になります。
解説
手続型でいうところの、 template の行が引数です。特殊化の無い struct の行が switch-case の deault です。特殊化のある struct の行が case です。 public の行により再帰的に同じ関数を定義して、定義を上書きしていきます。
最後に特殊化にマッチさせて、結果を求めます。たとえばイチ足すサンは…
Add<Number<>::Inc,Number<>::Inc::Inc::Inc>; イチ足すサン Add<Number<>::Inc::Inc,Number<>::Inc::Inc::Inc::Dec>; 再帰によりまずは Inc と Dec が増え... Add<Number<>::Inc::Inc::Inc,Number<>::Inc::Inc::Inc::Dec::Dec>; さらに増えて行って... Add<Number<>::Inc::Inc::Inc::Inc,Number<>::Inc::Inc::Inc::Dec::Dec::Dec>; Add<Number<>::Inc::Inc::Inc::Inc,Number<Null> >; Inc と Dec が同じになると特殊化にマッチする。 Add<Number<>::Inc::Inc::Inc::Inc,Number<Null> >::Value; この Value は、その値そのものなので, Number<Number<Number<Number<Number<> > > > >; Value はこう定義されています
式の評価は Add を定義したときに行われますが、 Value を評価しないと値は定義されないままです。
ひき算はたし算とほぼ同じようにできますが、 Fizz Buzz 問題には使わないので省略します。
かけ算
template<typename Op1,typename Op2,typename Count=Number<Null> >
struct Mul
:public Mul<Op1,typename Op2::Dec,Add<Count,Op1> >{};
template<typename Op1,typename Count>
struct Mul<Op1,Number<Null>,Count>
:public Count{};
結果用に一つ引数を増やし、たし算と同じ要領で片方を減らしつつ、結果を増やしていきます。これで大きな数も表現しやすくなりました。
わり算
まずあまりを出すのが簡単なので、簡単なほうから手を付けます。あまりのカウントを増やしていき、わる数になったらゼロに戻します。これをわられる数がゼロになるまで行います。
template<typename Op1,typename Op2,typename Count=Number<> >
struct Rem
:public Rem<typename Op1::Dec,Op2,typename Count::Inc>{};
template<typename Op1,typename Op2>
struct Rem<Op1,Op2,Op2 >
:public Rem<Op1,Op2>{};
template<typename Op2,typename Count>
struct Rem<Number<>,Op2,Count>
:public Count{};
template<typename Op2>
struct Rem<Number<Null>,Op2,Op2>
:public Number<>{};
わる数 (Op2) は一定にします。ひとつめの特殊化はカウントがわる数に達したときはゼロ（初期値）からやり直します。ふたつめの特殊化でわり切れずにあまりが出たときの定義をします。最後にわり切れたときのゼロを定義をします。わり算は、一つ目の特殊化にマッチしたときに、さらにカウントを増やすようにするだけなので省略します。
数字の定義
ここまでで演算もおおむねできるようになったので、今度は十進数の定義をします。ここまでの定義では、値の概念だけの抽象的なものです。
とりあえず１０までの数値を扱いやすいように定数とします。
typedef Number<> Zero; typedef Zero::Inc One; typedef One::Inc Two; typedef Two::Inc Three; typedef Three::Inc Four; typedef Four::Inc Five; typedef Five::Inc Six; typedef Six::Inc Seven; typedef Seven::Inc Eight; typedef Eight::Inc Nine; typedef Nine::Inc Ten;
表示
文字を表示させるために stdio が要ります。引数の数値はいままでどおりですが、 printf は副作用を及ぼすのでメソッドとしなければなりません。
template<typename Value>struct Print;
#include <stdio.h>
template<>struct Print<Zero >{static void print(){printf("0");}};
template<>struct Print<One >{static void print(){printf("1");}};
template<>struct Print<Two >{static void print(){printf("2");}};
template<>struct Print<Three>{static void print(){printf("3");}};
template<>struct Print<Four >{static void print(){printf("4");}};
template<>struct Print<Five >{static void print(){printf("5");}};
template<>struct Print<Six >{static void print(){printf("6");}};
template<>struct Print<Seven>{static void print(){printf("7");}};
template<>struct Print<Eight>{static void print(){printf("8");}};
template<>struct Print<Nine >{static void print(){printf("9");}};
一桁出力。文字を出力することによって、はじめて人間が理解できるかたちになります。
template<typename Value,typename Base=One>
struct PrintNumber{
static void print(){
PrintNumber<Div<Value,Ten>::Value,Base::Inc>::print();
Print<Rem<Value,Ten>::Value >::print();
}
};
十進数なので１０以上の値はニ桁にして表示させなければなりません。ひとつ上の桁と、その桁を再帰的に表示させます。一桁のゼロだけは特殊化し、”0″ を表示させます。特殊化は省略。
Fizz Buzz 定義
やっと Fizz Buzz の定義に入ります。カウントを減らしながら再帰させ、３で割ったあまり、５で割ったあまりをそれぞれ引数に与えます。それぞれのあまりがゼロの時を特殊化しつつ、カウントゼロで再帰を止めます。再帰が止まると手続が動作し、１から順に表示されていきます。
template<typename Count,typename Fizz=Rem<Count,Three>::Value,typename Buzz=Rem<Count,Five>::Value >
struct FizzBuzz{
static void count(){
FizzBuzz<Count::Dec>::count();
PrintNumber<Count>::print();
printf("\n");
}
};
template<typename Count>
struct FizzBuzz<Count,Zero,Zero>{
static void count(){
FizzBuzz<Count::Dec>::count();
printf("FizzBuzz\n");
}
};
template<typename Count,typename Buzz>
struct FizzBuzz<Count,Zero,Buzz>{
static void count(){
FizzBuzz<Count::Dec>::count();
printf("Fizz\n");
}
};
template<typename Count,typename Fizz>
struct FizzBuzz<Count,Fizz,Zero>{
static void count(){
FizzBuzz<Count::Dec>::count();
printf("Buzz\n");
}
};
template<>struct FizzBuzz<Zero,Zero,Zero>{static void count(){}};
１００までやれば十分だと思われるので、１０かける１０を与えて、呼び出します。
void main()
{
FizzBuzz<Mul<Ten,Ten>::Value>::count();
}
まとめ
- 四則演算やビットシフトなどの演算子は一切使わない
- 変数は使わない。文字列でない定数も使わない
- 組み込み型による演算を行っていないので、表示コストを除けば、このプログラムの実行時間はゼロ
- 最適化しなくても、この Number 型は実行時のコストがゼロ
- コンパイラの性能によっては大きな値も表現可能
- 数値とは、ゼロから等間隔で並んでる何かを表すもの。一般的には自然数というらしく、定義は非常にシンプル
- 十進数での表示は難しい