segunda-feira, 11 de julho de 2022

Iteradores avançados em Python

❝ Grandes pulgas têm pequenas pulgas nas costas para mordê-las, E as pulgas pequenas têm pulgas menores, e assim ad infinitum. ❞
— Augusto De Morgan

Mergulho

Assim como expressões regulares colocam esteróides em strings, o módulo itertools coloca esteróides nos iteradores. Mas primeiro, quero mostrar um quebra-cabeça clássico.

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

Quebra-cabeças como esse são chamados de criptaritmos ou alfaméticos. As letras formam palavras reais, mas se você substituir cada letra por um dígito de 0 a 9, ela também “soletra” uma equação aritmética. O truque é descobrir qual letra mapeia para cada dígito. Todas as ocorrências de cada letra devem ser mapeadas para o mesmo dígito, nenhum dígito pode ser repetido e nenhuma “palavra” pode começar com o dígito 0.

Neste capítulo, vamos mergulhar em um incrível programa Python originalmente escrito por Raymond Hettinger. Este programa resolve quebra-cabeças alfaméticos em apenas 14 linhas de código.

O quebra-cabeça alfamético mais conhecido é SEND + MORE = MONEY.

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)

Você pode executar o programa a partir da linha de comando. No Linux, ficaria assim. (Isso pode levar algum tempo, dependendo da velocidade do seu computador, e não há barra de progresso. Apenas seja paciente!)

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

Encontrando todas as ocorrências de um padrão

A primeira coisa que esse solucionador alfamético faz é encontrar todas as letras (A–Z) no quebra-cabeça.

>>> 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. O módulo re é a implementação de expressões regulares do Python. Ele tem uma função bacana chamada findall() que pega um padrão de expressão regular e uma string e encontra todas as ocorrências do padrão dentro da string. Nesse caso, o padrão corresponde a sequências de números. A função findall() retorna uma lista de todas as substrings que corresponderam ao padrão.
  2. Aqui o padrão de expressão regular corresponde a sequências de letras. Novamente, o valor de retorno é uma lista e cada item na lista é uma string que corresponde ao padrão de expressão regular.

Aqui está outro exemplo que vai esticar um pouco o seu cérebro.

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

Surpreso? A expressão regular procura um espaço, um s e, em seguida, a série mais curta possível de qualquer caractere (.*?), um espaço e outro s. Bem, olhando para essa string de entrada, vejo cinco correspondências:

  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.

Este é o trava-línguas mais difícil do idioma inglês.

Mas a função re.findall() retornou apenas três correspondências. Especificamente, ele retornou o primeiro, o terceiro e o quinto. Por que isso? Porque não retorna correspondências sobrepostas. A primeira correspondência se sobrepõe à segunda, de modo que a primeira é retornada e a segunda é ignorada. Em seguida, o terceiro se sobrepõe a quarta, de modo que a terceira é retornada e a quarta é ignorada. Finalmente, a quinta é retornada. Três corresponências, não cinco.

Isso não tem nada a ver com o solucionador alfamético; Eu só pensei que isso era interessante.

Encontrando os itens únicos em uma lista do Python

Os conjuntos do python tornam trivial encontrar os itens exclusivos em uma lista do python.


>>> 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. Dada uma lista de várias strings, a função set() retornará um conjunto de strings únicas da lista. Isso faz sentido se você pensar nisso como um loop for. Pegue o primeiro item da lista, coloque-o no conjunto. Segundo. Terceiro. Quarto. Quinto – espere, isso já está no conjunto, então só é listado uma vez, porque os conjuntos do Python não permitem duplicatas. Sexto. Sétimo – novamente, uma duplicata, então só é listada uma vez. O resultado final? Todos os itens exclusivos da lista original, sem duplicatas. A lista original nem precisa ser classificada primeiro.
  2. A mesma técnica funciona com strings, pois uma string é apenas uma sequência de caracteres.
  3. Dada uma lista de strings, ''.join(a_list) concatena todas as strings em uma.
  4. Assim, dada uma lista de strings, esta linha de código retorna todos os caracteres únicos em todas as strings, sem duplicatas.

