Esprimere una funzione in codice

[stev809]

Ciao a tutti
spero che mi possiate essere di aiuto ,
io ho questa funzione espressa così:

s: stringa
t: template
n: length(s)
d: dizionario

for i in [0,n)
   if t[i] e' una lettera minuscola AND s[i] diverso da t[i]
        return falso
   else if t[i] non nel dizionario d
       d[t[i]] = s[i]
   else if s[i] diverso da d[t[i]]
       return falso
endfor
return vero

e avrei bisogno di tradurla in codice java
Qualche suggerimento ?
Saluti e grazie

[pabloski]

Beh il suggerimento piu' ovvio e' quello di studiare Java e la sua standard library.

Li' c'e' praticamente scritto l'algoritmo in maniera dettagliatissima. Una conoscenza di base di Java e' quanto ti manca per realizzare il codice.

[stev809]

Grazie per il suggerimento .... ma non è che mi sia molto utile .
Io sono ancora uno studente e non riesco proprio a capire e più o meno mi è chiaro cosa devo fare.
L'unica cosa che non riesco a capire è questo passaggio :

d[t[i]] = s[i]

un suggerimento ?

[Mursey]

Originariamente inviato da stev809

L'unica cosa che non riesco a capire è questo passaggio :

d[t[i]] = s[i]

Mette la lettera nel dizionario.

Non so cosa sia il template ma da come lo usa sembra una sorta di stringa da usare come riferimento.
Quindi usa quella lettera del template (t[i]) come indice per il nuovo elemento del dizionario (d[t[i]]), il dizionario potrebbe essere un semplice array.

[pabloski]

Originariamente inviato da stev809

Grazie per il suggerimento .... ma non è che mi sia molto utile .
Io sono ancora uno studente e non riesco proprio a capire e più o meno mi è chiaro cosa devo fare.
L'unica cosa che non riesco a capire è questo passaggio :

d[t[i]] = s[i]

un suggerimento ?

Pero' cosi' mi fai capire che ti mancano addirittura i concetti base. Come spiegato da Mursey, quel d e' un dizionario, in gergo informatico un hash table, cioe' una struttura dati con particolari caratteristiche.

E' pressoche' impossibile che tu possa implementare quello pseudo-codice in Java, se ti risultano sconosciute le strutture dati basilari.

[stev809]

In effetti le sto studiando ora ti devo dire la verità ma già che mi avete detto che è un ash table posso usare la classe della libreria standard di java giusto ?
Forse ho capito come risolverlo ora
Grazie mille

ho altri dubbi posso contnuare a chiedere qui o apro un nuovo tread ?

[stev809]

ho provato a scriverlo come mi sembra sia scritto ho usato un hashMap di caratteri ma dove sto sbagliando ?

public boolean cercaParola(String schema){
		lettera = parola.toCharArray();
		 lunghezza = parola.length();
		 char[] caratteriSchema= schema.toCharArray();
	     mSchema = new HashMap();
	    
	     for (int i = 0 ; i < lunghezza ; i++){
	    	 mSchema.put(lettera[i], null);
	    	 if(Character.isUpperCase(lettera[i])&& caratteriSchema[i]!= lettera[i]){
	    		 return false;
	    	 }else if (!mSchema.containsKey(lettera[i])){
	    		 mSchema.put("",caratteriSchema[i]);
	    	 }else if (caratteriSchema[i]!= mSchema.get(lettera[i]))
	           return false;
	     }
	     return true;
	     }

plz help me

[tomminno]

Originariamente inviato da stev809

ho provato a scriverlo come mi sembra sia scritto ho usato un hashMap di caratteri ma dove sto sbagliando ?

public boolean cercaParola(String schema){
		lettera = parola.toCharArray();
		 lunghezza = parola.length();
		 char[] caratteriSchema= schema.toCharArray();
	     mSchema = new HashMap();
	    
	     for (int i = 0 ; i < lunghezza ; i++){
	    	 mSchema.put(lettera[i], null);
	    	 if(Character.isUpperCase(lettera[i])&& caratteriSchema[i]!= lettera[i]){
	    		 return false;
	    	 }else if (!mSchema.containsKey(lettera[i])){
	    		 mSchema.put("",caratteriSchema[i]);
	    	 }else if (caratteriSchema[i]!= mSchema.get(lettera[i]))
	           return false;
	     }
	     return true;
	     }

plz help me

