現在地: ホーム Dive Into Python 3

難易度: ♦♦♦♦♢

高度なイテレータ

大ノミの背中には小ノミが棲み、彼らに背中を噛みつかれる。
小ノミの背中にはもっと小さいノミが棲み……と無限に続く。
— Augustus De Morgan

 

飛び込む

正規表現文字列にステロイドを与えるのと同様に、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

このようなパズルは、「クリプト算術」や「覆面算」と呼ばれている。これらの文字は実在の単語を綴っているが、各々の文字を0-9の数字で置き換えると、方程式を「綴る」ようにもなる。このパズルのカギは、どの文字にどの数字が対応するのかを見つけ出すことだ。この時、同じ文字には同じ数字を対応させなければならず、同じ数字を2つの文字に割り当てることもできず、さらにどの「単語」も0で始めてはならない。

この章では、元はRaymond Hettingerによって作成された、驚くべきPythonプログラムに飛び込んでいく。このプログラムは覆面算のパズルをたった14行のコードで解く。

[alphametics.pyをダウンロードする]

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

パターンの出現をすべて見つける

覆面算ソルバが最初に行うのは、そのパズルに含まれるすべての文字 (A–Z) を見つけ出すことだ。

>>> 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']
  1. reモジュールはPythonの正規表現の実装だ。このモジュールはfindall()という素敵な関数を持っている。この関数は、正規表現パターンと文字列を受け取り、その文字列の中にあるパターンの出現をすべて見つけ出す。この場合は、パターンは数字の並びにマッチする。findall()関数は、パターンにマッチしたすべての部分文字列のリストを返す。
  2. この正規表現のパターンは文字の並びにマッチする。ここでも戻り値はリストであり、リストの各要素は正規表現パターンにマッチした文字列だ。

次の例も、頭をすこしストレッチしてくれる。

>>> re.findall(' s.*? s', "The sixth sick sheikh's sixth sheep's sick.")
[' sixth s', " sheikh's s", " sheep's s"]

意外だっただろうか? この正規表現が探すのは、空白、s、すべての文字のできるだけ短い繰り返し (.*?)、空白、そしてもうひとつのsだ。さて、入力文字列を見ると、5つのマッチが目に入る:

  1. The sixth sick sheikh's sixth sheep's sick.
  2. The sixth sick sheikh's sixth sheep's sick.
  3. The sixth sick sheikh's sixth sheep's sick.
  4. The sixth sick sheikh's sixth sheep's sick.
  5. The sixth sick sheikh's sixth sheep's sick.

だが、re.findall()関数は3つのマッチしか返していない。具体的は1つ目と3つ目と5つ目だ。これはなぜだろうか? 理由は、この関数は重なったマッチを返さないからだ。1つ目のマッチは2つ目に重なり合っているので、1つ目は返されるが2つ目はスキップされる。3つ目のマッチは4つ目に重なり合っているので、3つ目は返されるが4つ目はスキップされる。そして最後に5つ目が返される。マッチするのは5つではなく3つだ。

これが覆面算ソルバに影響を与えることはない。ただ興味深いと思って紹介しただけだよ。

シーケンスから重複を取り除く

集合を使うと、シーケンスから重複を取り除く作業が取るに足らないものになる。

>>> 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'}
  1. いくつかの文字列を持ったリストが与えられると、set()関数はリストから重複する要素を取り除いた集合を返す。これは、forループのように考えれば理解できる。リストから1つ目の要素を取って集合に入れる。2つ目を入れる。3つ目を入れる。4つ目を入れる。5つ目を……待った、5つ目はすでに集合に含まれている。Pythonの集合は重複を許さないので、これは一度しか追加されない。6つ目入れる。7つ目を……これも重複だ。よって、これも一度しか追加されない。最終的な結果はどうなっただろうか? 結果は元のリストから重複を取り除いたものとなる。あらかじめ元のリストをソートしておく必要すらないのだ。
  2. 文字列は文字のシーケンスなので、同様のテクニックは文字列でも機能する。
  3. 文字列のリストが与えられると、''.join(a_list)はすべての文字列を1つに連結する。
  4. つまりこの行のコードは、文字列のリストが与えられると、文字列にあるすべての文字から重複を取りのぞいたものを返す。