O solucionador alfamético usa essa técnica para construir um conjunto de todos os caracteres únicos do quebra-cabeça.

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

Essa lista é usada posteriormente para atribuir dígitos a caracteres à medida que o solucionador percorre as soluções possíveis.

Fazendo afirmações

Como muitas linguagens de programação, Python tem uma declaração assert. Aqui está como funciona.

>>> 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. A declaração assert é seguida por qualquer expressão Python válida. Nesse caso, a expressão 1 + 1 == 2 é avaliada como True, portanto, a instrução assert não faz nada.
  2. No entanto, se a expressão Python for avaliada como False, a instrução assert gerará um AssertionError.
  3. Você também pode incluir uma mensagem legível que é impressa se o AssertionError for gerado.

Portanto, esta linha de código:

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

…é equivalente a isso:

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

O solucionador alfamético usa essa declaração assert exata para sair mais cedo se o quebra-cabeça contiver mais de dez letras únicas. Como a cada letra é atribuído um dígito único e existem apenas dez dígitos, um quebra-cabeça com mais de dez letras únicas não pode ter uma solução.

Expressões do gerador

Uma expressão geradora é como uma função geradora sem a função.

>>> 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. Uma expressão geradora é como uma função anônima que produz valores. A expressão em si parece uma compreensão de lista, mas está entre parênteses em vez de colchetes.
    2. A expressão geradora retorna… um iterador.
    3. Chamar next(gen) retorna o próximo valor do iterador.
    4. Se desejar, você pode percorrer todos os valores possíveis e retornar uma tupla, lista ou conjunto, passando a expressão geradora para tuple(), list() ou set(). Nesses casos, você não precisa de um conjunto extra de parênteses — apenas passe a expressão “nua” ord(c) para c em unique_characters para a função tuple(), e o Python descobre que é uma expressão geradora.

Observação

Usar uma expressão geradora em vez de uma compreensão de lista pode economizar CPU e RAM. Se você está construindo uma lista apenas para jogá-la fora (por exemplo, passando para tuple() ou set()), use uma expressão geradora!

Aqui está outra maneira de fazer a mesma coisa, usando uma função de gerador:

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

gen = ord_map(unique_characters)

A expressão do gerador é mais compacta, mas funcionalmente equivalente.

Calculando Permutações… A Maneira Preguiçosa!

Em primeiro lugar, o que diabos são permutações? Permutações são um conceito matemático. (Na verdade, existem várias definições, dependendo do tipo de matemática que você está fazendo. Aqui estou falando de combinatória, mas se isso não significa nada para você, não se preocupe. Como sempre, a Wikipedia é sua amigo.)

A ideia é que você pegue uma lista de coisas (podem ser números, podem ser letras, podem ser ursos dançantes) e encontrar todas as maneiras possíveis de dividi-las em listas menores. Todas as listas menores têm o mesmo tamanho, que pode ser tão pequeno quanto 1 e tão grande quanto o número total de itens. Ah, e nada pode ser repetido. Os matemáticos dizem coisas como “vamos encontrar as permutações de 3 itens diferentes tomados 2 de cada vez”, o que significa que você tem uma sequência de 3 itens e deseja encontrar todos os pares ordenados possíveis.

>>> 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. O módulo itertools tem todos os tipos de coisas divertidas nele, incluindo uma função permutations() que faz todo o trabalho duro de encontrar permutações.
  2. A função permutations() recebe uma sequência (aqui uma lista de três inteiros) e um número, que é o número de itens que você deseja em cada grupo menor. A função retorna um iterador, que você pode usar em um loop for ou em qualquer lugar antigo que itere. Aqui vou percorrer o iterador manualmente para mostrar todos os valores.
  3. A primeira permutação de [1, 2, 3] pegando 2 de cada vez é (1, 2).
  4. Observe que as permutações são ordenadas: (2, 1) é diferente de (1, 2).
  5. É isso! Essas são todas as permutações de [1, 2, 3] pegando 2 de cada vez. Pares como (1, 1) e (2, 2) nunca aparecem, porque contêm repetições, então não são permutações válidas. Quando não há mais permutações, o iterador gera uma exceção StopIteration.

