8章 高度なイテレータ

飛び込む

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

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

以下のプログラムは覆面算のパズルをたった14行のコードで解く。

In [1]:
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
            
        
    
In [2]:
solution = solve("HAWAII + IDAHO + IOWA + OHIO == STATES")
print(solution)
510199 + 98153 + 9301 + 3593 == 621246
In [3]:
solve("I + LOVE + YOU == DORA")
Out[3]:
'3 + 1458 + 946 == 2407'
In [4]:
solve('SEND + MORE == MONEY')
Out[4]:
'9567 + 1085 == 10652'

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

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

reモジュールはPython の正規表現の実装。 このモジュールはfindall()という関数を持っている。 この関数は、正規表現パターンと文字列を受け取り、 その文字列の中にあるパターンの出現をすべて見つけ出す。 この場合は、パターンは数字の並びにマッチする。 findall()関数は、パターンにマッチしたすべての部分文字列のリストを返す。

In [ ]:
import re
re.findall('[0-9]+', '16 2-by-4s in rows of 8')  
In [ ]:
re.findall('[0-9]+', '16 2-by-4s in rows of 8 00')  

この正規表現のパターンは、文字の並びにマッチする。 ここでも戻り値はリストであり、リストの各要素は正規表現パターンにマッチした文字列。

In [ ]:
re.findall('[A-Z]+', 'SEND + MORE == MONEY')

re.findall のマッチ

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

この正規表現が探すのは、空白、s、すべての文字のできるだけ短い繰り返し (.*?)、空白、そしてもうひとつのsだ。

入力文字列を見ると、5つのマッチがわかる:

  1. The( sixth s)ick sheikh's sixth sheep's sick.
  2. The sixth( sick s)heikh's sixth sheep's sick.
  3. The sixth sick( sheikh's s)ixth sheep's sick.
  4. The sixth sick sheikh's( sixth s)heep's sick.
  5. The sixth sick sheikh's sixth (sheep's s)ick.

re.findall()関数は3つのマッチしか返していない。 具体的は1つ目と3つ目と5つ目。

理由は、この関数は重なったマッチを返さない。

  • 1つ目のマッチは2つ目に重なり合っているので、1つ目は返されるが2つ目はスキップされる。
  • 3つ目のマッチは4つ目に重なり合っているので、3つ目は返されるが4つ目はスキップされる。
  • そして最後に5つ目が返される。

マッチするのは5つではなく3つになる。

' s.* s' だと最長マッチで終わり。

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

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

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

In [5]:
a_list = ['The', 'sixth', 'sick', "sheik's", 'sixth', "sheep's", 'sick']
a_list
Out[5]:
['The', 'sixth', 'sick', "sheik's", 'sixth', "sheep's", 'sick']

いくつかの文字列を持ったリストが与えられると、set()関数はリストから重複する要素を取り除いた集合を返す。 これは、forループのように考えれば理解できる。リストから1つ目の要素を取って集合に入れる。2つ目を入れる。3つ目を入れる。4つ目を入れる。 5つ目はすでに集合に含まれている。

Pythonの集合は重複を許さないので、これは一度しか追加されない。 6つ目入れる。7つ目を……これも重複だ。よって、 これも一度しか追加されない。 最終的な結果はどうなっただろうか? 結果は元のリストから重複を取り除いたものとなる。あらかじめ元のリストをソートしておく必要すらない。

In [6]:
set(a_list)
Out[6]:
{'The', "sheep's", "sheik's", 'sick', 'sixth'}
In [7]:
a_string = 'EAST IS EAST'

文字列は文字のシーケンスなので、同様のテクニックは文字列でも機能する。

In [8]:
set(a_string)
Out[8]:
{' ', 'A', 'E', 'I', 'S', 'T'}
In [9]:
words = ['SEND', 'MORE', 'MONEY']

文字列のリストが与えられると、.join(a_list) はすべての文字列を1つに連結する。

In [10]:
''.join(words)
Out[10]:
'SENDMOREMONEY'
In [11]:
','.join(words)
Out[11]:
'SEND,MORE,MONEY'

