FizzBuzz を Brainfuck で書いてみた

FizzBuzz を Brainfuck で書いてみました。ソースコード

概要

FizzBuzz とは?

1から順に数え上げていき、3の倍数のとき "Fizz", 5の倍数のとき "Buzz", 15の倍数のとき "FizzBuzz" と言うゲームです。
「なるべく短く書く」「難解な言語で書く」など、屡々プログラミング技術を競うのに使われたりします。

Brainfuck とは?

たった8つの命令 + - > < [ ] . , だけで記述するプログラミング言語です。
命令は8つだけですが、これでもチューリング完全(普通のコンピュータで実行できるプログラムは全て記述できる)です。

1. 十進法カウンタの構成

カウンタのメモリ配置

FizzBuzz を書くに当たって、まず、1, 2, 3, ... と数え上げて表示できるカウンタが必要です。
カウンタは、メモリ上に次のような形で表現することにします。
Brainfuck 十進法カウンタ

上の図では、カウンタには "123" という値が格納されています。
各メモリ位置の値の意味は、次の通りです。

位置 内容
数字 その桁に格納されている数字の ASCII コード ('0' (48) 〜 '9' (57)) を表します。
中身は '1''2' → … → '9''0''1' → … と遷移します。
count その桁の数字と足して9になるような数値を格納しています。
8 → 7 → … → 1 → 0 → 9 → 8 → … と遷移します。
carry インクリメントの際に、前の桁からの繰り上がりの有無(有れば 1, 無ければ 0)を表します。
t1t4 計算の過程で一時的に使う変数です。使っていないときの値は 0 です。
(本当はバラバラに割り当てた方が判り易いのですが、勿体無いので同じ場所を共有しています)

インクリメント

こうして構成したカウンタの値をインクリメントする(1増やす)ことを考えます。
インクリメントは、次の擬似コードの要領で行います。

function increment_counter(){ 1の位.carry = 1 /* carry が 1 である位をインクリメント */ for (現在の位 = 1の位; 現在の位.carry == 1; 現在の位 = 次の位){ 現在の位.carry = 0 if (現在の位.数字 != 0){ /* 未使用領域でない */ if (現在の位.count != 0){ /* 現在の位.数字は '9' でない */ 現在の位.数字 = 現在の位.数字 + 1 現在の位.count = 現在の位.count - 1 } else { /* 現在の位.数字は '9' */ 現在の位.数字 = '0' 現在の位.count = 9 次の位.carry = 1 } } else { /* 未使用領域 */ 現在の位.数字 = '1' 現在の位.count = 8 } } /* 初期ポインタ位置に戻す */ while (現在の位.数字 != 0) 現在の位 = 前の位 }

これを Brainfuck で書くと、次のようになります。(途中の if 等はプログラムとしては無意味なコメントです)

function increment_counter(){ >>>>>>+ /* ポインタを 1の位.carry に移動し、値を 1 にする */ /* carry が 1 である位をインクリメント */ for [ - /* carry を 0 に戻す */ copy <<[->>+>+<<<]>>>[-<<<+>>>] /* 数字 を t1 にコピー (途中 t2 に退避) */ + /* t2 にフラグを立てる */ if <[ /* t1 (= 数字) が 0 でないのなら if 節を実行 */ [-]>- /* t1 も t2 も 0 にする */ copy <<[->+>+<<]>>[-<<+>>] /* count を t3 にコピー (途中 t4 に退避) */ + /* t4 にフラグを立てる */ if <[ /* t3 (= count) が 0 でないのなら if 節を実行 */ [-]>- /* t3 も t4 も 0 にする */ <<<+>-> /* 数字 のインクリメントと count のデクリメント */ ] else >[ /* t4 のフラグが立っていれば else 節を実行 */ - /* フラグを降ろす */ <<<--------- /* 数字を '0' にする */ >+++++++++ /* count を 9 にする */ >>>>>+<<< /* 次の位.carry を 1 にする */ ]< ] else >[ /* t2 のフラグが立っていれば else 節を実行 */ - /* フラグを降ろす */ <<<+++++++++++++++++++++++++++++++++++++++++++++++++ /* 数字を '1' にする */ >++++++++>> /* count を 8 にする */ ] >>>] /* ポインタを 次の位.carry に移動 */ /* 初期ポインタ位置に戻す */ <<<<<<[<<<<] }

これを実行すると、"123" だった値が "124" に更新されます。

カウンタの値の表示

こうして数え上げのできるカウンタができた訳ですが、内容を表示できなければ意味がありません。
内容の表示は、次の要領で行います。

function print_counter(){ /* 一番上の桁まで移動 */ for (現在の位 = 1の位; 現在の位.数字 != 0; 現在の位 = 次の位); /* 上の桁から順に表示 */ for (現在の位 = 前の位; 現在の位.数字 != 0; 現在の位 = 前の位){ putchar(現在の位.数字) } }

