FizzBuzzを1byteで実装する

以前「FizzBuzz Zero ―― 人類の知識なしでFizzBuzzをマスターする」という記事がQiitaに出ました。

これに対して「人類の知識を使わないと大変すぎる」という趣旨の意見がいくつかありました。確かにGitHubで公開されているコードをみると全部で31,086 バイトで、少し長いような気もします。

では、人類の知識を使うと、どれくらい簡単にFizzBuzzを書けるのでしょうか？

気になって調べたので、備忘録も兼ねて記録したいと思います。

この記事の内容をざっくり2行で：

• 様々なプログラミング言語の最小のFizzBuzzコードを比較する
• 最短で1バイトで実装できる

目次:

1. Code Golfとは
2. Python3
3. Python2
4. C
5. Ruby
6. Bash
7. GolfScript
8. Vim
9. Hexagony
10. Lazy K
11. Jelly
12. gs2
13. まとめ

Code Golf とは

問題の条件を満たすプログラムをできるだけ短い文字数で実現する競技は Code Golf と呼ばれます。
スポーツとしてのゴルフと同じように、スコアが小さいほど優れています。

Code Golfのスコアとは、文字数（=何バイトか）で、空白や改行なども1文字としてカウントされます。

*コードゴルフはコンピュータプログラミング・コンテストの一種。参加者は与えられたアルゴリズムを、可能な限りもっとも短いソースコードで記述することを競う。バイナリサイズではなく、ソースコードの文字数がスコアとなる。　　* ―Wikipedia

もちろん、予め用意しておいた外部ファイルを読みこんだりするのは禁止です。あくまでデフォルトの状態からそのコードだけで与えられた課題をクリアしないといけません。

言語ごとに最短のコードも異なるので、基本的に同一言語で競われます。Code Golfの課題には様々なバリエーションがありますが、FizzBuzz問題もその一つです。（FizzBuzzの説明はこちら）

• anarchy golf - FizzBuzz

例えばこちらのサイトでは主要なプログラミング言語でFizzBuzzのCode Golfが行われています。こういったサイトを参考にしつつ、最短のFizzBuzz実装を調べて行きたいと思います。

（以下、特に注釈がなければ、実装コードは見出しの脚注にある参考サイトからの引用となります。）

Python3 (59 bytes)

python3

