Aritmética com Regexp

Dia desses eu descobri que o SPOJ agora tem uma seção só para problemas pontuados por shortest code, e fiquei super animado! Mas não demorou muito até eu notar a maior constante desse tipo de concurso: você pode até participar usando Python e Haskell, mas, para competir, só usando Perl.

Então lá fui eu aprender Perl. Apanhei um pouco no começo, mas acabei descobrindo o segredo para conseguir uma boa colocação: basta resolver todos os problemas usando regexp. Os regexps originais do Posix são apenas autômatos finitos, mas a engine do Perl é bem mais poderosa que isso.

Naturalmente, eu fiquei tentado a ver quais são os limites do regexps do Perl. Por exemplo, dá pra fazer aritmética com eles? Depois de pensar um pouco, acabei concluindo que dá sim!

Antes de mostrar como eu fiz, uma revisão de Perl. O único comando que eu vou usar é o s///g (substituição com regexp). O primeiro argumento é uma regexp que será procurada na sua string de input, e o segundo é um string, possivelmente interpolada, que vai substituir o match. A opção g permite múltiplas substituições, recomeçando do ponto onde a última terminou. Por exemplo:

input: "kkkkkk Restart kkkk sacanagem"
regexp: s/k+/LOL/g
output: "LOL Restart LOL sacanagem"

Antes de fazer qualquer conta, precisamos também definir a representação numérica. Na escola nós aprendemos a fazer contas em decimal, que tem dez símbolos, de 0 a 9. Mais tarde, computeiros aprendem binário, que tem só dois símbolos: 0 e 1. Eu vou agora fazer contas em unário, que tem um símbolo só: I (eu escolhi o símbolo I para ficar parecido com os números romanos).

No sistema unário, o número é representado por repetições do símbolo único. Por exemplo:

1  = I
4  = IIII
10 = IIIIIIIIII

Por fim, para as regexps não ficarem muito grandes, eu vou me restringir apenas às operações definidas nos inteiros positivos (ou seja, tanto os argumentos quanto os resultados precisam ser inteiros positivos). Vamos lá então:

Adição

s/\+(I+)=/$1/g

A adição é a operação mais simples, basta tirar os sinais de mais e igual. O resultado é a concatenação dos operandos. Vamos ver, por exemplo, como ficaria 4+7.

"IIII+IIIIIII="
s/\+(I+)=/$1/g

"IIIIIIIIIII"

Como esperado, o resultado é 11.

Subtração

s/(I+)-\1=//g

Para fazer a subtração, nós usamos o recurso de backreference. Se ele achar um conjunto no lado direito, pode apagar esse conjunto e um outro igual no lado esquerdo. Sobram só os caracteres que estavam no primeiro mas não estavam no segundo, ou seja, a subtração deles. Vejamos o exemplo de 7-4:

"IIIIIII-IIII="
s/(I+)-\1=//g

"III"

Multiplicação

s/(I)(?=I*\*(I+))(\*I+=)?/$2/g

A multiplicação é um pouco mais complexa, agora precisamos usar o operador (?=), que serve para fazer positive lookahead, ou seja, ele faz o match, mas não consome o input. Como resultado, o operador /g pode passar várias vezes pela mesma string, e cada I que ele encontra no lado esquerdo é trocado pela string inteira do lado direito. Vejamos um exemplo passo-a-passo de 3*6 (mas note que o Perl faz isso num passo só, eu estou fazendo em vários passos só pra ficar mais claro).

"III*IIIIIII="
s/(I)(?=I*\*(I+))(\*I+=)?/$2/g

"IIIIII""II*IIIIIII="
s/(I)(?=I*\*(I+))(\*I+=)?/$2/g

"IIIIIIIIIIII""I*IIIIIII="
s/(I)(?=I*\*(I+))(\*I+=)?/$2/g

"IIIIIIIIIIIIIIIIII"

Divisão

s/(I+)(?=I*\/\1\=)(\/I+=)?/I/g

A divisão é similar à multiplicação, mas, ao invés de somas sucessivas, nós usamos subtrações sucessivas. Vejamos o exemplo de 12/4:

"IIIIIIIIIIII/IIII="
s/(I+)(?=I*\/\1\=)(\/I+=)?/I/g

"I""IIIIIIII/IIII="
s/(I+)(?=I*\/\1\=)(\/I+=)?/I/g

