LARA

// 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;
  }
}