steph1978 a écrit 3345 commentaires

Pas si difficile aujourd'hui mais j'ai butté sur à peut prêt toutes les instructions
- ah si un elf peut bouger partout alors il ne bouge pas ?!
- ah les directions changent a chaque tour ?!
- mais qu'est ce qu'il se passe au bord ?
- ah la grille est infinie ?!

Ce dernier point m'a contraint à changer ma conception : d'une matrice à un set. Moins sympa pour débuguer mais nécessaire quand on ne connaît pas les limites du jeu. Finalement un code plus simple car pas de gestion de dépassement, et utilisation des fonctions de set (appartenance, union, différences) et des list comprehension un peu partout. Et accessoirement beaucoup plus rapide : 1025 round en 8s pour le tout.

python, 60 loc

import sys

E = set()  # elves
for y,l in enumerate(sys.stdin.read().splitlines()):
    for x,c in enumerate(l):
        if c == '#':
            E.add((y,x))

def can(y,x):
    can1 = (y-1,x-1) not in E
    can2 = (y-1,x) not in E
    can3 = (y-1,x+1) not in E
    can4 = (y,x+1) not in E
    can5 = (y+1,x+1) not in E
    can6 = (y+1,x) not in E
    can7 = (y+1,x-1) not in E
    can8 = (y,x-1) not in E
    return [can1,can2,can3,can4,can5,can6,can7,can8]

def canN(y,x,can1,can2,can3,can4,can5,can6,can7,can8):
    if can1 and can2 and can3:
        return (y-1,x)
def canS(y,x,can1,can2,can3,can4,can5,can6,can7,can8):
    if can5 and can6 and can7:
        return (y+1,x)
def canW(y,x,can1,can2,can3,can4,can5,can6,can7,can8):
    if can7 and can8 and can1:
        return (y,x-1)
def canE(y,x,can1,can2,can3,can4,can5,can6,can7,can8):
    if can3 and can4 and can5:
        return (y,x+1)

from collections import deque
dirs = deque([canN,canS,canW,canE])
for r in range(int(sys.argv[1])):
    P = dict()
    for e in E:  # each elve
        (y,x) = e
        moves = [ d(y,x,*can(y,x)) for d in dirs ]
        if all(m is not None for m in moves):
            continue
        if all(m is None for m in moves):
            continue
        p = next(filter(lambda m: m is not None, moves))
        if p not in P: # can move
            P[p] = (y,x)
        else: # occupied, invalidate move
            P[p] = None
    moved = { v for k,v in P.items() if v is not None }
    newpos = { k for k,v in P.items() if v is not None }
    if r+1 == 10:
        minx = min(x for (x,_) in E)
        maxx = max(x for (x,_) in E)
        miny = min(y for (_,y) in E)
        maxy = max(y for (_,y) in E)
        print((maxx-minx+1) * (maxy-miny+1)  - len(E))
    if len(newpos) == 0:
        print(f"no move after {r+1}")
        break
    E = (E - moved) | newpos
    dirs.rotate(-1)

C'est de l'openscad. Évoqué jour 18.

On voulait me faire faire un AST et évaluer le bazar. Bah je voulais pas.
Du coup j'ai fait une boucle infinie jusqu'à tout évaluer.
Ça m'a permis de faire la partie 1 en quelques minutes.

Bon je l'ai un peu payé sur la partie 2, j'ai dû bidouiller. La vizu m'a permis de voir qu'il n'y a pas de lien entre les deux branches partant de root. Donc pas de réutilisation d'un résultat dans les deux sous arbres. Donc l'inconnu n'est impliqué que dans une seule équation. J'ai donc hardcodé a valeur du sous arbre de droite dans la racine du sous arbre de gauche, là où se situe "humn".

Chaque partie s'évalue en 0.30s et 10Mo de RAM.

part 1

import sys

N = dict()  # numbers
E = dict()  # expressions
for l in sys.stdin.read().splitlines():
    k, v = l.split(":")
    v = v.strip()
    if v.isdigit():
        N[k]=int(v)
    else:
        w = v.split(" ")
        E[k]=w
O = {
    '*': lambda x,y: x*y,
    '+': lambda x,y: x+y,
    '-': lambda x,y: x-y,
    '/': lambda x,y: x/y,
}
while len(E)>0:
    D = dict()
    for k,v in E.items():
        (a,o,b) = v
        if a in N and b in N:
            N[k] = O[o](N[a],N[b])
        else:
            D[k] = v
    E = D
print(N["root"])

 part 2

import sys

N = dict()
E = list()
I = {"+":"-","-":"+","*":"/","/":"*"}
for l in sys.stdin.read().splitlines():
    k, v = l.split(":")
    v = v.strip()
    if v.isdigit():
        N[k]=int(v)
    else:
        (a,o,b) = v.split(" ")
        E.append((k,a,o,b))
        if o in {"+","*"}:
            E.append((a,k,I[o],b))
            E.append((b,k,I[o],a))
        else:
            E.append((a,k,I[o],b))
            E.append((b,a,o,k))
if len(N)<100:
    N["pppw"] = 150
else:
    N["qmfl"] = 54426117311903
    N["qdpj"] = 54426117311903
