steph1978 a écrit 2985 commentaires

Un jour où la solution naïve à la première partie ne passe pas à l'échelle pour la seconde partie.

J'ai d'abord fait une solution qui a explosé la RAM (4M*4M d'int, ça explose).
Puis une solution sans rien en RAM mais qui explose le CPU (j'ai timeout à 10 minutes).
Troisième solution qui est un compromis entre RAM et CPU. Je stocke des intervalles pour 4M de lignes ; comme les autres solutions présentées ici.
Ça passe, en 40 secondes avec l'aide du JIT.

code partie 2

import sys

W = H = 4_000_000

# store position that are not reachable, row by row
L = [ [(0,0) for _ in range(32)] for _ in range(H+1) ]

for i,l in enumerate(sys.stdin.read().splitlines()):
    (_,_,X,Y,_,_,_,_,A,J) = l.split(" ")
    x, y = int(X[2:-1]), int(Y[2:-1])
    a, b = int(A[2:-1]), int(J[2:])
    d = abs(x-a)+abs(y-b)
    for ny in range(y-d, y+d+1):
        if ny>=0 and ny<=H:
            dy = abs(ny-y)
            dx = d-dy
            L[ny][i] = (x-dx,x+dx)

for (y,I) in enumerate(L):
    SI = sorted(I)
    maxx = 0
    for (a,b) in SI:
        if a>maxx+1:
            print(y, maxx+1, (maxx+1)*4_000_000+y)
            sys.exit(0)
        maxx = max(maxx,b)

https://betterjpeg.com/crop.htm

Permet de découper (crop) une image jpeg sans toucher à la qualité. L'astuce est que la découpe ne peut se faire que par pas de 8 pixels. En effet jpeg applique une FFT sur des carrés de 8x8. Donc pour croper il suffit de supprimer les carrés qui gênent et de garder les bons.

en plus joli : l'input et le resultat.

image disparue : 

J'aime bien utiliser le format PNM car c'est du texte et donc facile à générer.

Sous linux, ça se visualise nativement. Mais ça peut être converti en PNG grâce à ImageMagic : convert a.pnm -scale 400% a.png

Le parsing de l'input est presque plus long à écrire que l'application de règles : 4 boucles for imbriquées et 4 split contre 3 boucles while imbriquées.

Voici mon code pour la partie deux. La partie est identique excepté la condition de sortie.

import sys

W = 1000
H = 200

L = [[0 for _ in range(W)] for _ in range(H)]  # full or air

def s2li(s,sep=','):
    return list(map(int,s.split(sep)))

MAX_Y = 0
for l in sys.stdin.read().splitlines():
    lp = l.split(" -> ")
    for f,t in zip(lp,lp[1:]):
        (a,b,c,d)= (*s2li(f),*s2li(t))
        x0 = min(a,c)
        y0 = min(b,d)
        x1 = max(a,c)
        y1 = max(b,d)
        MAX_Y = max(MAX_Y, y1)
        for x in range(x0,x1+1):
            for y in range(y0,y1+1):
                L[y][x] = 1
for x in range(W):
    L[MAX_Y+2][x] = 1 # rock on the ground

stop = False
N = 0
while not stop:
    N += 1
    y = 0
    x = 500
    more = True  # can all left or right 
    while more and not stop:
        more = False
        while L[y][x]==0 : #and not stop:  # if only air
            y+=1
            stop = y == MAX_Y+2
        if L[y][x-1]==0: # can fall left
           x -= 1
           more = True
        elif L[y][x+1]==0: # can fall right
            x += 1
            more = True
        else:
            stop = y == 1 # can't put more sand
    L[y-1][x] = 2 # mark sand

print(N)

Et une jolie nimage de la caverne remplie de sable:

j'ai la même mais avec une rotation.

Tu veux dire à la place du eval. Oui clairement, c'est moins craignos.

À la première lecture je pensais que tu voulais résoudre le problème en javascript 😓. Je veux dire juste en comparant les deux listes avec un <. J'ai tenté, ça marche presque 😛. Mais non en fait, les règles de comparaisons ne sont pas les mêmes.

Je galérais à organiser ma comparaison de paquets, et j'ai eu un indice d'utiliser un comparateur. Je suis reparti là dessus et ça fonctionne.

import sys

P = [ tuple(map(eval, p.split("\n"))) for p in sys.stdin.read().split("\n\n") ]

def C(l,r):
    T = (type(l),type(r))
    if T == (int,int):
        if l<r: return -1
        return l>r # 0 or 1
    if T == (int,list):
        return C([l],r)
    if T == (list,int):
        return C(l,[r])
    # list,list
    for q in zip(l,r):
        c = C(*q)
        if c: return c
    return C(len(l),len(r))

# part 1
S = 0
for i,p in enumerate(P):
    if C(*p) <= 0:
        S += i+1
print(S)

# part 2
from functools import cmp_to_key
Q = [ q for (l,r) in P for q in [l,r] ]
Q.append([[2]])
Q.append([[6]])
Q.sort(key=cmp_to_key(C))
print((Q.index([[2]])+1)*(Q.index([[6]])+1))

Dans mon input, tous les b ne sont que dans la deuxième colonne. Et la première colone ne contient que des a. Comme il faut nécessairement passer par un b, je n'ai testé que des départs depuis la première colonne.

J'ai passé plusieurs heures à ne pas comprendre pourquoi je ne trouvais pas la solution. Et puis j'ai compris ; j'ai loupé une phrase cruciale dans l'énoncée : on a le droit de redescendre, bordel !

J'ai utilise la très précieuse bibliothèque de manipulation de graph en Python, networkx. Mon code ne fait que parser l'input et construire la liste de transitions possibles et présente donc peu d'intérêt. Mais permet au moins de faire une joli nimage du résultat:

Si vous vous baladez sur Reddit, y en a qui ont fait des représentations de ouf.

La seconde partie était triviale dans ces conditions et m'a pris moins de deux minutes.

J'ai fait l'empaquetage avec pyinstaller. Ça semble bien fonctionner. Ça donne un exe autoporteur (interpréteur python compris) de 26MB.

Un simple pip install pyinstaller && pyinstaller -F -n offpunk offpunk.py suffit.

Avec la possibilité de mettre l'exe dans les releases.

Peut être une façon de simplifier l'installation pour certains utilisateurs.

En poussant un peu plus la réflexion sur l’arithmétique modulaire, on peut se passer de balader des listes et garder un nombre. Trop tard pour moi :)

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.