steph1978 a écrit 3047 commentaires

Je me suis laissé emporté par le python du jour 9.
Le problème du jour passe très bien en AWK.

part 1, 11 lines

BEGIN { x=1 }
function inc() {
    c+=1
    S += index("20,60,100,140,180,220,", c ",")>0 ? x*c : 0
}
{ inc() }
$1 == "addx" {
    inc()
    x+=$2
}
END { print S }

part 2, 20 lines

BEGIN { x=1 }
function inc() {
    i = (c%40)
    A[c+1] = (i==x-1||i==x||i==x+1) ? "█" : "░"
    c+=1
}
{ inc() }
$1 == "addx" {
    inc()
    x+=$2
}
END {
    for (i=0;i<=5;i++) {
        r = ""
        for (j=1;j<=40;j++) {
            r = r A[i*40+j]
        }
        print r
    }
}

Mince alors, toute une matinée de code à mettre à la benne 😩

Blague à part, merci pour la remarque, je confonds probablement avec map ou reversed qui retournent un itérateur.

J'imagine que pour trier, il faut charger toutes les données, donc pas d'intérêt de retourner un itérateur. Ou alors ne pas chercher d'explication, l'API python n'est pas toujours cohérente.

Je suis tombé dans le piège de la solution qui ne scale pas en deuxième partie. Pas grave, on s'adapte.

Pour les deux parties, pour éviter un parsing laborieux, j'ai transformé l'input en code. Car à bien y regarder, c'est du code :)

La solution naïve ne scale pas car passé une certaine taille (32bit je crois) l'arithmétique des grands entiers sort du processeur, doit repasser par la mémoire et devient très très lente.

Chez moi c'était très net : les 500 premiers rounds sont fulgurants, moins de 1s, puis chaque round prends presque une seconde. Pour faire les 100000, en admettant avoir assez de RAM, il faudrait donc une grosse heure à 100% de CPU. Je n'ai pas cette patience.

L'astuce pour passer à l'échelle est de limiter la taille des nombres manipulés en appliquant l'arithmétique modulaire. Chaque singe à son diviseur (un nombre premier mais je crois pas que ça joue). Donc au lieu d'avoir l'item sous forme de nombre, on le transforme en une liste de restes de division, un pour chaque singe.

part 1

Je vous épargne le code complet de la première partie qui est en gros celui de la deuxième partie en un peu plus simple.

input

from collections import deque
M = [
(
    deque([ 84, 72, 58, 51])
  , lambda old:  old * 3
  , lambda x: 7 if divmod(x,13)[1] else 1
)
# ...
# same for all monkeys
# ...
]

part 2

input

from collections import deque

PRIMES = (13,2,7,17,5,11,3,19)

def mods(x):
    return [x%i for i in PRIMES]

M = [
[
    deque(mods(x) for x in [ 84, 72, 58, 51])
  , lambda old: [((o%i)*(3%i))%i for (o,i) in zip(old,PRIMES)]
  , lambda x: 7 if x[0] else 1
  ,0
],[
    deque(mods(x) for x in [ 88, 58, 58 ])
  , lambda old: [((o%i)+(8%i))%i for (o,i) in zip(old,PRIMES)]
  , lambda x: 5 if x[1] else 7
  ,0
]# ...
# same for all monkeys
# ...
]

main loop

import sys
mod = __import__(sys.argv[1])

M = mod.M
for r in range(10*1000):
    print(f"\rround {r+1}",end='')
    for m in M:
        items = m[0]
        m[3] += len(items)
        for _ in range(len(items)):
            i = items.popleft()
            ni = m[1](i) #// 3
            nm = m[2](ni)
            M[nm][0].append(ni)
print()

L=list(sorted(m[3] for m in M))
print(L[-1]*L[-2])

Je me moque gentiment. Tu as affiché clairement ton envie de faire du code propre, modélisé, typé. Et c'est louable.
Moi je pense avoir affiché mon objectif : peut importe le moyen pourvu qu'on ait la réponse le plus vite possible :)

Ah exacte, ligne 1527 et 1529 de son programme 😇

Splendide !

