メモ

FizzBuzz_51bytes.rb

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

どうしてこのコードでFizzBuzzできるのか少し調べたのでメモ。
少し冗長に書くと、以下のようになる。

1.upto(100) do |n|
  i = (n ** 4 % -15)

  str = "FizzBuzz\n"[i, i + 13]

  if str
    puts str
  else
    puts n
  end
end

"FizzBuzz\n"から[]メソッドで必要な文字列を抜き出している。
[]はインデックス・長さを指定して文字列を取り出せる。(String#sliceと同じ)
例えば"abc"[1, 1]だと、1番目から1文字を抜き出すので"b"が返る。

[]のインデックスの調整の為、末尾に無駄な1文字が必要なので改行を挿入している。(putsで無視される)
元のコードでは、改行を直接入力することで\nと書くよりも1バイト短くなっている。
この為、一行では記述出来ない。

n ** 4 % -15って何

[]のインデックス部分には、n ** 4 % -15という式が入っている。
また、同時に変数iを宣言し、代入している。

長さ部分には、そのiに13を足した数値が渡される。

実際にどのような数値が渡されているのか調べてみる。

という結果になった。
改行はputsによってシカトされるので、無いのと同じ。
インデックスに負の数値を指定すると、末尾から○○番目を指定できる。

Fizzを取り出す際のインデックスと長さはピッタリ指定されている。
Buzz、FizzBuzzはインデックスはピッタリだが、長さがデタラメ。
当てはまらない場合は両方デタラメ。インデックスの絶対値が文字列の大きさを超えているとnilが返る。

なぜこの数値になるのか少し調べてみる。
(数学は不得意なのであまりアテにならないと思う。)

負の剰余の計算を初めて見た。
計算結果は、言語によって異なるそうだ。

Rubyでは以下のような結果となる。

n	n % 15	-n % -15	-n % 15	n % -15
1	1	-1	14	-14
2	2	-2	13	-13
3	3	-3	12	-12
4	4	-4	11	-11
5	5	-5	10	-10

foo % -barという式の場合は、
foo % barからbarを引いた値になるようだ。

HackerRank Blog - FizzBuzz Code Golf Competition
上のリンクによると、このコードには、フェルマーの小定理が応用されているそうだ。

p を素数とし、a を p の倍数でない整数（a と p は互いに素）とするときに、
$a^{p−1} \equiv 1\ (mod\ p)$
すなわち、a の p − 1 乗を p で割った余りは 1 であるというもの。

3と5で、15回ずつ試してみる。

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
n ** (3-1) % 3	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0
n ** (5-1) % 5	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0

で、今回のコードでは$p-1$の箇所が4なので、pは5であるはずだが、15となっている。
これは3と5をかけた数値であり、この場合は以下のような結果になるようだ。
(最小公倍数だからかもしれないけど詳しくは分からない。)

(2015/4/16追記: 「カーマイケルの定理」によるものだそうです。コメント参照。)

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
n ** 4 % 15	1	1	6	1	10	6	1	1	6	10	1	6	1	1	0
n ** 4 % -15	-14	-14	-9	-14	-5	-9	-14	-14	-9	-5	-14	-9	-14	-14	0

3の倍数, 5の倍数, 3と5の倍数, その他で別々の数値を得ることが出来た。

なんか暇つぶしにググってたら中国の剰余定理という情報を発見しました

『孫子算経』には、「3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か」という問題とその解法が書かれている。中国の剰余定理は、この問題を他の整数についても適用できるように一般化したものである
Wikipedia - 中国の剰余定理

あとはFizzBuzzという文字列を用意して、[]で必要な箇所を取り出せるように工夫して終わり。
(解説雑すぎる)

解説下手くそで申し訳ない (というか、これ以上は理解出来てないから解説のしようが無い)