for i in range(100):print(i%3//2*"Fizz"+i%5//4*"Buzz"or-~i)

まずは皆大好きPython。Python3では59バイトが最小らしいです。
ポイントは-~iでi+1を表現するところ。orの後のスペースが不要になるので1バイト短縮できます。

実行テストはこちらからどうぞ。

Python2 (56 bytes)^{1 2}

python2

# (A)
for i in range(100):print i%3/2*"Fizz"+i%5/4*"Buzz"or-~i

# (B)
i=0
while~i<99:i-=1;print~i%3/2*'Fizz'+~i%5/4*'Buzz'or-i 

# (C)
i=0
exec"print i%3/2*'Fizz'+i%5/4*'Buzz'or-~i;i+=1;"*100 

# (D)
i=1;exec"print'FizzBuzz'[i%-3&4:12&8-i%5]or i;i+=1;"*100 

Python2では複数解が存在するようです（すべて56バイトです）。
Python3と異なり、整数除算が/で表現できること、printに()が不要であることから(A)¹のように3バイト短くできます。

(B)¹はwhileでiをデクリメントしていき、終了条件を~i<99にすることで1バイト短縮しています。

(C)¹はexec""を100回繰り返す方法。Python3ではexec("...")とする必要があるのでちょっと使いにくいです。

(D)²は負の剰余と4(=0x100),12(=0x1100)とのANDを用いることで[0:4],[4:4],[4:8],[0:8]を巧みに発生させています。（下記参照）

Python2

>> for i in range(1, 16): print (i, i%-3, i%5, 8-i%5, i%-3&4, 12&8-i%5)

( 1, -2, 1, 7, 4, 4) # "FizzBuzz"[4:4] = ""
( 2, -1, 2, 6, 4, 4) 
( 3,  0, 3, 5, 0, 4) # "FizzBuzz"[0:4] = "Fizz"
( 4, -2, 4, 4, 4, 4) 
( 5, -1, 0, 8, 4, 8) # "FizzBuzz"[4:8] = "Buzz"
( 6,  0, 1, 7, 0, 4)
( 7, -2, 2, 6, 4, 4)
( 8, -1, 3, 5, 4, 4)
( 9,  0, 4, 4, 0, 4)
(10, -2, 0, 8, 4, 8)
(11, -1, 1, 7, 4, 4)
(12,  0, 2, 6, 0, 4)
(13, -2, 3, 5, 4, 4)
(14, -1, 4, 4, 4, 4)
(15,  0, 0, 8, 0, 8) # "FizzBuzz"[0:8] = "FizzBuzz"

(B)と(D)を組み合わせればPython3の別解（59bytes）も導けます。

Python3

i=0
while~i<99:i-=1;print("FizzBuzz"[-i%-3&4:12&8-i%5]or-i)

また、対話型コンソール上ではiの代わりに_を用いて2バイト短くできるとのことです。

Python2

>> 0;exec"print _%3/2*'Fizz'+_%5/4*'Buzz'or-~_;_+=1;"*100

実行テストはこちら→(A), (B), (C), (D)からどうぞ。

C (73 bytes) ³

C

main(i){for(;i<101;puts("Buzz"-i*i++%5))printf(i%3?i%5?"%d":0:"Fizz",i);}

次は基本のC。有名な実装のようです。

こちらに短縮の過程と詳しい解説があり勉強になります。

• FizzBuzzのcodegolfを世界一分かりやすく解説！#c言語 - Qiita

コンパイラによっては出力がうまくいかないので、その場合は74バイトが最短とのこと。

C

main(i){for(;i<101;puts(i++%5?"":"Buzz"))printf(i%3?i%5?"%d":0:"Fizz",i);}

実行テストはこちらからどうぞ。

Ruby (50 bytes) ⁴

Ruby

1.upto(?d){|n|puts'FizzBuzz
'[i=n**4%-15,i+13]||n}

続いてRuby。
こちらも大変有名な実装ですが、そろそろ理解が追いつかなくなってきました。

内容についてはこちらで詳しい解説がされています。

• Ruby FizzBuzz最短コードメモ (51bytes) ネタバレ注意 - Qiita

なるほど、**フェルマーの小定理**が使われているようです。人類の知識が活用されていますね。

なお上記の50バイトのコードは古いRubyでしか受け付けず、最近のバージョンでは?dを100に変更した51バイトが最短だそうです。
実行テストはこちらからどうぞ。

Bash (41 bytes) ⁵

Bash

seq 100|sed 5~5cBuzz|sed 3~3s/[^B]*/Fizz/

男なら黙ってワンライナー。
anarchy golfでは12バイトが最短のようですが、調べた限りでは実装を見つけられませんでした。（不正ではという指摘もあります）

実行テストはこちらからどうぞ。

GolfScript (37 bytes) ⁶

GolfScript

100,{)..3%!'Fizz'*\5%!'Buzz'*+\or}%n*

いよいよQiitaでシンタックスハイライト可能な言語に存在しない領域に突入しました。
これ以降は何でもありです。

GolfScriptはその名の通りCode Golfをするために作られた言語です。

GolfScriptは、できるだけ少ないキーストロークで問題を解決することを目的としたスタック指向の難解プログラミング言語です。シンプルで簡単に書くことを目指しています。　ー golfscript.com

前半と後半で矛盾していないか? とにかくFizzBuzzも非常に簡単に書けます。

実行テストはこちらからどうぞ。

Vim (44 bytes) ⁷

Vim

33o<CR>Fizz<CR><Esc>qqABuzz<Esc>5kq19@q:%s/^$/\=line('.')<CR>

確かに何でもありとは言いましたが、そもそもプログラミング言語でない。

しかしVimGolfというのはVimユーザーではメジャーらしく、FizzBuzzも必修課題の一つのようです。
いったい何が人をそこまでVimに執着させるのでしょうか。

実際にVimを開いてタイプするとFizzBuzz文字列が魔法のように出現します。
恐ろしいことに最短はさらに短く39ストロークとのこと。

Hexagony (76 bytes) ⁸

Hexagony

=?3})"F\>%'5?\"\B;u;"}/4;d'%<>\g/"!{{\}.%<@>'...<>,}/${;;z;i;z;;$/<>?{$/"./_

ついにコード内に**FizzやBuzz**が確認できなくなりました。

Hexagonyは二次元難解プログラミング言語で、名前の通り六角形にコードを配置して実行するそうです。
なるほど！ ちょっと並べ替えてみましょう。

       = ? 3 } ) "
      . \ > % ' 5 ?
     \ F \ B ; u ; "
    } " / ; d ' % < >
   \ g 4 / ! { { \ } . 
  % < @ . > " ' . < > ,
   } / $ { ; ; z ; i ;
    z ; ; $ / < > ? {
     $ / " . / _ . .
      . . . . . . .
       . . . . . .

…………。
どうやら/や\や<で実行フローを制御するらしいのですが、さっぱり分かりません。

と思ったら別の実装（91バイト）の作者が解説gifを使って丁寧に説明してくれています。

見ているだけでも勉強になります。

実行テストはこちらからどうぞ。

Lazy K (1201 bytes) ⁹

Lazy_K

K(SII(S(S`KS(S`K`S(SI`K(S`K`SIK))(S`K`S`KK(S`K`S(S(S(S`KS(S`K`S(S(SI`K`KK)`K`K`K`SK)(S`KK(SII(S(S`KS(S`K`S`KS(S`K`S`K`S`K(SS(SSSS(SS`SK))(S`KSK)(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`KSK)))))`K`K(SS(SSSS(SS`SK))(S`KSK)(S(S(SI`K(S`K`SI(S`KK(SI`K`S(S`KSK)))))`K`K`SK)`KI)))))))(S`K`S`K`S(SI`K(S`K`SIK))(S`K`S`K`S`KK(S(S`KS(S`K`S`KS(S`K`S`KK(S`K`S`K(S`KSK)(S(S`KS(S`K`SI(S`K`S`KK(S(SII)`K`SK))))`K`KI)))))`K`K(S(S`KS(S`KK(S`KS(S`K`SI(S`KK(S(S(SS(SS(SS(SSS))))(SS`SK))S(S`KSK)))))))`KK)))))`SK))))`KI)(S(S(S`KS(S`K`S`K(S`KSK)(S(S(SI`K(SI`K`SK))`K(SII(S`K`S(SI`K`S`K(S`K(S`K`S(SI`K(S(S(S(SSS)(SS`SK))S)(SSSS(SS(SS`SK)))(S`KSK)))K)(S`K`S(SI`K(S(S(S(SS(SS(SSS)))(SS`SK))S)(SSSSSS(SS`SK))(S`KSK)))K)))(S`KK(S`K(S(S`KSK)I(S`K`S(SI`K`SK)K))(SII))))))`KK)))(S(S(SI`K(SI`K`SK))`K(SII(S`K`S(SI`K`S`K(S`K(S`K`S(SI`K(SS(SS(SSSS(SS(SS`SK))))(S`KSK)))K)(S`K`S(SI`K(S(S(SS`S(SSS)(SS`SK))S)(SSSSSS(SS`SK))(S`KSK)))K)))(S`KK(S`K(SII(S(S`KSK)I)(S`K`S(SI`K`SK)K))(SII))))))`KK))`K(S(S`KSK)I(S`K`S(SI`K(SS(S(SS`SK)(SS(SS(SSSS(SS`SK)))))(S`KSK)))K))))(S`K`S`K`S(SI`K(SS(SSSS(SS`SK))(S`KSK)))(S`K`S`KK(S(S`KS(S`KK(SII)))`K`S(S`KSK))))))))`K`K(S(SS`SK)(SS(SSSS(SS`SK)))(S`KSK)(S`K`SIK)`KK))I)

