8.1. 没頭しよう
正規表現が文字列にとってのステロイド剤であるように、itertoolsモジュールはイテレータにステロイド剤を投与します。まずは、古典的なパズルを見てみましょう。
HAWAII + IDAHO + IOWA + OHIO == STATES 510199 + 98153 + 9301 + 3593 == 621246 H = 5 A = 1 W = 0 I = 9 D = 8 O = 3 S = 6 T = 2 E = 4
このパズルは算術パズル(Cryptarithms、alphametics)と呼ばれています。アルファベットは意味のある単語になっていて、各アルファベットを0-9の数字に置き換えると計算式も"書き表す"ものです。 どの文字がどの数字に対応しているかを捻り出すのが面白いところです。同じ文字は同じ数字を表していて、同じ数字が複数の文字で繰り返し使われることはありません。また、0 で始まる"単語" はありません。
一番有名な算術パズルは、send + more=money です。 この章では、Raymond Hettingerによって書かれたPythonプログラムに没頭します。 このプログラムは、算術パズルをわずか14行で解いてしまいます。
import re import itertools def solve(puzzle): words = re.findall('[A-Z]+', puzzle.upper()) unique_characters = set(''.join(words)) assert len(unique_characters) <= 10, 'Too many letters' first_letters = {word[0] for word in words} n = len(first_letters) sorted_characters = ''.join(first_letters) + \ ''.join(unique_characters - first_letters) characters = tuple(ord(c) for c in sorted_characters) digits = tuple(ord(c) for c in '0123456789') zero = digits[0] for guess in itertools.permutations(digits, len(characters)): if zero not in guess[:n]: equation = puzzle.translate(dict(zip(characters, guess))) if eval(equation): return equation if __name__ == '__main__': import sys for puzzle in sys.argv[1:]: print(puzzle) solution = solve(puzzle) if solution: print(solution)
コマンドラインからプログラムを実行できます。Linuxでは、このようになります。(使っている コンピュータによっては少し時間がかかるかもしれません。プログレスバーはありませんから、辛抱しましょう！)
you@localhost:~/diveintopython3/examples$ python3 alphametics.py "HAWAII + IDAHO + IOWA + OHIO == STATES" HAWAII + IDAHO + IOWA + OHIO = STATES 510199 + 98153 + 9301 + 3593 == 621246 you@localhost:~/diveintopython3/examples$ python3 alphametics.py "I + LOVE + YOU == DORA" I + LOVE + YOU == DORA 1 + 2784 + 975 == 3760 you@localhost:~/diveintopython3/examples$ python3 alphametics.py "SEND + MORE == MONEY" SEND + MORE == MONEY 9567 + 1085 == 10652
8.2. パターンをすべてとらえる
算術パズルソルバはすべてのアルファベット文字 (A-Z)をはじめに探します。①reモジュールはPythonに正規表現を実装します。findall()という便利な関数があり、 正規表現パターンと文字列を受け取って、文字列内に現れるパターンをすべて見つけてくれます。 この場合、パターンは数字にマッチします。findalll()関数はパターンにマッチしたすべての文字列部分のリストを返します。>>> import re >>> re.findall('[0-9]+', '16 2-by-4s in rows of 8') # ① ['16', '2', '4', '8'] >>> re.findall('[A-Z]+', 'SEND + MORE == MONEY') # ② ['SEND', 'MORE', 'MONEY']
②アルファベットにマッチする正規表現パターンです。ここでも返り値は正規表現パターンにマッチした要素が入ったリストです。
この例は頭の体操になります。
驚きではないでしょうか？正規表現が探すのはこのような並びです。スペース、ｓ、最短の文字の並び(.*?)、スペース、s。入力文字列を見ていると、5つマッチします。>>> re.findall(' s.*? s', "The sixth sick sheikh's sixth sheep's sick.") [' sixth s', " sheikh's s", " sheep's s"]
The sixth sick sheikh's sixth sheep's sick.The sixth sick sheikh's sixth sheep's sick.The sixth sick sheikh's sixth sheep's sick.The sixth sick sheikh's sixth sheep's sick.The sixth sick sheikh's sixth sheep's sick.
これは算術パズルソルバーとは関係ありません。面白いと思ったので挙げただけです。
8.3. シーケンスの中で重複していない値を探す
setを使うとシーケンスの中で重複していない値を簡単に探すことができます。>>> a_list = ['The', 'sixth', 'sick', "sheik's", 'sixth', "sheep's", 'sick'] >>> set(a_list) # ① {'sixth', 'The', "sheep's", 'sick', "sheik's"} >>> a_string = 'EAST IS EAST' >>> set(a_string) # ② {'A', ' ', 'E', 'I', 'S', 'T'} >>> words = ['SEND', 'MORE', 'MONEY'] >>> ''.join(words) # ③ 'SENDMOREMONEY' >>> set(''.join(words)) # ④ {'E', 'D', 'M', 'O', 'N', 'S', 'R', 'Y'}
①文字列のリストに対してset()関数はリストの中で重複していない文字列を返します。これはforループと同じだと考えると理解しやすくなります。リストの最初の要素を取り出し、セットの中に入れます。続いて2、3、4番目を入れます。5番目を・・・待ってください、その要素はすでにセットの中にあります。Pythonのsetは重複を許さないため、1つしか入りません。6番目が入りません。7番目もまた重複しているので、1つしかセットに入りません。結果は、元のリストの重複を無くしたものになります。元のリストを最初に並べ替える必要もありません。
②文字列に対しても同じ方法が可能です。文字列は文字の並びに過ぎないからです。
③文字列のリスト(a_list)に対して、".join(a_list)"を使うとすべての文字列を1つに結合します。
④このコードは、リストの中のすべての文字列で使われるすべてのユニークな文字を重複なしで返します。
算術パズルソルバはパズルの重複しない文字のセットをこのようにして作っています。
このリストは、あとでソルバーが想定されうる解でイテレートするときに、数字を文字に代入するために使います。unique_characters = set(''.join(words))
8.4. アサーションを作る
他のプログラミング言語のように、Pythonにもアサート文があります。このようになります。
>>> assert 1 + 1 == 2 # ① >>> assert 1 + 1 == 3 # ② Traceback (most recent call last): File "", line 1, in AssertionError >>> assert 2 + 2 == 5, "Only for very large values of 2" # ③ Traceback (most recent call last): File " ", line 1, in AssertionError: Only for very large values of 2
①アサート文のあとには、どんなPython表記が続いてもかまいません。この場合、1+1==2はTrueですから、assert文は何もしません。
②ところが、Python表記がFalse判定であれば、assert文はAssertionErrorを出します。
③人間が読む用のメッセージを書いておくとAssertionErrorのときに出力できます。すなわち、このコード
は、以下と等価です。assert len(unique_characters) <= 10, 'Too many letters'
算術パズルソルバでは上のアサート文を使っていて、パズルに使われている文字が重複なしで10文字より多いとわかったら、その時点で離脱します。各文字には重複しない数字が割り当てているため、10文字より多く使われているパズルはどうやっても解けないからです。if len(unique_characters) > 10: raise AssertionError('Too many letters')
8.5. ジェネレータ内包表記
ジェネレータ内包表記は、関数のないジェネレータ関数のようなものです。
>>> unique_characters = {'E', 'D', 'M', 'O', 'N', 'S', 'R', 'Y'} >>> gen = (ord(c) for c in unique_characters) # ① >>> gen # ②at 0x00BADC10> >>> next(gen) # ③ 69 >>> next(gen) 68 >>> tuple(ord(c) for c in unique_characters) # ④ (69, 68, 77, 79, 78, 83, 82, 89)
①ジェネレータ内包表記は、値を生み出す匿名関数のようなものです。リスト内包表記のように見えますが、この表記では四角括弧ではなく丸括弧で囲まれています。
②ジェネレータ表記はイテレータを返します。
③next(gen)を呼び出すとイテレータの次の値が得られます。
④ジェネレータ表記をtuple()、list()、set()に渡し、条件を満たす値をすべて繰り返してタプル、リスト、セットを返すこともできます。このときは括弧は追加する必要はなく、ord(c) for c in unique_characters を"裸"のままtuple()関数に渡すだけでPythonはジェネレータ表記だと解釈してくれます。
👉リスト内包表記の代わりにジェネレータ表記を使うと、CPUとRAMの 節約になります。リストを作ってすぐに捨ててしまうのであれば(例えばtuple()、 set()に渡してしまうのであれば)、ジェネレータ表記を使いましょう！
こちらがジェネレータ関数を使った例です。
def ord_map(a_string): for c in a_string: yield ord(c) gen = ord_map(unique_characters)
ジェネレータ表記の方がコンパクトに書けますが、機能は同じです。
8.6. 順列の計算・・・ラクな方法で!
まず最初に、順列 (置換)とは何でしょうか？ 順列は、数学の概念です。(実際には数学の中でもいくつかの定義があります。ここでは順列/組み合わせについて話しますが、意味がわからなくても心配しないでください。いつものように、Wikipediaが友達です)
何かのリスト(数字、文字、踊るクマでもよいです)を小さなリストに分ける方法をすべて見つける、ということを考えてみましょう。
小さい方のリストはすべて同じサイズでなくてはなりません。サイズは1でもよいですし、全要素数になってもかまいません。どの要素も繰り返すことはできません。 数学者はこんな言い方をします―「3つの異なる要素のから2つを1度にとる順列を探そう」と。3要素のシーケンスがあるとき、順番のあるペアで可能な組み合わせをすべて見つけたい、ということです。
>>> import itertools # ① >>> perms = itertools.permutations([1, 2, 3], 2) # ② >>> next(perms) # ③ (1, 2) >>> next(perms) (1, 3) >>> next(perms) (2, 1) # ④ >>> next(perms) (2, 3) >>> next(perms) (3, 1) >>> next(perms) (3, 2) >>> next(perms) # ⑤ Traceback (most recent call last): File "", line 1, in StopIteration
①itertoolsモジュールにはいろいろと面白いものがあり、その中でpermutations()という関数があります。この関数は、組み合わせを探すという難しい仕事をすべてやってくれるのです。
②permutations()関数は、シーケンス（ここでは3つの整数のリスト）と数字を受け取ります。数字は小さいグループにいくつ要素を入れるかを示します。
③[1,2,3]から2つを取り出す組み合わせの最初は(1,2)でした。
④組み合わせには順序があることを注意します。(2,1)は(1,2)とは別のものです。
⑤これで終了です！ [1,2,3]から2つを取り出す組み合わせはこれですべて出ました。(1,1)、(2,2)といったペアが出てこないのは、同じ数字の繰り返しは有効な組み合わせではないからです。それ以上組み合わせがなくなると、イテレータはStopIteration例外を出します。
Permutations()関数は必ずしもリストを受け取らないといけないわけではありません。どんなシーケンスでも ― 文字列でもかまいません。
>>> import itertools >>> perms = itertools.permutations('ABC', 3) # ① >>> next(perms) ('A', 'B', 'C') # ② >>> next(perms) ('A', 'C', 'B') >>> next(perms) ('B', 'A', 'C') >>> next(perms) ('B', 'C', 'A') >>> next(perms) ('C', 'A', 'B') >>> next(perms) ('C', 'B', 'A') >>> next(perms) Traceback (most recent call last): File "", line 1, in StopIteration >>> list(itertools.permutations('ABC', 3)) # ③ [('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]
①文字列は文字のシーケンスです。順列を探すとき、文字列ABCはlist[A,B,C]と等価です。
②['A', 'B', 'C']の3要素から3つを取り出す順列の最初のパターンは('A', 'B', 'C')です。他にも5つの順列があります ― 同じ3文字で、考えられるすべての並べ方です。
③permutations()関数は常にイテレータを返すので、そのイテレータをlist()に入れてすべての順列をその場で見ることで順列を簡単に確認することができます。
8.7. itertoolsモジュールにあるその他の面白いもの
>>> import itertools >>> list(itertools.product('ABC', '123')) # ① [('A', '1'), ('A', '2'), ('A', '3'), ('B', '1'), ('B', '2'), ('B', '3'), ('C', '1'), ('C', '2'), ('C', '3')] >>> list(itertools.combinations('ABC', 2)) # ② [('A', 'B'), ('A', 'C'), ('B', 'C')]
①itertools.product()関数は、順序のある2つのシーケンスの直積集合を返します。
②itertools.combinations()関数は、シーケンスと長さを受け取って、すべての可能な組み合せを返します。これはitertools.pemutations() 関数と似ていますが、組み合せの場合は順番が違うだけの同じ要素は力ウントしません。つまりitertools.permutations('ABC', 2)には('A', 'B')と ('B', 'A') がどちらも含まれますが、itertools.combinations('ABC', 2)は、('A', 'B')を並び替えた('B', 'A')を返すことはありません。
>>> names = list(open('examples/favorite-people.txt', encoding='utf-8')) # ① >>> names ['Dora\n', 'Ethan\n', 'Wesley\n', 'John\n', 'Anne\n', 'Mike\n', 'Chris\n', 'Sarah\n', 'Alex\n', 'Lizzie\n'] >>> names = [name.rstrip() for name in names] # ② >>> names ['Dora', 'Ethan', 'Wesley', 'John', 'Anne', 'Mike', 'Chris', 'Sarah', 'Alex', 'Lizzie'] >>> names = sorted(names) # ③ >>> names ['Alex', 'Anne', 'Chris', 'Dora', 'Ethan', 'John', 'Lizzie', 'Mike', 'Sarah', 'Wesley'] >>> names = sorted(names, key=len) # ④ >>> names ['Alex', 'Anne', 'Dora', 'John', 'Mike', 'Chris', 'Ethan', 'Sarah', 'Lizzie', 'Wesley']
①こう書くと、テキストファイルを行ごとにリストにしたものが返ります。
②残念なことに、この例の list(open(filename))では行の末尾に改行が入っています。この内包表記ではrstrip()という文字列メソッ ドを使って各行の行末空白を削除しています。(文字列には lstrip()メソッ ドという行頭の空白を消す方法、strip()メソッドという両方を消す方法があります)
③sorted()関数はリストを受け取ってソートします。デフォルトではアルフアベット順のソートです。
④sorted()関数にkeyパラメータを渡して、そのkeyの順にソートすることが可能です。今の場合、ソート関数のkeyは len()なので、各要素の長さでソートするので、名前の短いものが先になります。 これがitertoolsモジュールとどう関係があるのかって？よくぞ間いてくれました。
…前の対話型シェルからのつづき… >>> import itertools >>> groups = itertools.groupby(names, len) # ① >>> groups>>> list(groups) [(4, ), (5, ), (6, )] >>> groups = itertools.groupby(names, len) # ② >>> for name_length, name_iter in groups: # ③ ... print('Names with {0:d} letters:'.format(name_length)) ... for name in name_iter: ... print(name) ... Names with 4 letters: Alex Anne Dora John Mike Names with 5 letters: Chris Ethan Sarah Names with 6 letters: Lizzie Wesley
①itertools.groupby()関数は、シーケンスとキー関数を受け取ってそのペアを作るイテレータを返します。各ペアにはキー関数の結果と、その結果に当てはまるすべての要素を含むイテレータが返ります。
②list()関数を呼び出すと、イテレータを”出し尽くし”ます。つまり、各イテレータに対して要素を生成して、リストを作ります。イテレータには"リセットボタン"はないので、出し尽くしたあとにやり直すことはできません。再度ループしたいのであれば、（例えば、次のループで）itertools.groupby()をもう一度呼び出して新しいイテレータを作る必要があります。
③この例では、文字数ですでにソートされた名前のリストが与えられ、itertools.groupby(names, len)によって4文字の名前はすべて1つのイテレータが入れられ、5文字の名前はすべて別のイテレータに入れられる、ということになります。groupby()関数はかなりの汎用性があります。文字列を最初の文字でグループ化したりするなど、考えられる他のどんなキー関数でも分類できます。
👉 itertools.groupby()関数が動作するのは入力シーケンスがグループ化関数で先にソートしてある場合に限ります。上の例では、namesリストをlen()関数でグループ化しました。入力したリストはすでに長さでソートされていたため、動作したのです。
ついてこれていますか？
>>> list(range(0, 3)) [0, 1, 2] >>> list(range(10, 13)) [10, 11, 12] >>> list(itertools.chain(range(0, 3), range(10, 13))) # ① [0, 1, 2, 10, 11, 12] >>> list(zip(range(0, 3), range(10, 13))) # ② [(0, 10), (1, 11), (2, 12)] >>> list(zip(range(0, 3), range(10, 14))) # ③ [(0, 10), (1, 11), (2, 12)] >>> list(itertools.zip_longest(range(0, 3), range(10, 14))) # ④ [(0, 10), (1, 11), (2, 12), (None, 13)]
①itertools.chain()関数は2つのイテレータを受け取り、1つ目、2つ目という順ですべての要素を持つイテレータを返します（実際には、何個でもイテレータを受け取ることができます。渡された順に繋いでいきます）。
②zip()関数は単純なことをやっているのですが、非常に役に立つことがわかります。シーケンスをいくつでも受け取り、各シーケンスの最初の要素を1つのタプルにして、次に2番目の要素をまとめて、さらに3番目へと続いてタプルを作ります。
③zip()関数は一番短いシーケンスが終わるとストップします。range(10, 14)には4要素(10, 11, 12, 13)がありますが、range(0, 3)には3要素しかないので、zip()関数は3要素のイテレータを返します。
④一方で、itertools.zip_longest()関数は、最も長いシーケンスの終点でストップします。短いシーケンスの要素がない部分にはNone値を挿入します。
オーケー、とても勉強になります。しかし、これがalphameticsソルバーとどう関係するのでしょうか？それを見ていきましょう。
①文字のリストと数字のリスト（長さ1の文字列）をzip関数に入れると、文字と数字を順の決まったペアにします。>>> characters = ('S', 'M', 'E', 'D', 'O', 'N', 'R', 'Y') >>> guess = ('1', '2', '0', '3', '4', '5', '6', '7') >>> tuple(zip(characters, guess)) # ① (('S', '1'), ('M', '2'), ('E', '0'), ('D', '3'), ('O', '4'), ('N', '5'), ('R', '6'), ('Y', '7')) >>> dict(zip(characters, guess)) # ② {'E': '0', 'D': '3', 'M': '2', 'O': '4', 'N': '5', 'S': '1', 'R': '6', 'Y': '7'}
②なぜこれがクールなのでしょうか？文字をキー、対応する数字を値としてdict()関数に渡すして、辞書を作るときとデータ構造がたまたま同じだからです（もちろん、これが唯一の方法ではありません。辞書内包表記を使って辞書を直接作ることもできます）。
出力された辞書ではペアが違う順になっていますが（辞書には順序がないからです）、元のcharacters、guessシーケンスに応じて各文字が数字に対応しているのがわかるでしょう。
alphameticsソルバーはこのテクニックを使って、可能性のある解それぞれに対して辞書を作り、パズルの文字を数字に当てはめます。
characters = tuple(ord(c) for c in sorted_characters) digits = tuple(ord(c) for c in '0123456789') ... for guess in itertools.permutations(digits, len(characters)): ... equation = puzzle.translate(dict(zip(characters, guess)))
このtranslate()メソッドとは何でしょうか？ここが一番楽しいところです。
8.8. 新しい文字列操作
Pythonの文字列には多くのメソッドがあります。例えば、文字列の章で学んだlower()、count()、format()などです。ここでは、あまり知られていませんが強力な文字列操作をテクニックである、translate()メソッドを紹介しましょう。>>> translation_table = {ord('A'): ord('O')} # ① >>> translation_table # ② {65: 79} >>> 'MARK'.translate(translation_table) # ③ 'MORK'
①文字列翻訳はtranslation_tableから始まりますが、これはある文字を別の文字に対応させる辞書です。実は、"文字"と言うと正しくありません。厳密には、translation_tableは1バイトを別のバイトに対応させているのです。
②覚えているでしょうか、Python3でバイトは整数でした。ord()関数は文字のascii値を返しますが、A-Zに対するバイトは常に65-90です。
③文字列のtranslate()メソッドはtranslation_tableを受け取って、すみずみまで見渡します。つまり、翻訳テーブルのキーが現れたらすべてを対応する値に置き換えるのです。この場合はMARKをMORKに"翻訳"します。
ここが本当に楽しいところです。
アルファベットパズルとどう関係しているでしょうか？これから判明しますが、すべてに関係しています。
>>> characters = tuple(ord(c) for c in 'SMEDONRY') # ① >>> characters (83, 77, 69, 68, 79, 78, 82, 89) >>> guess = tuple(ord(c) for c in '91570682') # ② >>> guess (57, 49, 53, 55, 48, 54, 56, 50) >>> translation_table = dict(zip(characters, guess)) # ③ >>> translation_table {68: 55, 69: 53, 77: 49, 78: 54, 79: 48, 82: 56, 83: 57, 89: 50} >>> 'SEND + MORE == MONEY'.translate(translation_table) # ④ '9567 + 1085 == 10652'
①ジェネレータ表記を使って文字列の各文字のバイト値を即座に計算します。charcterはalphametics.solve()関数のsorted_charactersの一例です。
②もう1つジェネレータ表記を使って、数字の列のバイトを計算します。結果は、guessはalphametics.solve()関数のitertools.permutations()関数の形で返ります。
③translation_tableはcharactersとguessをzip()関数に入れてできたペアのシーケンスでできた辞書です。これこそがalphametics.solve()関数がforループの中でやっていることです。
④最後に、この翻訳テーブルを元のパズル文字列のtranslate()メソッドに入れます。これで文字列の各文字が対応する数字に変換されます（charactersの文字とguessの数字に基づきます）。
結果は文字列として正しいPython表記となります。素晴らしいですね。しかし、文字列がPython表記として正しかったら、何ができるのでしょうか？
8.9. 任意の文字列をPythonの表現として評価する
これがパズルの最終ピースです（もしくは、パズルを解く最終ピースというべきでしょうか）。文字列の楽しい操作がすべて終わって、'9567 + 1085 == 10652' という文字列が得られました。これは文字列なのですが、文字列だと何がよいのでしょうか？Pythonのユニバーサルな評価ツールであるeval()を入力してみましょう。
>>> eval('1 + 1 == 2') True >>> eval('1 + 1 == 3') False >>> eval('9567 + 1085 == 10652') True
待ってください、もっとありますよ！eval()関数はブーリアン判定に限りません。Pythonのどんな表現にも使えて、どんなデータ型でも返します。
>>> eval('"A" + "B"') 'AB' >>> eval('"MARK".translate({65: 79})') 'MORK' >>> eval('"AAAAA".count("A")') 5 >>> eval('["*"] * 5') ['*', '*', '*', '*', '*']
待ってください、まだ終わりませんよ！
>>> x = 5 >>> eval("x * 5") # ① 25 >>> eval("pow(x, 2)") # ② 25 >>> import math >>> eval("math.sqrt(x)") # ③ 2.2360679774997898
①eval()という表現は、eval()の外側で定義されたグローバル変数を参照することができます。関数内で呼び出された場合は、ローカル変数を参照することもできます。
②関数を参照しています。
③モジュールを参照しています。
やれやれ、ちょっと待ってください・・・
①subprocessモジュールを使うと、任意のシェルコマンドを走らせて結果をPython文字列として得ることができます。>>> import subprocess >>> eval("subprocess.getoutput('ls ~')") # ① 'Desktop Library Pictures \ Documents Movies Public \ Music Sites' >>> eval("subprocess.getoutput('rm /some/random/file')") # ②
②シェルコマンドは好きなようにどこまでも続いても構いません。
さらに悪いことがあります。なぜなら、グローバル関数__import__()はモジュール名を文字列として受け取って、モジュールをインポートし、参照されたものを返します。eval()の力と組み合わせて、すべてのファイルを消す1行表現を作ることができます。
①出力は'rm -rf ~' になるはずだと思うことでしょう。実際、何も出力されませんが、ファイルは何も残されていません。>>> eval("__import__('subprocess').getoutput('rm /some/random/file')") # ①
eval() は EVIL
EVIL(邪悪)だというのは、信用できないソースから得た表現を評価してしまうということです。eval()を使うときは、入力が信用できるときに限るべきです。もちろん、何を"信用できる"とするかが、難しいところです。
しかし、確かなことがあります。このalphameticsソルバーを使ってWebサービスにちょっとした遊びとして埋め込んだりしてはいけません。こんな誤解をしないでください。「おー！この関数は文字列が判定される前に文字列操作をたくさんしてるぞ。どうやって開発したが想像できない」というように。きっと誰かが文字列操作の前にある実行可能コードの解読方法を発見して（もっとおかしなことが起こったのです)、サーバにサヨウナラすることになります。
表現が安全かどうか評価する方法はないのでしょうか？eval()をアクセスしたり外側から攻撃できないサンドボックスに入れてしまいますか？それはイエスであり、ノーです。
>>> x = 5 >>> eval("x * 5", {}, {}) # ① Traceback (most recent call last): File "", line 1, in File " ", line 1, in NameError: name 'x' is not defined >>> eval("x * 5", {"x": x}, {}) # ② 25 >>> import math >>> eval("math.sqrt(x)", {"x": x}, {}) # ③ Traceback (most recent call last): File " ", line 1, in File " ", line 1, in NameError: name 'math' is not defined
①eval()関数に渡されるパラメータの2、3番目は、表記を評価するグローバル、ローカル名前空間です。 この場合どちらも空で、"x*5"という文字列が評価されますが、xにはグローバル名前空間もローカル名前空間も存在しないということになり、eval() は例外を出します。
②特定の値を、選択的にグローバル名前空間に入れるためには、個別に列記します。そうすると、書かれた変数"だけ"は評価の間は使えることになります。
③mathモジュールをインポートしたばかりですが、eval()関数に渡される名前には入れていないため、評価は失敗します (*eval("math.sqrt(x)", {"x":x "math": math,{}) とやればできます)。
やった！簡単でしたね。アルファメティクスwebサービスを作ってみましょう！
>>> eval("pow(5, 2)", {}, {}) # ① 25 >>> eval("__import__('math').sqrt(5)", {}, {}) # ② 2.2360679774997898
①グローバル、ローカル名を空にした辞書を渡しても、Pythonのビルトイン 関数は評価の間使えます。つまり、pow(52)は使うことができます。5, 2 は定数で、pow()はビルトイン関数だからです。
②残念ながら(何が残念なのかは、読んでいけばわかります）、__import__()関数もまたビルトイン関数なので、動作します。そう、つまり無茶なことができるのです。eval()関数を呼び出したときに、敢えてグローバル、ロー力ル名前空間が空の辞書を使っても動作するのです。
おっと。アルファメティクスwebサービスを作らないで良かったですね。 eval()を安全に使う方法はないでしょうか？答えはイエスでありノーです。>>> eval("__import__('subprocess').getoutput('rm /some/random/file')", {}, {})
①信頼性のない表現が安全かどうか判定するには、グローバル名前空間の辞書を定義して、”__builtins__"をNoneに対応させます。 Python内部では、ビルトイン関数はは擬似的モジュール"__bultins__"の中に含まれています。このモジュールのようなもの(例えば、ビルトイン関数の集まり)、は明確に上書きしない限り、表記を判定します。>>> eval("__import__('math').sqrt(5)", ... {"__builtins__":None}, {}) # ① Traceback (most recent call last): File "", line 1, in File " ", line 1, in NameError: name '__import__' is not defined >>> eval("__import__('subprocess').getoutput('rm -rf /')", ... {"__builtins__":None}, {}) # ② Traceback (most recent call last): File " ", line 1, in File " ", line 1, in NameError: name '__import__' is not defined
②_bultins_を上書きしたことを確認ましょう。__bultin__ではなく、__bultins__です。他のバリエーションでも正常に動作しますが、壊滅する危険性があります。ということで、eval()は安全になったでしょうか？そう、イエスであり、ノーです。
①たとえ__buitins__にアクセスしなくても、DoS攻撃を始められます。例えば、2 の2147483647乗を与えると、サーバのCPU使用率は長時間 100%になってしまいます(これを対話型シェルでやる場合、Ctrl-Cを数秒間押せば止めることができます) 。正確には、この表記はある値を最終的には返すのですが、しばらくの間、サーバ は意味のないことをし続けます。>>> eval("2 ** 2147483647", ... {"__builtins__":None}, {}) ①
最終的には信頼性のないPython表記を安全に評価することができるようになります。ここでの"安全"の定義は、実生活とかけ離れたものです。遊んでいても大丈夫で、信頼できる入力を入れた場合は大丈夫ということになります。しかし、そうでないものはすべてトラブルを呼ぶことになります。
8.10. まとめ
総括すると、このプログラムはアルファーティクス・パズルを力技で解きます。可能性のある解を網羅的に検索するのです。このために以下のことをやります。
- refindal()関数でパズルのすべての文字を見つける
- sets, set()関数でパズルで使われるユニークな文字を見つける
- assert文でその文字が10以内であることをチェックする (確かに解けるこ とを確認する)
- ジェネレータオブジェクトで文字をASCIIに変換する
- iertools.permutations()で可能性のある解をすべて計算する
- 文字列メソッドtranslate()を使って、可能性のある解をPython表記に置き換える
- 可能性のある解をPython表記として eval()関数で評価してテストする
- True判定が出た最初の解を返す
0 件のコメント:
コメントを投稿