A função permutations() não precisa receber uma lista. Pode levar qualquer sequência – até mesmo uma string.

>>> 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')]

O módulo itertools tem todos os tipos de coisas divertidas.

  1. Uma string é apenas uma sequência de caracteres. Para fins de encontrar permutações, a string 'ABC' é equivalente à lista ['A', 'B', 'C'].
  2. A primeira permutação dos 3 itens ['A', 'B', 'C'], pegando 3 de cada vez, é ('A', 'B', 'C'). Existem cinco outras permutações – os mesmos três caracteres em todas as ordens concebíveis.
  3. Como a função permutations() sempre retorna um iterador, uma maneira fácil de depurar permutações é passar esse iterador para a função list() integrada para ver todas as permutações imediatamente.

Outras coisas divertidas no módulo 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. A função itertools.product() retorna um iterador contendo o produto cartesiano de duas sequências.
  2. A função itertools.combinations() retorna um iterador contendo todas as combinações possíveis da sequência dada do comprimento dado. É como a função itertools.permutations(), exceto que as combinações não incluem itens duplicados de outros itens em uma ordem diferente. Portanto, itertools.permutations('ABC', 2) retornará ('A', 'B') e ('B', 'A') (entre outros), mas itertools.combinations('ABC', 2) não retornará ('B', 'A') porque é uma duplicata de ('A', 'B') em uma ordem diferente.
>>> 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. Este idioma retorna uma lista das linhas em um arquivo de texto.
  2. Infelizmente (para este exemplo), o idioma list(open(filename)) também inclui os retornos de carro no final de cada linha. Essa compreensão de lista usa o método de string rstrip() para remover os espaços em branco à direita de cada linha. (Strings também têm um método lstrip() para remover o espaço em branco principal e um método strip() que remove ambos.)
  3. A função sorted() pega uma lista e a retorna ordenada. Por padrão, ele classifica em ordem alfabética.
  4. Mas a função sorted() também pode receber uma função como parâmetro de chave e classifica por essa chave. Nesse caso, a função de classificação é len(), então ela classifica por len(cada item). Nomes mais curtos vêm primeiro, depois mais longos e depois mais longos.

O que isso tem a ver com o módulo itertools? fico feliz que tenha perguntado.

…continuando do shell interativo anterior…

>>> 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. A função itertools.groupby() recebe uma sequência e uma função de chave e retorna um iterador que gera pares. Cada par contém o resultado de key_function (cada item) e outro iterador contendo todos os itens que compartilharam esse resultado de chave.
  2. Chamar a função list() “esgotou” o iterador, ou seja, você já gerou todos os itens no iterador para fazer a lista. Não há botão “reset” em um iterador; você não pode simplesmente recomeçar depois de esgotar. Se você quiser fazer um loop novamente (digamos, no próximo loop for), você precisa chamar itertools.groupby() novamente para criar um novo iterador.
  3. Neste exemplo, dada uma lista de nomes já ordenados por comprimento, itertools.groupby(names, len) colocará todos os nomes de 4 letras em um iterador, todos os nomes de 5 letras em outro iterador e assim por diante. A função groupby() é completamente genérica; ele pode agrupar strings pela primeira letra, números por seu número de fatores ou qualquer outra função chave que você possa imaginar.

A função itertools.groupby() só funciona se a sequência de entrada já estiver ordenada pela função de agrupamento. No exemplo acima, você agrupou uma lista de nomes pela função len(). Isso só funcionou porque a lista de entrada já estava classificada por comprimento.

Você está observando de perto?

