Ce qu'un vérificateur de palindrome doit décider avant de pouvoir répondre

La question n'a pas de sens tant que quatre choix ne sont pas faits

Un palindrome se lit pareil dans les deux sens. Cette définition n'est complète que pour une suite de minuscules nues, et presque aucun texte réel n'en est une. Dès qu'une phrase comporte des majuscules, des espaces, des virgules ou des accents, la question se divise en quatre : une majuscule vaut-elle sa minuscule, les espaces comptent-ils comme des caractères, la ponctuation compte-t-elle, et une lettre accentuée est-elle la même lettre que sa base ? Quatre réponses par oui ou non, seize combinaisons, et celles qui comptent forment une suite emboîtée, chacune admettant plus de phrases que la précédente.

Le tableau ci-dessus est cette suite appliquée à six phrases, exécutée plutôt que discutée. Lis-le colonne par colonne : chaque colonne justifie sa place. Les blancs seuls promeuvent la phrase italienne, la ponctuation seule promeut l'anglaise, et le repli des accents seul promeut la française, l'espagnole et la portugaise. Un vérificateur qui fige l'un de ces choix répond à une autre question que celle posée par son utilisateur, et il y répond en silence.

Quatre phrases, quatre points d'arrêt différents

Commençons par l'anglaise, la phrase que tout le monde cite. « A man, a plan, a canal: Panama » n'est pas un palindrome tel quel : le A majuscule d'un bout fait face à un a minuscule de l'autre. Replie la casse : toujours pas, les espaces ne tombent pas symétriquement. Retire les blancs : toujours pas, il reste une virgule et deux points. Retire aussi la ponctuation et cela y est enfin : amanaplanacanalpanama, vingt et un caractères, symétrique. Trois politiques ont dû être activées avant que la réponse célèbre n'apparaisse.

L'allemande « Ein Esel lese nie » s'arrête un cran plus tôt que tout le reste du tableau. Replie la casse et c'est déjà un palindrome : einesellesenie se lit pareil dans les deux sens, et la phrase avec ses espaces aussi, parce que ses longueurs de mots — trois, quatre, quatre, trois — sont symétriques par construction. Un vérificateur qui retire toujours les blancs donne ici la bonne réponse, mais pour la mauvaise raison, et il ne pourra jamais te dire que cette phrase est un palindrome au sens plus fort où ses espaces le sont aussi. L'autre exemple allemand, « O, Genie, der Herr ehre dein Ego ! », n'a besoin que de la règle sur la ponctuation.

Les trois phrases romanes ont toutes besoin de la quatrième règle et échouent à toutes les précédentes. « Ésope reste ici et se repose », ponctuation retirée mais accents conservés, donne ésoperesteicietserepose, dont l'inverse est esoperesteicietsereposé : l'accent a migré du premier caractère au dernier, et les chaînes diffèrent. Replie le signe diacritique et les deux deviennent esoperesteicietserepose. Il en va de même pour dábale…, dont l'inverse finit par á, et pour socorram-me…, où le ô atterrit au mauvais endroit. Note ce que cela implique : un vérificateur conçu pour l'anglais déclarera trois palindromes européens parfaitement valides comme des échecs, et le fera sans le moindre message d'erreur.

Inverser une chaîne n'est pas non plus une seule opération

Tout vérificateur de palindrome compare un texte à son inverse, et c'est dans cet inverse que réside la seconde moitié du problème. L'inversion en une ligne que tout le monde écrit — s.split('').reverse().join('') — inverse des unités de code UTF-16. Un article compagnon de cette série traite de ce qu'est un caractère ; la conséquence ici est que tout caractère hors du plan multilingue de base est stocké sur deux unités de code, et les inverser individuellement échange la paire. Inverse « ça va 😀 » ainsi et le résultat contient un substitut bas suivi d'un substitut haut : huit points de code au lieu de sept, et isWellFormed() rend faux. À l'écran, c'est un carré de remplacement.

