Che cosa deve decidere un verificatore di palindromi prima di poter rispondere

La domanda è indefinita finché non si prendono quattro decisioni

Un palindromo si legge uguale nei due sensi. Quella definizione è completa solo per una sequenza di minuscole nude, e quasi nessun testo reale lo è. Appena una frase ha maiuscole, spazi, virgole o accenti, la domanda si spezza in quattro: una maiuscola equivale alla sua minuscola, gli spazi contano come caratteri, conta la punteggiatura, e una lettera accentata è la stessa lettera della sua base? Quattro risposte sì o no, sedici combinazioni, e quelle che contano formano una sequenza annidata, ciascuna che ammette più frasi della precedente.

La tabella qui sopra è quella sequenza applicata a sei frasi, eseguita anziché discussa. Leggila colonna per colonna e ogni colonna si guadagna il posto: gli spazi da soli promuovono la frase italiana, la punteggiatura da sola promuove quella inglese, e il ripiegamento degli accenti da solo promuove la francese, la spagnola e la portoghese. Un verificatore che fissa una qualsiasi di queste scelte sta rispondendo a una domanda diversa da quella posta dal suo utente, e la risponde in silenzio.

Quattro frasi, quattro punti d'arresto diversi

Cominciamo dall'inglese, perché è la frase che tutti citano. «A man, a plan, a canal: Panama» non è un palindromo così com'è: la A maiuscola di un capo fronteggia una a minuscola dall'altro. Ripiega le maiuscole e ancora non lo è: gli spazi non cadono simmetricamente. Togli gli spazi e ancora non lo è, perché restano una virgola e due punti. Togli anche la punteggiatura e finalmente lo è: amanaplanacanalpanama, ventun caratteri, simmetrico. Tre politiche hanno dovuto essere attivate prima che comparisse la risposta famosa.

La tedesca «Ein Esel lese nie» si ferma un gradino prima di tutto il resto della tabella. Ripiega le maiuscole ed è già un palindromo: einesellesenie si legge uguale nei due sensi, e anche la frase con i suoi spazi al loro posto, perché le sue lunghezze di parola — tre, quattro, quattro, tre — sono simmetriche per costruzione. Un verificatore che toglie sempre gli spazi indovina qui, ma per la ragione sbagliata, e non potrà mai dirti che questa frase è un palindromo nel senso più forte in cui lo sono anche i suoi spazi. L'altro esempio tedesco, «O, Genie, der Herr ehre dein Ego!», ha bisogno solo della regola sulla punteggiatura.

Le tre frasi romanze richiedono tutte la quarta regola e falliscono a ogni regola precedente. «Ésope reste ici et se repose», con la punteggiatura tolta ma gli accenti conservati, dà ésoperesteicietserepose, il cui inverso è esoperesteicietsereposé: l'accento è migrato dal primo carattere all'ultimo, e le stringhe differiscono. Ripiega il segno diacritico ed entrambe diventano esoperesteicietserepose. Lo stesso accade con dábale…, il cui inverso finisce in á, e con socorram-me…, dove la ô atterra nel posto sbagliato. Nota che cosa implica: un verificatore costruito per l'inglese dichiarerà falliti tre palindromi europei perfettamente validi, e lo farà senza alcun messaggio di errore.

Nemmeno invertire una stringa è una sola operazione

Ogni verificatore di palindromi confronta un testo con il suo inverso, ed è in quell'inverso che vive la seconda metà del problema. L'inversione in una riga che tutti scrivono — s.split('').reverse().join('') — inverte unità di codice UTF-16. Un articolo compagno di questa serie tratta di che cosa sia un carattere; la conseguenza qui è che ogni carattere fuori dal piano multilingue di base è memorizzato su due unità di codice, e invertirle singolarmente scambia la coppia. Inverti «ça va 😀» così e il risultato contiene un surrogato basso seguito da uno alto: otto punti di codice invece di sette, e isWellFormed() restituisce falso. Sullo schermo è un quadratino di sostituzione.