J'ai réutilisé l'idée de l'utf8 pour le jour 10 aussi. La lecture du LCD est infiniment plus facile, plus besoin de plisser les yeux pour deviner les lettres.

Pour l'animation de la corde j'ai choisis d'afficher le numéro du noeud (0 à 9) en noir sur fond jaune ; et de déplacer la caméra de 19 d'un coup. J'aimais pas trop la voir manger le mur :). J'ai aussi géré les largeurs impaires, c'est le cas de mon terminal.

class display:
    def __init__(self):
        self.w, self.h = tuple(os.get_terminal_size())
        border = "o"
        self.delta = numpy.array((self.w//2, self.h//2))
        top = border * (self.w)
        wodd = self.w%2
        lines = [
            border + "░ " * (self.w//2-1) + "░"*wodd + border,
            border + " ░" * (self.w//2-1) + " "*wodd + border
        ]
        self.background = [
            top + "".join(lines[h%2] for h in range(self.h - 2)) + top,
            top + "".join(lines[1-h%2] for h in range(self.h - 2)) + top
        ]

    def __call__(self, knots):
        print("\033[0;0H", end='')
        x, y = self.delta + knots[0]
        J = 19  # must be odd to see scroll
        if x <= 0:
            self.delta[0] += J
        if x >= self.w-1:
            self.delta[0] -= J
        if y <= 0:
            self.delta[1] += J
        if y >= self.h-1:
            self.delta[1] -= J
        txt = [c for c in self.background[sum(self.delta)%2]]
        for i,knot in enumerate(reversed(knots)):
            x, y = knot + self.delta
            txt[int(x + y * self.w)] = "\033[30;43m" + str(9-i) + "\033[0m"
        print("".join(txt),end='')
        time.sleep(.008)

C'est l'AoC 2019 au moins un jour sur deux il fallait ressortir son processeur "intcode".

J'adore l'animation !

Pour limiter les glitches, j'ai ajouté print("\033[0;0H", end='') au début du __call__.
Ça replace le curseur la coordonnée (0,0) du terminal ce qui évite le scrolling.

Dans la même veine, il est bénéfique de cacher le curseur avec tput civis avant de lancer l'animation. À la fin de l'animation, le remettre avec tput cnorm

Ah ça c'est vu que j'ai bidouillé pour gérer un ou deux arguments par lignes :)
Merci pour l'astuce, ça me resservira.

Rien à voir avec hier, les deux parties en une grosse demie heure.

part 1

import sys

X = 1
C = 0
S = []
I = {20, 60, 100, 140, 180, 220}

def inc():
  global C
  C += 1
  if C in I:
    S.append(C*X)

for l in sys.stdin.read().splitlines():
  m, q = (l+" _").split(" ")[:2]
  if m == "noop":
    inc()
  else: # add
    inc()
    inc()
    X += int(q)

print(sum(S))

part 2

import sys

X = 1
C = 0
LCD = [["."]*40 for _ in range(6)]

def inc():
  global C
  (r,c) = divmod(C, 40)
  C+=1
  if c in [X, X-1, X+1]:
    LCD[r][c]="#"

for l in sys.stdin.read().splitlines():
  m, q = (l+" _").split(" ")[:2]
  if m == "noop":
    inc()
  else: # add
    inc()
    inc()
    X += int(q)

print("\n".join("".join(r) for r in LCD))

J'ai fait la première partie en AWK en une petite demie heure.
J'ai eu pas mal de chance car mes calculs étaient approximatifs mais suffisant pour le cas à un noeud.

En voyant la seconde partie, j'ai tout ré-écrit en python car j'y ai vu un truc récursif.
J'ai pigé assez vite qu'il fallait mieux faire toutes les étapes, case par case pour tous les neouds.
Ça donnait toujours le bon résultat pour le premier noeud mais pas pour le dernier.

J'ai mis vraiment beaucoup de temps à débugger en pas à pas et ajuster mes calculs. Plusieurs heures :(
Pour au final un code très impératif que j'aurai presque pu laisser en AWK.

Bref dur ce jour pour moi

part 1

BEGIN{P["0_0"]=1; Hx=Hy=Tx=Ty=0}
function abs(x) { return x>0?x:-x}
{
  print "==", Hx","Hy, ";", Tx","Ty, "==", $1, $2
  for(i=1;i<=$2;i++){
    if($1=="R") {Hx++}
    if($1=="L") {Hx--}
    if($1=="U") {Hy++}
    if($1=="D") {Hy--}
    dh = abs(Hx-Tx)  # tension horizontale
    dv = abs(Hy-Ty)  # tension vertivale
    if(dh>1 && $1=="R") {Tx++; if (dv>0) {Ty=Hy}}
    if(dh>1 && $1=="L") {Tx--; if (dv>0) {Ty=Hy}}
    if(dv>1 && $1=="U") {Ty++; if (dh>0) {Tx=Hx}}
    if(dv>1 && $1=="D") {Ty--; if (dh>0) {Tx=Hx}}
    P[Ty "_" Tx]=1
    print Hx, Hy, ";", "dh:"dh, "dv:"dv, "=>", Tx, Ty
  }
}
END{print length(P)}

part 2

import sys

rope = [(0,0) for _ in range(10)]
P = [{(0,0)} for _ in range(10) ]
D = {"R":(1,0),"L":(-1,0),"U":(0,1),"D":(0,-1)}

for l in sys.stdin.read().splitlines():
  M, q = l.split(" ")
  q = int(q)
  for k in range(q):
    (x,y) = rope[0]
    (dx,dy) = D[M]
    rope[0] = (x+dx, y+dy)
    for i in range(1,10):
      (Hx,Hy) = rope[i-1]
      (Tx,Ty) = rope[i]
      dh = Hx-Tx  # tension horizontale
      dv = Hy-Ty  # tension vertivale
      if (abs(dh)>1):
        Tx += 1 if dh > 0 else -1
        if (abs(dv)>0):
          Ty += 1 if dv > 0 else -1
      elif (abs(dv)>1):
        Ty += 1 if dv > 0 else -1
        if (abs(dh)>0):
          Tx += 1 if dh > 0 else -1
      P[i].add((Tx,Ty))
      rope[i] = (Tx,Ty)

print(*(len(p) for p in P))

Tu as eu une meilleure approche pour le première partie en effet. Il vaut mieux considérer les bords (N²⁾ que toute les position de la grille (N^3).
En pratique all va s'arrêter au premier False, ce qui fait que les chronos sont assez poche (0:33 pour les deux). Aussi parce que N est petit (N=99) et que lancer l'interpréteur est incompressible. Mais en théorie, c'est bien meilleur.

Même méthode pour les deux parties : un parcours de chaque position d'une matrice. Pour chaque position, regarder à gauche, à droite, en haut, en bas. Ça donne pas un code très beau mais ça marche.

part 1

import sys
L = list(list(map(int,s)) for s in sys.stdin.read().splitlines())
W = len(L[0]) ; H = len(L)
N=0
for i in range(H):
    for j in range(W):
        v = L[i][j]
        # look right
        r = all(L[i][k]<v for k in range(j+1, W))
        # look left
        l = all(L[i][k]<v for k in range(j))
        # look up
        u = all(L[k][j]<v for k in range(i))
        # look down
        d = all(L[k][j]<v for k in range(i+1,H))
        N += (r|l|u|d)
print(N, W*H)

part 2

Encore plus moche car le code à répéter quatre fois est plus long.

import sys
L = list(list(map(int,s)) for s in sys.stdin.read().splitlines())
W = len(L[0]) ; H = len(L)
S=0
for i in range(H):
    for j in range(W):
        v = L[i][j]
        # look right
        r = 0
        for k in range(j+1, W):
            r += 1
            if L[i][k]>=v:
                break
        # look left
        l = 0
        for k in range(j-1,-1,-1):
            l+=1
            if L[i][k]>=v:
                break
        # look up
        u = 0
        for k in range(i-1,-1,-1):
            u+=1
            if L[k][j]>=v:
                break
        # look down
        d = 0
        for k in range(i+1,H):
            d += 1
            if L[k][j]>=v:
                break
        S = max(S,r*l*u*d)
print(S)

Vivement que les lutins nous fournissent une carte pour aller quelque part.

Toi t'as envie de ressortir quelques algos de parcours de graphes :) Dijkstra sort de ce corps!

C'est vrai que rien n'empêche de repasser deux fois pas le mm endroit pour pousser l'exploration des répertoires. Mais en effet c'est tordu et je n'avais pas de raison de me protéger "à prirori" de ce cas de figure. Si je n'étais pas parvenu à passer le test et la première partie, j'aurai regardé d'un peu plus près pour voir si des commandes cd child ne se répetent pas.

n'allons pas prétendre que tout est devenu nickel en la matière.

Non en effet. Mais je pense que la balance a penché côté linux en terme de matériel supporté, en particulier quand tu veux prolonger un ordinateur qui a plus de 5 ans.

En fait vu la structure de l'input où il n'y a que de cd child et cd .. # parent, c'est nécessairement un parcours d'arbre en profondeur d'abord. Il n'y a pas d'autres représentations de la relation parent-enfants, genre cd /chemin/absolu en aléatoire.

Et puis je préfère faire un code simple, le valider sur l'exemple, voire cramer un essai, avant de compliquer le code.

En bon unixien

En bon unixien, un répertoire pèse en lui même 4096 octets, à ajouter à son contenu. Et un fichier est arrondi aux 4Ko supérieurs. Ça changerai sûrement la réponse. 😆

Comme le FS est parcourus "en profondeur d'abord" et dans l'ordre, pas besoin d'une structure de données trop compliquée type arbre, une simple liste suffit.

partie 1

BEGIN { LIMIT=100*1000 }
$2 == "ls" || $1 == "dir" { next}
$2 == "cd" && $3 == ".." { # on monte
    if (S[depth]<=LIMIT) {   # <= "at most" !!!!!!!!!
        R+=S[depth]
    }
    S[depth]=0   # ne pas oublier le reset du précédent cousin
    depth -= 1
}
$2 == "cd" && $3 != ".." { depth += 1; P[depth]=$3; }  # on descend
NF == 2 {  # fichier
    for (i=1;i<=depth;i++) {
        S[i]+=$1
    }
}
END { print R }

J'ai perdu au moins une demie heure sur le fait que j'ai interprété "at most" en "au moins" car j'imaginais chercher des trucs gros (on veut libérer de la place). Alors que c'est "au plus" ; GRRR ; Bien lire l'énoncée sans faire d'hypothèse !

partie 2

Pour cette partie où il faut trouver le dossier qui permet de libérer l'espace juste nécessaire pour dl la mise à jour, j'ai utilise un script de debug qui me liste les tailles de tous les répertoires. J'ai calculé à la main l'espace qu'il me faillait, et j'ai regardé dans la liste triée des tailles (| sort -n) celle qui était juste au dessus. Oui on a le droit de bidouiller pour l'AoC si ça permet d'aller plus vite à la solution.

transmettre un paramètre d'une requête à une autre

C'est en gros le principe du cookie. Et ce n'est pas sale :)

une imprimante non reconnue

Tu vis dans les années 90 ? Aujourd'hui le matériel de tout poil est mieux reconnu sous Linux que sous Wouinoui. En particulier les imprimantes. Tu branches l'USB et c'est fini. Winouin tu rien ne se passe, tu vas sur le site du constructeur, tu installes en admin une application de 80Mo, tu reboot.

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

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.

ne peux pas installer de réseau social ni d'appli bancaire,

Je n'utilise que deux applications non disponible sur fdroid : ma banque et l'appli SNCF. J'utilise Aurora Store pour les DL et ça juste marche.

J'imagine qu'un fabriquant français pourrait fournir le mm mécanisme ainsi qu'une store à lui. J'imagine aussi qu'on pourrait persuader des entreprises françaises de mettre leur applications à dispo aussi sur ce store. Cela ne complique pas bcp le déploiement pour eux.

où tu dois paramétrer ton propre cloud pour synchroniser tes données, ça ne sert pas à grand-chose à la clientèle cible de Crosscall

Un constructeur pourrait proposer son cloud ou un cloud souverain.

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