覆面算ソルバはこのテクニックを使って、パズルに含まれるすべての文字を含んだ集合を構築する。

unique_characters = set(''.join(words))

このリストは、あとでソルバが解候補をイテレートする際に、数字を文字に割り当てるために使われる。

表明する

多くのプログラミング言語と同様に、Pythonはassert文を持っている。これは次のように動作する。

>>> assert 1 + 1 == 2                                     
>>> assert 1 + 1 == 3                                     
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AssertionError
>>> assert 2 + 2 == 5, "Only for very large values of 2"  
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AssertionError: Only for very large values of 2
  1. assert文には、正しいPythonの式であれば何でも置ける。この場合、式1 + 1 == 2Trueと評価されるので、assert文は何もしない。
  2. しかし、もしPythonの式がFalseと評価された場合、assert文はAssertionErrorを送出する。
  3. AssertionErrorが起きた場合に表示するための、人間が読めるメッセージ含めておくこともできる。

つまり、コードのこの行は:

assert len(unique_characters) <= 10, 'Too many letters'

……これと同等だ:

if len(unique_characters) > 10:
    raise AssertionError('Too many letters')

覆面算ソルバは、パズルが10種類以上の文字を含んでいるときの緊急脱出手段としてassert文を使っている。各々の文字は一意な数字に割り当てられるわけだが、数字は10個しかないので、10種類以上の文字を持つパズルは解を持ち得ないのだ。

ジェネレータ式

ジェネレータ式は、関数を使わずに作るジェネレータ関数、という感じのものだ。

>>> unique_characters = {'E', 'D', 'M', 'O', 'N', 'S', 'R', 'Y'}
>>> gen = (ord(c) for c in unique_characters)  
>>> gen                                        
<generator object <genexpr> at 0x00BADC10>
>>> next(gen)                                  
69
>>> next(gen)
68
>>> tuple(ord(c) for c in unique_characters)   
(69, 68, 77, 79, 78, 83, 82, 89)
  1. ジェネレータ式は、値をyieldする匿名関数のようなものだと思えばいい。この式はリスト内包表記に似ているが、角括弧の代わりに丸括弧に包まれている。
  2. ジェネレータ式は……イテレータを返す。
  3. next(gen)の呼び出しによって、イテレータから次の値が返される。
  4. お望みなら、ジェネレータ式をtuple()list()set()に渡せば、すべての値がイテレートされてタプル・リスト・集合として返ってくる。これらの場合、余分な括弧は必要ない。つまり、tuple()関数に「はだか」の式ord(c) for c in unique_charactersを渡すだけで、Pythonがジェネレータ式だと識別してくれるのだ。

リスト内包表記の代わりにジェネレータ式を使うことで、CPU使用量とRAM使用量の両方を削減できる。もし作ったリストをすぐ投げ捨てるのであれば(つまり、それをtuple()set()に渡しているのなら)、代わりにジェネレータ式を使おう!

以下では、同じことをジェネレータ関数を使ってやっている:

def ord_map(a_string):
    for c in a_string:
        yield ord(c)

gen = ord_map(unique_characters)

ジェネレータ式のほうがコンパクトだが、機能的には同等だ。

順列を計算する…… 怠惰なやり方!

そもそも、順列というのは一体何だろう? 順列は数学の概念だ(実際には、数学の分野によっていくつかの定義がある。ここで私が話しているのは組み合わせ論についてのものだが、その意味がまったく分からなくても心配する必要はない。いつものことながら、Wikipediaはあなたの味方だ)。