つまりこの行のコードは、文字列のリストが与えられると、 文字列にあるすべての文字から重複を取りのぞいたものを返す。

(文字列リストを連結して1つの文字列にして、文字の集合をつくる)

In [12]:
set(''.join(words))
Out[12]:
{'D', 'E', 'M', 'N', 'O', 'R', 'S', 'Y'}

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

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

In [13]:
unique_characters = set(''.join(words))

表明する(assert)

Pythonは assert文を持っている。

assert文には、正しいPythonの式であれば何でも置ける。 この場合、式1 + 1 == 2True と評価されるので、assert文は何もしない。

In [14]:
assert 1 + 1 == 2

しかし、もしPython の式が False と評価された場合、assert文は AssertionError を送出する。

In [15]:
assert 1 + 1 == 3
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-15-bbebc67e583c> in <module>()
----> 1 assert 1 + 1 == 3

AssertionError: 

AssertionError が起きた場合に表示するための、 人間が読めるメッセージ含めておくこともできる。

In [16]:
assert (2 + 2 == 5), "Only for very large values of 2"
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-16-0c1e852e77f5> in <module>()
----> 1 assert (2 + 2 == 5), "Only for very large values of 2"

AssertionError: Only for very large values of 2

以下のコード

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

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

は等価。

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

ジェネレータ式

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

In [17]:
unique_characters = {'E', 'D', 'M', 'O', 'N', 'S', 'R', 'Y'}

ジェネレータ式は、値をyield する匿名関数のようなものだと思えばいい。 この式はリスト内包表記に似ているが、角括弧の代わりに丸括弧に包まれている。

タプル内包表記はなくジェネレータ式になる。

In [18]:
gen = (ord(c) for c in unique_characters) 

ジェネレータ式はイテレータを返す。

In [19]:
gen
Out[19]:
<generator object <genexpr> at 0x000002571F24E468>

next(gen) の呼び出しによって、イテレータから次の値が返される。

In [20]:
next(gen)
Out[20]:
77
In [21]:
next(gen)
Out[21]:
89

ジェネレータ式をtuple()、list()、set()に渡せば、すべての値がイテレートされてタプル・リスト・集合として返すこともできる。 これらの場合、余分な括弧は必要ない。 つまり、tuple()関数に「はだか」の式ord(c) for c in unique_charactersを渡すだけで、 Pythonがジェネレータ式だと識別してくれる。

In [22]:
tuple(ord(c) for c in unique_characters)
Out[22]:
(77, 89, 82, 83, 68, 79, 78, 69)

ord関数は、文字(character) をユニコードのバイト(0-255の整数)に変える。

In [23]:
ord.__doc__
Out[23]:
'Return the Unicode code point for a one-character string.'

リスト内包表記の代わりにジェネレータ式を使うことで、

  • cpu使用量
  • ram使用量

の両方を削減できる。

もし作ったリストをすぐ投げ捨てるのであれば(つまり、それをtuple()やset()に渡しているのなら)、代わりにジェネレータ式を使う。

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

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