Le correctif habituel consiste à inverser des points de code : [...s].reverse().join(''). Cela répare l'émoji — « ça va 😀 » devient « 😀 av aç », toujours sept points de code — et cela ne suffit toujours pas. Prends « José » sous forme décomposée, où le é est un e suivi d'un accent aigu combinant : cinq points de code, quatre graphèmes. Inverser les points de code place l'accent combinant en tête, où il n'a plus de lettre à laquelle s'attacher, et laisse un e nu : le résultat compte cinq graphèmes là où il y en avait quatre, et l'accent se dessine sur rien. Le cas allemand est plus frappant encore. Décompose « Grüße », inverse ses points de code et tu obtiens eß̈urG : le tréma a sauté du u pour atterrir sur le ß.

Les émojis composés de plusieurs points de code échouent de la même façon. La famille 👨‍👩‍👧 est faite de trois personnes reliées par des liants sans chasse : seize unités de code, treize points de code, un seul graphème. Inverser ses points de code produit une famille qui s'affiche 👧‍👩‍👨 — fille, mère, père — c'est-à-dire un autre émoji, non un émoji inversé ; inverser ses unités de code produit quelque chose qui s'affiche en fragments. Seule l'inversion par grappe de graphèmes le laisse intact.

Inverser par grappe de graphèmes

Une grappe de graphèmes est le nom que donne Unicode à ce qu'un lecteur appelle un caractère : une lettre de base plus ce qui se combine à elle, ou une séquence d'émoji entière. JavaScript expose directement les règles de segmentation via Intl.Segmenter, et une inversion correcte tient en trois lignes : construire un segmenteur de granularité « grapheme », étaler sa sortie, inverser, joindre. Sur tous les exemples ci-dessus, elle fait ce qu'il faut : l'émoji survit, la famille reste une famille, et le Grüße décomposé revient en eßürG, tréma toujours sur son u.

Une décision de normalisation se cache là-dessous, et le mot français été la révèle en une ligne. Sous forme composée, il fait trois points de code et les inverser rend été : palindrome. Sous forme décomposée, il fait cinq points de code, les inverser donne une chaîne aux accents mal placés, et le même mot visible est déclaré non palindrome. L'inversion par grappe de graphèmes donne la bonne réponse dans les deux formes — mais si tu compares les deux formes entre elles, elles restent inégales, et c'est pourquoi un vérificateur doit normaliser en NFC avant toute autre chose. L'article de cette série consacré aux accents traite les formes NFC et NFD en détail.

Un palindrome numérique est un autre problème

Les nombres ont l'air du cas facile et ne le sont pas. Un palindrome numérique est une propriété d'une valeur dans une base ; un palindrome textuel est une propriété d'un rendu. 12321 est un palindrome en base dix. Rendu pour un lecteur, il cesse de l'être dans toutes les locales de cet article : 12,321 inversé donne 123,21 en anglais, 12.321 inversé donne 123.21 en allemand, espagnol et italien, et 12 321 inversé donne 123 21 en français et en portugais — le séparateur étant une espace insécable étroite U+202F en français et une espace insécable ordinaire U+00A0 en portugais, deux caractères invisibles qu'une comparaison naïve traitera de toute façon comme différents.

Trois autres différences découlent de la même distinction. Un signe est un caractère mais pas un chiffre : -121, en tant que texte, s'inverse en 121- et échoue, alors qu'en tant que valeur la question de savoir si un nombre négatif peut être un palindrome relève d'une convention à choisir. Un séparateur décimal est de même un caractère : 0,1 s'inverse en 1,0, deux chaînes différentes qui désignent des valeurs différentes. Et les zéros de tête existent en texte, pas en nombre : 010 est un palindrome comme texte, et vaut 10 comme nombre, qui n'en est pas un. Si ton entrée est un nombre, retire le formatage et travaille sur les chiffres ; si c'est un texte qui ressemble à un nombre, dis-le et traite-le comme du texte.

Ce qu'il faut construire, dans l'ordre

La recette qui survit aux six langues est courte. Normalise d'abord en NFC, pour que le même texte visible ait toujours la même représentation. Applique ensuite les politiques que tu as choisies et que tu sais nommer : minuscules, retrait des blancs, retrait de tout ce qui n'est ni lettre ni chiffre, repli des accents par décomposition puis suppression des marques. Inverse enfin par grappe de graphèmes et compare. Quatre étapes, et chacune est un choix que tu peux exposer dans l'interface plutôt qu'un défaut caché dans le code.

