• # python, on a RAMé

    Posté par . En réponse au message Avent du Code jour 15. Évalué à 2.

    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)