>>> 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. A função itertools.chain() recebe dois iteradores e retorna um iterador que contém todos os itens do primeiro iterador, seguidos por todos os itens do segundo iterador. (Na verdade, pode levar qualquer número de iteradores e encadeia todos eles na ordem em que foram passados para a função.)
  2. A função zip() faz algo prosaico que acaba sendo extremamente útil: pega qualquer número de sequências e retorna um iterador que retorna tuplas dos primeiros itens de cada sequência, depois os segundos itens de cada, depois o terceiro e assim por diante.
  3. A função zip() para no final da sequência mais curta. range(10, 14) tem 4 itens (10, 11, 12 e 13), mas range(0, 3) tem apenas 3, então a função zip() retorna um iterador de 3 itens.
  4. Por outro lado, a função itertools.zip_longest() para no final da sequência mais longa, inserindo valores None para itens após o final das sequências mais curtas.

OK, tudo isso foi muito interessante, mas como isso se relaciona com o solucionador alfamético? Veja como:

>>> 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. Dada uma lista de letras e uma lista de dígitos (cada um representado aqui como strings de 1 caractere), a função zip criará um par de letras e dígitos, em ordem.
  2. Por que isso é legal? Porque essa estrutura de dados é exatamente a estrutura certa para passar para a função dict() para criar um dicionário que usa letras como chaves e seus dígitos associados como valores. (Esta não é a única maneira de fazer isso, é claro. Você pode usar uma compreensão de dicionário para criar o dicionário diretamente.) Embora a representação impressa do dicionário liste os pares em uma ordem diferente (os dicionários não têm “ordem” por se), você pode ver que cada letra está associada ao dígito, com base na ordenação dos caracteres originais e nas sequências de adivinhação.

O solucionador alfamético usa essa técnica para criar um dicionário que mapeia letras no quebra-cabeça para dígitos na solução, para cada solução possível.

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)))

Mas o que é esse método translate()? Ah, agora você está chegando à parte realmente divertida.

Um novo tipo de manipulação de strings

As strings do Python têm muitos métodos. Você aprendeu sobre alguns desses métodos no capítulo sobre strings do python: lower(), count() e format(). Agora quero apresentar a você uma técnica de manipulação de strings poderosa, mas pouco conhecida: o método translate().

>>> translation_table = {ord('A'): ord('O')}  ①
>>> translation_table                         ②
{65: 79}
>>> 'MARK'.translate(translation_table)       ③
'MORK'
  1. A tradução de strings começa com uma tabela de tradução, que é apenas um dicionário que mapeia um caractere para outro. Na verdade, "caractere" está incorreto - a tabela de tradução realmente mapeia um byte para outro.
  2. Lembre-se, os bytes no Python 3 são inteiros. A função ord() retorna o valor ASCII de um caractere, que, no caso de A–Z, é sempre um byte de 65 a 90.
  3. O método translate() em uma string pega uma tabela de tradução e executa a string nela. Ou seja, ele substitui todas as ocorrências das chaves da tabela de conversão pelos valores correspondentes. Neste caso, “traduzindo” MARK para MORK.

O que isso tem a ver com a resolução de quebra-cabeças alfaméticos? Como se vê, tudo.

>>> 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'

Agora você está chegando à parte realmente divertida.

  1. Usando uma expressão geradora, calculamos rapidamente os valores de byte para cada caractere em uma string. caracteres é um exemplo do valor de sorted_characters na função alphametics.solve().
  2. Usando outra expressão geradora, calculamos rapidamente os valores de byte para cada dígito nesta string. O resultado, palpite, é da forma retornada pela função itertools.permutations() na função alphametics.solve().
  3. Esta tabela de tradução é gerada compactando caracteres e adivinhando juntos e construindo um dicionário a partir da sequência de pares resultante. Isso é exatamente o que a função alphametics.solve() faz dentro do loop for.
  4. Finalmente, passamos esta tabela de tradução para o método translate() da string original do quebra-cabeça. Isso converte cada letra na string para o dígito correspondente (com base nas letras em caracteres e nos dígitos em palpite). O resultado é uma expressão Python válida, como uma string.

