summer_tree_home

Check iOでPython3をマスターするぜっ

Restricted Prime (Incinerator) - 素数の判定、ただし制限あり

Python CheckiO

どんな問題？

Restricted Prime
http://www.checkio.org/mission/restricted-prime/

与えられた数字が素数かどうかを判定せよ。
ただし、「import, div, eval, range, len, / % -, 0-9」は使ってはならない。
数字は 0 < n < 10000 とする。

Restricted sum の続編という位置づけ。
ちなみに、lenを使ってはいけない、というのは len() 関数を使ったらダメってのはもちろんだが、関数名や変数名に len が含まれている場合（例えば length）でも不可、コメント中でも不可だ。ただし、大文字にして Len や LEN ならOKだ。

例題：

checkio(5) == True
checkio(18) == False

どうやって解く？

まずは、制限を考えずに、素数の判定を考えてみる。
素数とは1とその数以外に割れない数だから、

def is_prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

これでいいはず。あとで検算用に使おう。

これをベースにして、禁止ワードを書き換えてみる。まず、range()を使わないように forループを while で置き換えてみる。

def checkio(n):
    i = 2
    while i < n:
        if n % i == 0:
            return False
        i += 1
    return True

次は、% をどうにかしたい。n が i で割り切れるかどうかを調べればいいのだから、これも while で書き換えできそうだ。

def is_divisible(n, d):
    # nがdで割り切れるか（nもdも正の数とする）
    temp = d
    while True:
        if temp == n:
            return True
        elif temp > n:
            return False
        temp += d

あとは、

def checkio(n):
    i = 2
    while i < n:
        if is_divisible(n, i):
            return False
        i += 1
    return True

これでOK
Run & Check!
おっと、関数名にdivが含まれているので FAIL になってしまった。
is_Divisibleにしておく。（divはダメでも、Divなら大丈夫なのだ。）

さて、Run & Check!
またもFAIL。2 が含まれている。
そうか、数字もダメだっけ。

ONE = '*'.count('*')
TWO = '**'.count('*')

として、数字の1,2の代わりに使おう。

そもそも、range関数が使えないなら、自作すればいいんじゃないか。

def Range(start, stop):
    i = start
    while i < stop:
        yield i
        i += 1

これで、ちょっと見やすくなるかな。

ONE = '*'.count('*')
TWO = '**'.count('*')

def Range(start, stop):
    i = start
    while i < stop:
        yield i
        i += ONE

def is_Divisible(n, d):
    temp = d
    while True:
        if temp == n:
            return True
        elif temp > n:
            return False
        temp += d

def checkio(n):
    for i in Range(TWO, n):
        if is_Divisible(n, i):
            return False
    return True

じゃあ、これで公開しておこう。

見直してみると、なんか、もっと良い方法がある気がする。「%」が使えないなら、ExcelのMOD()みたいに剰余を返す関数を自作すればいいか。あれ？Pythonにmod()ってなかったっけ？調べてみたら、ビルトインにdivmod()というのがあるじゃないか。商と剰余をタプルで返す。

>>> divmod(14, 3)
(4, 2)

いや、ダメだ、名前にdivが含まれている。じゃあ、やっぱりMOD()を自作しよう。

def mod(n, d):
    m = n
    while m >= d:
        m -= d
    return m

これもダメか。「-」が含まれている。「-」を使わずに「-」を得ることはできないものか・・・。

文字列のfind()メソッドって見つからなければ、-1を返すんだっけ？

MINUS = ''.find('*')

def mod(n, d):
    m = n
    while m >= d:
        m += d * MINUS
    return m

これでどーだ！

まとめ(2)

MINUS = ''.find('*')
ZERO = ''.count('*')
ONE = '*'.count('*')
TWO = '**'.count('*')

def Range(start, stop):
    i = start
    while i < stop:
        yield i
        i += ONE

def mod(n, d):
    m = n
    while m >= d:
        m += d * MINUS
    return m

def checkio(n):
    for i in Range(TWO, n):
        if mod(n, i) == ZERO:
            return False
    return True

他の人の答え

うわー、みんなそれぞれ違ってて面白い。

まず、0,1を作るのに、boolを使っている人が多かった。

ZERO = int(False)
ONE = int(True)

ONE = True + False
TWO = True + True

なるほど。
今までDelphiやC#を使ってきたから、intとboolが変換可能ってのにどうも慣れない。

globals

evalが使えないと思ってあきらめていたが、globals()を使えば突破できるようだ。

evaI = globals()['__builtins__']['ev'+'al']

http://www.checkio.org/mission/restricted-prime/publications/DiEvAl/python-3/first/

特殊メソッド

Pythonでたまに見かける、__hoge__()という表記。これを特殊メソッドというそうだ。
例えば、「%」を使うかわりに、__mod__()を使うことができる。

>>> n = 14
>>> n % 3
2
>>> n.__mod__(3)
2

（参考）特殊メソッド名 - Dive Into Python 3 日本語版

ビット反転でマイナス

最初見たとき、なんだこれ？って思ったのがこちら。
http://www.checkio.org/mission/restricted-prime/publications/osa_k/python-3/how-to-negate-without-/

v += ~cur + one

「~」ってなんだっけ？…あー、ビット演算子か。ビット反転？なんでビット反転させて1を足してるの？？？

調べてみて、やっと理解できた。

Pythonにおけるビット反転は次のように定められています。
　-(a + 1)
元の値に1を加え、そして符号を反転させたものをビット反転演算子の結果と定められています。
ビット演算子 - 数値 - Python入門

へー、知らなかった。


この Restricted シリーズは勉強になるし面白いな。