steph1978 a écrit 3405 commentaires

Maintenant, si TikTok c'est de la merde comme certains le disent, pourquoi y a-t-il autant de monde qui y va ?

Pourquoi le macdo ? Pourquoi le quinzième xmen ? Pourquoi TPMP ? Pourquoi la kronenbourg ? Pourquoi la voiture ? Pourquoi la cigarette ? Pourquoi la poubelle ordures ménagères ? Pourquoi windows ? Pourquoi …

Réponse: parce que la médiocrité ne tue pas - enfin pas sur le coup.

Arf, oui, bien vu : "ceux qui étaient contre".

Ceux qui vont me faire défendre le nucléaire ne sont pas les pros (la plupart sont ridicules à oublier les inconvénients, oui) mais les anti (encore plus caricaturaux que les pros, et généralement moins tu as d'arguments plus tu es caricatural).

Ah, ça m'a fait la même chose pour le mariage pour tous. J'étais hyper neutre au début, ni pour ni contre, car pas concerné de près ou de loin. Mais quand j'ai vu ceux qui étaient pour et leurs arguments et leur haine. Je me suis dis: ok, je suis pour en fait.

Du moment que tu peaufines l'art ascii, tout est possible :)

Ma fille a eu celui-ci pour Noël.

L'idée est venu parce qu'elle jouait à un jeu très ressemblant à celui-là dans GCompris (ancre foireux, CTRL+F "Embouteillage").

J'ai adoré ce moment où elle m'a dit "tu fais pas!", traduction: "laisse moi faire!" parce qu'elle avait pigé le truc.

Ça me donne envie de contribuer des exercices gcp en s'inspirant de smart games.

Texte également rédigé à l'aide de ChatGPT (et corrigé par mes soins)

Oh mazette, après l'écriture inclusive, il va falloir aussi dire ce qui est écrit par un·e intelligen·ce humain·e et ce qui est écrit par un·e intelligen·ce artificiel·le. Help!

Ce commentaire a été écrit par mes gros doigts.

Et une petite vidéo démo en asciinema dans le README, ça claquerait !

Pour la partie deux, aucun intérêt à bufferiser avant d'afficher :

awk, 14 loc

function inc() {
    i = (c%40)
    r = r ((i==x||i==x+1||i==x+2) ? "█" : " ")
    if (i == 39) {
        print r
        r = ""
    }
    c++
}
{ inc() }
$1 == "addx" {
    inc()
    x+=$2
}

En image

J'arrive pas à comprendre en partant de l'input et de règles pourquoi ça se propage pas uniformément mais privilégie la direction en bas à droite.

après la version ascii, la version png, voici la version 3D. ma préférée.

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