Ma almeno hai provato a debuggare il tuo codice?
La risposta alla tua domanda dovrebbe essere evidente!

Perchè aggiungi sempre al dizionario il carattere lettera[i]? E perchè utilizzi stringa vuota come chiave? Anche se quel pezzo di codice non verrà mai eseguito...

[stev809]

La verità ? è che non so nemmeno quello che ho fatto....
la mia idea è quella di riempire la mappa solo con uno schema che viene letto dal metodo .
Ma quello che dovrebbe fare il metodo sarebbe verificare se una lettera è una chiave o una lettera di una parola ....
cioè se la lettera è maiuscola allora è una chiave e se la lettera è minuscola è la componente vera e propria della parola .
In pratica attraverso questo metodo io dovrei verificare quali stringhe corrispondono allo schema dato.
Come implemento la mappa per effettuare questa verifica ?
cosa devo fare ?

[pabloski]

Francamente a me pare assurdo pure lo pseudo-codice. Il primo if causa l'uscita della procedura ogni qualvolta t[i] sia minuscolo e diverso da s[i], cosa che dovrebbe accadere abbastanza spesso.

Poi non e' nemmeno chiaro che vada a fare quella procedura. Cioe' mentre si enumera su s[i] ( visto che si usa n ), in realta' si sta operando su t[i].

E length(t) = length(s) sempre? Credo sia irrealistico. Per cui l'intero for sarebbe sbagliato.

L'implementazione pure e' sbagliata. Perche' mSchema.put(lettera[i], null)? Lo pseudo-codice dice che t[i] va inserito nel dizionario solo se manca, tu invece lo inserisci ad ogni iterazione e peggio ancora gli accoppi un valore null.

Esattamente quello pseudo-codice da dove e' venuto fuori?

[stev809]

Originariamente inviato da pabloski

Esattamente quello pseudo-codice da dove e' venuto fuori?

da questo testo :