Une dernière observation sur l'inversion, car elle est contre-intuitive et cache des bugs. Inverser deux fois rend toujours la chaîne d'origine, quelle que soit l'unité choisie : unités de code, points de code et graphèmes sont tous des involutions sur la séquence qu'ils manipulent. Un test d'aller-retour ne te dit donc rien sur la justesse de ton inversion. Le seul test qui attrape les cas cassés consiste à regarder le résultat intermédiaire, et le moyen le plus rapide est de compter les graphèmes avant et après : pour un José décomposé, ils sont quatre puis cinq.

Questions fréquentes

« A man, a plan, a canal: Panama » est-il un palindrome ?

Sous la politique habituelle, oui ; tel qu'il est tapé, non. Replie la casse, retire les espaces et la ponctuation et cela devient amanaplanacanalpanama, qui est symétrique. Conserve l'un des trois et ce n'en est pas un. Ce n'est pas une question piège : c'est exactement ce que fait la formule « en ignorant la casse, les espaces et la ponctuation » de toutes les définitions scolaires, et un outil qui laisse activer les trois règles séparément dit la vérité au lieu de la cacher.

Pourquoi l'inversion de mon texte a-t-elle produit un carré cassé ?

Parce que l'inversion a porté sur des unités de code UTF-16 et que ton texte contenait un caractère hors du plan multilingue de base — un émoji, un idéogramme CJC rare, un symbole mathématique. Ceux-là sont stockés en paire de substitution, et inverser les deux moitiés produit une séquence qu'aucune police ne peut dessiner. Vérifie avec isWellFormed(), qui rend faux sur une telle chaîne, et passe l'inversion aux grappes de graphèmes avec Intl.Segmenter.

Un vérificateur de palindrome doit-il ignorer les accents ?

Il doit offrir le choix et replier par défaut, car la tradition du jeu de mots en français, en espagnol et en portugais traite é et e comme la même lettre. Sans repli, trois des six phrases du tableau ci-dessus cessent d'être des palindromes : « Ésope reste ici et se repose », « Dábale arroz a la zorra el abad » et « Socorram-me, subi no ônibus em Marrocos » échouent toutes sur leurs premier et dernier caractères. Replie en décomposant vers NFD, en supprimant les marques combinantes, puis en recomposant — l'article de cette série sur les accents explique pourquoi ce n'est pas la même chose que remplacer les lettres une à une.

12321 est-il un palindrome ?

En tant que nombre en base dix, oui. En tant que texte affiché, non — dans toutes les locales de cet article. Formaté pour un lecteur, il devient 12,321 en anglais et 12.321 ou 12 321 ailleurs, et inverser ces chaînes donne 123,21, 123.21 et 123 21. Si tu vérifies des nombres, travaille sur les chiffres et décide explicitement du sort du signe, du séparateur décimal et des zéros de tête : -121 s'inverse en 121-, 0,1 s'inverse en 1,0, et 010 est un palindrome comme texte alors que le nombre qu'il désigne vaut 10.

Inverser deux fois une chaîne rend-il toujours l'originale ?

Oui, et c'est précisément pourquoi un test d'aller-retour ne vaut rien ici. Inverser par unité de code, par point de code ou par grappe de graphèmes sont toutes des involutions : applique l'une d'elles deux fois et tu retrouves l'entrée, même quand l'inversion simple a produit entre-temps une chaîne cassée. Teste plutôt le résultat intermédiaire : compare le nombre de graphèmes avant et après, ou appelle isWellFormed() dessus.

Un mot seul peut-il être un palindrome sans aucune de ces règles ?

Oui, et ce sont les seuls cas où la question a une seule réponse. Les mots entièrement en minuscules ASCII comme racecar, radar, kayak, le français ressasser, l'espagnol reconocer, l'italien onorarono et le portugais reviver sont des palindromes sans aucune politique — vérifié caractère par caractère. Mets-leur une majuscule et il te faut la règle de casse : les allemands Reliefpfeiler, Rentner et Lagerregal ne sont des palindromes qu'une fois la capitale initiale repliée, ce qui fait une politique et non quatre.