Codici e Pizzini.

Descrizione del problema
Il Commissario Basettoni è riuscito a localizzare il nascondiglio del pericoloso Gambadilegno.
Facendo irruzione nel covo, Basettoni trova una serie di foglietti (detti "pizzini") che riportano, cifrati, i codici di accesso ai conti correnti del gruppo di malavitosi capeggiato da Gambadilegno.

Il Commissario Basettoni chiede aiuto a Topolino per interpretare questi pizzini.
Dopo approfondite analisi, Topolino scopre le seguenti cose:

ogni pizzino contiene N righe e ciascuna riga è una sequenza di cifre decimali ('0', '1', ..., '9') concatenate senza spazi intermedi (quindi la sequenza 0991, come tale, non va interpretata come il numero 991);
ogni pizzino riporta, cifrato, un codice di accesso a N cifre;
tale codice si ottiene concatenando una dopo l'altra, senza spazi intermedi, le cifre estratte dalle N sequenze scritte nel pizzino, più precisamente, una cifra per ogni sequenza;
la cifra da estrarre per ciascuna sequenza è quella in posizione p, dove p è il numero di anagrammi che, per tale sequenza, appaiono nel pizzino.

Un anagramma di una sequenza S è ottenuto permutando le sue cifre (per esempio, 1949 e 9419 sono anagrammi); inoltre, S è anagramma di se stessa. Quindi Topolino deduce che, per calcolare il numero p di anagrammi di S, deve includere S tra i suoi anagrammi contenuti nel pizzino. In questo modo, p = 1 indica che una sequenza non ha altri anagrammi, a parte se stessa, per cui va estratta la sua prima cifra.

Per illustrare quanto descritto sopra a Basettoni, Topolino prende un pizzino che contiene i tre anagrammi 1949, 9419 e 9149 (e non ce ne sono altri) e ne estrae la loro terza cifra, ossia 4, 1 e 4, poiché p = 3; poi, prende un altro pizzino con due soli anagrammi 1949 e 9419, estraendone la seconda cifra, ossia 9 e 4, poiché p = 2. Utilizzando questo meccanismo di estrazione delle cifre, aiutate Topolino a decifrare i pizzini di Gambadilegno trovati da Basettoni.

Dati di input
Il file input.txt è composto da N+1 righe.
La prima riga contiene un intero positivo che rappresenta il numero N di sequenze contenute nel pizzino.
Ciascuna delle successive N righe contiene una sequenza di cifre decimali senza spazi intermedi.

Dati di output
Il file output.txt è composto da una sola riga contenente una sequenza di N cifre decimali, senza spazi intermedi ossia il codice di accesso cifrato nel pizzino.

Assunzioni

1 ≤ N ≤ 100.
Ogni sequenza contiene al massimo 80 cifre decimali.
Le sequenze contenute in uno stesso pizzino sono tutte diverse tra loro.
Una sequenza di K cifre decimali presenta al massimo K anagrammi in uno stesso pizzino. Inoltre, tali anagrammi non necessariamente appaiono in righe consecutive del pizzino

Esempio di input/output

file `input.txt`	file `output.txt`
4	0537
022
524
322
742

file `input.txt`	file `output.txt`
6	411244
1949
21
9419
12
4356373
9149

Dati di Input

In questa sezione si illustra il procedimento per fornire i dati di input al programma.

Si prepari, usando Blocco Note, un file denominato input.txt contenente le stesse righe usate nell'esempio.

Nota: In figura sono stati forniti come dati di input i valori dei due esempi. Per eseguire una prova del programma sulla seconda serie di valori, basta invertire le due tabelle di dati (con Taglia e Incolla), infatti è il valore letto nella prima riga che determina il numero di righe da leggere.

Aprire un nuovo progetto, denominarlo Pizzini.
Nella funzione main scrivere le seguenti dichiarazioni:

un puntatore a FILE (denominarlo f)
Una variabile intera N
un array M di 100 stringhe di 80 caratteri, al massimo, ciascuna.
Un array Codice di 100 caratteri, corrispondente alla sequenza di 100 cifre

Lo scopo delle restanti variabili sarà motivato durante l'analisi del problema.

Leggere i dati dal file:

Per poter accedere al file, occorre prima aprire il file in modalità lettura.

La prima riga del file contiene un numero intero da trasferire nella variabile N.

Le N righe successive contengono stringhe di caratteri numerici, che si possono leggere utilizzando la funzione fscanf:

si deve notare che, quando si legge da file, la funzione fscanf richiede che venga specificato l'indirizzo della variabile in cui memorizzare il valore letto. Poichè M è una matrice bidimensionale, nel linguaggio C esiste la regola che se non si specifica una coordinata, il compilatore usa l'indirizzo della matrice, a iniziare dalla coordinata specificata.

Quindi M[i] si riferisce all'indirizzo della riga i.

