Nacházíte se zde: Domů ‣ Ponořme se do Pythonu 3 ‣
Úroveň obtížnosti: ♦♦♦♦♢
❝ Great fleas have little fleas upon their backs to bite ’em,
And little fleas have lesser fleas, and so ad infinitum. ❞
(Veliké blechy maj malé své blechy, aby je kousaly do jejich zad,
Hle, malé si nesou své o něco menší; konce to nemá — podivný řád.)
— Augustus De Morgan
Jestliže přirovnáme regulární výrazy ke steroidům pro řetězce, pak modul itertools představuje steroidy pro iterátory. Ale nejdříve si ukážeme jednu klasickou hádanku.
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 = 4Hádankám tohoto typu se říká algebrogramy (anglicky cryptarithms nebo alphametics). Písmena jsou složena do skutečných slov, ale pokud každé z nich nahradíte číslicí 0–9, pak tvoří aritmetickou rovnici. Úkol spočívá v nalezení dvojic písmeno/číslice. Všechny výskyty stejného písmene se musí dát nahradit stejnou číslicí. Žádná číslice se nesmí opakovat a žádné „slovo“ nesmí začínat číslicí 0.
V této kapitole se ponoříme do neuvěřitelného pythonovského programu, který původně napsal Raymond Hettinger. Program řeší algebrogramy na pouhých 14 řádcích kódu.
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)Program můžeme spustit z příkazového řádku. Pod Linuxem to bude vypadat nějak takto. (V závislosti na rychlosti vašeho počítače to může zabrat nějaký čas a není zde žádný indikátor průběhu výpočtu. Buďte trpěliví.)
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
⁂
Program pro řešení algebrogramu v něm ze všeho nejdřív hledá písmena (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']
re implementuje v Pythonu regulární výrazy. Najdeme v něm i šikovnou funkci nazvanou findall(), které zadáváme vzorek pro regulární výraz a řetězec. Funkce v zadaném řetězci nalezne všechny výskyty vzorku. V tomto případě vzorek pasuje na posloupnosti číslic. Funkce findall() vrací seznam všech podřetězců, které vzorku vyhovují.
Následuje další příklad, který vám trochu procvičí mozek.
>>> re.findall(' s.*? s', "The sixth sick sheikh's sixth sheep's sick.")
[' sixth s', " sheikh's s", " sheep's s"]
Překvapeni? Regulární výraz hledá mezeru, znak s, pak nejkratší možnou posloupnost libovolných znaků (.*?), pak mezeru a další s. Když se tak dívám na vstupní řetězec, vidím pět pasujících podřetězců:
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.
Ale funkce re.findall() vrátila jen tři shody. Konkrétně vrátila jen první, třetí a pátou. Proč jen tři? Protože nevrací překrývající se shody se vzorkem. První shoda se překrývá s druhou, takže první se vrací a druhá se přeskakuje. Pak se třetí shoda překrývá se čtvrtou, takže třetí se vrací a čtvrtá se přeskakuje. A nakonec je tu pátá shoda, která se vrací. Najdou se tedy tři výskyty a ne pět.
Tahle poznámka neměla s řešením algebrogramu nic společného. Prostě mi to připadlo zajímavé.
⁂
Jedinečné hodnoty z posloupnosti můžeme snadno najít pomocí množin (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() vytvoří množinu jedinečných řetězců. Dá se to snadno pochopit, když si to představíte jako cyklus for. Vezmeme první položku ze seznamu a vložíme ji do množiny. Pak druhou. A třetí. Čtvrtou. Pátou... Počkat! Ta už v množině je, takže se bude vypisovat jen jednou, protože množiny v Pythonu neumožňují existenci duplicit. A šestou. Sedmou — a znovu duplicita, takže se pak objeví jen jednou. A jaký je konečný výsledek? Z původního seznamu zbyly jen jedinečné položky bez duplicit. Původní seznam ani nemusíme předem seřadit.
''.join(a_list) spojí všechny řetězce do jednoho.
Program pro řešení algebrogramů tuto techniku používá pro vytvoření množiny všech jedinečných znaků v zadání.
unique_characters = set(''.join(words))Program postupně prochází všemi možnými řešeními a tuto množinu používá pro přiřazení číslic jednotlivým znakům.
⁂
V Pythonu, stejně jako v mnoha jiných programovacích jazycích, najdeme příkaz assert. Funguje následovně.
>>> 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
assert uvedeme libovolný platný pythonovský výraz. V tomto případě se výraz 1 + 1 == 2 vyhodnotí jako True, takže příkaz assert nedělá nic.
False, vyvolá příkaz assert výjimku AssertionError.
AssertionError zobrazí.
Takže následující řádek kódu:
assert len(unique_characters) <= 10, 'Too many letters'… je ekvivalentem zápisu:
if len(unique_characters) > 10:
raise AssertionError('Too many letters')Program řešící algebrogram používá přesně takový příkaz assert k předčasnému ukončení činnosti v případě, kdy hádanka obsahuje víc než deset jedinečných znaků. Protože každému písmenu přiřazujeme jedinečnou číslici a číslic máme jen deset, hádanka s více než deseti jedinečnými znaky nemůže mít řešení.
⁂
Generátorový výraz se podobá generátorové funkci, ale funkce to není.
>>> 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)
next(gen) se nám vrací další hodnota iterátoru.
tuple(), list() nebo set(). V takovém případě nemusíte používat sadu kulatých závorek navíc. Funkci tuple() stačí předat „holý“ výraz ord(c) for c in unique_characters a Python už pozná, že jde o generátorový výraz.
☞Když místo generátorové notace seznamu použijete generátorový výraz, ušetříte jak CPU, tak RAM. Pokud konstruujete seznam jen proto, abyste ho zase zahodili (tj. když ho například chcete předat do
tuple()neboset()), použijte raději generátorový výraz!
Následující ukázka dosahuje stejného efektu s použitím generátorové funkce:
def ord_map(a_string):
for c in a_string:
yield ord(c)
gen = ord_map(unique_characters)Generátorový výraz je kompaktnější, ale funguje stejně.
⁂
Ze všeho nejdříve se podívejme, co to vlastně jsou permutace? Permutace jsou matematický koncept. (Ve skutečnosti existuje několik definicí v závislosti na tom, jakým druhem matematiky se zabýváte. Zde se dotkneme kombinatoriky. Ale pokud vám to nic neříká, nedělejte si s tím starosti. Tak jako vždy, vaším kamarádem je Wikipedie.)
Základní myšlenka spočívá v tom, že vezmeme seznam věcí (mohou to být čísla, písmenka nebo tancující medvídci) a najdeme všechny možné způsoby, jak z něj udělat menší seznamy. (Poznámka překladatele: V našich školách se pro označení tohoto úkonu používá pojem variace k-té třídy z n prvků bez opakování. Pojem permutace bez opakování se u nás používá jen pro speciální případ, kdy k je rovno n. V dalším textu zůstanu u chápání pojmu z originální publikace také z důvodu pojmenování příslušné funkce.) Všechny menší seznamy mají mít stejnou velikost, která může být od 1 až po celkový počet prvků. A nic se nesmí opakovat. Matematici by řekli „najděme permutace dvojic z tří různých prvků“ (u nás „najděte variace druhé třídy z tří prvků bez opakování“). To znamená, že máme posloupnost tří prvků a chceme nalézt všechny možné uspořádané dvojice.
>>> 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
itertools obsahuje celou řadu zábavných věcí, včetně funkce permutations(), která nás při hledání permutací zbaví veškeré námahy.
permutations() přebírá posloupnost (zde jde o seznam tří čísel) a požadovaný počet prvků v menších skupinách. Funkce vrací iterátor, který můžeme použít v cyklu for nebo na jakémkoliv starém známém místě, ve kterém se iteruje (tj. prochází všemi prvky). Zde budeme provádět kroky iterátoru ručně, abychom si všechny hodnoty ukázali.
[1, 2, 3] je dvojice (1, 2).
(2, 1) je něco jiného než (1, 2). [1, 2, 3]. Dvojice jako (1, 1) nebo (2, 2) zde nikdy neuvidíte, protože obsahují opakující se prvky. Takže nejde o platné permutace. Pokud už více permutací neexistuje, iterátor vyvolá výjimku StopIteration.
Funkci permutations() nemusíme předávat jen seznam. Může přebírat jakoukoliv posloupnost, dokonce i řetězec.
>>> 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')]
'ABC' ekvivalentem k seznamu ['A', 'B', 'C'].
['A', 'B', 'C'] je ('A', 'B', 'C'). Pro stejné znaky existuje pět dalších myslitelných uspořádání, tedy permutací.
permutations() vrací vždy iterátor. Snadný způsob zviditelnění všech permutací při ladění spočívá ve vytvoření jejich seznamu předáním iterátoru do zabudované funkce 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')]
itertools.product() vrací iterátor, který vytváří kartézský součin dvou posloupností.
itertools.combinations() vrací iterátor, který vytváří všechny možné kombinace dané délky z dané posloupnosti. Podobá se funkci itertools.permutations() s tou výjimkou, že kombinace nezahrnují výsledky, které vzniknou pouhou změnou uspořádání položek jiného výsledku. Takže itertools.permutations('ABC', 2) vrátí jak ('A', 'B'), tak ('B', 'A') (mimo jiné), ale itertools.combinations('ABC', 2) nevrátí ('B', 'A'), protože jde o duplicitu vytvořenou změnou pořadí položek ('A', 'B').
[stáhnout 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']
list(open(filename)) vrací na konci každého řádku i znak konce řádku. V této generátorové notaci seznamu použijeme metodu řetězce rstrip(), která z konce každého řádku odstraní koncové bílé znaky. (Řetězce definují též metodu lstrip(), která odstraňuje úvodní bílé znaky, a metodu strip(), která odstraňuje bílé znaky z obou konců.)
sorted() přebírá seznam a vrací nový, seřazený. Neřekneme-li jinak, řadí se podle abecedy.
sorted() můžeme parametrem key předat funkci a pak se provede řazení podle jejích výsledků. V tomto případě byla předána funkce len(), takže řazení probíhá podle výsledků funkce len(položka). Nejkratší jména se dostanou na začátek, pak budou následovat delší a delší.
A co to má společného s modulem itertools? To jsem rád, že se ptáte.
…pokračování v předchozí práci s interaktivním shellem… >>> 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
itertools.groupby() přebírá posloupnost a funkci klíče. Vrací iterátor, který vytváří dvojice. Každá dvojice obsahuje jednak výsledek funkce_klic(každá položka) a jednak další iterátor, který prochází všemi položkami se stejným výsledkem funkce klíče.
list() jsme iterátor „vyčerpali“. To znamená, že jsme při vytváření seznamu vygenerovali každou položku iterátoru. Iterátor nemá žádné tlačítko „reset“. Jakmile jsme posloupnost jednou vyčerpali, nemůžeme začít znovu. Pokud chceme hodnoty projít znovu (dejme tomu v dalším cyklu for), musíme znovu zavolat itertools.groupby() a vytvořit nový iterátor.
itertools.groupby(names, len) všem jménům délky 4 jeden iterátor, všem jménům délky 5 druhý iterátor atd. Funkce groupby() je zcela obecná. Řetězce můžeme seskupit podle prvního písmene, čísla podle počtu jejich prvočinitelů nebo podle jakékoliv myslitelné funkce klíče.
☞Funkce
itertools.groupby()funguje jen v případě, kdy je vstupní posloupnost již seřazená podle sdružovací funkce. Ve výše uvedeném příkladu jsme seznam jmen seskupili podle funkcelen(). Fungovalo to jen díky tomu, že byl vstupní seznam již seřazen podle délky položek.
Díváte se pozorně?
>>> 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() přebírá dva iterátory a vrací iterátor, který vytváří posloupnost všech položek nejdříve z prvního iterátoru a pak všech položek z druhého iterátoru. (Ve skutečnosti můžeme předat libovolný počet iterátorů a tato funkce zřetězí všechny jejich hodnoty v pořadí, v jakém jsme je funkci předali.)
zip() dělá něco docela obyčejného, ale ukazuje se, že je velmi užitečná. Přebírá libovolný počet posloupností a vrací iterátor, který vytváří n-tice z prvních položek každé posloupnosti, pak z druhých položek, pak z třetích atd.
zip() zastaví na konci nejkratší posloupnosti. Funkce range(10, 14) produkuje 4 položky (10, 11, 12 a 13), ale range(0, 3) jen 3. Takže funkce zip() vrátí iterátor produkující 3 položky.
itertools.zip_longest() zastaví až na konci nejdelší posloupnosti. Místo chybějících položek kratších posloupností doplní hodnoty None.
No dobrá, tohle všechno je sice velmi zajímavé, ale jak se to vztahuje k programu na řešení algebrogramů? Takto:
>>> 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'}
zip spáruje písmena a číslice v uvedeném pořadí.
dict(), aby vytvořila slovník, který používá písmena jako klíče a k nim přidružené číslice jako hodnoty. (Není to, samozřejmě, jediný způsob, jak toho můžeme dosáhnout. Slovník bychom mohli vytvořit přímo, pomocí generátorové notace.) Ačkoliv textová reprezentace obsahu slovníku zobrazuje dvojice v jiném pořadí (slovníky samy o sobě nedefinují „pořadí“), vidíme, že každé písmeno má k sobě číslici přidruženou na základě původních posloupností characters a guess.
Program pro řešení algebrogramů tuto techniku používá pro vytvoření slovníku, který převádí písmena z hádanky na čísla v řešení — pro každé možné řešení.
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)))Ale co je za metodu ta translate()? Teď se dostáváme k opravdu zábavné části.
⁂
Pythonovské řetězce definují mnoho metod. O některých z nich jsme se učili v kapitole Řetězce: lower(), count() a format(). Teď si představíme mocnou, ale málo známou techniku pro manipulaci s řetězcem. Jde o metodu translate().
>>> translation_table = {ord('A'): ord('O')} ①
>>> translation_table ②
{65: 79}
>>> 'MARK'.translate(translation_table) ③
'MORK'
ord() vrací ASCII hodnotu daného znaku. V případě znaků A–Z to budou vždy bajty od 65 do 90.
translate() přebírá překladovou tabulku a obsah řetězce přes ni propasíruje. To znamená, že nahradí všechny výskyty klíčů z překladové tabulky odpovídajícími hodnotami. V tomto případě se MARK „přeloží“ na MORK.
Ale co to má společného s řešením algebrogramů? Jak se ukáže za chvíli, všechno.
>>> 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'
alphametics.solve().
itertools.permutations() — viz funkce alphametics.solve()
alphametics.solve() uvnitř cyklu for.
translate() původního řetězce hádanky. Tím se každý znak řetězce přeloží na odpovídající číslici (podle písmen v characters a číslic v guess). Výsledkem je platný pythonovský výraz v řetězcové podobě.
To je docela efektní. Ale co můžeme dělat s řetězcem, který shodou okolností zachycuje platný pythonovský výraz?
⁂
Tohle je poslední kousek skládanky (nebo spíše poslední kousek programu pro řešení hádanky). Po všech těch efektních manipulacích s řetězci jsme skončili u řetězce, jako je '9567 + 1085 == 10652'. Ale je to jen řetězec. A k čemu je nám řetězec dobrý? Seznamte se s eval(), s univerzálním pythonovským vyhodnocovacím nástrojem.
>>> eval('1 + 1 == 2')
True
>>> eval('1 + 1 == 3')
False
>>> eval('9567 + 1085 == 10652')
True
Ale počkejte! Je toho ještě víc! Funkce eval() se neomezuje jen na booleovské výrazy. Zvládne libovolný pythonovský výraz a vrací libovolný datový typ.
>>> eval('"A" + "B"')
'AB'
>>> eval('"MARK".translate({65: 79})')
'MORK'
>>> eval('"AAAAA".count("A")')
5
>>> eval('["*"] * 5')
['*', '*', '*', '*', '*']
Ale počkejte, to ještě není vše!
>>> x = 5
>>> eval("x * 5") ①
25
>>> eval("pow(x, 2)") ②
25
>>> import math
>>> eval("math.sqrt(x)") ③
2.2360679774997898
eval() se může odkazovat na globální proměnné definované vně eval(). A pokud se volá uvnitř funkce, může se odkazovat i na lokální proměnné.
Hej, zastav na minutku…
>>> import subprocess
>>> eval("subprocess.getoutput('ls ~')") ①
'Desktop Library Pictures \
Documents Movies Public \
Music Sites'
>>> eval("subprocess.getoutput('rm /some/random/file')") ②
subprocess vám dovolí spustit libovolný shellovský příkaz a získat výsledek v podobě pythonovského řetězce.
A je to dokonce ještě horší, protože existuje globální funkce __import__(), která přebírá jméno modulu v řetězcové podobě, importuje ho a vrací na něj odkaz. Když to zkombinujeme se silou funkce eval(), můžeme vytvořit výraz, který smaže všechny vaše soubory:
>>> eval("__import__('subprocess').getoutput('rm /some/random/file')") ①
'rm -rf ~'. Ve skutečnosti žádný výstup neuvidíte. Ale neuvidíte už ani své soubory.
eval() is EVIL
(tj. eval() je zlý, špatný, zlověstný). Tou zlou stránkou je vyhodnocování libovolných výrazů pocházejících z nedůvěryhodných zdrojů. Funkci eval() byste měli používat výhradně pro vstup z důvěryhodných zdrojů. Problém je v tom, jak určit, co je „důvěryhodný“ zdroj. Ale něco vím určitě. Určitě byste NEMĚLI vzít tento program pro řešení algebrogramů a zveřejnit jej na internetu v podobě malé webovské služby. A nemyslete si: „Vždyť ta funkce dělá tolik řetězcových operací, než se vůbec dostane k vyhodnocení. Nedovedu si představit, jak by toho někdo mohl zneužít.“ Někdo přijde na to, jak propašovat nějaký nebezpečný kód všemi těmi řetězcovými manipulacemi (už se staly divnější věci). A pak už můžete svému serveru poslat jen polibek na rozloučenou.
Ale existuje vůbec nějaký způsob, jak výrazy vyhodnotit bezpečně? Lze nějak eval() umístit na pískoviště, odkud nemá přístup k okolnímu světu a nemůže mu škodit? Hmm, ano i ne.
>>> 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}, {}) ②
25
>>> 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
eval() se chovají jako globální a lokální prostor jmen. Tyto prostory se používají při vyhodnocování výrazu. V tomto případě jsou oba prázdné. To znamená, že při vyhodnocování řetězce "x * 5" neexistuje žádný odkaz na x ani v globálním ani v lokálním prostoru jmen. Takže eval() vyvolá výjimku.
math, nevložili jsme jej do prostoru jmen, který předáváme funkci eval(). V důsledku toho vyhodnocení selhalo.
Tý jo. Tak to bylo jednoduché. Teď si udělám webovskou službu pro řešení algebrogramů!
>>> eval("pow(5, 2)", {}, {}) ①
25
>>> eval("__import__('math').sqrt(5)", {}, {}) ②
2.2360679774997898
pow(5, 2) funguje, protože 5 a 2 jsou literály a pow() je zabudovaná funkce.
__import__() také zabudovanou funkcí, takže také funguje.
Ano, to znamená, že můžete pořád dělat odporné věci, i když jste při volání eval() pro globální a lokální prostor jmen explicitně nastavili prázdné slovníky:
>>> eval("__import__('subprocess').getoutput('rm /some/random/file')", {}, {})
A do prčic! To jsem rád, že jsem pro řešení algebrogramů nevytvořil webovou službu. Je zde vůbec nějaký způsob, kterým bychom mohli eval() používat bezpečně? Ano i ne.
>>> 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
"__builtins__" na None, tedy na pythonovskou hodnotu null (nic, nil). „Zabudované“ funkce jsou totiž vnitřně uzavřeny do pseudomodulu nazvaného "__builtins__". Tento pseudomodul (tj. množina zabudovaných funkcí) je vyhodnocovaným výrazům zpřístupněn — pokud jej explicitně nepotlačíte.
__builtins__. Žádné __builtin__, __built-ins__ nebo nějakou podobnou variantu. Ono by to fungovalo bez problémů, ale vystavilo by vás to riziku katastrofy.
Takhle už je eval() bezpečný? Nu, ano i ne.
>>> eval("2 ** 2147483647",
... {"__builtins__":None}, {}) ①
__builtins__ můžete stále spustit útok typu odmítnutí služby. Pokud se například pokusíte o umocnění 2 na 2147483647, využití procesoru vašeho serveru stoupne na 100 % na pěkně dlouhou dobu. (Pokud to zkoušíte v interaktivním shellu, můžete ho přerušit, když několikrát stisknete Ctrl-C.) Technicky vzato, tento výraz nakonec vrátí nějakou hodnotu, ale do té doby bude server dělat spoustu zbytečné práce.
Takže nakonec je možné bezpečně vyhodnocovat pythonovské výrazy z nedůvěryhodných zdrojů. Vyžaduje to ale určitou definici pojmu „bezpečně“, která v reálném životě není zas tak užitečná. Dobré je, když si hrajete někde poblíž. Dobré taky je, když připustíte jen důvěryhodný vstup. Cokoliv jiného znamená, že si koledujete o malér.
⁂
Rekapitulace: Tento program řeší algebrogramy hrubou silou, tj. vyčerpávajícím hledáním všech možných řešení. Program za tím účelem…
re.findall().
set().
assert, zda se v zadání nevyskytuje více než 10 jedinečných znaků (což by znamenalo, že hádanka je neřešitelná).
itertools.permutations().
translate().
eval().
True.
… to vše na pouhých 14 řádcích kódu.
⁂
itertools module
itertools — Iterator functions for efficient looping
Mnohokrát děkuji Raymondu Hettingerovi za souhlas s úpravou licence jeho kódu, abych ho mohl přepsat pro Python 3 a použít jako základ této kapitoly.
© 2001–11 Mark Pilgrim