FizzBuzz 問題とは
基礎的なプログラミング能力が身に付いているかどうかを確認する試金石として,次のような問題が知られている。
1 から 100 までの数を順に表示するプログラムを作れ。
ただし,3 の倍数は数字の代わりに Fizz,5 の倍数は Buzz,3 と 5 の両方の倍数のときは FizzBuzz と出力するものとする。
これはもともと,複数人が集まった時に順に数字を言い合う遊びとして知られるものだそうで,2007 年に Imran Ghory という人がブログでブログラマ志望者を篩い分けるのにちょうどよい課題ではないかと提案したのが,プログラミングの世界における FizzBuzz 問題の起こりである。(後述の「起源」の項目を参照のこと。)
この問題を自力で解きたいという方は,以下の「出会い」と「起源」までは目を通していただいても構いませんが,それ以降は読まないことをお勧めいたします。
なお,通常は 1 から唱え始めるもののようだが,0 から始めるとすれば,それは 15 の倍数なのだから,ゲーム名の「FizzBuzz!」を叫んでゲームを開始することになるので,trivial かつ「ど」minor な改変として,「0 から 100 までの数」にすることを提案したい。
FizzBuzz 問題との出会い
私が初めて FizzBuzz 問題というのに触れたのは 10 年ほど前かなと思って自分のブログ記事を検索してみたら,
7 年前の秋のことであった。
そこには,十進 BASIC で作った解答が載せてある。
今回はそれをオワコン(号泣)の CASL II で書いてみようというわけである。
なお,十進 BASIC の方は保守が非常に行き届いており,久々に
公式サイトを覗いてみると,Mac や Linux (Intel 系?),Raspberry Pi なんていう変わり種にまで移植されていて,オラびっくりこいただよ。
極めつけは Chromebook かな。ちょうど一年前に Chromebook を購入して
(使い辛いので全く使っていないが)試した覚えがある。私が買った機種は Arm 系の CPU だということを突き止めるのに小一時間費やしたが,無事に十進 BASIC が稼働して感激したのは懐かしい思い出である。もっとも,Chomebook では設定画面で開発者モードとかそんな感じのをオンにすれば Linux が使えるので,十進 BASIC が Linux に移植された時点で Chromebook もオマケで参加に入ったということであろう。
余談ついでに,CPU の違いは OS が吸収してくれるものではないかと思っていたのだが,そういうものでもないらしい。一番人間に近い側のアプリにおいて OS や CPU の違いを意識せずに済むように,OS が中間管理職よろしく,ヒトとハードウェアの間を取り持つ「被せ物」になっているという私の素朴な認識は正しくないということなのだろう。
ところで,7 年前ならばまだ CASL II が現役でブイブイ言わせていた時代(今となっては晩年と言い表すべきか)なので,そのときに CASL II で FIzzBuzz に挑戦するのが妥当だったであろう。当時の記憶は全く残っていないが,11 月 1 日付けのブログ記事であることから察するに,その季節は例年後期の半ばの大学祭休みで体調を崩すので,そんな中でちょこっとだけ遊んでみたといった程度であったろう。しかるに,ろくにマスターしていないアセンブラ言語なんぞを学び直そうという気力はなかったに違いない。
FizzBuzz 問題の起源
ついでながら,7 年前に参照した Jeff Atwood 氏のブログ記事
"Why Can't Programmers..Program?" の日本語訳が読める日本語で書かれたブログはいくつか健在である。この記事を書いている現在,日本語版の Wikipedia の Fizz Buzz の項目には,FizzBuzz 問題の解答となるソースコードを書けるかどうかでプログラマ志望者を選別する面接手法を Jeff Atwood 氏のブログ記事に由来すると記しているが,それは誤りである。
上に引用した "Why Can't ..." の記事において,Atwood 氏は Reginald Braithwaite のブログ記事
"Don't Overthink FizzBuzz"(「FizzBuzz 問題について深刻に考え込まないようにね」といった意味合いだろうか)を読んだ感想から始めている。
その引用元である Reginald Braithwaite 氏のブログ記事は,Imran Ghory 氏のブログ記事から,自身のジャグリングに関するブログ記事をたどってきた人たちがいることに気付いた,という出だしで始まっている。その Imran Ghory 氏のブログ記事は,かつて Imranontech.com というドメイン名のサイトに掲載されていたと見られ,Atwood 氏と Braithwaite 氏はともにそのサイトへのリンクを貼っているが,2024 年 4 月現在,そのドメインは空き家となっている。代わりに
imranghory.org というサイトがあり,そのトップページに,
In 2007 I invented the Fizzbuzz interview question for developer competence.
と記しており,そこに貼られたリンク先には,Fizz Buzz Test というタイトルのまとめ記事(スマホ向けのレイアウト??)があるが,そこで Source として挙げられた元記事 "Using FizzBuzz to Find Developers who Grok Coding" へのリンクは wordpress のブログ記事のように見えるものの,やはり売りに出されている Imran On Tech (imranontech.com) にリダイレクトされてしまうので,現時点で私はこれぞという原典にたどり着けないままでいる。
ただし,Jeff Atwood 氏に FizzBuzz 問題の提唱者を帰している日本語版 Wikipedia の記述は間違っていると判断してよいであろう。それは自称プロオタク (professional geek) の Imran Ghory 氏であると訂正せねばなるまい。なお,とりあえず英語版だけ確認したところ,FizzBuzz 問題の由来に関しては 1 ミリも記述がない。というか,プログラミングにおける FizzBuzz 問題の項目自体に一つも出典が明記されていない。
ところで,FizzBuzz という単語でネット検索をすると様々なプログラミング言語,および,様々な「縛り」を課した下での解答がたくさんヒットする。まさにそのような方法で個別にプログラムを収集することは可能であるが,いろんなプログラミング言語における解答をまとめたサイトがあると面白いかなと思う。先ほど触れた Fizz Buzz Test というサイトはややそれに近い。最近,hello, world プログラムの Wikipedia 記事も読む機会があったが,英語版の方には,サンプルプログラムとして hello, world を挙げている数多くのプログラミング言語の Wikipedia 記事へのリンクリスト (Wikipedia articles containing "Hello, World!" programs) が掲載されているので,それらを覗きに行くだけでもとても楽しいブラウジングができそうである。残念ながら日本語版にはそれがない。手打ちで作成したのだとすると大変だが,そのようなリストを自動生成する方法があるようなら日本語版にも同様のリストを追加したいものである。Wikipedia の書き方のヘルプ項目のうち,リンクの項目を見たとき,「東海大学」のページに対して 4,000 以上のリンクが貼られているなどの話(
Wikipedia: リンクのしすぎで危機状態)が載っている項目に行き着いたことがある。それをどうやって調べるかというと,Wikipedia の各項目のページにある「元リンク」というメニューをクリックすると,その記事にリンクを張っている,Wikipedia 内の他のページの一覧が表示されるのである。それをうまく使えば hello, world プログラム一覧が容易く作成できそうな気はしている。が,それをすぐにどうこうというわけではない。
他に,全く別の記事であからさまな誤り(と思しき記述)が記載されている項目もあるのだが,そちらももう少し調査を詰め次第,訂正するつもりでいる。
CASL II で解答を作る際の困難
本題に戻ろう。
仮想アセンブラ言語 CASL II で Fizz Buzz プログラムを作るのは,なかなか大変である。
Fizz Buzz プログラムというのは,1 から 100 までの数を順に表示するプログラムであるが,3 の倍数で 5 の倍数でないときは Fizz,3 の倍数でなく 5 の倍数のときは Buzz,そして 3 と 5 のどちらの倍数でもあるとき,つまり 15 の倍数のときは FizzBuzz と表示せよ,という条件付きである。
それをどう実現するかを,プログラミング志望者は自分が知っているプログラム言語で,与えられた制限時間内にプログラミングしなければならない,というのが,プログラマ採用面接試験でほどよい課題ではないか,という話である。実際に企業等での採用面接現場においてどのくらいこのテストが行われてきたか,もしくは行われているかはわからないが,何がしかのプログラミング言語の基礎的なことを一通り学んだ後での演習問題としては手ごろであると思う。
その理由として私が考えるのは次の通りである。
- 番号を 1 から 100 までカウントするのに,通常,for 文のような基本的なループ制御が必要となる。
- 番号が 3 の倍数であるかどうかといった判定に,四則演算,特に,ある数がある数の倍数であるかを見分ける方法が必要となる。
- 番号が 3 の倍数であって 5 の倍数でなければ Fizz と表示する,といった,if 文のような基本的な条件分岐制御が必要となる。
- 条件分岐の際に,あるデータが指定された条件を満たしているかどうかの判定が必要となる。
- 結果をモニタ等に出力する,基本的な入出力の方法が必要となる。
かなり細かく分ければこんなところであろうか。
ここで,CASL II というアセンブラ言語において,もっともハードな項目は 5 である。
CASL II では OUT というマクロ命令を使用して標準出力(パソコンなどの画面と考えてほぼ差し支えないが,Windows にしろ Linux や Mac にしろ,実際にはモニタ画面上に表示される「窓」(ウィンドウ)などで結果を表示する,などと述べるのがより正確であろう)に文字列等を表示することができるが,現存するシミュレータの中には OUT 命令をサポートしていないものもあるため,自作プログラムの動作確認があまりお手軽ではない。
そういった環境問題だけでなく,CASL II そのものに由来する大問題が一つある。それは,カウンタ番号を数字として表示するのが一番難しいということである。
実は Fizz だの Buzz だのといった文字列を表示する方が簡単なのである。CASL II では文字定数というものが使えるので,
OUT F3,LEN
F3 DC 'Fizz'
LEN DC 4
のような命令群で,標準出力装置に Fizz という文字列を表示することが可能である。
OUT F3,LEN というのは,F3 というラベルが貼られた番地内のデータを,LEN で指定された文字数分だけ標準出力に出力せよ,という命令であって,表示したい文字列そのものを文字定数という形式で 'Fizz' のようにそのまま記述することが許される。
なお,CASL II(の最終版)ではリテラル(直値,即値。イミディエイト (immadiate) とも呼ばれる)という記述方式が認められているので,それを利用すると,先ほどの 2 つの DC 命令の行を省いて
OUT ='Fizz',=4
のように記述することも可能である。これは,先に示したプログラム(の一部なので,プログラム片とでも称すべきであろうか)において,F3 に Fizz という文字列を,LEN のところに 10 進表示の数 4 を代入したものに相当する。CASL II の仕様では,むしろ逆に後に示した 1 行プログラムの方を先に示した 3 行プログラムに相当するものに変換してアセンブルされるものとなっている(IPA 公式の資料■アセンブラ言語の仕様「2.5 機械語命令」参照)。
ただし,OUT 命令は機械語命令ではなくてマクロ命令のグループに属するため,1 行プログラムのようなリテラルを用いた記述を許すのかどうかはグレーゾーンである。したがって,OUT 命令でリテラル形式を認めるかどうかはシミュレータ作成者の判断に委ねられるというのが私の見解である。
Daytime さん作のシミュレータでは,リテラルを用いた次のような 1 行プログラムがちゃんと通る。
TEST START
OUT ='hello, world',=12
RET
END
ただし,その挙動には 1 つの疑問が残る。
それは,RET 命令を書くべきかどうかである。初め,私は RET は不要だと考えて書かなかったのだが,シミュレータは作業の終わりどころが掴めないらしく,しばらく経つと hello, world を 2 行目,3 行目,・・・,と延々と繰り返し書いていくのである。どうやら無限ループになってしまっているらしい。
どうやら,END 命令はプログラムの終わりを定義するものの,プログラムの実行の停止を意味するものではないらしい。
そういうわけで,実質的にプログラムの実行を停止させるのは RET 命令のようである。これは,このプログラム TEST を実行し終えたよ,ということで,プログラムを終了し OS に制御を戻す印である(仕様の「3. プログラム実行の手引」内の「3.1 OS (4)」)。今後は RET を書くのをサボらないように気を付けたい。
CASL II シミュレータを自作したいと常々思っているものの,そうしないでいる要因の一つは,仕様を隅々まで正しく理解できている自信が全くないところである。少なくとも私には公式の仕様だけを頼りに,その仕様の通りに正しく動作するシミュレータを作ることは無理そうである。
話を戻そう。Fizz だの Buzz だのを出力するだけならお安い御用だ,ということは分かっていただけたのではないかと思う。
問題は,普通の数字である。Fizz Buzz ゲームは,もとは数人で順番に 1 から数字を言っていき,3 の倍数が当たったら Fizz という,といったルールの遊びなので,我々が日常的に使用している 10 進表示で標準出力に表示したい。
ところが,カウンタ変数内の数字は内部的には 16 ビットの 2 進数として扱われているので,それを 10 進表示の数に直すのには少なくとも 2 つの工程が必要となる。
まず,16 ビットの 2 進数を 10 進表示に直す。具体的には,その 2 進数を 10 進数に直したときの,100 の位,10 の位,1 の位の数を読み取る。
そして,その読み取った結果を 10 進数に見える数字の並びで出力する。これはつまり,数字を文字列として扱うことを意味する。
CASL II の OUT 命令で出力できるのは文字列である。それは内部的には各文字に対応する文字符号(文字コード)という 2 進数として扱われる。
CASL II では JIS X 0201 という規格で定められた文字の符号表を用いることになっている。したがって,例えば,3 の倍数でも 5 の倍数でもない「普通の」数 31 を表示させるには,
OUT ='31',=2
のような記述が必要である。これをうっかり
OUT =31,=2
のように書いてしまうと,=31 は 10 進数の 31 に相当する数値,に相当する文字符号とみなされる。
まず,10 進表示の 31 は 16 ビットの 2 進表示で
0000 0000 0001 1111
となる。これを 16 進表示に直すと,CASL II では 16 進数であることを示すのに,冒頭に # を付ける習わしなので,
#001F
となる。この 1 語(=16 ビット)の上位 8 ビットは,OUT 命令においては OS が無視するので 00 であってもなくてもどちらでもよい。
肝心なのは下 8 ビットの 1F の部分であるが,上位の数字が 1 のときは「制御文字」というゾーンに属していて,数字やアルファベット,記号から外れるため,標準出力にはおそらく何も表示されない。
少なくとも,我々が期待する「31」という,3 という数字と 1 という数字の 2 文字からなる文字列は決して表示されないのである。
このようなわけで,2 進数を 10 進数風に変換する手続きと,10 進数として各桁の数字をちゃんと並べた文字列を出力する機構を自前で用意しなければならない,という苦難を無事に乗り越えなければならない。
そんなわけで,CASL II 学習者にとって,この問題は入門コースの卒業試験としてはいささかレベルが高いように感じられる。初級,もしくは中級の試験問題といってよさそうである。
上級コースの試験はさしずめビット列操作であろうか。それは結局,基本情報技術者試験の問題がそれに相当すると言ってよいであろうが。
暫定案
解答のプランのみを記しておく。
2017 年の自分の十進 BASIC による解答と本質的には同じアイデアに基づく。
というか,その記事を書いたことはすっかり忘れていたのに,CASL II のプログラム案を書き上げた今,その記事を読み直してみると,同じ発想に基づいた解答であることに気付いた。中の人が同じであるから当然とも言えるが,無意識に当時考えたことを思い出したのであろう。
1 から 100 まで,カウンタの値を 1 ずつ増やしていくわけだが,そのメインのカウンタだけではなく,次の 2 つの補助的なカウンタを自前で用意しておく。
- 1, 2, 0 を繰り返す,周期 3 のカウンタ,かっこよく言うと,メインカウンタの値を 3 で割った余りに相当する,mod3 カウンタ。
- 1, 2, 3, 4, 0 を繰り返す,周期 5 のカウンタ,名付けて mod5.
ただし,CASL II ではラベル名には英大文字と数字しか使えない(ラベル名の最初の文字は必ず英大文字)。また,CASL II には変数という概念もない。実際に使用するのは汎用レジスタと呼ばれるものであるが,プログラムを作成する際に初めから汎用レジスタのどれをどういった役割のカウンタに使用するか,という割り当てをすると,私はこんがらがってくるので,仮に小文字を用いたラベルの変数をこうして用意しておき,一通りプログラムが完成したら,小文字変数ラベルのところを対応する汎用レジスタ名で置き換えていくと作業がしやすいのではないかな,と考えている。
これらのカウンタは,例えば mod3 の値が 3 になったら,その段階で mod3 の値に 0 を代入してこのカウンタをリセットすることにすれば,「3 で割る」といった操作をどう実現すればよいか,頭を悩ませる必要がなくなる。また,このときは Fizz と表示させることも忘れてはならない。
このように,「3 の倍数であるか」,「5 の倍数であるか」という判定を行うのに,除法を用いず,周期 3 や周期 5 のカウンタを用意することで代用するというのは,CASL II だからこその工夫である。なにしろ,CASL II では除法や剰余(余り)を求める手続き自体,自分で一から組まなければならないのである!
さて,3 の倍数であるかどうかだけを判定し,そうであるときとそうでないときとで異なる出力をするということなら問題は比較的単純なのだが,5 の倍数かどうかも考えねばならず,3 と 5 の公倍数であるときにはまた違った動作が要求される(文字列の結合が手軽に扱えるプログラミング言語であれば,公倍数のときに特別な処理を考える必要はない)。
落ち着いて考えれば,このプログラムは 4 通りの異なる出力を行う必要がある。
3 の倍数でも 5 の倍数でもなければ,カウンタの数字をそのまま出力する。
3 の倍数であって 5 の倍数でなければ Fizz と出力する。
3 の倍数でなくて 5 の倍数であれば Buzz と出力する。
3 の倍数であり,5 の倍数でもあれば FizzBuzz と出力する。
こうして並べてみると(表にまとめるのがもっと分かりやすいが),ちょうど 4 通りであるから,2 ビットの符号をこれらの場合に割り当てて識別するのはどうか,というアイデアに自然と導かれるであろう。
例えば,2 ビットの変数 cases を用意しておき,cases が 2 進表示で 00 のときが数字そのまま,01 のときが Fizz,10 のときが Buzz,11 のときが FizzBuzz のように,cases の値に応じて 4 通りのどの出力を行うかを分岐させればよい。
なお,互いに排反な(どの 2 つの場合も同時には起こり得ない)場合に分けてあるので,どの場合に相当するかの篩い分けをする際,関門は 3 つ用意するだけで済む。
というわけで,例えば次のような部分的な擬似 CASLL II コードを書けば良いことになる。
CPA x,y というのは算術比較という命令で,SF (Sign Flag) と ZF (Zero Flag) という 2 種類のフラグレジスタ (FR) の値が,この順に,
x<y のときは 10 に,
x=y のときは 01 に,
x>y のときは 00 に
セットされる。これは x-y が算術減算とみて負になるか,ちょうど 0 になるか,正になるかということに相当していると考えればよいだろう。
このように比較した結果に応じてそれぞれの場合の処理を行わせるには,分岐命令と組み合わせるのが常道である。
このような,「比較演算」+「結果に応じた分岐処理」というのがプログラミングの要である。
そして分岐処理のうちに「跳躍」(飛躍)が含まれていないと,プログラムが冗長にならざるを得ない(for 文や do loop 文なしで if 文だけで,1 から 100 までの数字の和を求めるような繰り返し処理を実現しようとしたら,非常に長いプログラムになりそうである。そう考えると,同型の処理をまとめておいて,それを繰り返し呼び出して用いる for 文などは再帰的な処理の一種とみてよいのであろう)。
というわけで,識別子 cases の値が 01 のときの処理を記すと,
CPA cases,=1
JMI NUM ; cases<1 のとき,つまり cases=0 のときはカウンタの値の数字をそのまま出力する処理(ラベルを NUM とした)に移る。
JZE F3 ; cases=1 のときは ZF=1 なので,この分岐命令で Fizz のみを出力する処理(ラベルは F3)に移る。
CPA cases,=2 ; 上の分岐命令で飛ばされていないということは cases=10 または cases=11 のときである。
JZE B5 ; cases=2 のときは ZF=1 なので,この分岐命令で Buzz のみを出力する処理(ラベルは B5)に移る。
OUT ='FizzBuzz',=8 ; ここまでの分岐命令で飛ばされずにここまでたどり着くのは cases=11 のときだけであるから,FizzBuzz と出力させる。
JUMP LOOP ; 一連の繰り返し処理の最初に戻る。
といった感じになる。もちろん,この数行をシミュレータにコピペしただけではプログラムは動かない。というか,そもそもアセンブルエラーが出て,実行以前の状態に留まるであろう。
また,実際の CASL II プログラムの一部として使用する場合には,cases という変数名のところに,汎用レジスタ GR0 から GR7 までのどれか,他の用途に用いていない,空いているものを当てはめて,そのレジスタ名ですべて置き換える必要がある。
ところで,こういう,アセンブラ言語をほんの少しだけ高級にしたものを,アセンブラを通るような正式のプログラムに直す段階に何か名前はついているのだろうか?
アセンブラ言語で書かれたプログラムを機械語に直すのは「アセンブル」というそうで,それを機械ではなく人間が行う場合は「ハンドアセンブル」などというらしい。
cases を GR3 などと手で書き換えていくのはハンドアセンブルに近いので,なんかそういったカッコイイ呼び方があると嬉しい。
今回紹介したかったのは,場合分けをスムーズに行う場合,各場合に対応する「識別子」を自分で設定して,その識別子に応じた処理を別に考えるとよいのではないか,というプログラミング方針である。
そしてそれは 7 年前,2017 年に一度このブログで同じ話題を取り上げたことがあり,その繰り返しになってしまった,というのがオチである。
ともかく,ここにはソースプログラムを挙げないが,普通の数字の表示をさぼって,3 でも 5 でも割り切れない数字は全て * と表示する簡易版は完成しており,Daytime さんのシミュレータで(おそらく)正しく動作していることを確認した,とだけ報告しておく。
Daytime さんの CASL II 講座の方にも解説があるようだが,2 進数を 10 進表示に直すといったミッションについてはまだ考えていないので,そちらの実装もうまくいったら続編を書くかもしれない(し,書かないかもしれない)。
トホホのホ~ (;´д`)