// File : decrypteurs.java // Date : 2007/05/24 // Authors: Mikaël Mayer & Sébastien Mignot [...] class DecryptoMAffiche extends decrypteurs { int Nmorts; //Nombre de morts détectés. int NmotsNonDecryptesMax; //On part du total. Permutation permSolution; DecryptoMAffiche(Dico dico,Mot[] motPhrase, String sphrase, int NmortsMax, Permutation ps) { super(dico, motPhrase, sphrase); Nmorts = 0; NmotsNonDecryptesMax = NmortsMax==-1?Phrase.length:NmortsMax; permSolution = new Permutation(ps.P.clone()); } void recupere(Mot[] motPhrase) { Phrase= new MotDuMessage[motPhrase.length]; for (int i=0; i<Phrase.length; i++) { Phrase[i] = new MotDuMessage(motPhrase[i], dico); if(!Phrase[i].decryptable()) { Phrase[i].marquerMort(); Nmorts++; } } } enum Action { RecuperationPermutation, RetourArriere, ApplicationPermutation, RetraitPermutationGauche, ChercheMeilleurGauche } Permutation decrypte() { PermutationPile Sp = new PermutationPile(); int curseur = 0, curseurApplication = 0; Triage(0, new Permutation()); Permutation permutationEnCours=null; Action action = Action.RecuperationPermutation; int premierMort = Phrase.length; int minMort = 0; //Pour le débugage int numeroBonInclus = -1; for(int i=0;i<Phrase.length;i++) { System.out.println("Nouvelle étape Sp="+Sp); System.out.print("CEP du MDM"+i+" "+Phrase[i].motCrypte()+":{"); int compteur=0; motTestant machin = Phrase[i].tete.succ; while(machin!=null&&compteur++<10){ System.out.print(machin.motDico+","); machin=machin.succ; } System.out.println("}"); } while(curseur>=0) { //Si on revient en arrière, ça ne marche plus... if(action==Action.RecuperationPermutation) { if(curseur>=Phrase.length) { NmortsTrouves = Nmorts; if(Nmorts > NmotsNonDecryptesMax) throw new Error("Cas impossible de supériorité"); NmotsNonDecryptesMax = Nmorts-1; //On ne va plus faire pire maintenant if(Nmorts==0) { //On a trouvé LA solution! ptrouvee = new Permutation(Sp.P.clone()); break; } ptrouvee = new Permutation(Sp.P.clone()); if(NmortsTrouves<meilleurDecryptage) { meilleurDecryptage=NmortsTrouves; System.out.println("Décodage trouvé avec "+NmortsTrouves+" morts"); System.out.println(decoderPhrase(ptrouvee)); } //System.out.println("Recherche d'une meilleure solution..."); action = Action.RetourArriere; //Et on fait semblant qu'un mot est mort pour trouver une meilleure solution. curseur--;//Si le dernier mot était mort, on a un problème! if(!Phrase[curseur].estMort()) Sp.retrait(curseur); permutationEnCours=null; //La permutation ne va plus! curseurApplication = curseur; if(ptrouvee.compatible(permSolution)) break; } else if(Phrase[curseur].decryptable()&&Nmorts<=NmotsNonDecryptesMax) { if(!Phrase[curseur].apporteQuelqueChose(Sp)) { /*System.out.println(Sp); System.out.println(Sp.lettres); System.out.println(Phrase[curseur].motCrypte().lettres);*/ Phrase[curseur].motSuivant(); //On passe au mot suivant sans le garder permutationEnCours=null; //Ne sert à rien de fusionner si la permutation n'apporte rien. } else { //System.out.println("Application "+curseur+" "+Phrase[curseur].tete.motDico+"=>"+Phrase[curseur].indice.motDico+" Nmorts="+NmotsNonDecryptesMax); permutationEnCours=Phrase[curseur].PermutationSuivante(Sp); } action=Action.ApplicationPermutation; curseurApplication = curseur+1; } else if(Phrase[curseur].estMort()||Nmorts>NmotsNonDecryptesMax) { //Le mort est normalement déjà compté if(Nmorts<=NmotsNonDecryptesMax){ //On peut passer au suivant if(numeroBonInclus==curseur-1){ numeroBonInclus=curseur; } curseur++; //On recherche en arrière une permutation valable. curseurApplication = curseur; } else { action=Action.RetourArriere; } } else if(Phrase[curseur].nombreMotListe()!=0){//Nécessaire pour avoir le droit de retirer une permutation. throw new Error("On ne doit pas passer par là!"); } else { //Le nombre de mots de la liste est nul. Mais pq pas marqué comme mort? throw new Error("Arrivée dans un cas impossible de RecupererPermutation n°"+curseur); } } else if (action==Action.RetourArriere){ if(Phrase[curseur].estMort()) { if(Phrase[curseur].nombreMotListe()!=0) { //Problème: On ne doit pas tout ressuciter. Phrase[curseur].marquerVivant(); Nmorts--; } curseur--; if(curseur>=0) { permutationEnCours=null; //La permutation ne va plus! if(Phrase[curseur].estMort()) { curseurApplication=curseur; } else { Sp.retrait(curseur); //On peut tranquillement revenir en arrière. curseurApplication=Phrase.length; action = Action.RetraitPermutationGauche; } } } else if(Phrase[curseur].decryptable()&&Nmorts<=NmotsNonDecryptesMax) { action = Action.RecuperationPermutation; //On peut directement appliquer une permutation } else if(Phrase[curseur].nombreMotListe()!=0||Nmorts>NmotsNonDecryptesMax){ Phrase[curseur].marquerMort(); if(curseur<premierMort) { premierMort=curseur; if(premierMort==minMort) { minMort++; premierMort=Phrase.length; } //Débugage //System.out.println("les "+minMort+" premiers sont morts. Premier mort suivant="+(curseur+1)); } permutationEnCours=null; Nmorts++; action=Action.RecuperationPermutation; /*if(Nmorts<=NmotsNonDecryptesMax){ //On peut passer au suivant curseur++; //On recherche en arrière une permutation valable. curseurApplication = curseur; action=Action.RecuperationPermutation; } else { action=Action.RetourArriere; }*/ } else { throw new Error("Arrivée dans un cas impossible de RetourArriere"); } } else if(action== Action.RetraitPermutationGauche) { curseurApplication--; if(curseurApplication>curseur) //Si on est encore en train de remonter { Phrase[curseurApplication].retirerPermutation(); //Si après avoir retiré la permutation, il est décryptable, c'est qu'il est vivant. if(Phrase[curseurApplication].estMort()&& Phrase[curseurApplication].nombreMotListe()!=0) { Phrase[curseurApplication].marquerVivant(); Nmorts--; //ça fait toujours un mot de moins non décrypté à compter } } else { action = Action.RetourArriere;//TODO: A vérifier. } } else if (action==Action.ApplicationPermutation) { if(curseurApplication<Phrase.length) { Phrase[curseurApplication].appliquerPermutation(permutationEnCours, dico); if(!Phrase[curseurApplication].estMort()) { //Si le mot n'est pas mort à l'origine if(Phrase[curseurApplication].nombreMotListe()==0){//mais s'il n'est plus décryptable, //System.out.println("Marquage mort App "+curseurApplication); Phrase[curseurApplication].marquerMort(); //On le marque comme mort. Nmorts++; if(Nmorts>NmotsNonDecryptesMax) { //On arrête l'applicationPermutation action = Action.RetraitPermutationGauche; //On retire la permutation lors de la boucle suivante. //System.out.println("Retrait "+curseurApplication+ " Nmorts="+Nmorts+"/"+NmotsNonDecryptesMax); } } //Sinon on a réussi } curseurApplication++; } else { //On a atteint la fin des applications avec succès. action = Action.ChercheMeilleurGauche; } } else if(action == Action.ChercheMeilleurGauche) { action = Action.RecuperationPermutation; Sp.fusion(permutationEnCours, curseur); if(Phrase[curseur].motCourant.compatible(Phrase[curseur].motCrypte(),permSolution)&&numeroBonInclus==curseur-1) { numeroBonInclus=curseur; //Et on affiche les CEP commme des bourrins ou juste les mots choisis for(int i=0;i<Phrase.length;i++) { System.out.println("Nouvelle étape Sp="+Sp); if(i<=curseur) { System.out.println("MDM "+i+", n°="+(Phrase[i].numero-1)+":"+Phrase[i].motCourant); } else { System.out.print("CEP du MDM"+i+" "+Phrase[i].motCrypte()+":{"); int compteur=0; motTestant machin = Phrase[i].tete.succ; while(machin!=null&&compteur++<10){ System.out.print(machin.motDico+","); machin=machin.succ; } System.out.println("}"); } } //try {System.in.read();} catch( IOException e) {} } curseur++; curseurApplication = curseur; if(curseur<Phrase.length) Triage2(curseur, Sp); } } System.out.println("Nombre de non-décryptés: "+(NmotsNonDecryptesMax+1)); return ptrouvee; } }