順列というのはこういうものだ。あなたは何か(数字とか、文字とか、踊っている熊さんとか)のリストを受け取る。そして、そのリストから取り出せる小さなリストをすべて見つけ出す。この時、取り出すリストはすべて同じサイズにする。そのサイズは最小で1、最大で全要素の数にできる。加えて、リストを取り出す際には1つの要素を2回以上使ってはならない。数学者は、「3つの異なる要素から2つずつ取り出すときの順列を見つけましょう」というようなことを言うが、これが意味することは、あなたは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 "<stdin>", line 1, in <module>
StopIteration
  1. itertoolsモジュールには愉快なものがたくさん詰まっており、その中には、順列を見つけるという面倒な仕事をすべてやってくれるpermutations()関数も入っている。
  2. permutations()関数は、シーケンス(ここでは3つの整数からなるリスト)と数値を受け取る。この数値が個々の小さなグループの要素の数になる。この関数はイテレータを返すが、このイテレータはfor文のようなイテレートを行う場所でならどこでも使用できる。ここでは手動でイテレータを動かして、すべての値を示している。
  3. [1, 2, 3]から一度に2つずつ取り出したときの最初の順列は(1, 2)だ。
  4. 順列は順序付けされていることに注意しよう。(2, 1)(1, 2)は区別される。
  5. これで終わりだ! 以上が[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 "<stdin>", line 1, in <module>
StopIteration
>>> list(itertools.permutations('ABC', 3))    
[('A', 'B', 'C'), ('A', 'C', 'B'),
 ('B', 'A', 'C'), ('B', 'C', 'A'),
 ('C', 'A', 'B'), ('C', 'B', 'A')]
  1. 文字列は単なる文字のシーケンスだ。順列を見つけるという目的からは、文字列'ABC'はリスト['A', 'B', 'C']と等価だ。
  2. 3つの要素['A'、'B'、'C']から一度に3つずつ取るときの最初の順列は('A', 'B', 'C') だ。この他に5つの順列 — すなわち、この3文字の考えうる並べ方すべて — が存在する。
  3. permutations()関数は常にイテレータを返すので、順列をデバッグする簡易な方法として、イテレータを組み込みのlist()関数に渡すことで、順列の全体を即座に見るというやり方がある。

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')]
  1. itertools.product()関数は、2つのシーケンスの直積からなるイテレータを返す。
  2. itertools.combinations()関数は与えられたシーケンスについて、指定された要素の数からなる組み合わせ全部を取り出して、イテレーターとして返す。これはitertools.permutations()関数に似ているが、順序違いのものは含まないということが異なる。すなわち、itertools.permutations('ABC', 2)は、('A', 'B')('B', 'A')の両方を返すが、itertools.combinations('ABC', 2)は、('B', 'A')を返さない。なぜなら、これは('A', 'B')の順序を変えたものでしかないからだ。

[favorite-people.txtをダウンロードする]

>>> 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']
  1. このイディオムは、テキストファイルの行のリストを返す。
  2. (この例にとっては)都合が悪いことに、list(open(filename))というイディオムで処理すると、各行の末尾にある改行文字が残ってしまう。このリスト内包表記は、文字列メソッドのrstrip()を使って、文字列の後ろに付いている空白文字を各行から取り除いている(文字列は、先頭にある空白文字を取り除くためのlstrip()メソッドや、先頭と末尾の両方の空白文字を取り除くstrip()メソッドも持っている)。
  3. sorted()関数はリストを受け取って、そのリストをソートしたものを返す。デフォルトではアルファベット順にソートする。
  4. しかし、sorted()関数はkey引数として関数を受け取り、そのキーに基づいてソートを行うこともできる。この例では、ソート関数はlen()なので、これはlen(各要素)に基づいてソートを行う。短い名前が先に来て、次に長い名前、その後ろにもっと長い名前が続くというわけだ。

これがitertoolsモジュールと何の関係があるのかって? その質問を待っていた。

……前の対話シェルの続き……
>>> import itertools
>>> groups = itertools.groupby(names, len)  
>>> groups
<itertools.groupby object at 0x00BB20C0>
>>> list(groups)
[(4, <itertools._grouper object at 0x00BA8BF0>),
 (5, <itertools._grouper object at 0x00BB4050>),
 (6, <itertools._grouper object at 0x00BB4030>)]
>>> 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
  1. itertools.groupby()関数はシーケンスとキー関数を受け取り、ペアを生成するイテレータを返す。各々のペアには、key_function(each item)の値と、キー関数に渡したときにその値を返すような要素を集めたイテレータが入っている。
  2. list()関数を呼び出したことでイテレータは「使い果たされた」。つまり、リストを作るために、イテレータの要素をすべて生成しつくしたのだ。イテレータに「リセット」ボタンは無いので、一度使い果たしたら最初からやり直させることはできない。もう一度(例えば、次のforループで)イテレートしたいのであれば、再びitertools.groupby()を呼び出して新しいイテレータを作る必要がある。
  3. この例では、すでに長さでソートしてある名前のリストが与えられたので、itertools.groupby(names, len)は、4文字の名前をすべて1つのイテレータに入れ、5文字の名前をすべてもう1つのイテレータに入れ……というように同じ長さの名前を同じ1つのイテレータに入れてくれた。groupby()関数は完全に汎用的なので、文字列を最初の1文字でグループ分けすることもできるし、数字を因数の数で分類することもできる。思いつくキー関数ならどんなものでも使えるのだ。

itertools.groupby()関数は、入力されたシーケンスがグループ関数ですでにソートされているときにだけ機能する。上の例では、名前のリストを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)]
  1. itertools.chain()関数は、2つのイテレータを受け取って、1つ目のイテレータのすべての要素と、それに続いて2つ目のイテレータのすべての要素を含んだ1つのイテレータを返す(実は、任意数のイテレータを受け取ることができ、それらを関数に渡された順序で連結する)。
  2. zip()関数はつまらないことを行うのだが、実はこれはものすごく便利なことが分かる。この関数は任意の数のシーケンスを受け取り、各シーケンスの1つ目の要素からなるタプル、各シーケンスの2つ目の要素からなるタプル、3つ目の要素からなるタプル……を生成するイテレータを返す。
  3. zip()関数は、最も短いシーケンスの終わりで停止する。range(10, 14)は4つの要素 (10, 11, 12, 13) を持つが、range(0, 3)は3つしか持たないので、このzip()関数は3つの要素を持つイテレータを返す。
  4. その一方で、itertools.zip_longest()関数は最も長いシーケンスの終わりで停止する。短いシーケンスが尽きた後についてはNoneを挿入する。