"II""IIII/IIII="
s/(I+)(?=I*\/\1\=)(\/I+=)?/I/g

"III"

GCD

s/gcd\((I+)\1*,\1+\)=/$1/g

Por que parar nas quatro operações? É bem simples fazer também o gcd (máximo divisor comum). Nesse caso basta mandar repetir a backreference, o resultado é que os matches sempre vão ser múltiplos do tamanho dela. Como o primeiro grupo é greedy, ele vai tentar fazer o maior match possível, e daí temos como resultado o gcd. Vejamos para 15 e 9:

"gcd(IIIIIIIIIIIIIII,IIIIIIIII)="
s/gcd\((I+)\1*,\1+\)=/$1/g

"III"

Embora brincar com regexps desse jeito seja divertido, vale a recomendação de sempre: faça isso apenas acompanhado de adulto responsável :)

O algoritmo mais lento do oeste

Por que as pessoas aprendem complexidade computacional? Para achar os algoritmos mais rápidos, é claro. Dada uma lista de algoritmos equivalentes, você pode ordená-los pela complexidade, e o primeiro da lista é o mais eficiente.

Uma brincadeira divertida é fazer isso ao contrário: dada uma especificação, qual o algoritmo determinístico mais lento que a resolve? Por exemplo, qual o algoritmo mais lento para decompor um número em fatores primos?

O algoritmo mais rápido que resolve esse problema é o algoritmo de Shor, que roda em O((log n)³) e requer um computador quântico. Meu candidato a algoritmo mais lento é o abaixo, que na falta de nome melhor eu chamei de Fatoração Bozo:

import itertools

def factor(n):
 solutions = []
 for f in itertools.product(range(1,1+n),repeat=n):
   if reduce(lambda x,y: x*y, f) == n:
     solutions.append(filter(lambda x:x>1, list(f)))
 solutions.sort(key=len, reverse=True)
 return solutions[0]

Parece complexo, mas o funcionamento é bem simples. Vamos pensar no nosso objetivo: queremos achar uma lista de fatores primos, que multiplicados resultam no número desejado (vamos chamá-lo de N).

Nós sabemos que os primos dessa lista são menores ou iguais a N, e sabemos também que essa lista nunca vai ter mais que N elementos. A primeira coisa que fazemos no algoritmo é gerar todas as possíveis listas candidatas, que são o produto cartesiano do intervalo de 1 a N com N repetições. Por exemplo, para N=3, teríamos 27 combinações:

111 112 113 121 122 123 131 132 133
211 212 213 221 222 223 231 232 233
311 312 313 321 322 323 331 332 333

Em python o jeito mais fácil de gerar essa lista é usando itertools.product(), que faz o serviço sozinho. Mas, dessas listas, só interessam aquelas cujo produto seja igual a N. Por exemplo, se N=4, então as listas interessantes são:

1114 1122 1141 1212 1221
1411 2112 2121 2211 4111

Python não tem um operador para multiplicação de listas como tem o sum() para adições, mas pra isso que serve o reduce() né. As listas selecionadas até agora estão boas, mas elas têm um monte de elementos 1 que não contribuem em nada. Usando o filter() podemos jogar fora os uns. Para N=4:

4 22 4 22 22 4 22 22 22 4

Várias listas repetidas, mas tudo bem. O truque agora é notar que, de todas essas listas, a fatoração em primos é a lista de comprimento máximo. É fácil provar isso: se a lista máxima tivesse um elemento composto, então você poderia fatorá-lo, e trocar o número composto pela sua fatoração. Logo, você estaria gerando uma lista maior que a lista máxima, o que é uma contradição.

Pedindo para que o Python ordene as listas por tamanho, basta pegar a primeira lista da seqüência e temos então a nossa fatoração!

E qual a complexidade dessa solução? Ela é dominada pelo número de listas que geramos no primeiro passo, então a complexidade da Fatoração Bozo é maior que O(nⁿ). Se você não tem noção de como isso é lento, veja o tempo que esse código leva para fatorar alguns números:

N=6 - 0.2 segundos
N=7 - 2.1 segundos
N=8 - 45.8 segundos
N=9 - 20 minutos

A função cresce tão rapidamente que, para fatorar N=18, você levaria mais tempo que a idade do universo até agora! Como exercício para o leitor, tente calcular quanto tempo levaria para fatorar o RSA-704, que em decimal tem 212 dígitos :)