Code Golfとは一体何だったのでしょうか。

Lazy Kは難解プログラミング言語の代表格で、組み込み関数を3種類しか持たない純関数型言語です。

純粋関数型言語として、チューリング完全でありながら、絶対必要なエッセンスだけを抜き出したプログラミング言語である。遅延評価を行う。使用するにも、処理系を実装するにも、コンビネータ論理の知識が必要である。

標準入力をプログラムである関数の引数として受け取る。ただし、標準入力は1バイトごとのチャーチ数のスコットエンコードされたリストとしてエンコードされ、出力も同様に1バイトごとのチャーチ数のスコットエンコードされたリストとなる。

Wikipediaの説明からして難解です。
Lazy Kについてはこちらの解説が大変わかりやすいです。

• Lazy K プログラムを書く - Qiita

しかしHello World!ですでに17KBを超えているので、FizzBuzzで1.2KBは恐ろしく短い気がします。

実行テストはこちらからどうぞ。

Jelly (20 bytes) ¹⁰

Jelly

³µ3,5ḍTị“¡Ṭ4“Ụp»ȯµ€G

文字化けではありません。

JellyはGolfScriptと同様、Code Golfのために開発された言語です。
それぞれの文字コードに対応した組み込み関数が存在するようです。

開発者の方が上記のコードについて解説してくれていますので、翻訳してみます。

