Itt vagy: Kezdőlap ‣ Ugorj fejest a Python 3-ba ‣
Nehézségi szint: ♦♦♦♦♢
❝ A nagy bolhák hátán kisebb bolhák lakmároznak,
A kisebb bolhák hátán pedig még kisebb bolhák, és így tovább a végtelenségig. ❞
– Augustus De Morgan
Ahogyan a reguláris kifejezések felturbózzák a karakterláncokat, az itertools modul az iterátorokat turbózza fel. De előbb szeretnék mutatni egy klasszikus, angol nyelvű rejtvényt.
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 = 4Az ilyen rejtvényeket kriptaritmusoknak vagy alfametikáknak nevezik. A betűk valódi szavakká állnak össze, de ha az egyes betűket egy 0–9 közti számmal helyettesíted, akkor egy aritmetikai egyenlet áll elő. A feladat a betűkhöz tartozó számjegyek megtalálása. Az egyes betűk minden előfordulása ugyanannak a számjegynek felel meg, a számjegyek nem ismétlődhetnek, és egyik „szó” sem kezdődhet a 0 számjeggyel.
Ebben a fejezetben egy hihetetlen Python programba ugrunk fejest, amelyet eredetileg Raymond Hettinger írt. Ez a program alfametikus feladatokat old meg összesen 14 sor kóddal.
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)A programot a parancssorból futtathatod. Linuxon ez így néz ki. (A program futása eltarthat egy ideig, a számítógéped sebességétől függően, és nincs folyamatjelző. Légy türelmes!)
te@localhost:~/diveintopython3/examples$ python3 alphametics.py "HAWAII + IDAHO + IOWA + OHIO == STATES" HAWAII + IDAHO + IOWA + OHIO = STATES 510199 + 98153 + 9301 + 3593 == 621246 te@localhost:~/diveintopython3/examples$ python3 alphametics.py "I + LOVE + YOU == DORA" I + LOVE + YOU == DORA 1 + 2784 + 975 == 3760 te@localhost:~/diveintopython3/examples$ python3 alphametics.py "SEND + MORE == MONEY" SEND + MORE == MONEY 9567 + 1085 == 10652
⁂
A program első lépésként megkeresi a feladvány összes betűjét (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 modul a Python reguláris kifejezés megvalósítása. Ez tartalmazza a findall() nevű függvényt, amely egy reguláris kifejezésként megadott mintát és egy karakterláncot vár, és megkeresi a minta összes előfordulását a karakterláncban. Ebben az esetben a minta számok sorozatára illeszkedik. A findall() függvény a mintára illeszkedő összes részkarakterlánc listáját adja vissza.
A következő példa is egy pici gondolkodásra fog késztetni.
>>> re.findall(' s.*? s', "The sixth sick sheikh's sixth sheep's sick.")
[' sixth s', " sheikh's s", " sheep's s"]
Meglepődtél? A reguláris kifejezés egy szóközt, egy s betűt, majd tetszőleges karakterek lehetséges legrövidebb sorozatát (.*?), majd egy szóközt, és egy újabb s betűt keres. Nos, a bemeneti karakterláncra nézve, öt találatot látok:
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.
Azonban a re.findall() függvény csak három találatot adott vissza. Ezen belül az első, harmadik és ötödik találatot adta vissza. Miért van ez így? Mert nem adja vissza az egymást átfedő találatokat. Az első találat átfedi a másodikat, így az első visszaadásra kerül, a második pedig kimarad. Ezután a harmadik átfedi a negyediket, így a harmadik visszaadásra kerül, a negyedik pedig kimarad. Végül az ötödik is visszaadásra kerül. Három találat, nem öt.
Ennek semmi köze az alfametikus megoldóhoz, csak érdekesnek találom.
⁂
A halmazok triviálissá teszik egy sorozat egyedi elemeinek megtalálását.
>>> 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() függvény visszaadja a lista egyedi karakterláncainak halmazát. Ennek van értelme, ha úgy gondolsz rá, mint egy for ciklusra. Vegyük a lista első elemét, tegyük be a halmazba. A másodikat. A harmadikat. A negyediket. Az ötödiket – várj, ilyen már van a halmazban, így most kimarad, mert a Python nem engedélyezi a másodpéldányokat. A hatodikat. A hetediket – újra egy másodpéldány, ismét kimarad. A végeredmény? Az eredeti lista összes egyedi eleme másodpéldányok nélkül. Az eredeti listát nem is kell rendezni előtte.
''.join(a_list) összefésüli az összes karakterláncot egyetlen eggyé.
Az alfametikus megoldó ezt a módszert használja a feladvány összes egyedi karakterét tartalmazó halmaz felépítéséhez.
unique_characters = set(''.join(words))Ez a lista később a számjegyek karakterekhez rendelésénél lesz felhasználva, amikor a megoldó végigjárja a lehetséges megoldásokat.
⁂
Sok programozási nyelvhez hasonlóan a Python is rendelkezik egy assert utasítással. Így működik:
>>> assert 1 + 1 == 2 ① >>> assert 1 + 1 == 3 ② Traceback (most recent call last): File "<stdin>", line 1, in <module> AssertionError >>> assert 2 + 2 == 5, "Csak a 2 nagyon nagy értékeihez" ③ Traceback (most recent call last): File "<stdin>", line 1, in <module> AssertionError: Csak a 2 nagyon nagy értékeihez
assert utasítást tetszőleges érvényes Python kifejezés követheti. Ebben az esetben az 1 + 1 == 2 kifejezés True-ra értékelődik ki, így az assert utasítás nem csinál semmit.
False-ra értékelődik ki, akkor az assert utasítás AssertionError kivételt dob.
AssertionError dobásakor kiírásra kerül.
Emiatt ez a sor kód:
assert len(unique_characters) <= 10, 'Túl sok betű'…ezzel egyenértékű:
if len(unique_characters) > 10:
raise AssertionError('Túl sok betű')Az alfametikus megoldó pontosan ezt az assert utasítást használja, hogy időben megálljon, ha a feladvány tíz egyedi betűnél többet tartalmazna. Mivel minden betűhöz egyedi számjegy kerül hozzárendelésre, és csak tíz számjegy van, a tíz betűnél többet tartalmazó feladványoknak nem lehet megoldásuk.
⁂
A generátorkifejezés olyan, mint egy függvény nélküli generátorfüggvény.
>>> 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) hívása az iterátorból származó következő értéket adja vissza.
tuple(), list() vagy set() függvénynek. Ezekben az esetekben nincs szükséged extra zárójelekre – csak add át a „nyers” ord(c) for c in unique_characters kifejezést a tuple() függvénynek, és a Python megállapítja, hogy ez egy generátorkifejezés.
☞Listafeldolgozó helyett generátorkifejezést használva egyaránt spórolhatsz a CPU és a RAM használatán is. Ha csak azért építesz egy listát, hogy rögtön eldobhasd (például a
tuple()vagyset()függvénynek átadva), használj generátorkifejezést.
Ugyanezt máshogy is elérheted egy generátorfüggvény használatával:
def ord_map(a_string):
for c in a_string:
yield ord(c)
gen = ord_map(unique_characters)A generátorkifejezés tömörebb, de funkcionálisan egyenértékű.
⁂
Először is, mi a csuda az a permutáció? A permutáció egy matematikai fogalom. (Valójában több meghatározás van, az épp használt matematikai rendszertől függően. Itt a kombinatorikáról van szó, de ha ez nem jelent neked semmit, akkor se aggódj. Mint mindig, a Wikipédia a barátod.)
Az alapötlet a következő: veszed elemek (számok, betűk, táncoló medvék) listáját, és az összes lehetséges módon felosztod kisebb listákra. Az összes kisebb lista azonos méretű, akár egy eleműek is lehetnek, de az elemek teljes számával egyenlő méretűek is. Ja és egyáltalán nem lehetnek ismétlődések. A matematikusok olyanokat mondanak, mint például „keressük meg 3 különböző elem permutációit egyszerre kettőt véve”, ami azt jelenti, hogy egy 3 elemből álló listád van, és meg akarod találni az összes lehetséges rendezett párt.
>>> 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 modul mindenféle jópofa dolgot tartalmaz, beleértve egy permutations() függvényt, amely elvégzi a permutációk keresésének fáradtságos munkáját.
permutations() függvény egy sorozatot (itt egy három számból álló listát) és egy számot vár, amely a kisebb csoportokba beosztandó elemek száma. A függvény egy iterátort ad vissza, amelyet felhasználhatsz egy for ciklusban vagy bármely más helyen, ami iterál. Itt saját kezűleg lépkedek végig az iterátoron az értékek megjelenítéséhez.
[1, 2, 3] első permutációja egyszerre 2 elemet véve az (1, 2).
(2, 1) eltér az (1, 2)-től.
[1, 2, 3] összes permutációja egyszerre két elemet véve. Az (1, 1) és (2, 2) párok soha nem jelennek meg, mert ismétléseket tartalmaznak, így nem érvényes permutációk. Ha nincs több permutáció, akkor az iterátor egy StopIteration kivételt dob.
A permutations() függvénynek nem kötelező listát átadni. Tetszőleges sorozatot kaphat – akár egy karakterláncot is.
>>> 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' egyenértékű a ['A', 'B', 'C'] listával.
['A', 'B', 'C'] egyszerre 3 elemet véve ('A', 'B', 'C'). Öt másik permutáció is van – ugyanaz a három karakter minden elképzelhető sorrendben.
permutations() függvény mindig egy iterátort ad vissza, a permutációk hibakeresése egyszerűen megoldható az iterátor átadásával a beépített list() függvénynek, így az összes permutáció azonnal megjeleníthető.
⁂
itertools modulban>>> 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() függvény a két sorozat Descartes-szorzatát tartalmazó iterátort ad vissza.
itertools.combinations() függvény az adott sorozat összes adott hosszú kombinációját adja vissza. Ez olyan, mint az itertools.permutations() függvény, csak a kombinációk nem tartalmaznak olyan elemeket, amelyek ugyanazon elemek más sorrendben lévő másodpéldányai. Így az itertools.permutations('ABC', 2) visszaadja mind az ('A', 'B') és ('B', 'A') elemeket (többek közt), de az itertools.combinations('ABC', 2) nem adja vissza a ('B', 'A') elemet, mert az az ('A', 'B') másodpéldánya más sorrendben.
[a favorite-people.txt letöltése]
>>> 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)) kifejezés tartalmazza a sorok végén lévő kocsivissza karaktert is. Ez a listafeldolgozó az rstrip() karakterlánc-metódust használja a záró üres hely eltávolítására a karakterláncok végéről. (A karakterláncok rendelkeznek egy lstrip() metódussal is a kezdő üres hely eltávolításához, és egy strip() metódussal mindkettő eltávolításához.)
sorted() függvény egy listát vár, és rendezve adja vissza. Alapértelmezésben ábécérendbe rendez.
sorted() függvény kaphat függvényt is a key paraméteren keresztül, ekkor aszerint rendez. Ebben az esetben a rendezési függvény a len(), így a len(minden elem) szerint rendez. A rövidebb nevek jönnek előre, aztán a hosszabbak, végül a leghosszabbak.
Mi köze van ennek az itertools modulhoz? Örülök, hogy megkérdezted!
…folytatás az előző interaktív parancsértelmezőből… >>> 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('{0:d} betűs nevek:'.format(name_length)) ... for name in name_iter: ... print(name) ... 4 betűs nevek: Alex Anne Dora John Mike 5 betűs nevek: Chris Ethan Sarah 6 betűs nevek: Lizzie Wesley
itertools.groupby() függvény egy sorozatot és egy kulcsfüggvényt vár, és visszaad egy iterátort, amely párokat generál. Minden pár a kulcsfüggvény(minden elem) eredményét, és egy másik iterátort tartalmaz, amely az összes azonos kulcsú elemet tartalmazza.
list() függvény hívása „kimerítette” az iterátort, azaz előállítottad az iterátor minden elemét a lista létrehozásához. Nincs „újraindítás” gomb az iterátorokon, az egyszer már kimerített iterátoron nem kezdhetsz újra végigjárni. Ha újra végig szeretnél rajta járni (mondjuk a soron következő for ciklusban), akkor újra meg kell hívnod az itertools.groupby() metódust egy új iterátor létrehozásához.
itertools.groupby(names, len) az összes 4 betűs nevet egy iterátorba teszi, az összes 5 betűset egy másikba és így tovább. A groupby() függvény teljesen általános, csoportosíthatja a karakterláncokat az első betű szerint, a számokat a tényezőik száma szerint vagy tetszőleges kulcsfüggvény szerint, amit csak el tudsz képzelni.
☞Az
itertools.groupby()függvény csak akkor működik, ha a bemeneti sorozat már rendezve van a csoportosító függvény által. A fenti példában a nevek listáját alen()függvénnyel csoportosítottad. Ez csak azért működött, mert a bemenet már rendezve volt hossz szerint.
Nagyon figyelsz?
>>> 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() függvény két iterátort vár, és egy olyan iterátort ad vissza, amely az első elemeit, majd azok után a második elemeit tartalmazza. (Valójában tetszőleges számú iterátort át lehet neki adni, hogy aztán a függvénynek való átadásuk sorrendjében összefűzze azokat.)
zip() függvény egy teljesen hétköznapi dolgot tesz, amely azonban különösen hasznosnak fog bizonyulni: tetszőleges számú sorozatot vár, és visszaad egy iterátort, amely az egyes sorozatokból az első, második, harmadik stb. elemeket tartalmazó tuple-kat ad vissza.
zip() függvény a legrövidebb sorozat végén áll meg. A range(10, 14) 4 elemet (10, 11, 12 és 13) tartalmaz, de a range(0, 3) csak hármat, így a zip() függvény egy 3 elemű iterátort ad vissza.
itertools.zip_longest() függvény a leghosszabb sorozat végén áll meg, None értékeket szúrva be a rövidebb sorozatok vége utáni elemekhez.
Oké, ez mind nagyon érdekes, de mi köze van az alfametikus megoldóhoz? A következő:
>>> 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 függvény létrehozza a betűk és számjegyek sorba rendezett párjait.
dict() függvénynek való átadáshoz, hogy az létrehozzon egy szótárat, amelynek kulcsai betűk, értékei pedig számjegyek. (Ez természetesen nem az egyetlen megoldás. Használhatnál szótárfeldolgozót is a szótár közvetlen létrehozásához.) Noha a szótár kiírt ábrázolása a párokat eltérő sorrendben sorolja fel (a szótárak maguk nem rendelkeznek „sorrenddel”), azért láthatod, hogy minden betű egy számjegyhez tartozik, az eredeti characters és guess sorozatok sorrendje alapján.
Az alfametikus megoldó ezt a módszert használja egy szótár létrehozásához, amely a feladvány betűit leképezi a megoldás számjegyeire, minden lehetséges megoldás esetén.
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)))De mi az a translate() metódus? Ó, most jutunk el az igazán vidám részhez.
⁂
A Python karakterláncok sok metódussal rendelkeznek. Ezen metódusok némelyikével a Karakterláncok fejezetben már megismerkedtél: lower(), count() és format(). Most szeretnék megmutatni egy hatékony, de kevéssé ismert karakterlánc-manipulálási módszert: a translate() metódust.
>>> translation_table = {ord('A'): ord('O')} ①
>>> translation_table ②
{65: 79}
>>> 'MARK'.translate(translation_table) ③
'MORK'
ord() függvény visszaadja egy karakter ASCII értékét, amely az A–Z esetén mindig egy 65 és 90 közti bájt.
translate() metódusa egy fordítási táblát vár, és átfuttatja rajta a karakterláncot. Azaz a fordítási tábla kulcsainak minden előfordulását lecseréli a megfelelő értékre. Ebben az esetben „lefordítja” a MARK szót MORK-ra.
Mi köze van ennek az alfametikus feladványok megoldásához? Amint kiderül, rengeteg.
>>> 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() függvényben.
alphametics.solve() függvényben az itertools.permutations() függvény által visszaadott formátumú.
alphametics.solve() függvény csinál a for cikluson belül.
translate() metódusának. Ez a karakterlánc minden betűjét átalakítja a megfelelő számjeggyé (a characters betűi és a guess számjegyei alapján). Az eredmény egy érvényes Python kifejezés, karakterláncként.
Ez meglehetősen meggyőző. De mit lehet kezdeni egy karakterlánccal, amely egyúttal érvényes Python kifejezés is?
⁂
Ez a feladvány utolsó darabja (vagy inkább a feladványmegoldó utolsó darabja). A rengeteg karakterlánc-manipuláció után egy ilyen karakterláncot kapsz: '9567 + 1085 == 10652'. De ez egy karakterlánc, és mire jó egy karakterlánc? Most lép színre az eval(), az univerzális Python kiértékelési eszköz.
>>> eval('1 + 1 == 2')
True
>>> eval('1 + 1 == 3')
False
>>> eval('9567 + 1085 == 10652')
True
De várj, van még más is! Az eval() függvény nincs logikai kifejezésekre korlátozva. Képes kezelni bármely Python kifejezést és tetszőleges adattípust adhat vissza.
>>> eval('"A" + "B"')
'AB'
>>> eval('"MARK".translate({65: 79})')
'MORK'
>>> eval('"AAAAA".count("A")')
5
>>> eval('["*"] * 5')
['*', '*', '*', '*', '*']
De várj, ez nem minden!
>>> x = 5
>>> eval("x * 5") ①
25
>>> eval("pow(x, 2)") ②
25
>>> import math
>>> eval("math.sqrt(x)") ③
2.2360679774997898
eval() által kapott kifejezés az eval() híváson kívül definiált globális változókra is hivatkozhat. Ha függvényen belül hívod, akkor helyi változókra is hivatkozhat.
Hé, várj egy percet…
>>> import subprocess
>>> eval("subprocess.getoutput('ls ~')") ①
'Asztal Gyűjtemény Képek \
Dokumentumok Videók Nyilvános \
Zenék Oldalak'
>>> eval("subprocess.getoutput('rm /valami/véletlen/fájl')") ②
subprocess modul lehetővé teszi a parancsértelmező tetszőleges parancsainak futtatását, és az eredmény lekérését Python karakterláncként.
Ennél is rosszabb a helyzet, mert van egy globális __import__() függvény, amely egy modulnevet vár karakterláncként, importálja a modult, és visszaad egy hivatkozást rá. Az eval() erejével egyesítve előállíthatsz egy olyan kifejezést, amely letörli az összes fájlod:
>>> eval("__import__('subprocess').getoutput('rm /valami/véletlen/fájl')") ①
'rm -rf ~' kimenetét. Valójában nem lenne kimenete, de fájljaid sem maradnának.
Az eval() GONOSZ
A gonosz rész a megbízhatatlan forrásokból származó tetszőleges kifejezések kiértékelése. Az eval() függvényt csak megbízható bemeneten szabad használni. Természetesen a trükk a „megbízható” bemenet meghatározása. De van egy dolog, amiben biztos vagyok: ezt az alfametikus megoldót NEM szabad kitenni az internetre egy vicces kis webszolgáltatásként. Ne kövesd el azt a hibát, hogy úgy gondolod: „Ugyan már, a függvény rengeteg karakterlánc-manipulációt végez, mielőtt megkapja a kiértékelendő karakterláncot, nem tudom elképzelni, hogyan lehetne ezt kihasználni.” Valaki ki FOGJA találni, hogyan lehet megadni a karakterlánc-manipulációkat túlélő rosszindulatú végrehajtható kódot (furább dolgok is történtek már), és akkor elköszönhetsz a kiszolgálódtól.
De biztos van valami lehetőség a kifejezések biztonságos kiértékelésére, nem? Az eval() nem tehető be egy homokozóba, ahol nem tudja elérni vagy károsítani a külvilágot? Hát, igen is meg nem is.
>>> 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() függvénynek átadott második és harmadik paraméter a kifejezés kiértékeléséhez használandó globális és helyi névterekként működnek. Ebben az esetben mindkettő üres, ami azt jelenti, hogy az "x * 5" karakterlánc kiértékelésekor nincs hivatkozás az x-re a globális vagy helyi névtérben, így az eval() kivételt dob.
math modult, nem vetted fel az eval() függvénynek átadott névtérbe, így a kiértékelés meghiúsult.
Hát, ez könnyű volt. Hadd csináljam meg most azt az alfametikus webszolgáltatást!
>>> eval("pow(5, 2)", {}, {}) ①
25
>>> eval("__import__('math').sqrt(5)", {}, {}) ②
2.2360679774997898
pow(5, 2) működik, mert az 5 és a 2 literálok, a pow() pedig beépített függvény.
__import__() függvény szintén beépített, így ez is működik.
Igen, ez azt jelenti, hogy továbbra is lehet huncut dolgokat csinálni, még ha a globális és helyi névtereket kifejezetten üres szótárakra is állítottad az eval() hívásakor:
>>> eval("__import__('subprocess').getoutput('rm /valami/véletlen/fájl')", {}, {})
Hoppá. Örülök, hogy nem csináltam meg azt az alfametikus webszolgáltatást. Létezik valami módszer az eval() biztonságos használatára? Hát, igen is meg nem is.
>>> 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__" modulnevet a Python null értékére, a None-ra. A felszín alatt a „beépített” függvényeket egy "__builtins__" nevű álmodul tartalmazza. Ez az álmodul (azaz a beépített függvények halmaza) elérhető a kiértékelt kifejezések számára, hacsak nem bírálod felül kifejezetten.
__builtins__ modult bírálod felül. Nem a __builtin__, __built-ins__ vagy valami más változatot, amely működni épp működik, de katasztrofális kockázatoknak tesz ki.
Akkor az eval() végre már biztonságos? Hát, igen is meg nem is.
>>> eval("2 ** 2147483647",
... {"__builtins__":None}, {}) ①
__builtins__ elérése nélkül is indíthatsz egy szolgáltatás megbénításával járó támadást. Például a 2 2147483647. hatványra emelése a kiszolgálód CPU-kihasználtságát meglehetősen hosszú időre 100%-ra tornázza fel. (Ha ezt az interaktív parancsértelmezőben próbáltad ki, akkor nyomd meg párszor a Ctrl-C kombinációt a megszakításához.) Technikailag ez a kifejezés idővel vissza fog adni egy értéket, de addig a kiszolgálód rengeteg értelmetlen számolást fog végezni.
Végső soron lehetséges biztonságosan kiértékelni megbízhatatlan Python kifejezéseket, a „biztonságos” bizonyos definíciója mellett, amely a való életben nem bizonyul annyira hasznosnak. Ez rendben van, ha csak játszol, és rendben van, ha mindig csak megbízható bemenetet adsz át. De minden más csak felhívás keringőre.
⁂
Ismételjünk: ez a program alfametikus feladványokat old meg nyers erő használatával, azaz az összes lehetséges megoldás kimerítő keresése útján. Ehhez…
re.findall() függvénnyel
set() függvénnyel
assert utasítással
itertools.permutations() függvénnyel
translate() karakterlánc-metódussal
eval() függvénnyel
True-ra értékelődött ki
…mindössze 14 sor kódban.
⁂
itertools modul
itertools – Iterator functions for efficient looping
Hatalmas köszönet Raymond Hettingernek, amiért beleegyezett kódja újralicencelésébe, így át tudtam portolni Python 3-ra, és felhasználhattam ezen fejezet alapjául.
© 2001–11 Mark Pilgrim