Isso é bem impressionante. Mas o que você pode fazer com uma string que é uma expressão Python válida?

Avaliando strings arbitrárias como expressões Python

Esta é a peça final do quebra-cabeça (ou melhor, a peça final do solucionador de quebra-cabeças). Depois de toda essa manipulação sofisticada de strings, ficamos com uma string como '9567 + 1085 == 10652'. Mas isso é uma string, e para que serve uma string? Digite eval(), a ferramenta de avaliação universal do Python.

>>> eval('1 + 1 == 2')
True
>>> eval('1 + 1 == 3')
False
>>> eval('9567 + 1085 == 10652')
True

Mas espere, tem mais! A função eval() não se limita a expressões booleanas. Ele pode lidar com qualquer expressão Python e retornar qualquer tipo de dados.

>>> eval('"A" + "B"')
'AB'
>>> eval('"MARK".translate({65: 79})')
'MORK'
>>> eval('"AAAAA".count("A")')
5
>>> eval('["*"] * 5')
['*', '*', '*', '*', '*']

Mas espere, isso não é tudo!

>>> x = 5
>>> eval("x * 5")         ①
25
>>> eval("pow(x, 2)")     ②
25
>>> import math
>>> eval("math.sqrt(x)")  ③
2.2360679774997898
  1. A expressão que eval() usa pode referenciar variáveis globais definidas fora de eval(). Se chamado dentro de uma função, também pode referenciar variáveis locais.
  2. E funções.
  3. E módulos.

Ei, espere um minuto...

>>> import subprocess
>>> eval("subprocess.getoutput('ls ~')")                  ①
'Desktop         Library         Pictures \
 Documents       Movies          Public   \
 Music           Sites'
>>> eval("subprocess.getoutput('rm /some/random/file')")  ②
  1. O módulo subprocess permite que você execute comandos shell arbitrários e obtenha o resultado como uma string Python.
  2. Comandos shell arbitrários podem ter consequências permanentes.

É ainda pior do que isso, porque há uma função global __import__() que recebe um nome de módulo como uma string, importa o módulo e retorna uma referência a ele. Combinado com o poder de eval(), você pode construir uma única expressão que eliminará todos os seus arquivos:

>>> eval("__import__('subprocess').getoutput('rm /some/random/file')") ①
  1. Agora imagine a saída de 'rm -rf ~'. Na verdade, não haveria saída, mas você também não teria nenhum arquivo.

eval() é do mal

Bem, a parte ruim é avaliar expressões arbitrárias de fontes não confiáveis. Você só deve usar eval() na entrada confiável. Claro, o truque é descobrir o que é “confiável”. Mas aqui está algo que eu sei com certeza: você NÃO deve pegar este solucionador de alfamética e colocá-lo na internet como um pequeno serviço web divertido. Não cometa o erro de pensar: “Nossa, a função faz muita manipulação de strings antes de obter uma string para avaliar; Não consigo imaginar como alguém poderia explorar isso.” Alguém VAI descobrir como esconder código executável desagradável por toda essa manipulação de strings (coisas mais estranhas aconteceram), e então você pode dar adeus ao seu servidor.

Mas certamente há alguma maneira de avaliar expressões com segurança? Para colocar eval() em uma sandbox onde não pode acessar ou prejudicar o mundo exterior? Bem, sim e não.

>>> 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
  1. O segundo e o terceiro parâmetros passados para a função eval() atuam como namespaces globais e locais para avaliar a expressão. Nesse caso, ambos estão vazios, o que significa que quando a string "x * 5" é avaliada, não há referência a x no namespace global ou local, então eval() lança uma exceção.
  2. Você pode incluir seletivamente valores específicos no namespace global listando-os individualmente. Então essas — e apenas essas — variáveis estarão disponíveis durante a avaliação.
  3. Mesmo que você tenha importado o módulo math, você não o incluiu no namespace passado para a função eval(), então a avaliação falhou.

