O que um verificador de palíndromos tem de decidir antes de poder responder

A pergunta não está definida enquanto não se tomarem quatro decisões

Um palíndromo lê-se igual nos dois sentidos. Essa definição só é completa para uma cadeia de minúsculas nuas, e quase nenhum texto real o é. Assim que uma frase tem maiúsculas, espaços, vírgulas ou acentos, a pergunta parte-se em quatro: uma maiúscula equivale à sua minúscula?, os espaços contam como caracteres?, a pontuação conta?, uma letra acentuada é a mesma letra que a sua base? Quatro respostas de sim ou não, dezasseis combinações, e as que importam formam uma sequência encaixada, cada uma admitindo mais frases do que a anterior.

A tabela acima é essa sequência aplicada a seis frases, executada em vez de discutida. Leia-a coluna a coluna e cada coluna ganha o seu lugar: os espaços sozinhos promovem a frase italiana, a pontuação sozinha promove a inglesa, e o dobramento de acentos sozinho promove a francesa, a espanhola e a portuguesa. Um verificador que fixe qualquer uma destas decisões está a responder a uma pergunta diferente da que o seu utilizador fez, e responde-a em silêncio.

Quatro frases, quatro pontos de paragem diferentes

Comecemos pela inglesa, que é a frase que toda a gente cita. «A man, a plan, a canal: Panama» não é um palíndromo tal e qual: o A maiúsculo de uma ponta enfrenta um a minúsculo da outra. Dobre a caixa e continua a não ser: os espaços não caem simetricamente. Retire os espaços e continua a não ser, porque ficam uma vírgula e dois pontos. Retire também a pontuação e finalmente é: amanaplanacanalpanama, vinte e um caracteres, simétrico. Foi preciso ligar três políticas antes de a resposta famosa aparecer.

A alemã «Ein Esel lese nie» para um degrau antes de tudo o resto da tabela. Dobre a caixa e já é um palíndromo: einesellesenie lê-se igual nos dois sentidos, e a frase com os seus espaços no lugar também, porque os seus comprimentos de palavra — três, quatro, quatro, três — são simétricos por construção. Um verificador que retira sempre os espaços acerta aqui, mas pela razão errada, e nunca poderá dizer-lhe que esta frase é um palíndromo no sentido mais forte de que os seus espaços também o são. O outro exemplo alemão, «O, Genie, der Herr ehre dein Ego!», só precisa da regra de pontuação.

As três frases românicas precisam todas da quarta regra e falham todas as anteriores. «Socorram-me, subi no ônibus em Marrocos», com a pontuação retirada mas os acentos mantidos, dá socorrammesubinoônibusemmarrocos, cujo inverso é socorrammesubinôonibusemmarrocos: o acento migrou de um lado para o outro, e as cadeias diferem. Dobre o diacrítico e ambas se tornam socorrammesubinoonibusemmarrocos. O mesmo acontece com ésope…, cujo inverso acaba em é, e com dábale…, cujo inverso acaba em á. Repare no que isto implica: um verificador construído para o inglês declarará falhados três palíndromos europeus perfeitamente bons, e fá-lo-á sem qualquer mensagem de erro.

Inverter uma cadeia também não é uma só operação

Todo o verificador de palíndromos compara um texto com o seu inverso, e é nesse inverso que vive a segunda metade do problema. A inversão de uma linha que toda a gente escreve — s.split('').reverse().join('') — inverte unidades de código UTF-16. Um artigo companheiro desta série trata do que é um caráter; a consequência aqui é que todo o caráter fora do plano multilingue básico é guardado em duas unidades de código, e invertê-las individualmente troca o par. Inverta «ça va 😀» assim e o resultado contém um substituto baixo seguido de um substituto alto: oito pontos de código em vez de sete, e isWellFormed() devolve falso. No ecrã é um quadrado de substituição.

