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 décembre 2022 à 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.