Puxa, isso foi fácil. Deixe-me fazer um web service alfamético agora!

>>> eval("pow(5, 2)", {}, {})                   ①
25
>>> eval("__import__('math').sqrt(5)", {}, {})  ②
2.2360679774997898
  1. Mesmo que você tenha passado dicionários vazios para os namespaces globais e locais, todas as funções internas do Python ainda estão disponíveis durante a avaliação. Então pow(5, 2) funciona, porque 5 e 2 são literais, e pow() é uma função embutida.
  2. Infelizmente (e se você não vê por que é lamentável, continue lendo), a função __import__() também é uma função embutida, então também funciona.

Sim, isso significa que você ainda pode fazer coisas desagradáveis, mesmo se você definir explicitamente os namespaces globais e locais para dicionários vazios ao chamar eval():

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

Ops. Estou feliz por não ter feito esse serviço da web alphametics. Existe alguma maneira de usar eval() com segurança? Bem, sim e não.

>>> 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. Para avaliar expressões não confiáveis com segurança, você precisa definir um dicionário de namespace global que mapeie "__builtins__" para None, o valor nulo do Python. Internamente, as funções “incorporadas” estão contidas em um pseudo-módulo chamado "__builtins__". Este pseudomódulo (ou seja, o conjunto de funções internas) é disponibilizado para expressões avaliadas, a menos que você o substitua explicitamente.
  2. Certifique-se de ter substituído __builtins__. Não __built-in__, __built-ins__, ou alguma outra variação que funcionará muito bem, mas o exporá a riscos catastróficos.

Então eval() está seguro agora? Bem, sim e não.

>>> eval("2 ** 2147483647",
...     {"__builtins__":None}, {})          ①
  1. Mesmo sem acesso a __builtins__, você ainda pode iniciar um ataque de negação de serviço. Por exemplo, tentar elevar 2 à potência 2147483647 aumentará a utilização da CPU do seu servidor para 100% por algum tempo. (Se você estiver tentando isso no shell interativo, pressione Ctrl-C algumas vezes para sair dele.) Tecnicamente, essa expressão retornará um valor eventualmente, mas enquanto isso seu servidor não fará nada.

No final, é possível avaliar com segurança expressões Python não confiáveis, para alguma definição de “seguro” que acaba não sendo muito útil na vida real. Tudo bem se você estiver apenas brincando, e tudo bem se você apenas passar uma entrada confiável. Mas qualquer outra coisa é apenas pedir problemas.

Juntando tudo

Para recapitular: este programa resolve quebra-cabeças alfaméticos por força bruta, ou seja, através de uma busca exaustiva de todas as soluções possíveis. Para isso, é preciso …

  1. Encontra todas as letras do quebra-cabeça com a função re.findall()
  2. Encontre todas as letras únicas no quebra-cabeça com conjuntos e a função set()
  3. Verifica se há mais de 10 letras únicas (o que significa que o quebra-cabeça é definitivamente insolúvel) com uma declaração assert
  4. Converte as letras em seus equivalentes ASCII com um objeto gerador
  5. Calcula todas as soluções possíveis com a função itertools.permutations()
  6. Converte cada solução possível em uma expressão Python com o método de string translate()
  7. Testa cada solução possível avaliando a expressão Python com a função eval()
  8. Retorna a primeira solução avaliada como True

…em apenas 14 linhas de código.

Leitura adicional

Muito obrigado a Raymond Hettinger por concordar em relicenciar seu código para que eu pudesse portá-lo para o Python 3 e usá-lo como base para este capítulo.

Esse artigo é uma tradução de um capítulo do livro "Dive Into Python 3" escrito por Mark Pilgrim. Você pode ler o livro desde o início em português clicando aqui.

Traduzido por Acervo Lima. O original pode ser acessado aqui.

Licença

0 comentários:

Postar um comentário

Assinar: Postar comentários (Atom)