OK、全部とても興味深いものだったけど、覆面算ソルバにはどんな関係があるのだろうか? それはこういうことだ:

>>> 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'}
  1. 文字のリストと数字(ここではそれぞれが1文字の文字列として表されている)のリストを与えると、zip関数は文字と数字のペアを順番通りに作成する。
  2. これのどこがクールなのだろうか? なんとこのタプルは偶然にも、dict()関数に渡すことで、「文字をキー、対応する数字を値とした辞書」を構築できる構造になっているのだ(もちろんこれは唯一の方法ではない。辞書内包表記を使って、この辞書を直接構築することだってできる)。表示された辞書の表現ではペアの順序が変わっているが(辞書は本質的に「順序」を持たない)、元のcharactersguessのシーケンス内の順序に基づいて、各文字に数字が対応付けられていることが見て取れるだろう。

覆面算ソルバは、パズルの文字を解の数字に対応させる辞書を作るために、各々の解候補に対してこのテクニックを使っている。

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()メソッドというのは何かって? それでは、これから本当に面白い部分に入っていくとしよう。

新種の文字列操作

Pythonの文字列は多くのメソッドを持っている。lower(), count(), format()といった一部のメソッドについては文字列の章で学んだ。今度は、パワフルだがほとんど知られていない文字列操作のテクニックであるtranslate()メソッドを紹介したいと思う。

>>> translation_table = {ord('A'): ord('O')}  
>>> translation_table                         
{65: 79}
>>> 'MARK'.translate(translation_table)       
'MORK'
  1. 文字列の変換は変換表の用意から始まる。これは、文字を他の文字に対応付けた単なる辞書だ。実を言うと「文字」と言ったのは不正確だ。実際には、変換表はバイトを他のバイトに対応させるのだ。
  2. 思い出して欲しい。Python 3のバイトは整数だ。ord()関数は文字のASCII値を返し、これはA–Zの場合、常に65から90までの1バイトになる。
  3. 文字列のtranslate()メソッドは変換表を受け取り、文字列をその変換表に通す。つまり、変換表のキーに一致する部分をすべて対応する文字に変換するのだ。この例では、MARKMORKに「変換 (translate)」している。

これが覆面算パズルを解くのとどう関係するのかって? 結論を言えば、これはすべてに関係しているのだ。

