Pangrammi!

[JoJo1973]

I pangrammi, ah che nostalgia! ))

Sembra ieri (magari!) quando lessi per la prima volta dei pangrammi, proprio su CCC numero 33, e fui subito affascinato dall'idea...

In un pomeriggio o due mi misi all'opera e digitai pazientemente tutti i numeri del listato, li ricontrollai e diedi il RUN: avrei sicuramente trovato per primo la soluzione al pangramma italiano.

Un'ora, due ore, otto ore, ventiquattro ore... niente!

Avevo sbagliato qualcosa, un bug si era insinuato da qualche parte, le mie stime erano errate? Mah! Purtroppo non cavai un ragno dal buco, forse la ricerca avrebbe impiegato davvero troppo tempo o forse il pangramma proposto era matematicamente impossibile... senza un controesempio era difficile verificare qualunque ipotesi!

Poco male, qualcun altro ci riuscirà al posto mio e pubblicherà i suoi risultati in un prossimo numero di CCC... e invece niente!

La news di Ready64 mi ha riacceso la lampadina: con i teraflops a disposizione di chiunque non sarà più un problema tentare una ricerca, resta solo da scrivere il programma!

E qui casca l'asino, perché il lavoro, la famiglia, le cavallette e le inondazioni ci mettono del loro... Cosa fare?

Naturalmente, rivolgiamoci al fantastico mondo dell'open source e troviamo una risposta: la risposta si chiama "Seppy" (https://github.com/garydoranjr/seppy), un pratico programma in Python per la ricerca di pangrammi, ma in inglese!

Poco male, in pochi minuti aggiorno il programma a Python3, localizzo i testi in italiano e limito la ricerca alle lettere dell'alfabeto senza "jkwxy" per rientrare nelle condizioni proposte da Antonio Visconti nel suo articolo.

Avvio un po' trepidante il programma e, RULLO DI TAMBURI, dopo pochi minuti ecco qua la soluzione!

QUESTO PANGRAMMA TROVATO CON IL COMMODORE SESSANTAQUATTRO CONTIENE SEDICI A, UNA B, DODICI C, QUATTORDICI D, VENTIQUATTRO E, UNA F, DUE G, UNA H, VENTIDUE I, DUE L, CINQUE M, DICIANNOVE N, QUINDICI O, DUE P, SETTE Q, SETTE R, UNDICI S, VENTUNO T, DICIASSETTE U, SEI V, E UNA Z.

Finalmente!!!

Non sempre la ricerca va a termine, sembra che certe condizioni iniziali non portino ad una soluzione, ma certamente possiamo dire che

AL GIORNO D'OGGI NON E' PIU' COSI DIFFICILE TROVARE UN PANGRAMMA IN CUI CI SONO QUATTORDICI A, UNA B, QUATTORDICI C, DIECI D, VENTI E, TRE F, CINQUE G, UNA H, TRENTA I, TRE L, TRE M, DICIANNOVE N, TREDICI O, TRE P, SETTE Q, QUINDICI R, QUATTRO S, VENTI T, TREDICI U, CINQUE V, E UNA Z.

Saluti, e buona esplorazione dello spazio dei pangrammi!!!!

[Flavioweb]

Ho fatto anch'io alcune prove per capire se il listato proposto su CCC fosse realmente utilizzabile nella pratica sul Commodore 64.
Come prima prova l'ho messo in esecuzione sull'emulatore Denise che sul mio PC gira a circa il 3300% della velocità originale del 64.
Come "parametri" ho settatto il limite minimo proposto e come "massimo" esattamente il doppio di ogni valore. Non ho usato un criterio particolare per utilizzare questi valori ma sono andato a "sentimento".
Dopo 5 giorni di elaborazione continuata non ho ancora ottenuto alcun risultato: nessun pangramma e nemmeno un esito negativo.

Come secondo tentativo, giusto per capire se il codice potesse realmente funzionare, ho usato la AI Gemini di Google.
L'ho da prima istruita a comprendere cosa facesse il codice assembly necessario al funzionamento del prg basic e poi le ho chiesto di analizzare il funzionamento dei due codici in maniera combinata.
Il risultato è stato questo:

Ok, proviamo a incrociare l'analisi del codice assembly con il codice BASIC per dedurre il funzionamento e ipotizzare dei valori di input.

Ipotesi sul Funzionamento Generale:

Considerando le operazioni di lettura/scrittura nella pagina di memoria $C2xx, i salti condizionati, e le informazioni che abbiamo sul BASIC, ecco un'ipotesi più dettagliata:

Inizializzazione:

Il codice assembly legge i limiti inferiori e superiori (min/max occorrenze di lettere) che l'utente ha inserito tramite INPUT nel BASIC e che sono stati scritti nella pagina $C2xx (probabilmente $C2A0-$C2AF).

Inizializza una tabella (forse in $C2B0-$C2BF) con dei valori di partenza.

Ciclo Principale (Ricerca Pangramma):

Il codice assembly seleziona una combinazione di numeri dalla lista N$() (uno, due, tre, ... cinquanta).