O remendo habitual é inverter pontos de código: [...s].reverse().join(''). Repara o emoji — «ça va 😀» torna-se «😀 av aç», ainda sete pontos de código — e continua a não bastar. Tome «José» em forma decomposta, onde o é é um e seguido de um acento agudo combinante: cinco pontos de código, quatro grafemas. Inverter os pontos de código põe o acento combinante à cabeça, onde não tem letra a que se agarrar, e deixa um e nu: o resultado tem cinco grafemas onde havia quatro, e o acento desenha-se sobre nada. O caso alemão é ainda mais vistoso. Decomponha «Grüße» e inverta os seus pontos de código e obtém eß̈urG: o trema saltou do u e aterrou sobre o ß.

Os emojis compostos por vários pontos de código falham do mesmo modo. A família 👨‍👩‍👧 são três pessoas unidas por juntores de largura zero: dezasseis unidades de código, treze pontos de código, um só grafema. Inverter os seus pontos de código produz uma família que se desenha 👧‍👩‍👨 — filha, mãe, pai —, ou seja outro emoji, não um invertido; inverter as suas unidades de código produz algo que se desenha aos pedaços. Só a inversão por grupo de grafemas o deixa intacto.

Inverter por grupo de grafemas

Um grupo de grafemas é o nome que o Unicode dá ao que um leitor chama um caráter: uma letra base mais o que se combine com ela, ou uma sequência de emoji inteira. O JavaScript expõe as regras de segmentação diretamente através do Intl.Segmenter, e uma inversão correta cabe em três linhas: construir um segmentador com granularidade «grapheme», espalhar a sua saída, inverter, juntar. Sobre todos os exemplos acima faz o correto: o emoji sobrevive, a família continua uma família, e o Grüße decomposto volta como eßürG, com o trema ainda sobre o seu u.

Por baixo esconde-se uma decisão de normalização, e a palavra francesa été revela-a numa linha. Em forma composta são três pontos de código e invertê-los devolve été: palíndromo. Em forma decomposta são cinco pontos de código, invertê-los dá uma cadeia com os acentos fora do sítio, e a mesma palavra visível é declarada não palíndroma. A inversão por grupo de grafemas dá a resposta certa em ambas as formas — mas se comparar as duas formas entre si continuam desiguais, e é por isso que um verificador deve normalizar para NFC antes de tudo o resto. O artigo desta série dedicado aos acentos trata as formas NFC e NFD por extenso.

Um palíndromo numérico é outro problema

Os números parecem o caso fácil e não são. Um palíndromo numérico é uma propriedade de um valor numa base; um palíndromo textual é uma propriedade de uma representação. 12321 é um palíndromo em base dez. Representado para um leitor deixa de o ser em todas as locales deste artigo: 12,321 invertido dá 123,21 em inglês, 12.321 invertido dá 123.21 em alemão, espanhol e italiano, e 12 321 invertido dá 123 21 em francês e português — sendo o separador um espaço inquebrável estreito U+202F em francês e um espaço inquebrável normal U+00A0 em português, dois caracteres invisíveis que uma comparação ingénua tratará de qualquer modo como diferentes.

Da mesma distinção decorrem mais três diferenças. Um sinal é um caráter mas não um dígito: -121 como texto inverte-se em 121- e falha, ao passo que como valor a questão de saber se um número negativo pode ser palíndromo é uma convenção a escolher. Um separador decimal é igualmente um caráter: 0,1 inverte-se em 1,0, duas cadeias diferentes que denotam valores diferentes. E os zeros à esquerda existem em texto e não em números: 010 é palíndromo como texto, e como número é 10, que não é. Se a sua entrada é um número, retire a formatação e trabalhe sobre os dígitos; se é um texto que parece numérico, diga-o e trate-o como texto.

O que construir, por ordem

A receita que sobrevive às seis línguas é curta. Normalize primeiro para NFC, para que o mesmo texto visível tenha sempre a mesma representação. Aplique depois as políticas que decidiu e sabe nomear: minúsculas, retirar os espaços, retirar tudo o que não seja letra ou dígito, dobrar os acentos decompondo e removendo as marcas. Depois inverta por grupo de grafemas e compare. Quatro passos, e cada um é uma decisão que pode expor na interface em vez de um valor por omissão escondido no código.