Ogni riga (un record) letta dal file viene scritta in una riga della matrice, non è necessario leggere carattere per carattere.

Analisi del problema: descrizione della soluzione.

Ognuna delle sequenze scritte su un pizzino, in successione dalla prima fino all'ultima, viene confrontata con tutte le successive. Ciò può essere descritto in pseudolinguaggio:

for (i=0; i<N; i++) lettura della sequenza in posizione i dell'array M for (j=i+1; j<N; j++) { se la sequenza in posizione j è un anagramma della sequenza che si trova in posizione i allora conta un altro anagramma. }

Al termine del confronto di M[i] con tutte le sequenze successive, nella variabile Conta si conosce il numero di anagrammi di M[i]

Quindi si devono riprendere tutte le parole trovate ed usare il conteggio (Conta) degli anagrammi come indice per estrarre da ciascuna sequenza M[i] la cifra che occupa la posizione Conta.

Questo procedimento, in pseudolinguaggio si scrive:

A iniziare dall'elemento M[i] Ripeti { Nella stessa posizione x occupata dalla sequenza nel pizzino, scrivere la cifra del codice presa da M[x][Conta] prelevare la successiva sequenza che è anagramma fino a quando una sequenza non è seguita da altri anagrammi. }

Per poter compiere questa operazione si deve rivedere l'operazione di ricerca degli anagrammi. Infatti per poterli rintracciare nuovamente, è necessario concatenare in lista tutte le sequenze mano a mano che si riconoscono gli anagrammi.

Ad ogni riga viene perciò associato un campo puntatore: pun.

Inoltre, avanzando nelle operazioni di confronto, si possono escludere tutte le sequenze che risultano già essere state individuate come anagramma di una sequenza precedente.

L'operazione di ricerca degli anagrammi può essere riformulata in questi termini:

for (i=0; i<N; i++) lettura della sequenza M[i] Se M[i] è un anagramma di sequenze precedenti passare alla sequenza successiva. Contare, nella variabile Conta un anagramma. Annotare l'indice i allo scopo di creare una lista di anagrammi. for (j=i+1; j<N; j++) (per tutte le sequenze successive) Se M[j] è anagramma di M[i] allora conta un altro anagramma inserire questo elemento in lista (cioè nel campo puntatore, della sequenza precedente M[i], inserire j, l'indice dell'anagramma trovato). annotare l'indice di j di questa sequenza. }

Resta da specificare in quale modo si riconosce se due sequenze contengono gli stessi simboli, quindi sono anagrammi. Una possibile soluzione consiste nel mettere in ordine tutti i simboli delle due parole e, quindi, dal confronto in parallelo delle due stringhe risulta semplice stabilire se le due stringhe sono uguali.

Programma

L'array Codice contiene una cifra per ogni sequenza, quindi poichè ci possono essere al massimo 100 sequenze su ogni pizzino, l'array Codice contiene al massimo 100 caratteri.

Anche l'array pun viene dimensionato per contenere al massimo 100 elementi. Il valore -1 indica che il puntatore rappresenta l'ultimo elemento della lista.

Per verificare se due stringhe sono anagrammi si ordinano i loro caratteri e si confrontano le stringhe risultanti:

La funzione ordina riceve come parametro il puntatore alla stringa.

Infine il ciclo che svolge l'elaborazione principale:

Commenti:

Per tutte le sequenze contenute nel pizzino:
Se è stata individuata come anagramma si passa alla sequenza successiva.
Si copia la sequenza in una variabile temporanea,
Si ordina la seuqnza dei caratteri copiati,
Si annota l'indice di questa sequenza
Si conta un anagramma (la sequenza è anagramma di se stessa),
Per tutte le sequenze successive:
Si crea una copia della sequenza M[j]
Si ordinano i caratteri di tale copia,
Se le due sequenze ordinate sono uguali,
conta un anagramma,
mostra i due anagrammi
Nel campo pun della sequenza precedente si scrive l'indice j di questa sequenza, allo scopo di inserire l'elemento in una lista. L'indice j si salva anche nella variabile p che rappresenta il puntatore all'ultimo elemento della lista
Nel suo campo pun dell'elemento in posizione j c'è il valore -1, ad indicare la marca di fine lista).
Fine delle operazioni se le sequenze sono anagrammi
Fine del confronto di M[i] con tutti i successivi.
Si punta all'elemento M[i] tramite il puntatore p,
Ripetere:
Prelevare dalla sequenza M[p] la cifra in posizione Conta-1 e scriverla nella stessa posizione p dell'array Codice
Si mostra (a scopo di verifica) la cifra del codice,
Si passa al successivo elemento della lista e, se diverso da -1, si ripete
Si stampa un "vai a capo" per terminare la stampa della sequenza di cifre di un codice
Fine ciclo su tutte le sequenze del pizzino.

A questo punto si può mostrare il codice risultante e si chiude il file: