matsulibの日記

Ingredients as Code

FizzBuzz・スライス・剰余計算

python

このFizzBuzzのコードがどうなってるのかすぐに分からなかったのでメモ。
http://codepad.org/fizzbuzz#Python

for i in range(1,101):
    print("FizzBuzz"[i*i%3*4:8--i**4%5] or i)

まず
(1) "FizzBuzz"[i*i%3*4:8--i**4%5] は文字列のスライスである
(2) (1)が空文字列ならFalseとして扱われ、その場合、真値となる i が返される
ということが分かる。

残る問題は(1)の中身だけなので
スライスの左側と右側を別けて考える。（以下、i は自然数とする）

i*i%3*4 について

i が3の倍数のとき "FizzBuzz"[i*i%3*4:8--i**4%5] が "Fizz" を返すためには
少なくとも ((i*i)%3)*4 が0になる必要があるけど、これは自明だ。
でもどうして二乗するのか。これを計算するために次の公式が使える。
剰余計算の復習

a*b mod n = (a mod n)*(b mod n) mod n

つまり i*i%3 は ((i%3)**2)%3 と同値である。
これで i が3の倍数でないときを考えると、
i%3∈{1,2}なので、((i%3)**2)%3 は 1%3 か 4%3 となり、これはいずれの場合も1になる。
最後に4をかけるので、i*i%3*4 は i が3の倍数のときは0、それ以外は4になるということが分かる。

8--i**4%5 について

これも基本的には上で書いたことと同じだが式の構造がわかりにくい。
演算子の優先度（べき乗＞正符号、負符号＞乗算、除算、剰余＞加算および減算）に
注意して見やすいように括弧を付けると 8-((-(i**4))%5)となる。
負の数の剰余はどうなるんだっけ…

なんと言語によって値が変わるらしい。
負数の剰余を計算してはならない - おともだちティータイム

Pythonでは、(-1)%5 は4である。i**4%5の計算は上記参照。
なので i が5の倍数でないとき、(-(i**4))%5 を計算すると

-(i^4) mod 5 = -1*(i^4) mod 5
             = (-1 mod 5)*(i^4 mod 5) mod 5
             = 4*1 mod 5
             = 4

となる。したがって 8--i**4%5 は i が5の倍数のとき8、それ以外で4となる。

まとめ

  • a*b mod n = (a mod n)*(b mod n) mod n
  • 演算子の優先度は、べき乗＞正符号、負符号＞乗算、除算、剰余＞加算および減算＞ブール演算 OR
  • 負数の剰余は注意が必要

※演算子の優先度リスト
http://docs.python.jp/2.5/ref/summary.html

上で説明した値になっているか確認する。

for i in xrange(1, 16):
    print i, i*i%3*4, 8--i**4%5, ("FizzBuzz"[i*i%3*4:8--i**4%5] or i)
# 1 4 4 1
# 2 4 4 2
# 3 0 4 Fizz
# 4 4 4 4
# 5 4 8 Buzz
# 6 0 4 Fizz
# 7 4 4 7
# 8 4 4 8
# 9 0 4 Fizz
# 10 4 8 Buzz
# 11 4 4 11
# 12 0 4 Fizz
# 13 4 4 13
# 14 4 4 14
# 15 0 8 FizzBuzz

OK。負数の剰余が嫌だったら "FizzBuzz"[i*i%3*4:8-i**4%5*4] でも良い。

まあ、だからと言ってこんなわかりにくいコードを書くのはPythonicじゃないけど…


もっと短くてもう少し分かりやすいコードがこちら
FizzBuzz問題 - Engineer as a Lifestyle @tenkoma

for i in range(1,101):print"Fizz"*(i%3<1)+"Buzz"*(i%5<1)or i

(文字列)*(ブール値)なんて出来るのね…
ブール値が真ならその文字列、偽なら空文字列になる。（掛け算以外はできない）