Uma última observação sobre a inversão, porque é contraintuitiva e esconde erros. Inverter duas vezes devolve sempre a cadeia original, seja qual for a unidade escolhida: unidades de código, pontos de código e grafemas são todos involuções sobre a sequência que manipulam. Por isso um teste de ida e volta nada lhe diz sobre se a sua inversão está correta. O único teste que apanha os casos partidos é olhar para o resultado intermédio, e a forma mais rápida de o olhar é contar os grafemas antes e depois: para um José decomposto são quatro e depois cinco.

Perguntas frequentes

«A man, a plan, a canal: Panama» é um palíndromo?

Sob a política habitual, sim; tal como está escrito, não. Dobre a caixa, retire os espaços e retire a pontuação e torna-se amanaplanacanalpanama, que é simétrico. Mantenha qualquer um dos três e não é. Não é uma pergunta com rasteira: é exatamente o que faz a fórmula «ignorando maiúsculas, espaços e pontuação» de qualquer definição de manual, e uma ferramenta que deixa ligar as três regras em separado diz a verdade em vez de a esconder.

Porque é que ao inverter o meu texto saiu um quadrado partido?

Porque a inversão trabalhou sobre unidades de código UTF-16 e o seu texto continha um caráter fora do plano multilingue básico: um emoji, um ideograma CJK raro, um símbolo matemático. Esses são guardados como par substituto, e inverter as duas metades produz uma sequência que nenhuma fonte consegue desenhar. Verifique com isWellFormed(), que devolve falso sobre essa cadeia, e passe a inversão a grupos de grafemas com Intl.Segmenter.

Um verificador de palíndromos deve ignorar os acentos?

Deve oferecer a escolha e dobrar por omissão, porque a tradição do jogo de palavras em francês, espanhol e português trata é e e como a mesma letra. Sem dobramento, três das seis frases da tabela deixam de ser palíndromos: «Ésope reste ici et se repose», «Dábale arroz a la zorra el abad» e «Socorram-me, subi no ônibus em Marrocos» falham todas no primeiro e no último caráter. Dobre decompondo para NFD, apagando as marcas combinantes e recompondo — o artigo desta série sobre os acentos explica porque isso não é o mesmo que substituir letras uma a uma.

12321 é um palíndromo?

Como número em base dez, sim. Como texto mostrado, não — em todas as locales deste artigo. Formatado para um leitor torna-se 12,321 em inglês e 12.321 ou 12 321 noutros lados, e inverter essas cadeias dá 123,21, 123.21 e 123 21. Se verifica números, trabalhe sobre os dígitos e decida explicitamente o que fazer com um sinal, um separador decimal e os zeros à esquerda: -121 inverte-se em 121-, 0,1 inverte-se em 1,0, e 010 é palíndromo como texto enquanto o número que denota é 10.

Inverter uma cadeia duas vezes devolve sempre a original?

Sim, e é precisamente por isso que um teste de ida e volta não vale nada aqui. Inverter por unidade de código, por ponto de código ou por grupo de grafemas são todas involuções: aplique qualquer uma duas vezes e recupera a entrada, mesmo quando a inversão simples produziu entretanto uma cadeia partida. Teste antes o resultado intermédio: compare o número de grafemas antes e depois, ou chame isWellFormed() sobre ele.

Pode uma só palavra ser palíndroma sem nenhuma destas regras?

Sim, e esses são os únicos casos em que a pergunta tem uma só resposta. As palavras inteiramente em minúsculas ASCII como racecar, radar, kayak, o francês ressasser, o espanhol reconocer, o italiano onorarono e o português reviver são palíndromos sem política nenhuma — verificado caráter a caráter. Ponha-lhes uma maiúscula e precisa da regra de caixa: os alemães Reliefpfeiler, Rentner e Lagerregal só são palíndromos depois de dobrada a capital inicial, o que é uma política e não quatro.