>>> 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'
  1. ジェネレータ式を使い、この文字列にある各々の文字のバイト値を素早く計算する。"SMEDONRY"は、alphametics.solve()関数におけるsorted_charactersの値の例だ。
  2. 別のジェネレータ式を使い、この文字列にある各々の数字のバイト値を素早く計算する。戻り値のguessは、alphametics.solve()関数においてitertools.permutations()関数によって返されるものと同じ形をしている。
  3. charactersguessをzipして、その戻り値のペアのシーケンスから辞書を構築することによって、この変換表は生成される。これは、alphametics.solve()関数がforループの中でやっていることそのものだ。
  4. 最後に、オリジナルのパズル文字列のtranslate()メソッドに変換表を渡す。これは、文字列の各文字を(charactersの文字とguessの数字にもとづいて)対応する数字に変換する。その結果は、有効なPythonの式を文字列として表したものになる。

これはずいぶん感動的だ。しかし、たまたま正しいPythonの式になった文字列を使って何ができるのだろうか?

任意の文字列をPythonの式として評価する

これはパズルの最後のピースだ(というより、パズルソルバの最後のピースと言うべきか)。手の込んだ文字列操作の末に、'9567 + 1085 == 10652'というような文字列が手に入った。しかし、これは文字列であって、文字列で何ができるというのだ? eval()の話に入ろう。これは、Pythonの式を評価するための万能ツールだ。

>>> 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
  1. eval()が受け取る式は、eval()の外側で定義されたグローバル変数を参照できる。関数の中で呼び出されたときはローカル変数も参照できる。
  2. 関数も参照できる。
  3. モジュールも参照できる。

話はもう少し……

>>> import subprocess
>>> eval("subprocess.getoutput('ls ~')")                  
'Desktop         Library         Pictures \
 Documents       Movies          Public   \
 Music           Sites'
>>> eval("subprocess.getoutput('rm /some/random/file')")  
  1. subprocessモジュールは、任意のシェルコマンドを実行し、その結果をPythonの文字列として受け取る機能を提供する。
  2. シェルコマンドの無制限な実行を許すと、とりかえしのつかない結果を招く可能性がある。

状況はもっと悪くなる。というのは、グローバルの__import__()関数が存在するからだ。この関数はモジュール名を文字列として受け取り、そのモジュールをインポートしてそれへの参照を返す。この関数とeval()の力を組み合わせれば、すべてのファイルを消し飛ばす式を作れるのだ:

>>> eval("__import__('subprocess').getoutput('rm /some/random/file')")  
  1. 'rm -rf ~'の実行結果を想像してみよう。実際には一切何も出力されないのだが、あなたのファイルは全て消え去ってしまう。

eval() is EVIL
eval()は邪悪

邪悪というのは、信頼できないところから入力された任意の式を評価してしまうことだ。eval()を使うのは、信頼している入力に対してだけにすべきだ。もちろん重要なのは「信頼している」とは何かを理解することであるが、確実に言えることがある: この覆面算ソルバを小さなおもしろWebサービスとしてインターネットに公開すべきではない。「え? この関数は文字列を評価する前に沢山の文字列操作をしてるんだから、これのセキュリティホールを突く方法を誰かが見つけ出すなんて想像できないや」という誤った考えをしてはいけない。きっと何者かが、すべての文字列操作を通過する気色悪い実行可能コードを忍び込ませる方法を見いだすだろう(奇妙なことは実際に起きている)。そうしたら、自分のサーバにキスして、お別れをしなければならない。

でも、式を安全に評価する何らかの方法は本当に無いの? 外の世界にアクセスしたり傷つけたりできないサンドボックスにeval()を入れる方法は無いの? うーん、それはイエスでもノーでもある。

>>> x = 5
>>> eval("x * 5", {}, {})               
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<string>", line 1, in <module>
NameError: name 'x' is not defined
>>> eval("x * 5", {"x": x}, {})         
>>> import math
>>> eval("math.sqrt(x)", {"x": x}, {})  
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<string>", line 1, in <module>
NameError: name 'math' is not defined
  1. eval()関数に渡された2つ目と3つ目のパラメータは、式を評価するときのグローバル名前空間とローカル名前空間として機能する。この場合は、両方が空になっている。このことは、"x * 5"という文字列が評価されるときに、グローバルとローカル名前空間のどちらにもxへの参照が存在しないということを意味するので、このeval()は例外を送出する。
  2. 値を一つ一つ列挙することによって、特定の値を選択的にグローバル名前空間に含めておける。そうすると、評価を行っているあいだは、これらの変数だけが利用できる。
  3. 直前でmathモジュールをインポートしているが、eval()関数に渡す名前区間にこれを含めていないので、この評価は失敗する。

