Forum Programmation.autre Avent du code jour 25

• # J'ai galéré :)

  Posté par syj le 25 décembre 2022 à 11:49. Évalué à 2. Dernière modification le 25 décembre 2022 à 11:52.

  

  Environ 2h40 pour faire ce fichu dernier problème. Je genre d'éxercice, ce n'est vraiment pas mon truc.

  J'y suis allé à la méthode ajustement test unitaire.

  Le parsing est assez simple à réaliser. En gros, c'est comme une conversion d'une base 5 avec des -1 , et -2 :)

  Le problème, c'est l'opération inverse. Mon algo est tellement tordu que je n'arrive pas à l'expliquer :)
  Je n'ai même pas l'excuse de l'alcool car je suis sous antibiotique. Résultat, c'est mon premier noël sans une goutte d'alcool.

  Joyeux noël à tous.

      static String toSnafu(long v) {
          String s  =Long.toString(v, 5);
          if(s.indexOf("3") < 0 && s.indexOf("4") < 0) {
              return s;
          }
          long[] seek = prepareSeek(v);
          long seekValue = seek[0] * ((long)Math.pow(5, seek.length-1));
  
          for(int x=1;x < seek.length;x++) {
              long lowestGreater = 2;
              for(int e=VALUES.length-1;e >= 0;e--) {
  
  
                  long add = VALUES[e] * ((long)Math.pow(5, seek.length-1-x));
  
                  long s1 = seekValue + add + maxWithOnly2(seek.length-1-x) ;
                  long s2 = v;
  
  
                  if(s1 < s2) {                   
                      break;
                  }
  
                  lowestGreater = VALUES[e];
  
              }
  
  
  
              seek[x] = lowestGreater;
              //System.out.println(Arrays.stream(seek).mapToObj(i->Long.toString(i)).collect(Collectors.joining(",")));
              long add = lowestGreater * ((long)Math.pow(5, seek.length-1-x));
              seekValue += add;
          }
  
  
  
  
          return seekToString(seek);
      }
  
  
      private static String seekToString(long[] seek) {
          StringBuilder sb = new StringBuilder();
          for(int x=0;x < seek.length;x++) {
              if(seek[x] == 0 && x == 0) {
                  continue;
              }
  
              if(seek[x] == -2) {
                  sb.append('=');
              } else if(seek[x] == -1) {
                  sb.append('-');
              } else {
                  sb.append(Long.valueOf(seek[x]));
              }
  
          }
  
          return sb.toString();
      }
  
      static long[] prepareSeek(long v) {
          if(v == 0) {
              return new long[] {0};
          }
          long power = 0;
          boolean greater = false;
          long greaterNb = 0;
          while(! greater) {
              long max = maxWithOnly2(power);
  
              for(long x=1; x <= 2;x++) {
                  long l = (x* ((long)Math.pow(5, power))) +max ;
                  if(l >= v) {
                      greater =true;
                      greaterNb = x;
                      break;
                  }
              }
              power += 1;
          }
  
          long[] mask = new long[(int)power];
          mask[0]=greaterNb;
          return mask;
      }
  
  
      private static long maxWithOnly2(long power) {
          long max = 0;
          for(int j=0; j < power;j++) {
              max += 2* Math.pow(5, j);
          }
          return max;
      }

  • [^] # Re: J'ai galéré :)

    Posté par Yth (Mastodon) le 25 décembre 2022 à 12:28. Évalué à 3.

    

    Réponse en voiture (mais pas au volant !).
    On est en base 5, donc l'algo de base c'est un divmod : division entière pour l'itération suivante, reste de la division pour le chiffre courant.

    Ici le chiffre va de -2 à 2, donc on prend le reste, donc x%5, qu'on ramène sur -2/2, par exemple r=(x+2)%5-2, on a notre chiffre dans "=-012".
    Là tu retires ton reste, donc x-=r, ton nouvel x est divisible par 5, ru divises et tu itères.

    Plus simple mais j'ai pas testé :
    x, r = divmod(x+2, 5)
    r -= 2
    Et là ton r est le bon entre -2 et 2, ton x est le suivant dans l'itération.

    • Yth.

    • [^] # Re: J'ai galéré :)

      Posté par Eric P. le 25 décembre 2022 à 12:58. Évalué à 2.

      

      Je me doutais qu'il y avait un algorithme assez simple comme ca pour faire la conversion, mais comme Jerome ce n'est pas ma specialite du tout et a cause du fait que les entiers vont de -2 a 2 j'aurais ete incapable de le trouver.
      Du coup j'ai fait un algo a ma sauce qui est nettement moins joli (mais au moins je le comprends). Mais j'ai ete plutot vite, environ une heure.

      Bravo Yth pour tes algos et pour avoir remporte le leaderboard linuxfr!

      Excusez l'absence d'accents dans mes commentaires, j'habite en Australie et n'ai pas de clavier francais sous la main.

      • [^] # Re: J'ai galéré :)

        Posté par syj le 25 décembre 2022 à 20:02. Évalué à 2.

        

        Yes bien joué Yth

        Bien joué tt le monde.

        Je trouve qu il etait vraiment plus simple que l'an dernier.

        Le prochain challenge sympa dans ce genre, c est ctf de l Ansi en mai.

        • [^] # Re: J'ai galéré :)

          Posté par Yth (Mastodon) le 29 décembre 2022 à 17:12. Évalué à 2.

          

          Bah bravo à tous les deux d'être allés au bout !
          Heureusement que les derniers jours étaient plus faciles, parce que bon, j'ai vraiment aimé le challenge dans son ensemble, mais beaucoup moins le jour de Noël :p

          Merci aussi à tous les gens ici qui ont participé, en particulier Tanguy qui a bien animé la chose, c'était fun de partager et discuter :)

          Bonne année !

          • Yth.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.