[java] il gioco dello Scarabeo

[manuela_ela_78]

Salve a tutti,
una settimana fa mi sono imbattuta in un implementazione ricorsiva del gioco dello Scarabeo in cui, data una lista di caratteri (compreso il carattere '*')ed una stringa, si doveva creare un metodo statico boolean componibile(List<Character> l, String s) che risultasse true se la stringa poteva essere composta con i caratteri della lista e false altrimenti.

Siccome ne ho letto lo sviluppo ma proprio non capisco la logica della soluzione, se lo posto qui sul forum qualcuno potrebbe commentarmi il codice in modo che io comprenda i passaggi oppure è contro il regolamento ?

Grazie mille,
Manuela

[Daniels118]

E' vietata la risoluzione degli esercizi, non le spiegazioni... posta il codice e vediamo.

[manuela_ela_78]

Grazie a tutti.
Posto il codice dell'esercizio.

import java.util.*;

public class Scarabeo {

public static boolean componibile(List<Character> l, String s){

Object [] lettere=l.toArray();
char [] parola=s.toCharArray();


return componibile(lettere, parola, 0);

}



private static boolean componibile(Object[]lettere, char[]parola, int i){

if(i==parola.length)
return true;

int pos=find(lettere, parola[i], 0);
if(pos!=-1){
lettere[pos]=null;
return componibile(lettere, parola, i+1);
}
else {
pos=find(lettere, '*', 0);
if(pos!=-1){
lettere[pos]=null;
return componibile(lettere, parola, i+1);
}
else return false;
}



}

private static int find(Object[]lettere, char c, int i){

if(i==lettere.length)
return -i-1;

if( (new Character(c)).equals((Character)lettere[i] ))
return 0;

else return 1+find(lettere, c, i+1);

}

}

[Daniels118]

Dunque... il metodo ricorsivo che risolve il problema è il secondo, il primo metodo serve per fare da wrapper al primo, in particolare converte i dati di input da un formato comodo per il chiamante ad uno comodo per l'elaborazione, e maschera il passaggio del terzo parametro al metodo ricorsivo (questo parametro serve solo per l'elaborazione e non ha alcun significato per il chiamante).

Prima di scendere nel dettaglio dell'implementazione di "componibile", analizziamo il terzo metodo (find): è un metodo ricorsivo che restituisce la posizione di un carattere all'interno di una stringa.
Il metodo funziona verificando che un carattere della stringa alla posizione specificata corrisponda al carattere cercato. Se il carattere non corrisponde, il metodo richiama se stesso, specificando però di testare il carattere nella posizione successiva.
Se la posizione da testare eccede la lunghezza della stringa viene restituito un valore speciale che spiegherò in seguito.
Se il carattere corrisponde viene restituito zero, se non corrisponde viene restituito il valore ottenuto dal test del carattere successivo incrementato di uno; se dopo N iterazioni viene trovata la corrispondenza, l'ultima chiamata restituirà zero, e ad ogni ritorno dalla chiamata tale valore verrà incrementato di uno: all'ultimo ritorno verrà restituito proprio N-1 (l'ultima chiamata ha restituito zero e quindi non ha incrementato il conteggio), che è l'indice del carattere cercato.
Se si raggiunge le fine della stringa il metodo restituisce -i-1; ricordiamo che in questo caso abbiamo fatto tante chiamate quant'è lunga la stringa e che i è uguale al numero di chiamate, per cui il metodo restituirà -n°chiamate-1: siccome ad ogni ritorno abbiamo un incremento, avremo il seguente risultato finale:
-n°chiamate-1+n°incrementi
siccome n°chiamate e n°incrementi sono uguali, e n°chiamate compare con segno negativo, il risultato finale sarà -1: tale valore viene generalmente inteso come "carattere non trovato" (non può essere confuso con una posizione valida perché gli indici dei caratteri vanno da zero a lunghezza-1).

Nel prossimo post la spiegazione del secondo metodo.

[Daniels118]

Il secondo metodo prende in input la stringa da testare, l'elenco dei caratteri e un valore che indica il livello di ricorsione.
Il valore di ritorno è un booleano e su di esso non vengono eseguite operazioni, pertanto l'ultimo valore ritornato viene propagato al chiamante principale.
In linea di principio il metodo fa questo:
per ogni carattere della stringa, se è presente nell'elenco dei caratteri lo rimuove da quest'ultimo, altrimenti ritorna false; se arriva alla fine ritorna true.
Questo sistema permette di non utilizzare due volte lo stesso carattere (ma non esclude che nell'elenco possano esserci due o più caratteri uguali).
Vi è inoltre un'eccezione: se il carattere non viene trovato al primo colpo, viene fatta la ricerca per il carattere "*" che vale come jolly; se anche in questo caso il carattere non viene trovato il metodo ritorna false.

Veniamo all'implementazione.
Viene effettuata una chiamata ricorsiva per ogni carattere della stringa da testare.
Ad ogni chiamata viene incrementato l'indice del livello di ricorsione; tale valore viene utilizzato per indicare quale carattere stiamo testando.
Il primo IF è ovvio, siamo arrivati alla fine della stringa trovando tutti i caratteri: restituiamo true.
Il resto è altrettanto semplice: verifichiamo se il carattere che stiamo testando è presente nell'elenco delle lettere; se non c'è (risultato di find = -1) verifichiamo che ci sia almeno l'asterisco; se anche questo non c'è ritorniamo false.
Se il carattere viene trovato (che sia il carattere della parola o l'asterico), tale carattere viene rimosso dall'elenco, quindi viene testato il carattere successivo richiamando ricorsivamente la funzione passandole l'indice incrementato di uno.

[manuela_ela_78]

Che dire,
Grazie, sei stato chiarissimo !

una sola cosa:
nel primo if dell'implementazione, come deduci che "siamo arrivati alla fine della stringa trovando tutti i caratteri" ?

[Daniels118]

Perché l'analisi parte dal primo carattere e va verso la fine della stringa, inoltre se un qualunque carattere non viene trovato non vengono più fatte chiamate ricorsive, ma viene restituito subito false.
Da questo si deduce che si può arrivare alla fine della stringa solo se tutti i caratteri precedenti sono stati trovati.

[manuela_ela_78]

Che mito !
Era l'anello che mi mancava per far girare il ragionamento !
Grazie !!!