Lo que un verificador de palíndromos debe decidir antes de poder responder

La pregunta no está definida hasta tomar cuatro decisiones

Un palíndromo se lee igual en los dos sentidos. Esa definición solo es completa para una cadena de minúsculas desnudas, y casi ningún texto real lo es. En cuanto una frase tiene mayúsculas, espacios, comas o acentos, la pregunta se parte en cuatro: ¿una mayúscula equivale a su minúscula?, ¿los espacios cuentan como caracteres?, ¿cuenta la puntuación?, ¿una letra acentuada es la misma letra que su base? Cuatro respuestas de sí o no, dieciséis combinaciones, y las que importan forman una secuencia anidada, cada una admitiendo más frases que la anterior.

La tabla de arriba es esa secuencia aplicada a seis frases, ejecutada en vez de discutida. Léela columna a columna y cada columna se gana su sitio: los espacios por sí solos promueven la frase italiana, la puntuación por sí sola promueve la inglesa, y el plegado de acentos por sí solo promueve la francesa, la española y la portuguesa. Un verificador que fije cualquiera de estas decisiones está respondiendo a una pregunta distinta de la que hizo su usuario, y la responde en silencio.

Cuatro frases, cuatro puntos de parada distintos

Empecemos por la inglesa, que es la frase que todo el mundo cita. «A man, a plan, a canal: Panama» no es un palíndromo tal cual: la A mayúscula de un extremo se enfrenta a una a minúscula del otro. Pliega la caja y sigue sin serlo: los espacios no caen simétricamente. Quita los espacios y sigue sin serlo, porque quedan una coma y dos puntos. Quita también la puntuación y por fin lo es: amanaplanacanalpanama, veintiún caracteres, simétrico. Hubo que activar tres políticas antes de que apareciera la respuesta famosa.

La alemana «Ein Esel lese nie» se detiene un escalón antes que todo lo demás de la tabla. Pliega la caja y ya es un palíndromo: einesellesenie se lee igual en ambos sentidos, y la frase con sus espacios en su sitio también, porque sus longitudes de palabra — tres, cuatro, cuatro, tres — son simétricas por construcción. Un verificador que siempre quita los espacios acierta aquí, pero por la razón equivocada, y nunca podrá decirte que esta frase es un palíndromo en el sentido más fuerte de que sus espacios también lo son. El otro ejemplo alemán, «O, Genie, der Herr ehre dein Ego!», solo necesita la regla de puntuación.

Las tres frases románicas necesitan todas la cuarta regla y fallan todas las anteriores. «Dábale arroz a la zorra el abad», con la puntuación quitada pero los acentos conservados, da dábalearrozalazorraelabad, cuyo inverso es dabalearrozalazorraelabád: el acento ha migrado del primer carácter al último, y las cadenas difieren. Pliega el diacrítico y ambas se vuelven dabalearrozalazorraelabad. Lo mismo pasa con ésope…, cuyo inverso termina en é, y con socorram-me…, donde el ô aterriza en el sitio equivocado. Fíjate en lo que implica: un verificador construido para el inglés declarará fallidos tres palíndromos europeos perfectamente buenos, y lo hará sin ningún mensaje de error.

Invertir una cadena tampoco es una sola operación

Todo verificador de palíndromos compara un texto con su inverso, y en ese inverso vive la segunda mitad del problema. La inversión de una línea que todo el mundo escribe — s.split('').reverse().join('') — invierte unidades de código UTF-16. Un artículo compañero de esta serie trata de qué es un carácter; la consecuencia aquí es que todo carácter fuera del plano multilingüe básico se almacena en dos unidades de código, e invertirlas por separado intercambia el par. Invierte «ça va 😀» así y el resultado contiene un suplente bajo seguido de un suplente alto: ocho puntos de código en vez de siete, e isWellFormed() devuelve falso. En pantalla es un cuadro de reemplazo.