これを Brainfuck で書くと、次のようになります。

function print_counter(){ /* 一番上の桁まで移動 */ >>>>[>>>>] /* 上の桁から順に表示 */ <<<<[.<<<<] }

2. 指定回数の繰り返し処理

今度は、繰り返し処理を用いて、1から100まで順々に表示するプログラムを書きます。
そのために、メモリの使い方を次のように変更します。
(「不使用」となっている箇所は、後で使うので空けておきます)
Brainfuck 指定回数の繰り返し

位置 内容
イテレータ 反復子です。繰り返し処理をあと何回行うかを表します。
プログラムの最初に、繰り返したい回数を格納しておきます。
(注: 1バイトしかないので、最大で 255 回までです。複数バイトのイテレータはここでは扱いません。)
文字定数 '␣' 空白文字の ASCII コード (32) を格納しておきます。

これを用いて、プログラムは次のように書けます。

function count_up(){ ++++++++++++++++++++++++++++++++ /* 文字定数 '␣' を格納 */ >>>>>> ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ /* イテレータに 100 を格納 */ /* 繰り返し */ for [ <<< /* ポインタを基準の位置に移動 */ increment_counter() /* 本当はここに上記プログラム increment_counter() の内容を書く */ print_counter() /* 本当はここに上記プログラム print_counter() の内容を書く */ <<<.>>>>>> /* 空白文字の出力 */ -] }

これを実行すると、次のような出力を得ます。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

3. Fizz と Buzz

最後に、Fizz と Buzz の処理を加えれば完成です。
Fizz と Buzz の処理のために、メモリの使い方をまた少し拡張します。
FizzBuzz in Brainfuck

位置 内容
Fizz Fizz のためのカウンタです。
3 → 2 → 1 → 3 → 2 → 1 → … と遷移します。
Buzz Buzz のためのカウンタです。
5 → 4 → 3 → 2 → 1 → 5 → 4 → 3 → 2 → 1 → … と遷移します。
FB 3の倍数か5の倍数のとき 1, それ以外のとき 0 です。
tmp1, tmp2 計算の過程で一時的に使う変数です。使っていないときの値は 0 です。
これまでは「常に0」としていた箇所も使います。
文字定数 文字定数 'F' (70), 'i' (105), 'B' (66), 'u' (117), 'z' (122), '␣' (32) を格納しておきます。

これを用いて、FizzBuzz の計算は次の要領で行います。

function FizzBuzz(){ 文字定数FizzBuzzイテレータの初期化 for (; イテレータ != 0; イテレータ = イテレータ - 1){ increment_counter() /* Fizz の処理 */ Fizz = Fizz - 1 if (Fizz == 0){ Fizz = 3 print("Fizz") FB = FB + 1 } /* Buzz の処理 */ Buzz = Buzz - 1 if (Buzz == 0){ Buzz = 5 print("Buzz") FB = FB + 1 } /* 数の表示 */ if (FB != 0){ FB = 0 } else { print_counter() } putchar(空白文字) } }

これを Brainfuck で書くと、次のようになります。

function FizzBuzz(){ ++++++++++++++++++++++++++++++++++++++++++++++++++ /* 文字定数 'F' を格納 */ ++++++++++++++++++++> ++++++++++++++++++++++++++++++++++++++++++++++++++ /* 文字定数 'i' を格納 */ ++++++++++++++++++++++++++++++++++++++++++++++++++ +++++> ++++++++++++++++++++++++++++++++++++++++++++++++++ /* 文字定数 'B' を格納 */ ++++++++++++++++> ++++++++++++++++++++++++++++++++++++++++++++++++++ /* 文字定数 'u' を格納 */ ++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++> ++++++++++++++++++++++++++++++++++++++++++++++++++ /* 文字定数 'z' を格納 */ ++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++> ++++++++++++++++++++++++++++++++>>>> /* 文字定数 '␣' を格納 */ +++> /* Fizz に 3 を格納 */ +++++> /* Buzz に 5 を格納 */ ++++++++++++++++++++++++++++++++++++++++++++++++++ /* イテレータに 100 を格納 */ ++++++++++++++++++++++++++++++++++++++++++++++++++ /* 繰り返し */ for [ <<< /* ポインタを基準の位置に移動 */ increment_counter() /* 本当はここに上記プログラム increment_counter() の内容を書く */ /* Fizz の処理 */ >- /* Fizz = Fizz - 1 */ copy [-<<+>+>]<[->+<] /* Fizz を tmp1 にコピー (途中 tmp2 に退避) */ + /* tmp2 にフラグを立てる */ <[[-]>-<] /* tmp1 (= Fizz) が 0 でないのなら tmp1 も tmp2 も 0 にする */ if >[ /* tmp2 のフラグが立っていれば if 節を実行 */ - /* フラグを降ろす */ >+++ /* Fizz = 3 */ <<<<<<<<<.>.>>>.. /* "Fizz" と表示 */ >>+>> /* FB = FB + 1 */ ] /* Buzz の処理 */ >>- /* Buzz = Buzz - 1 */ copy [-<<<+>+>>]<<[->>+<<] /* Buzz を tmp1 にコピー (途中 tmp2 に退避) */ + /* tmp2 にフラグを立てる */ <[[-]>-<] /* tmp1 (= Buzz) が 0 でないのなら tmp1 も tmp2 も 0 にする */ if >[ /* tmp2 のフラグが立っていれば if 節を実行 */ - /* フラグを降ろす */ >>+++++ /* Buzz = 5 */ <<<<<<<<.>.>.. /* "Buzz" と表示 */ >>+>> /* FB = FB + 1 */ ] /* 数の表示 */ <+ /* tmp1 にフラグを立てる */ if <[ /* FB が 0 でなければ if 節を実行 */ [-]>-< /* FB = tmp1 = 0 */ ] else >[ /* tmp1 のフラグが立っていれば else 節を実行 */ -> /* フラグを降ろす */ print_counter() /* 本当はここに上記プログラム print_counter() の内容を書く */ < ] <<.>>>>>> /* 空白文字の出力 */ -] }