gen = ord_map(unique_characters)`

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

順列を計算(怠惰なやり方)

順列というのは、

  1. 何か(数字とか、文字とか、踊っている熊さんとか)のリストを受け取る。
  2. そして、そのリストから取り出せる小さなリストをすべて見つけ出す。
    • この時、取り出すリストはすべて同じサイズにする。そのサイズは最小で1、最大で全要素の数にできる。
    • 加えて、リストを取り出す際には1つの要素を2回以上使ってはならない。

数学者は、「3つの異なる要素から2つずつ取り出すときの順列を見つけましょう」というようなことを言うが、 これが意味することは、あなたは3つの要素からなるシーケンスを持っており、 その要素から作り出せるすべての順序対を見つけ出したいということ。

$$ {}_3 P_2 = 3 * 2 = 6通り $$

itertoolsモジュールの中には、 順列を見つけるという面倒な仕事をすべてやってくれる permutations()関数も入っている。

In [24]:
import itertools
itertools
Out[24]:
<module 'itertools' (built-in)>

permutations()関数は、

  • シーケンス(ここでは3つの整数からなるリスト)
  • 数値(個々の小さなグループの要素の数)

を受け取る。

この関数はイテレータを返すが、このイテレータはfor文のようなイテレートを行う場所でならどこでも使用できる。 ここでは手動でイテレータを動かして、すべての値を示している。

In [25]:
perms = itertools.permutations([1, 2, 3], 2)

[1, 2, 3] から一度に2つずつ取り出したときの最初の順列は(1, 2)

In [26]:
next(perms)
Out[26]:
(1, 2)
In [27]:
next(perms)
Out[27]:
(1, 3)
In [28]:
next(perms)
Out[28]:
(2, 1)

順列は順序付けされていることに注意。(2, 1)(1, 2) は区別される。

In [29]:
next(perms)
Out[29]:
(2, 3)
In [30]:
next(perms)
Out[30]:
(3, 1)
In [31]:
next(perms)
Out[31]:
(3, 2)

これで終わり. 以上が[1, 2, 3]から一度に2つずつ取り出したときのすべての順列。 (1, 1)や(2, 2)のようなペアは絶対に現れない。 これらは同じ要素が繰り返し使われているので、 正しい順列ではないのだ。 返す順列が無くなると、 イテレータはStopIteration例外 を送出する。

In [32]:
next(perms)
---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
<ipython-input-32-2f38aa3f83d9> in <module>()
----> 1 next(perms)

StopIteration: 

permutations() 関数はリストしか受け取れないわけではない。 これは任意のシーケンスを受けとれる. 文字列も受け取れる。

In [33]:
import itertools

文字列は単なる文字のシーケンス。 順列を見つけるという目的からは、 「文字列'ABC'はリスト['A', 'B', 'C']と等価」。

In [35]:
perms = itertools.permutations('ABC', 3)

3つの要素['A'、'B'、'C'] から一度に3つずつ取るときの最初の順列は ('A', 'B', 'C') 。 この他に5つの順列 — すなわち、この3文字の考えうる並べ方すべて — が存在する。

$$ {}_3 P_3 = 3 * 2 * 1 = 6通り $$
In [36]:
next(perms)
Out[36]:
('A', 'B', 'C')

permutations()関数は常にイテレータを返すので、 順列をデバッグする簡易な方法として、 イテレータを組み込みのlist()関数に渡すことで、 順列の全体を即座に見るというやり方がある。

In [37]:
list(itertools.permutations('ABC', 3))
Out[37]:
[('A', 'B', 'C'),
 ('A', 'C', 'B'),
 ('B', 'A', 'C'),
 ('B', 'C', 'A'),
 ('C', 'A', 'B'),
 ('C', 'B', 'A')]

itertoolsモジュールにある他の愉快なもの

In [38]:
import itertools

itertools.product()関数は、 2つのシーケンスの直積からなるイテレータを返す。

In [39]:
list(itertools.product('ABC', '123'))
Out[39]:
[('A', '1'),
 ('A', '2'),
 ('A', '3'),
 ('B', '1'),
 ('B', '2'),
 ('B', '3'),
 ('C', '1'),
 ('C', '2'),
 ('C', '3')]

itertools.combinations()関数は、与えられたシーケンスについて、 指定された要素の数からなる組み合わせ全部を取り出して、 イテレーターとして返す。

これはitertools.permutations()関数に似ているが、順序違いのものは含まないということが異なる。 すなわち、itertools.permutations('ABC', 2)は、('A', 'B')と('B', 'A')の両方を返すが、itertools.combinations('ABC', 2) は、('B', 'A')を返さない。

$$ {}_3 C_2 = \frac{3*2}{2*1} = 3通り $$
In [40]:
list(itertools.combinations('ABC', 2))
Out[40]:
[('A', 'B'), ('A', 'C'), ('B', 'C')]

イディオム:テキストファイルの行のリストを返す

favorite-people.txt >
Dora
Ethan
Wesley
John
Anne
Mike
Chris
Sarah
Alex
Lizzie
In [41]:
names = list(open('favorite-people.txt', encoding='utf-8'))
names
Out[41]:
['Dora\n',
 'Ethan\n',
 'Wesley\n',
 'John\n',
 'Anne\n',
 'Mike\n',
 'Chris\n',
 'Sarah\n',
 'Alex\n',
 'Lizzie\n']

(この例にとっては)都合が悪いことに、 list(open(filename)) というイディオムで処理すると、 各行の末尾にある改行文字( \n )が残ってしまう。

このリスト内包表記は、

  • 文字列メソッドのrstrip() を使って、 文字列の後ろに付いている空白文字を各行から取り除いている

文字列は、他に、

  • 先頭にある空白文字を取り除くための lstrip() メソッドや、
  • 先頭と末尾の両方の空白文字を取り除く strip() メソッドも持っている)
In [42]:
names = [name.rstrip() for name in names]
In [43]:
names
Out[43]:
['Dora',
 'Ethan',
 'Wesley',
 'John',
 'Anne',
 'Mike',
 'Chris',
 'Sarah',
 'Alex',
 'Lizzie']

sorted()関数はリストを受け取って、 そのリストをソートしたものを返す。

デフォルトではアルファベット順にソートする。

In [44]:
names = sorted(names)
names
Out[44]:
['Alex',
 'Anne',
 'Chris',
 'Dora',
 'Ethan',
 'John',
 'Lizzie',
 'Mike',
 'Sarah',
 'Wesley']

さらに、 sorted()関数は、key引数として関数を受け取り、 そのキーに基づいてソートを行うこともできる。

この例では、ソート関数はlen()なので、 これはlen(各要素)に基づいてソートを行う。 短い名前が先に来て、次に長い名前がくる。

In [45]:
names = sorted(names, key=len)
names
Out[45]:
['Alex',
 'Anne',
 'Dora',
 'John',
 'Mike',
 'Chris',
 'Ethan',
 'Sarah',
 'Lizzie',
 'Wesley']

itertools.groupby()関数は、 シーケンスとキー関数を受け取り、 ペアを生成するイテレータを返す。

各々のペアには、key_function(each item) の値と、 キー関数に渡したときにその値を返すような要素を集めたイテレータが入っている。

In [46]:
import itertools
groups = itertools.groupby(names, len)
groups
Out[46]:
<itertools.groupby at 0x2571f25b728>
In [47]:
list(groups)
Out[47]:
[(4, <itertools._grouper at 0x2571f25d048>),
 (5, <itertools._grouper at 0x2571f25d438>),
 (6, <itertools._grouper at 0x2571f25d780>)]

list()関数を呼び出したことでイテレータは「使い果たされた」。 つまり、リストを作るために、イテレータの要素をすべて生成しつくした。 イテレータに「リセット」ボタンは無いので、一度使い果たしたら最初からやり直させることはできない。

もう一度(例えば、次のforループで)イテレートしたいのであれば、 再びitertools.groupby() を呼び出して新しいイテレータを作る必要がある。

In [48]:
groups = itertools.groupby(names, len)

この例では、すでに長さでソートしてある名前のリストが与えられたので、itertools.groupby(names, len) は、

  • 4文字の名前をすべて1つのイテレータに入れ、
  • 5文字の名前をすべてもう1つのイテレータに入れ……

というように同じ長さの名前を同じ1つのイテレータに入れてくれた。

groupby()関数は完全に汎用的なので、 文字列を最初の1文字でグループ分けすることもできるし、 数字を因数の数で分類することもできる。 思いつくキー関数ならどんなものでも使える。

In [49]:
for name_length, name_iter in groups: 
    print('Names with {0:d} letters:'.format(name_length))
    
    for name in name_iter:
        print(name)
    
    print('\n')
Names with 4 letters:
Alex
Anne
Dora
John
Mike


Names with 5 letters:
Chris
Ethan
Sarah


Names with 6 letters:
Lizzie
Wesley


itertools.groupby()関数は、 入力されたシーケンスがグループ関数ですでにソートされているときにだけ機能する。

上の例では、名前のリストをlen()関数でグループ分けしたが、 これが上手くいったのは、あらかじめ入力リストを名前でソートしておいたから。

In [50]:
list(range(0, 3))
Out[50]:
[0, 1, 2]
In [51]:
list(range(10, 13))
Out[51]:
[10, 11, 12]

itertools.chain()関数は、 2つのイテレータを受け取って、 1つ目のイテレータのすべての要素と、 それに続いて2つ目のイテレータのすべての要素を含んだ1つのイテレータを返す.

(実は、任意数のイテレータを受け取ることができ、それらを関数に渡された順序で連結する)。

In [52]:
list(itertools.chain(range(0, 3), range(10, 13)))
Out[52]:
[0, 1, 2, 10, 11, 12]

zip()関数は、任意の数のシーケンスを受け取り、各シーケンスの1つ目の要素からなるタプル、各シーケンスの2つ目の要素からなるタプル、3つ目の要素からなるタプル……を生成するイテレータを返す。

In [53]:
zip(range(0, 3), range(10, 13))
Out[53]:
<zip at 0x2571f25ecc8>
In [ ]:
list(zip(range(0, 3), range(10, 13)))

zip()関数は、最も短いシーケンスの終わりで停止する。 range(10, 14) は4つの要素 (10, 11, 12, 13) を持つが、 range(0, 3) は3つしか持たないので、このzip()関数は3つの要素を持つイテレータを返す。

In [54]:
list(zip(range(0, 5), range(10, 14))) 
Out[54]:
[(0, 10), (1, 11), (2, 12), (3, 13)]
In [55]:
list(zip(range(0, 7), range(10, 14))) 
Out[55]:
[(0, 10), (1, 11), (2, 12), (3, 13)]

その一方で、itertools.zip_longest()関数は最も長いシーケンスの終わりで停止する。 短いシーケンスが尽きた後についてはNoneを挿入する。

In [56]:
list(itertools.zip_longest(range(0, 3), range(10, 14)))
Out[56]:
[(0, 10), (1, 11), (2, 12), (None, 13)]
In [57]:
list(itertools.zip_longest(range(0, 7), range(10, 14)))
Out[57]:
[(0, 10), (1, 11), (2, 12), (3, 13), (4, None), (5, None), (6, None)]

覆面算ソルバにはどんな関係があるのだろうか?

In [58]:
characters = ('S', 'M', 'E', 'D', 'O', 'N', 'R', 'Y')
guess = ('1', '2', '0', '3', '4', '5', '6', '7')

文字のリストと数字(ここではそれぞれが1文字の文字列として表されている)のリストを与えると、zip関数は文字と数字のペアを順番通りに作成する。

In [59]:
tuple(zip(characters, guess))
Out[59]:
(('S', '1'),
 ('M', '2'),
 ('E', '0'),
 ('D', '3'),
 ('O', '4'),
 ('N', '5'),
 ('R', '6'),
 ('Y', '7'))

このタプルは、dict()関数に渡すことで、 「文字をキー、対応する数字を値とした辞書」を構築できる構造になっている (辞書内包表記を使って、この辞書を直接構築することだってできる)。

表示された辞書の表現ではペアの順序が変わっているが(辞書は本質的に「順序」を持たない)、元のcharactersguess のシーケンス内の順序に基づいて、各文字に数字が対応付けられていることが見て取れるだろう。

In [60]:
dict(zip(characters, guess))
Out[60]:
{'D': '3',
 'E': '0',
 'M': '2',
 'N': '5',
 'O': '4',
 'R': '6',
 'S': '1',
 'Y': '7'}

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

equation = puzzle.translate(dict(zip(characters, guess)))

新種の文字列操作

文字列操作のテクニックであるtranslate()メソッドについて。

文字列の変換は変換表の用意から始まる。 これは、文字を他の文字に対応付けた単なる辞書だ。 実際には、変換表はバイトを他のバイトに対応させるのだ。

In [61]:
translation_table = {ord('A'): ord('O')}

Python 3のバイトは整数。 ord()関数は文字のascii値を返し、 これはA–Zの場合、常に65から90までの1バイトになる。

In [62]:
translation_table 
Out[62]:
{65: 79}

文字列のtranslate() メソッドは変換表を受け取り、 文字列をその変換表に通す。 つまり、変換表のキーに一致する部分をすべて対応する文字に変換するのだ。 この例では、MARKをMORKに「変換 (translate)」している。

In [63]:
'MARK'.translate(translation_table)
Out[63]:
'MORK'

ジェネレータ式を使い、 この文字列にある各々の文字のバイト値を素早く計算する。 "SMEDONRY"は、alphametics.solve()関数におけるsorted_charactersの値の例だ。

In [64]:
characters = tuple(ord(c) for c in 'SMEDONRY')
characters
Out[64]:
(83, 77, 69, 68, 79, 78, 82, 89)

別のジェネレータ式を使い、 この文字列にある各々の数字のバイト値を素早く計算する。 戻り値のguessは、alphametics.solve()関数において itertools.permutations()関数によって返されるものと同じ形をしている。

In [65]:
guess = tuple(ord(c) for c in '91570682')
guess
Out[65]:
(57, 49, 53, 55, 48, 54, 56, 50)

charactersguesszip して、 その戻り値のペアのシーケンスから辞書を構築することによって、この変換表は生成される。 これは、alphametics.solve()関数がforループの中でやっていること。

In [66]:
translation_table = dict(zip(characters, guess))
translation_table
Out[66]:
{68: 55, 69: 53, 77: 49, 78: 54, 79: 48, 82: 56, 83: 57, 89: 50}

オリジナルのパズル文字列のtranslate()メソッドに変換表を渡す。 これは、文字列の各文字を(charactersの文字とguessの数字にもとづいて)対応する数字に変換する。その結果は、有効なPythonの式を文字列として表したものになる。

In [67]:
'SEND + MORE == MONEY'.translate(translation_table) 
Out[67]:
'9567 + 1085 == 10652'

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

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

In [68]:
eval('1 + 1 == 2')
Out[68]:
True
In [69]:
eval('1 + 1 == 3')
Out[69]:
False
In [70]:
eval('9567 + 1085 == 10652')
Out[70]:
True

eval()関数が扱えるものはブール式だけではなく、 どんなPythonの式でも扱えるし、どんなデータ型でも返せる。

In [71]:
eval('"A" + "B"')
Out[71]:
'AB'
In [72]:
eval('"MARK".translate({65: 79})')
Out[72]:
'MORK'
In [73]:
eval('"AAAAA".count("A")')
Out[73]:
5
In [74]:
["*"] * 5
Out[74]:
['*', '*', '*', '*', '*']
In [75]:
eval('["*"] * 5')
Out[75]:
['*', '*', '*', '*', '*']

eval() が受け取る式は、eval() の外側で定義されたグローバル変数を参照できる。 関数の中で呼び出されたときはローカル変数も参照できる。

In [76]:
x = 5
eval("x * 5")
Out[76]:
25
In [77]:
eval("pow(x, 2)")
Out[77]:
25

モジュールも参照できる。

In [78]:
import math
eval("math.sqrt(x)")
Out[78]:
2.23606797749979

subprocessモジュールは、 任意のシェルコマンドを実行し、その結果をPythonの文字列として受け取る機能を提供する。

import subprocess
eval("subprocess.getoutput('dir ~')") 

> dirコマンドの返り値が使える
eval("subprocess.getoutput('rm /some/random/file')")

シェルコマンドの無制限な実行を許すと、とりかえしのつかない結果を招く可能性がある。

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

eval("__import__('subprocess').getoutput('rm /some/random/file')")

'rm -rf ~'の実行結果を想像してみよう。実際には一切何も出力されないのだが、あなたのファイルは全て消え去ってしまう。

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

でも、式を安全に評価する何らかの方法は本当に無いの?

eval()関数に渡された2つ目と3つ目のパラメータは、 式を評価するときの グローバル名前空間とローカル名前空間として機能する。

この場合は、両方が空になっている。このことは、 "x * 5" という文字列が評価されるときに、 グローバルとローカル名前空間のどちらにもxへの参照が存在しないということを意味するので、このeval()は例外を送出する。

In [80]:
x = 5
eval("x * 5", {}, {})   
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-80-ed0dd49f6458> in <module>()
      1 x = 5
----> 2 eval("x * 5", {}, {})

<string> in <module>()

NameError: name 'x' is not defined
In [81]:
eval("x * 5", {"x": x}, {}) 
Out[81]:
25

mathモジュールをインポートしているが、eval()関数に渡す名前空間にこれを含めていないので、この評価は失敗する

In [82]:
import math
eval("math.sqrt(x)", {"x": x}, {})
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-82-a32a42b5c316> in <module>()
      1 import math
----> 2 eval("math.sqrt(x)", {"x": x}, {})

<string> in <module>()

NameError: name 'math' is not defined

空の辞書をグローバル・ローカル名前空間に渡した場合でも、 Pythonの組み込み関数ならどれでも評価の際に利用できる。 つまり pow(5, 2) は問題なく評価される。

In [83]:
eval("pow(5, 2)", {}, {}) 
Out[83]:
25

__import__()関数も組み込み関数なので、これも使えてしまう。

In [84]:
eval("__import__('math').sqrt(5)", {}, {})
Out[84]:
2.23606797749979

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

eval("__import__('subprocess').getoutput('rm /some/random/file')", {}, {})
 eval("2 ** 2147483647", {"__builtins__":None}, {})

__builtins__ にアクセスできなかったとしても、なおDOS攻撃を仕掛けることはできる。

例えば、2の2147483647乗は、長時間にわたってサーバのcpu使用率を100%に跳ね上げるだろう(これを対話シェルで試すときは、Ctrl-Cを何回か押して脱出しよう)。 厳密にいえば、最終的にはこの式は実際に値を返すのだが、その間、サーバは無意味な処理に全力を注ぎ込むことになる。

まとめ

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

def solve(puzzle):
    # 1.`re.findall()`関数を使って、パズルに含まれる文字をすべて見つける
    words = re.findall('[A-Z]+', puzzle.upper())
    # 2. 集合と`set()`関数を使って、パズルに含まれるすべてのユニークな文字を見つける
    unique_characters = set(''.join(words))
    # 3.`assert`文を使って、10個以上のユニークな文字があるかチェックする(その場合、パズルは絶対に解けない)
    assert len(unique_characters) <= 10, 'Too many letters'

    first_letters = {word[0] for word in words}
    n = len(first_letters)

    # first_lettersを最初に、そのあとに残り
    sorted_characters = ''.join(first_letters) + ''.join(unique_characters - first_letters)
    # 4. ジェネレータオブジェクトを使って、文字を対応するASCIIコードに変換する
    characters = tuple(ord(c) for c in sorted_characters)
    digits = tuple(ord(c) for c in '0123456789')
    zero = digits[0]
    # 5. itertools.permutations()関数を使って、すべての解候補を求める
    for guess in itertools.permutations(digits, len(characters)):
        if zero not in guess[:n]:
            # 6.文字列メソッドのtranslate()を使って、すべての解候補をPythonの式に変換する
            equation = puzzle.translate(dict(zip(characters, guess)))
            # 7.eval()関数を使い、Pythonの式を評価することによってそれぞれの解候補をテストする
            if eval(equation):
                # 8. Trueと評価された最初の解を返す
                return equation
  1. re.findall()関数を使って、パズルに含まれる文字をすべて見つける
  2. 集合とset()関数を使って、パズルに含まれるすべてのユニークな文字を見つける
  3. assert文を使って、10個以上のユニークな文字があるかチェックする(その場合、パズルは絶対に解けない)
  4. ジェネレータオブジェクトを使って、文字を対応するASCIIコードに変換する
  5. itertools.permutations()関数を使って、すべての解候補を求める
  6. 文字列メソッドのtranslate()を使って、すべての解候補をPythonの式に変換する
  7. eval()関数を使い、Pythonの式を評価することによってそれぞれの解候補をテストする
  8. Trueと評価された最初の解を返す

参考リンク