El arreglo habitual es invertir puntos de código: [...s].reverse().join(''). Repara el emoji — «ça va 😀» se vuelve «😀 av aç», todavía siete puntos de código — y sigue sin bastar. Toma «José» en forma descompuesta, donde la é es una e seguida de un acento agudo combinante: cinco puntos de código, cuatro grafemas. Invertir los puntos de código pone el acento combinante en cabeza, donde no tiene letra a la que engancharse, y deja una e desnuda: el resultado tiene cinco grafemas donde había cuatro, y el acento se dibuja sobre nada. El caso alemán es aún más vistoso. Descompón «Grüße» e invierte sus puntos de código y obtienes eß̈urG: la diéresis ha saltado de la u y ha aterrizado sobre la ß.

Los emojis compuestos de varios puntos de código fallan igual. La familia 👨‍👩‍👧 son tres personas unidas por juntores de ancho cero: dieciséis unidades de código, trece puntos de código, un solo grafema. Invertir sus puntos de código produce una familia que se dibuja 👧‍👩‍👨 — hija, madre, padre —, es decir otro emoji, no uno invertido; invertir sus unidades de código produce algo que se dibuja en fragmentos. Solo la inversión por grupo de grafemas lo deja intacto.

Invertir por grupo de grafemas

Un grupo de grafemas es el nombre que da Unicode a lo que un lector llama un carácter: una letra base más lo que se combine con ella, o una secuencia de emoji entera. JavaScript expone las reglas de segmentación directamente mediante Intl.Segmenter, y una inversión correcta cabe en tres líneas: construir un segmentador con granularidad «grapheme», desplegar su salida, invertir, unir. Sobre todos los ejemplos anteriores hace lo correcto: el emoji sobrevive, la familia sigue siendo una familia, y el Grüße descompuesto vuelve como eßürG, con la diéresis todavía sobre su u.

Debajo se esconde una decisión de normalización, y la palabra francesa été la revela en una línea. En forma compuesta son tres puntos de código e invertirlos devuelve été: palíndromo. En forma descompuesta son cinco puntos de código, invertirlos da una cadena con los acentos fuera de sitio, y la misma palabra visible se declara no palíndroma. La inversión por grupo de grafemas da la respuesta correcta en ambas formas — pero si comparas las dos formas entre sí siguen siendo desiguales, y por eso un verificador debe normalizar a NFC antes que nada. El artículo de esta serie dedicado a los acentos trata las formas NFC y NFD por extenso.

Un palíndromo numérico es otro problema

Los números parecen el caso fácil y no lo son. Un palíndromo numérico es una propiedad de un valor en una base; un palíndromo textual es una propiedad de una representación. 12321 es un palíndromo en base diez. Representado para un lector deja de serlo en todas las locales de este artículo: 12,321 invertido da 123,21 en inglés, 12.321 invertido da 123.21 en alemán, español e italiano, y 12 321 invertido da 123 21 en francés y portugués — donde el separador es un espacio duro estrecho U+202F en francés y un espacio duro normal U+00A0 en portugués, dos caracteres invisibles que una comparación ingenua tratará de todos modos como distintos.

De la misma distinción se siguen otras tres diferencias. Un signo es un carácter pero no un dígito: -121 como texto se invierte en 121- y falla, mientras que como valor la cuestión de si un número negativo puede ser palíndromo es una convención que hay que elegir. Un separador decimal es igualmente un carácter: 0,1 se invierte en 1,0, dos cadenas distintas que denotan valores distintos. Y los ceros a la izquierda existen en texto y no en números: 010 es palíndromo como texto, y como número es 10, que no lo es. Si tu entrada es un número, quita el formato y trabaja sobre los dígitos; si es un texto que parece numérico, dilo y trátalo como texto.

Qué construir, en orden

La receta que sobrevive a las seis lenguas es corta. Normaliza primero a NFC, para que el mismo texto visible tenga siempre la misma representación. Aplica luego las políticas que has decidido y sabes nombrar: minúsculas, quitar los espacios, quitar todo lo que no sea letra o dígito, plegar los acentos descomponiendo y eliminando las marcas. Después invierte por grupo de grafemas y compara. Cuatro pasos, y cada uno es una decisión que puedes exponer en la interfaz en vez de un valor por defecto escondido en el código.

