Forum Programmation.autre Avent du Code, jour 6

Post√©¬†par¬† (site web personnel) . Licence CC¬†By‚ÄĎSA.
√Čtiquettes¬†:
5
6
déc.
2022

Avent du Code, jour 6.

On va pouvoir partir en expédition dans la jungle. Enfin, demain. Peut-être. Pour le moment, comme nous avons beaucoup d'expérience avec ces machins, les lutins nous ont refilé un transmetteur pété, il faut le réparer.

  • # En Python

    Post√©¬†par¬† (site web personnel) . √Čvalu√©¬†√†¬†4.

    from typing import Iterable
    
    
    def solve1(lines: Iterable[str]) -> int:
        """Solve part 1 of today's puzzle"""
        for line in lines:
            # There is actually only one line :-)
            for i in range(4, len(line) - 1):  # ignore final '\n'
                if len(set(line[i-4:i])) >= 4:
                    return i
        return 0
    
    
    def solve2(lines: Iterable[str]) -> int:
        """Solve part 2 of today's puzzle"""
        for line in lines:
            # There is actually only one line :-)
            for i in range(14, len(line) - 1):  # ignore final '\n'
                if len(set(line[i-14:i])) >= 14:
                    return i
        return 0

    Le fait que mes fonctions mangent un it√©rable de cha√ģnes vient des fonctions utilitaires que j'ai cod√©es pour int√©grer √ßa facilement. Ici, √ßa donne quelque chose d'un peu artificiel puisqu'il n'y a qu'une ligne √† lire.

    Je ne suis pas du tout satisfait par le fait de transformer √† chaque fois un bout glissant de la cha√ģne d'entr√©e en un ensemble. J'aimerais bien faire quelque chose d'un peu mieux optimis√©, mais je n'ai rien de probant en t√™te.

    • [^] # Re: En Python

      Post√©¬†par¬† . √Čvalu√©¬†√†¬†2.

      J'ai simplement fait un ring buffer :

      from collections import deque
      
      d = deque([], maxlen=14)
      
      with open("input", "r") as h:
          for l in h:
              l = l.strip()
              for i, c in enumerate(l):
                  d.append(c)
                  if len(set(d)) == 14:
                      print(i + 1)
      • [^] # Re: En Python

        Post√©¬†par¬† (site web personnel) . √Čvalu√©¬†√†¬†3.

        Ça n'optimise rien du tout, si ?

        Je veux dire, nous avons tous deux la ligne enti√®re en m√©moire, mais l√† o√Ļ j'en prends √† chaque fois une tranche pour la convertir en ensemble et regarder sa longueur, tu enfonces un par un chacun de ses caract√®res dans une file √† taille limit√©e, que tu convertis en ensemble pour regarder sa longueur.

        Quoique, √ßa √©vite une copie de cha√ģne √† chaque √©tape, c'est √ßa¬†? La file √† taille limit√©e √©tant persistante et ne copiant qu'un caract√®re √† chaque fois.

        • [^] # Re: En Python

          Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†3.

          Franchement, je ne fais pas mieux.
          Toute optimisation semble compliquer terriblement le code.
          Et vu la taille des données…

          C'est quoi la citation √† propos des optimisations trop t√īt dans le code¬†? :)

          • Yth.
    • [^] # Re: En Python

      Post√©¬†par¬† . √Čvalu√©¬†√†¬†2.

      Pas mieux

      import sys
      s = sys.stdin.read()
      for i in range(14, len(s)):
          if len(set(s[i-14:i])) == 14:
              print(i)
              break
    • [^] # Re: En Python

      Post√©¬†par¬† . √Čvalu√©¬†√†¬†4.

      Je ne suis pas du tout satisfait par le fait de transformer √† chaque fois un bout glissant de la cha√ģne d'entr√©e en un ensemble

      Ma première solution était à base de deque et n'utilisait pas set. L'idée étant que si tu as dédoublonné la fenêtre précédente, et tu as un nouveau caractère, seul celui-ci peu créer un doublon. Donc au lieu de tout dédoublonner (set), tu dédoublonnes que par rapport à ce nouveau caractère.

      Voici:

      import sys
      from collections import deque
      
      dq = deque()
      for (i,c) in enumerate(sys.stdin.read()):
          equals = list(filter(lambda x: c == x[1], enumerate(dq)))  # find duplicate
          assert len(equals)<2
          if len(equals)==1: # remove left part until a char equal to c, included
              for _ in range(equals[0][0]+1):
                  dq.popleft()
          if len(dq) == 13: # if we have 13+1 distinct chars, we're good
              print(i+1)
              break
          dq.append(c)

      Mais honnêtement, c'est bien plus compliqué pour pas grand chose.

      Faudrait faire du profilage cpu et ram pour comparer mais sur la taille de mon input et avec la commande time, rien de visible. Et je crains que construire un set de 14 caract√®res ne soit pas plus co√Ľteux que de manipuler la deque et et le filter.

  • # un bout de AWK

    Post√©¬†par¬† . √Čvalu√©¬†√†¬†4. Derni√®re modification le 06/12/22 √† 20:14.

    Finalement une solution en AWK, pas si moche quand on a pas de "set".

    BEGIN { W = 14 }
    {
        for (i=1; i<=length($1); i++) {
            window = substr($1,i,W)
            # compare each char of window to all char of window
            S = 0  # to count match
            for (j=1; j<=W; j++) {
                for (k=1; k<=W; k++) {
                    S+= (substr(window,j,1) == substr(window,k,1)) ? 1 : 0
                }
            }
            if (S == W) {  # if each char match only itsef
                print i + W - 1
                next  # finish
            }
        }
    }
  • # en Go

    Post√©¬†par¬† . √Čvalu√©¬†√†¬†2.

    Je suis √† la bourre, j'ai pris du retard sur le n¬į5. J'ai trouv√© celui ci plus facile, solution en Go (fonction principale) :

    func startOfPacket(line string, msgLen int) int {
        l := len(line)
        if l <= msgLen {
            return -1
        }
    mainloop:
        for i := msgLen - 1; i < l; i++ {
            message := line[i-msgLen+1 : i+1]
            chars := make(map[rune]int, msgLen)
            for _, r := range message {
                chars[r]++
                if chars[r] == 2 {
                    continue mainloop
                }
            }
            return i + 1
        }
        return -1
    }

Suivre le flux des commentaires

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