Il rimedio abituale è invertire i punti di codice: [...s].reverse().join(''). Ripara l'emoji — «ça va 😀» diventa «😀 av aç», ancora sette punti di codice — e ancora non basta. Prendi «José» in forma decomposta, dove la é è una e seguita da un accento acuto combinante: cinque punti di codice, quattro grafemi. Invertire i punti di codice mette l'accento combinante in testa, dove non ha più una lettera a cui attaccarsi, e lascia una e nuda: il risultato ha cinque grafemi dove ce n'erano quattro, e l'accento si disegna sul nulla. Il caso tedesco è ancora più vistoso. Decomponi «Grüße» e inverti i suoi punti di codice e ottieni eß̈urG: la dieresi è saltata dalla u ed è atterrata sulla ß.

Le emoji composte da più punti di codice falliscono allo stesso modo. La famiglia 👨‍👩‍👧 sono tre persone unite da giuntori a larghezza zero: sedici unità di codice, tredici punti di codice, un solo grafema. Invertire i suoi punti di codice produce una famiglia che si disegna 👧‍👩‍👨 — figlia, madre, padre —, cioè un'altra emoji, non una invertita; invertire le sue unità di codice produce qualcosa che si disegna a frammenti. Solo l'inversione per gruppo di grafemi la lascia intatta.

Invertire per gruppo di grafemi

Un gruppo di grafemi è il nome che Unicode dà a ciò che un lettore chiama un carattere: una lettera base più tutto ciò che vi si combina, o un'intera sequenza emoji. JavaScript espone le regole di segmentazione direttamente tramite Intl.Segmenter, e un'inversione corretta sta in tre righe: costruire un segmentatore con granularità «grapheme», distendere il suo output, invertire, unire. Su tutti gli esempi qui sopra fa la cosa giusta: l'emoji sopravvive, la famiglia resta una famiglia, e il Grüße decomposto torna come eßürG, con la dieresi ancora sulla sua u.

Sotto si nasconde una decisione di normalizzazione, e la parola francese été la rivela in una riga. In forma composta sono tre punti di codice e invertirli restituisce été: palindromo. In forma decomposta sono cinque punti di codice, invertirli dà una stringa con gli accenti fuori posto, e la stessa parola visibile viene dichiarata non palindroma. L'inversione per gruppo di grafemi dà la risposta giusta in entrambe le forme — ma se confronti le due forme fra loro restano diverse, ed è per questo che un verificatore dovrebbe normalizzare in NFC prima di ogni altra cosa. L'articolo di questa serie dedicato agli accenti tratta per esteso le forme NFC e NFD.

Un palindromo numerico è un altro problema

I numeri sembrano il caso facile e non lo sono. Un palindromo numerico è una proprietà di un valore in una base; un palindromo testuale è una proprietà di una resa. 12321 è un palindromo in base dieci. Reso per un lettore smette di esserlo in ogni locale di questo articolo: 12,321 invertito dà 123,21 in inglese, 12.321 invertito dà 123.21 in tedesco, spagnolo e italiano, e 12 321 invertito dà 123 21 in francese e portoghese — dove il separatore è uno spazio unificatore stretto U+202F in francese e uno spazio unificatore normale U+00A0 in portoghese, due caratteri invisibili che un confronto ingenuo tratterà comunque come diversi.

Dalla stessa distinzione discendono altre tre differenze. Un segno è un carattere ma non una cifra: -121 come testo si inverte in 121- e fallisce, mentre come valore la questione se un numero negativo possa essere palindromo è una convenzione da scegliere. Un separatore decimale è ugualmente un carattere: 0,1 si inverte in 1,0, due stringhe diverse che denotano valori diversi. E gli zeri iniziali esistono nel testo e non nei numeri: 010 è palindromo come testo, e come numero è 10, che non lo è. Se il tuo input è un numero, togli la formattazione e lavora sulle cifre; se è un testo che sembra numerico, dillo e trattalo come testo.

Che cosa costruire, in ordine

La ricetta che sopravvive a tutte e sei le lingue è corta. Normalizza prima in NFC, così che lo stesso testo visibile abbia sempre la stessa rappresentazione. Applica poi le politiche che hai deciso e sai nominare: minuscole, togliere gli spazi, togliere tutto ciò che non è lettera o cifra, ripiegare gli accenti decomponendo e rimuovendo i segni. Poi inverti per gruppo di grafemi e confronta. Quattro passaggi, e ognuno è una scelta che puoi mostrare nell'interfaccia invece di un valore predefinito nascosto nel codice.