del N["humn"]
O = {
    '/': lambda x,y: x/y,
    '-': lambda x,y: x-y,
    '+': lambda x,y: x+y,
    '*': lambda x,y: x*y,
}
while len(E)>0:
    D = list()
    for (k,a,o,b) in E:
        if a in N and b in N:
            N[k] = O[o](N[a],N[b])
            if k == "humn":
                print(N[k])
                D = {}
                break
        else:
            D.append((k,a,o,b))
    E = D

Je dirai qu'il n'y a pas de règle car cela dépend de l'input.
Le code que j'ai pour la partie deux donne la bonne réponse en gardand le top 1000, ne marche pas à 700. Mais sur un autre input que j'ai testé, il a fallu monter à 2000.

J'utilise AWK pour construire un fichier openscad.
C'est un fichier texte qui décrit les formes à dessiner. exemple ici : translate([17.05,9.05,3.05]) cube([0.9,0.9,0.9]); Je laisse un petit espace entre chaque cube pour que ça ne fasse pas une grosse masse.
Habituellement, je m'en sers pour faire des modèles pour de l'impression 3D.
Je faisais un blocage avec le modeleur clicodrome, type Freecad. Openscad m'a sauvé :)

Relativement facile ce jour

La partie 1 étant un échauffement, parlons partie 2. Il faut "remplir" toutes les aspérités d'une boule constituée de petits cubes de 1x1x1 et dont la surface est irrégulière. Et compté les surfaces exposées au liquide.

vizu

La visualisation m'a bien aidé :

On peut voir les creux qui doivent se remplir.

code partie 2

J'ai rempli par itération (while True) en m'arrêtant quand plus rien de nouveau ne se remplissait.

Ensuite, pour chaque cube, on compte combien de face sont en contact avec de l'eau (6 voisins, 2 par dimension x, y, z).

import sys

S = set()  # cubes
for l in sys.stdin.read().splitlines():
    S.add(tuple(map(int,l.split(','))))

A = 23
L = set()  # water
for x in range(-2,A+1):
    for y in range(-2,A+1):
        L.add((x,y,-2))
more = True
while more:
    c = 0
    for x in range(-2,A+1):
        for y in range(-2,A+1):
            for z in range(-2,A+1):
                if (x,y,z) not in S and (x,y,z) not in L: # water can only expand in air
                    for (i,j,k) in [(0,0,1),(0,0,-1),(0,1,0),(0,-1,0),(1,0,0),(-1,0,0)]:
                        if (x+i,y+j,z+k) in L: # if neighbour is water
                            L.add((x,y,z)) # water expand
                            c += 1
    more = (c>0)

N = 0
for (x,y,z) in S:
    for (i,j,k) in [(0,0,1),(0,0,-1),(0,1,0),(0,-1,0),(1,0,0),(-1,0,0)]:
        if (x+i,y+j,z+k) in L:
            N += 1
print(N)

Exécution en 0.11s et 11MB RAM.

Un parcours de graph avec la complication que l'état du graph change pendant le parcours.

J'ai procédé en brute force et n'ai pas trouvé vraiment de moyen de couper des branches, si ce n'est marquer dès le départ les vannes à 0 comme étant déjà ouverte. Ça marchait bien jusqu'à 20 de profondeur mais passé ça, ça ramait trop (je timeout à 10 min). J'ai donc ajouté du cache et bim, 0.37s et 91MB de cache.

Cependant cette solution ne passe pas à l'échelle pour le parcours à 2 qui multiplie les branches.

J'ai ouïe dire des solutions où on pré-calcul des distances ou des scores mais je crois que je vais en rester là, j'ai déjà un retard de deux jours. J'ai atteint ma limite.

part 1

import sys
import re

pat = re.compile('Valve ([A-Z]{2}) has flow rate=([0-9]+); tunnels? leads? to valves? ([ ,A-Z]+)')
P = dict()
for i,l in enumerate(sys.stdin.read().splitlines()):
    g = pat.search(l)
    p = int(g[2])
    P[g[1]] = (i, p, g[3].split(", "))

STEPS = int(sys.argv[1])
ALLO = 0
for _,(i,p,_) in P.items():
    if p == 0:
        ALLO = ALLO | (1<<i) 

cache = {}
def step(pos="AA", left=STEPS, opens=ALLO):
    if left <= 0:
        return 0
    key = (pos, left, opens)
    r = cache.get(key, -1)
    if r >= 0:
        return r
    (i, p, nh) = P[pos]
    is_open = opens & (1 << i)
    a = 0
    if not is_open:  # also means 0 - worth opening valve ?
        left -= 1 # cost to open
        opens = opens | (1<<i)
        a = p*(left+30-STEPS) + max(step(n, left-1, opens) for n in nh)
    b = max(step(n, left-1, opens) for n in nh)
    r = max(a,b)
    cache[key] = r
    return r

print(step())

À priori on a le même algo. Peut être ma fonction d'union d'intervalles moins efficace. Faudrait que je profile. Mais là j'ai deux jours de retard alors je vais passer :)

parallélogrammes

Plus précisément ce sont des carrés tournés de 45°. Je sais pas si ça simplifie…

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.