Conta le occorrenze di ogni lettera (a, b, c, ... z) in questa combinazione.

Confronta queste occorrenze con i limiti min/max letti precedentemente dalla pagina $C2xx.

Se tutte le lettere rientrano nei limiti, e se sono presenti tutte le lettere (cioè, se è un pangramma), memorizza questa combinazione come un potenziale risultato.

Continua a provare altre combinazioni finché non trova una soluzione o esaurisce le possibilità.

Tabella di Salto (Gestione Risultati o Condizioni):

La tabella di salti (le istruzioni JMP dopo i BNE) potrebbe servire per gestire diverse situazioni:

Se una lettera è troppo rara nella combinazione corrente, salta a una routine per provare una combinazione diversa.

Se una lettera è troppo frequente, salta a una routine per provare una combinazione diversa.

Se tutte le lettere rientrano nei limiti ma non sono presenti tutte, salta a una routine per aggiungere altre parole alla combinazione.

Se trova un pangramma valido, salta a una routine per memorizzare i risultati.

Output dei Risultati:

Se trova un pangramma valido, il codice assembly scrive gli indici delle parole che compongono il pangramma nella memoria (probabilmente $C2C0-$C2CF).

Imposta un flag in memoria per indicare il successo della ricerca.

Ipotizziamo Valori di Input:

Dato che il programma cerca un pangramma con lettere da 'a' a 'v' e 'z', un input sensato sarebbe:

a (min 12, max 15): Un valore alto perché ci sono molte parole che non contengono la lettera 'a'.

b (min 1, max 2): Valori bassi, poiché 'b' non è frequentissima.

c (min 5, max 7): Anche qui, valori bassi.

d (min 5, max 7): Valori bassi.

e (min 11, max 14): Valore alto, 'e' è molto comune.

i (min 4, max 6): Valori medi.

n (min 11, max 14): Valore alto, 'n' è comune.

o (min 10, max 13): Valore alto, 'o' è comune.

q (min 4, max 5): Valore basso, 'q' è rara.

r (min 5, max 7): Valori medi.

s (min 5, max 7): Valori medi.

t (min 8, max 10): Valori medi/alti.

u (min 11, max 13): Valore alto, 'u' è abbastanza comune.

v (min 2, max 3): Valore basso, 'v' è rara.

Esempio di Interazione Utente (ipotetica):

Codice: [Seleziona]

ESTREMO INFERIORE A (MIN. 12)? 12
ESTREMO SUPERIORE A? 15

ESTREMO INFERIORE B (MIN. 1)? 1
ESTREMO SUPERIORE B? 2

ESTREMO INFERIORE C (MIN. 5)? 5
ESTREMO SUPERIORE C? 7

... e così via ...

INIZIATA RICERCA PANGRAMMI
ATTENDERE PREGO!

QUESTO PANGRAMMA TROVATO CON IL
COMMODORE SESSANTAQUATTRO CONTIENE:
UNDICI A, UNA B, SEI C, CINQUE D,
DODICI E, UNA F, DUE G, UNA H,
CINQUE I, DUE L, CINQUE M, DODICI N,
DODICI O, DUE P, QUATTRO Q, CINQUE R,
SEI S, OTTO T, UNDICI U, DUE V,
E UNA Z.

Come questi input influenzano il codice assembly:

Gli input dell'utente vengono scritti nella pagina $C2xx, quindi le istruzioni LDA $C2xx nel codice assembly leggono direttamente questi valori.

I limiti min/max vengono usati per i confronti all'interno del ciclo di ricerca. Il codice assembly confronta il numero di occorrenze di ogni lettera con questi limiti e decide se accettare o rifiutare la combinazione corrente.

La scelta degli input influenza direttamente il tempo di esecuzione. Se i limiti sono troppo restrittivi, il codice potrebbe impiegare molto tempo per trovare una soluzione (o non trovarla affatto).

Prossimi Passi:

Debug con gli input ipotizzati: Prova a eseguire il programma nel VICE con questi input ipotizzati e usa il debugger per vedere come il codice assembly reagisce.

Identificare la tabella di salto: Cerca di capire quali condizioni attivano i diversi salti nella tabella di salto. Questo ti darà un'idea di come il codice gestisce le diverse situazioni.

Analizzare il codice intorno ai salti: Analizza il codice immediatamente prima e dopo le istruzioni BNE e JMP per capire cosa viene confrontato e cosa succede quando il salto viene eseguito o non eseguito.

Quindi sembra che il codice funzioni anche sulla macchina reale anche se io personalmente non sono ancora riuscito a verificarlo nella pratica.

[JoJo1973]

Queste IA diventano sempre più inquietanti! Comunque ho fatto una semplice prova inserendo per ciascuna lettera un limite ±1 centrato sul valore della soluzione ed il pangramma è stato trovato.

Il prossimo step sarà quello di adattare il programma a trovare il secondo pangramma che ho trovato col programma in Python e poi, tempo permettendo, disassemblare e commentare la routine in LM.