Un'ultima osservazione sull'inversione, perché è controintuitiva e nasconde bug. Invertire due volte restituisce sempre la stringa originale, qualunque sia l'unità scelta: unità di codice, punti di codice e grafemi sono tutti involuzioni sulla sequenza su cui operano. Quindi un test di andata e ritorno non ti dice nulla sulla correttezza della tua inversione. L'unico test che intercetta i casi rotti è guardare il risultato intermedio, e il modo più rapido di guardarlo è contare i grafemi prima e dopo: per un José decomposto sono quattro e poi cinque.

Domande frequenti

«A man, a plan, a canal: Panama» è un palindromo oppure no?

Con la politica abituale sì; così com'è scritto no. Ripiega le maiuscole, togli gli spazi e togli la punteggiatura e diventa amanaplanacanalpanama, che è simmetrico. Conserva uno qualsiasi dei tre e non lo è. Non è una domanda trabocchetto: è esattamente ciò che fa la formula «ignorando maiuscole, spazi e punteggiatura» di ogni definizione da manuale, e uno strumento che lascia attivare le tre regole separatamente dice la verità invece di nasconderla.

Perché invertendo il mio testo è comparso un quadratino rotto?

Perché l'inversione ha lavorato su unità di codice UTF-16 e il tuo testo conteneva un carattere fuori dal piano multilingue di base: un'emoji, un ideogramma CJK raro, un simbolo matematico. Quelli sono memorizzati come coppia surrogata, e invertirne le due metà produce una sequenza che nessun font sa disegnare. Verificalo con isWellFormed(), che restituisce falso su una stringa simile, e passa l'inversione ai gruppi di grafemi con Intl.Segmenter.

Un verificatore di palindromi deve ignorare gli accenti?

Dovrebbe offrire la scelta e ripiegare per impostazione predefinita, perché la tradizione del gioco di parole in francese, spagnolo e portoghese tratta é ed e come la stessa lettera. Senza ripiegamento, tre delle sei frasi della tabella smettono di essere palindromi: «Ésope reste ici et se repose», «Dábale arroz a la zorra el abad» e «Socorram-me, subi no ônibus em Marrocos» falliscono tutte sul primo e sull'ultimo carattere. Ripiega decomponendo in NFD, cancellando i segni combinanti e ricomponendo — l'articolo di questa serie sugli accenti spiega perché non è la stessa cosa che sostituire lettere una per una.

12321 è un palindromo?

Come numero in base dieci, sì. Come testo visualizzato, no — in ogni locale di questo articolo. Formattato per un lettore diventa 12,321 in inglese e 12.321 o 12 321 altrove, e invertire quelle stringhe dà 123,21, 123.21 e 123 21. Se verifichi numeri, lavora sulle cifre e decidi esplicitamente che fare con un segno, un separatore decimale e gli zeri iniziali: -121 si inverte in 121-, 0,1 si inverte in 1,0, e 010 è palindromo come testo mentre il numero che denota è 10.

Invertire due volte una stringa restituisce sempre l'originale?

Sì, ed è proprio per questo che un test di andata e ritorno qui non vale nulla. Invertire per unità di codice, per punto di codice o per gruppo di grafemi sono tutte involuzioni: applicane una due volte e riottieni l'input, anche quando l'inversione singola ha prodotto nel frattempo una stringa rotta. Verifica invece il risultato intermedio: confronta il numero di grafemi prima e dopo, o chiama isWellFormed() su di esso.

Una singola parola può essere palindroma senza nessuna di queste regole?

Sì, e quelli sono gli unici casi in cui la domanda ha una sola risposta. Le parole interamente in minuscolo ASCII come racecar, radar, kayak, il francese ressasser, lo spagnolo reconocer, l'italiano onorarono e il portoghese reviver sono palindromi senza alcuna politica — verificato carattere per carattere. Mettici una maiuscola e ti serve la regola sulle maiuscole: i tedeschi Reliefpfeiler, Rentner e Lagerregal sono palindromi solo una volta ripiegata la capitale iniziale, il che è una politica e non quattro.