これを実行すると、次のような出力を得ます。

1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fizz 22 23 Fizz Buzz 26 Fizz 28 29 FizzBuzz 31 32 Fizz 34 Buzz Fizz 37 38 Fizz Buzz 41 Fizz 43 44 FizzBuzz 46 47 Fizz 49 Buzz Fizz 52 53 Fizz Buzz 56 Fizz 58 59 FizzBuzz 61 62 Fizz 64 Buzz Fizz 67 68 Fizz Buzz 71 Fizz 73 74 FizzBuzz 76 77 Fizz 79 Buzz Fizz 82 83 Fizz Buzz 86 Fizz 88 89 FizzBuzz 91 92 Fizz 94 Buzz Fizz 97 98 Fizz Buzz

4. まとめ

以上を全部纏めると、最終的なソースコードは次のようになります。
(若干コードを短くする最適化をしています)

function FizzBuzz(){ ++++++++++++ /* 文字定数・初期値を格納(若干の最適化) */ [->++++++>+++++++++>+++++>++++++++++>++++++++++>+++>>>>>>++++++++<<<<<<<<<<<<] >-->--->++++++>--->++>---->>>>+++>+++++>++++ /* 繰り返し */ for [ increment_counter(){ >>>+ for [- copy <<[->>+>+<<<]>>>[-<<<+>>>] + if <[[-]>- copy <<[->+>+<<]>>[-<<+>>] + if <[[-]>- <<<+>-> ] else >[- <<<--------->+++++++++>>>>>+<<< ]< ] else >[- <+++++++[<<+++++++>>-]< /* 数字を '1' にする(若干の最適化) */ ++++++++>> ] >>>] <<<<<<[<<<<] } /* Fizz の処理 */ >- copy [-<<+>+>]<[->+<] +<[[-]>-<] if >[- >+++<<<<<<<<<.>.>>>..>>+>> ] /* Buzz の処理 */ >>- copy [-<<<+>+>>]<<[->>+<<] +<[[-]>-<] if >[- >>+++++<<<<<<<<.>.>..>>+>> ] /* 数の表示 */ <+ if <[ [-]>-< ] else >[-> print_counter(){ >>>>[>>>>]<<<<[.<<<<] } < ] <<.>>>>>> -] }

最終的なソースコード

コメントを全部取り除いた最終的なソースコードは、次の通りです(473バイト)。

++++++++++++[->++++++>+++++++++>+++++>++++++++++>++++++++++>+++>>>>>>++++++++<<<<<<<<<<<<]>-->--->++ ++++>--->++>---->>>>+++>+++++>++++[>>>+[-<<[->>+>+<<<]>>>[-<<<+>>>]+<[[-]>-<<[->+>+<<]>>[-<<+>>]+<[[ -]>-<<<+>->]>[-<<<--------->+++++++++>>>>>+<<<]<]>[-<+++++++[<<+++++++>>-]<++++++++>>]>>>]<<<<<<[<<< <]>-[-<<+>+>]<[->+<]+<[[-]>-<]>[->+++<<<<<<<<<.>.>>>..>>+>>]>>-[-<<<+>+>>]<<[->>+<<]+<[[-]>-<]>[->>+ ++++<<<<<<<<.>.>..>>+>>]<+<[[-]>-<]>[->>>>>[>>>>]<<<<[.<<<<]<]<<.>>>>>>-]
公開: 2011年9月4日
「ソフトウェア・PCツール」へ戻る
鵺帝国トップに戻る