Forum Programmation.autre Avent du Code, jour 6

Posté par 🚲 Tanguy Ortolo (site web personnel) le 06 décembre 2022 à 10:43. Licence CC By‐SA.

Étiquettes :

déc.

2022

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 🚲 Tanguy Ortolo (site web personnel) le 06 décembre 2022 à 10:45. É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 alkino le 06 décembre 2022 à 14:00. É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 🚲 Tanguy Ortolo (site web personnel) le 06 décembre 2022 à 15:00. É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 Yth (Mastodon) le 07 décembre 2022 à 09:55. É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 steph1978 le 06 décembre 2022 à 16:26. É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 steph1978 le 06 décembre 2022 à 17:39. É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 steph1978 le 06 décembre 2022 à 20:14. É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 Colargol le 08 décembre 2022 à 14:32. É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.