Una última observación sobre la inversión, porque es contraintuitiva y esconde errores. Invertir dos veces devuelve siempre la cadena original, sea cual sea la unidad elegida: unidades de código, puntos de código y grafemas son todos involuciones sobre la secuencia que manipulan. Así que una prueba de ida y vuelta no te dice nada sobre si tu inversión es correcta. La única prueba que atrapa los casos rotos es mirar el resultado intermedio, y la forma más rápida de mirarlo es contar los grafemas antes y después: para un José descompuesto son cuatro y luego cinco.

Preguntas frecuentes

¿Es «A man, a plan, a canal: Panama» un palíndromo?

Bajo la política habitual, sí; tal como está escrito, no. Pliega la caja, quita los espacios y quita la puntuación y se vuelve amanaplanacanalpanama, que es simétrico. Conserva cualquiera de los tres y no lo es. No es una pregunta trampa: es exactamente lo que hace la fórmula «ignorando mayúsculas, espacios y puntuación» de toda definición de manual, y una herramienta que deja activar las tres reglas por separado dice la verdad en vez de esconderla.

¿Por qué al invertir mi texto salió un cuadrado roto?

Porque la inversión trabajó sobre unidades de código UTF-16 y tu texto contenía un carácter fuera del plano multilingüe básico: un emoji, un ideograma CJK raro, un símbolo matemático. Esos se almacenan como par suplente, e invertir las dos mitades produce una secuencia que ninguna fuente puede dibujar. Compruébalo con isWellFormed(), que devuelve falso sobre esa cadena, y pasa la inversión a grupos de grafemas con Intl.Segmenter.

¿Debe un verificador de palíndromos ignorar los acentos?

Debe ofrecer la opción y plegar por defecto, porque la tradición del juego de palabras en francés, español y portugués trata é y e como la misma letra. Sin plegado, tres de las seis frases de la tabla dejan de ser palíndromos: «Ésope reste ici et se repose», «Dábale arroz a la zorra el abad» y «Socorram-me, subi no ônibus em Marrocos» fallan todas en su primer y último carácter. Pliega descomponiendo a NFD, borrando las marcas combinantes y recomponiendo — el artículo de esta serie sobre los acentos explica por qué eso no es lo mismo que sustituir letras una a una.

¿Es 12321 un palíndromo?

Como número en base diez, sí. Como texto mostrado, no — en todas las locales de este artículo. Formateado para un lector se vuelve 12,321 en inglés y 12.321 o 12 321 en otras partes, e invertir esas cadenas da 123,21, 123.21 y 123 21. Si compruebas números, trabaja sobre los dígitos y decide explícitamente qué hacer con un signo, un separador decimal y los ceros a la izquierda: -121 se invierte en 121-, 0,1 se invierte en 1,0, y 010 es palíndromo como texto mientras que el número que denota es 10.

¿Invertir una cadena dos veces devuelve siempre la original?

Sí, y por eso mismo una prueba de ida y vuelta no vale nada aquí. Invertir por unidad de código, por punto de código o por grupo de grafemas son todas involuciones: aplica cualquiera dos veces y recuperas la entrada, incluso cuando la inversión simple produjo entretanto una cadena rota. Prueba en cambio el resultado intermedio: compara el número de grafemas antes y después, o llama a isWellFormed() sobre él.

¿Puede una sola palabra ser palíndroma sin ninguna de estas reglas?

Sí, y esos son los únicos casos en que la pregunta tiene una sola respuesta. Las palabras enteramente en minúsculas ASCII como racecar, radar, kayak, el francés ressasser, el español reconocer, el italiano onorarono y el portugués reviver son palíndromos sin política alguna — verificado carácter a carácter. Ponles una mayúscula y necesitas la regla de caja: los alemanes Reliefpfeiler, Rentner y Lagerregal solo son palíndromos una vez plegada la capital inicial, lo que es una política y no cuatro.