Una parola è una sequenza finita di lettere minuscole
Uno schema è una sequenza finita di caratteri appartenenti all alfabeto {a,b,c,.....z} U {A,B,C....Z}. Le lettere maiuscole rappresentano delle variabili su cui agisce la funzione di assegnamento.
Un assegnamento è una funzione "SIGMA" da {A,B,C,...Z} a {a,b,c,....} (ossia, a ogni lettera maiuscola l' assegnamento associa una lettera maiuscola).
Dato uno schema W = "alfa"1 ......"alfa"n e un assegnamento "SIGMA",indichiamo con "SIGMA"(W) la parola w= "BETA"1...."BETA"n tale che , per ogni 1<=i<=n, se "ALFA"i è una lettera minuscola allora "BETA"i = "SIGMA"("ALFA"i), se "ALFA"i è una lettera minuscola allora "BETA"i = "ALFA"i.
Una parola w è un istanza di uno schema W se esiste un assegnamento "SIGMA" tale che w= "SIGMA"(W).

[pabloski]

Gli Alfa e i Beta chi sarebbero? Caratteri ascii?

In sostanza il succo sarebbe:

1. parola = sequenza di lettere minuscole
2. schema = sequenza di lettere minuscole e maiuscole

La chiarezza finisce qui pero'. Se SIGMA e' una funzione da {A,B,C,...Z} a {a,b,c,....}, significa che mappa caratteri maiuscoli in caratteri minuscoli, cioe' e' la funzione lowercase delle stringhe.

La riga successiva dice che presa una stringa, la scorri carattere per carattere e vai a vedere se quel carattere e' maiuscolo nello schema. Se si lo trasformi in maiuscolo anche nella stringa, altrimenti lo trasformi in minuscolo tramite SIGMA.

L'ultima riga genera ancora piu' confusione, perche' dicendo che w e' un membro di W, mi fa pensare che W sia un'insieme di stringhe e non una sorta di stringa.

[stev809]

No guarda ...
le lettere maiuscole non le trasformi in minuscole ma le associ a minuscole
ti faccio un esempio
Se hai la parola "acca" lei è un istanza di:

"aBBa" dove B corrisponde alla lettera "c"
"aCBa" dove sia B che C corrispondono a "c"
"XYZT" dove X e T corrispondono ad "a" e ,Y e Z corrispondono a "c"

Lo svolgimento mi è chiaro quello che non mi è chiaro è come devo implementare la mappa .

[pabloski]

Non vedo pero' da dove quelle associazioni vengano fuori. Sono memorizzate nel dizionario mi pare di capire, ma e' la procedura per generarle che e' alquanto nebulosa.

La HashMap comunque richiede solo l'uso di put(chiave, valore).

Per verificare se una chiave e' gia' presente nella HashMap puoi usare containsKey(chiave), che restituisce true se gia' presente.

Questo e' quello che si puo' dire guardando allo pseudocodice. L'unico punto in cui s'interagisce con la HashMap e' questo

if t[i] non nel dizionario d
       d[t[i]] = s[i]

appunto si va a verificare se la chiave t[i] e' gia' presente, in caso contrario la si aggiunge

[stev809]

Ok col metodo put aggiungo alla mappa chiave e valore ....Ma la mia domanda è che chiavi e che valori devo aggiungere ?
Cioè ho le due stringhe da confrontare e le aggiungo lettere per lettera alla mappa una come chiave e una come valore ? E questo che mi manda in pappa il cervello e non riesco a capire .

[stev809]

Secondo te così puo andare bene ?

 
  public boolean cercaParola(String schema){
	 char[] arrParola = parola.toCharArray();
	  lettera = schema.toCharArray();
	  //confronto se la lunghezza delle parole è uguale :
	  if(arrParola.length!= lettera.length)return false;
	  
	  for(int i = 0; i < lettera.length; i++){
		  //verifico se le lettere minuscole corrispondono
		  if(Character.isLowerCase(lettera[i])&& lettera[i]!= arrParola[i]){
			  return false;
		  }
		  //controllo che sia una chiave
		   if(Character.isUpperCase(lettera[i])){
			  for(int j = i ;j< lettera.length; j++){
				  //Controllo che non vengano occoppiate 2 lettere alla stessa chiave;
				  if(arrParola[i]!=arrParola[j] && lettera[i]==lettera[j]){
					  return false;
				  }
			  }
				  // assegno allo schema la lettera corrispondente
			  lettera[i]= arrParola[i];
		  }
	  }
	     return true;
	     }

[pabloski]

Originariamente inviato da stev809

Ma la mia domanda è che chiavi e che valori devo aggiungere ?

Questo dovrebbe essere chiaro dallo pseudo-codice. Ovvero

d[t[i]] = s[i]

Credo sia chiaro che t[i] e' la chiave e s[i] il valore.

Originariamente inviato da stev809

Cioè ho le due stringhe da confrontare e le aggiungo lettere per lettera alla mappa una come chiave e una come valore ? E questo che mi manda in pappa il cervello e non riesco a capire .

No, solo se t[i] e' maiuscolo ed e' uguale a s[i]. Pero' vuol dire che:

1. t e s devono avere la stessa lunghezza
2. s[i] dev'essere una lettera maiuscola
3. vale solo una volta, cioe' se la lettera t[i] sta gia' nel dizionario, anche se t[k] = t[i] = s[k], comunque la coppia t[k],s[k] non viene aggiunta al dizionario

[stev809]

che dici così puo andare ?

	 public boolean cercaParola1(String schema){
				char[] letteraParola =parola.toCharArray();
				char[] letteraSchema =schema.toCharArray();
				HashMap<Character,Character> mSchema = new HashMap<>();
			 //	controllo lunghezza stringhe
				if(letteraParola.length!= letteraSchema.length)
					return false;
				
				for(int i= 0 ; i< letteraSchema.length; i++){
					// confronto lettere tra schema e parola se la lettera dello schema è minuscola
					if(Character.isLowerCase(letteraSchema[i])&& letteraSchema[i]!= letteraParola[i]){
						return false;
					}else 
						//aggiunta di chiave e valore alla mappa se non presente 
						if (!mSchema.containsKey(letteraSchema[i])){
							mSchema.put(letteraSchema[i],letteraParola[i]);
						}else
							// se la chiave è presente nella mappa allora verifico se i valori corrispondono
							if(mSchema.get(letteraSchema[i])!=letteraParola[i] ){
								return false;
							}
						
				}
				     return true;
				     }

[pabloski]

Come traduzione di quello pseudo-codice si. Ma come logica no. Usare letteraSchema.length significa che la parola non puo' essere piu' corta, altrimenti letteraParola[i] si ha un errore out of range.

[stev809]

Ma il problema della lunghezza non sussiste ... Perchè viene verificato a priori , cioè le stringhe devono avere la stessa lunghezza se una è lo schema dell altra quindi non importa se il ciclo termina con la fine di una o dell altra perchè sono della stessa lunghezza