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