³                       100を取得
 µ                      新しいモナドチェーンを開始
                 µ€     [1,...,100]のすべての整数nに前のチェーンを適用する
  3,5ḍ                  3と5でnが割り切れるかをテストする
      T                 すべての真の指標を取得する / [1] 3の倍数　[2] 5の倍数 [1,2] 15の倍数 [] その他
        “¡Ṭ4“Ụp»        辞書から['Fizz', 'Buzz']を取得
       ị                現在の指標の文字列を取得
                ȯ       空のリストをnと置換する
                   G    改行で区切ってリストに追加する

実行テストはこちらからどうぞ。

gs2 (1 byte) ¹¹

gs2

f

いや、流石におかしいのでは。

gs2もJellyと同様、Code Golfのために生み出された言語です。
Jellyとの違いは、組み込み関数が直接16進数に対応しているという点のようです。

しかし1バイトだけでどうやってFizzBuzzを実現しているのでしょうか?
将来シンギュラリティが実現しても、一字タイプするだけでFizzBuzzを実行することを予想できるAIは現れないでしょう。

言語の実装を調べてみましょう（Pythonで書かれているようです）。
どうやら**h**で"Hello World!"を出力するなど、Code Golf頻出テーマについては組み込み関数が存在するようです。

gs2.py

    elif t == '\x66': #= fizzbuzz
        fizzbuzz = []
        for i in range(1, 101):
            s = ("Fizz" if i % 3 == 0 else "") + \
                ("Buzz" if i % 5 == 0 else "")
            fizzbuzz.append(s or str(i))
        self.stack.append(to_gs('\n'.join(fizzbuzz)))
    elif t == '\x67': #= popcnt right-cons
        x = self.stack.pop()
        if is_num(x):
            x = abs(x)
            p = 0
            while x:
                p += (x & 1)
                x >>= 1
            self.stack.append(p)
        elif is_list(x):
            y = self.stack.pop()
            self.stack.append(x + [y])
    elif t == '\x68': #= hello
        x = 0
        if len(self.stack) >= 1 and is_num(self.stack[-1]):
            x = self.stack.pop()
            x = (range(0, 11) + [100, 1000, 16, 64, 256]).index(x)
        s1 = 'h' if x & 1 else 'H'
        s2 = 'W' if x & 2 else 'w'
        s3 = ['!', '', '.', '...'][((x & 4) >> 2) | ((x & 16) >> 3)]
        s4 = '' if x & 8 else ','
        f = '%sello%s %sorld%s' % (s1, s4, s2, s3)
        self.stack.append(to_gs(f))

確かに言語上の仕様であればルールには抵触しません。
発想の転換といいますか、皆が思いつくけど恥ずかしくて誰もやらなかった方法な気がします。

もちろんプログラミング言語なので、1バイトではない解法もちゃんと存在します。

gs2

1b 2f fe cc 04 46 69 7a 7a 09 07 42 75 7a 7a 19 06 27 2d d8 62 32 ec 99 dc 61 0a

文字コードが対応していないものもあり16進数表記ですが、全部で27バイトです。変なことしなくても十分短いのでは。

いずれにせよ、1バイトでFizzBuzzが実装できるのは確かなようです。
実行テストはこちらからどうぞ。

まとめ

様々なプログラミング言語での最短FizzBuzzコードを調べた結果、1バイトで実装できることがわかりました。
人類の知識すごい。

後半はほとんど難解プログラミング言語の紹介になってしまいましたが、いかがでしたでしょうか。
コードに間違いがあったり、もっと短い実装があるよ、という方はコメントをいただければ幸いです。

Twitter（@ymg_aq）もやっていますので、よければこちらもお願いいたします。

参考サイト

1. FizzBuzz - Pythonのお勉強 ↩ ↩² ↩³ ↩⁴

2. FizzBuzz! - xkcd.com ↩ ↩²

3. FizzBuzzのcodegolfを世界一分かりやすく解説！#c言語 - Qiita ↩

4. Ruby FizzBuzz最短コードメモ (51bytes) ネタバレ注意 - Qiita ↩

5. Bash + coreutils, 41 bytes - Programming Puzzles & Code Golf Stack Exchange ↩

6. GolfScript, 37 bytes - Programming Puzzles & Code Golf Stack Exchange ↩

7. Vim, 44 bytes - Programming Puzzles & Code Golf Stack Exchange ↩

8. Hexagony, 76 bytes - Programming Puzzles & Code Golf Stack Exchange ↩

9. rst76/Lazy-K: Project seeking the supreme (shortest) Lazy K program. ↩

10. Jelly, 20 bytes - Programming Puzzles & Code Golf Stack Exchange ↩

11. nooodl/gs2: code-golf-oriented esoteric programming language ↩