おお、これなら簡単だ。覆面算ウェブサービスを作らせてよ!

>>> eval("pow(5, 2)", {}, {})                   
25
>>> eval("__import__('math').sqrt(5)", {}, {})  
2.2360679774997898
  1. 空の辞書をグローバル・ローカル名前空間に渡した場合でも、Pythonの組み込み関数ならどれでも評価の際に利用できる。つまりpow(5, 2)は問題なく評価される。52がリテラルで、pow()が組み込み関数だからだ。
  2. 不幸なことに(何が不幸なのか分からなければ、読み続けて欲しい)__import__()関数も組み込み関数なので、これも使えてしまう。

そう、これが意味するのは、たとえeval()を呼び出すときにグローバル・ローカル名前空間に空の辞書を明示的に設定したとしても、悪事を働けるということだ:

>>> eval("__import__('subprocess').getoutput('rm /some/random/file')", {}, {})

わぁ、覆面算ウェブサービスを作っていなくて良かったよ。eval()を安全に使う方法は何か無いの? うーん、イエスでもあり、ノーでもある。

>>> eval("__import__('math').sqrt(5)",
...     {"__builtins__":None}, {})          
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<string>", line 1, in <module>
NameError: name '__import__' is not defined
>>> eval("__import__('subprocess').getoutput('rm -rf /')",
...     {"__builtins__":None}, {})          
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<string>", line 1, in <module>
NameError: name '__import__' is not defined
  1. 信頼されていない式を安全に評価するには、"__builtins__"をPythonのNull値のNoneにマッピングしたグローバル名前空間を定義する必要がある。内部的には「組み込み」関数は"__builtins__"という疑似モジュールに含まれているのだ。この疑似モジュール(つまり、組み込み関数の集合)は、明示的に無効にしないかぎり、評価される式で使用できるようになっている。
  2. __builtins__が上書きされていることを確認しよう。これが__builtin____built-ins__のようなものになっていると、問題なく動作するにもかかわらず、恐ろしいリスクにさらされることになる。

じゃあ、eval()はもう安全? うーん、イエスでもノーでもある。

>>> eval("2 ** 2147483647",
...     {"__builtins__":None}, {})          
  1. __builtins__にアクセスできなかったとしても、なおDOS攻撃を仕掛けることはできる。例えば、22147483647乗は、長時間にわたってサーバのCPU使用率を100%に跳ね上げるだろう(これを対話シェルで試すときは、Ctrl-Cを何回か押して脱出しよう)。厳密にいえば、最終的にはこの式は実際に値を返すのだが、その間、サーバは無意味な処理に全力を注ぎ込むことになる。

最終的に、信頼されていないPythonの式を安全に評価できるようになった。ただし、現実世界ではほとんど役に立たない「安全」の定義においてだが。これは、遊びでつかう場合や、信頼された入力だけを渡すのであれば良いが、他のことに使うと災いを招くことになる。

まとめ

復習: このプログラムは、ブルートフォースによって(つまり、すべての解候補を総当り的に検索することによって)覆面算パズルを解く。これを行うために、このプログラムは……

  1. re.findall()関数を使って、パズルに含まれる文字をすべて見つける
  2. 集合とset()関数を使って、パズルに含まれるすべてのユニークな文字を見つける
  3. assert文を使って、10個以上のユニークな文字があるかチェックする(その場合、パズルは絶対に解けない)
  4. ジェネレータオブジェクトを使って、文字を対応するASCIIコードに変換する
  5. itertools.permutations()関数を使って、すべての解候補を求める
  6. 文字列メソッドのtranslate()を使って、すべての解候補をPythonの式に変換する
  7. eval()関数を使い、Pythonの式を評価することによってそれぞれの解候補をテストする
  8. Trueと評価された最初の解を返す

……これを14行のコードで行う。

もっと知りたい人のために

コードの再ライセンスに同意してくれたことについて、Raymond Hettingerに大変感謝している。そのおかげで、私はこのコードをPython 3へ移植することができ、この章の土台として使うことができた。

© 2001– Mark Pilgrim
© Fukada, Fujimoto(日本語版)