steph1978 a écrit 3541 commentaires

C'est quoi "leurs média sociaux" ?

Autant j'ai un passeport à mon nom autant je n'ai aucun compte facebook/insta/snap/tiktok/x/bluesky/mastodon à mon nom.

Et 43% des statistiques sont complètement inventées.

Mon cerveau a lu à l'envers : un jeu de la vie de Conway en Lisp. Moui, pas ouf.

Mais non c'est un lisp en jeu de la vie de Conway.

Je savais que le jeu de la vie était Timuring complete. Donc pourquoi pas un interpréteur Lisp.

Ce qui est balaise, c'est de trouver la bonne configuration de départ.

À noter que cell·eux qui prennent leur retraite le plus tard sont les politicien·nes et les hommes/femmes d'affaire. Car 1/ leur métier n'est pas pénible 2/ leur métier leur confère un statut social 3/ leur métier leur payent la plupart de leurs frais qu'ils·elles devraient payer de leur poche une fois à la retraite 4/ ça leur permet de prétendre montrer l'exemple, valeur travail, blabla.

451 microsecondes pour les deux parties en version compilée.

Bon, je sais pas ce que j'ai merdé mais c'est en effet trivial, en 10 lignes:

from functools import cache

G = dict()
for line in open(0).read().strip().split('\n'):
    p, c = line.split(":")
    G[p] = c.strip().split()
G["out"] = []

@cache
def count_paths(node, target):
    return 1 if node == target else sum(count_paths(c, target) for c in G[node])

print(count_paths("you","out"), count_paths("svr","fft")* count_paths("fft","dac")* count_paths("dac","out"))

En 13MB et 0.05s

Bonne tranche de rigolade aujourd'hui. On est sur du parcours de graphes.

Première partie implémentée en deux minutes, sans erreurs, directement sur l'input et hop une étoile. On commence à être rôdé.

Partie deux, sur ce bon élan, j'adapte ma solution pour partir d'un autre nœud et ne compter que les chemins qui contiennent les nœuds imposés. Trivial. Je vais faire la journée 11 en moins de dix minutes.

Sauf que le script ne me rend pas la main. Et là, je me dis que je me suis fait avoir.
Je trace le graphe avec Graphviz et je vois l'étendue des dégâts. Le nœud de départ de la première partie est tout près du nœud de sortie. Mais pour la seconde partie, il est très très loin. Donc la combinatoire explose.

Je tente une mise en cache, mais ça ne semble rien améliorer.

J'ai donc exploité la structure du graphe proposé qui 1/ est acyclique, 2/ présente des "couches". J'ai donc calculé un graph plus simple avec seulement les nœuds qui matérialisent les couches et le cout pour passer de l'un à l'autre. Puis lancé le calcul du nombre de chemins sur ce graphe plus simple (18 nœuds versus 644).

Forcément, ça m'a pris une bonne paire d'heures.

Je ne sais pas s'il y avait plus malin à faire ; je lirai avec plaisir d'autres solutions.

Je me doutais un peu que l'input avait un pattern particulier qui devrait permettre d'être plus efficace qu'avec un input plus aléatoire. Qqun a senti la même chose et l'a fait.

Voici 

Partie 1 en 2 lignes

from itertools import product as prod
P = [tuple(map(int,line.split(","))) for line in open(0).read().strip().split('\n')]
print(max((1+abs(a-c))*(1+abs(b-d)) for (a,b),(c,d) in prod(P,P)))

Au moins deux fois trop de calculs, mais l'optimisation ne valait pas la peine, ça reste très rapide.

Partie 1 et 2

from shapely.geometry.polygon import Polygon
from shapely.geometry import Point
from itertools import product as prod
P = [tuple(map(int,line.split(","))) for line in open(0).read().strip().split('\n')]
shape = Polygon(P)
ans1 = ans2 = 0
for (a,b),(c,d) in prod(P,P):
    if (a,b)>=(c,d):  # avoid comapring a pair twice
        continue
    area = (1+abs(a-c))*(1+abs(b-d))
    ans1 = max(ans1, area)
    if area <= ans2:  # avoid more computation if not a new max
        continue
    rect = Polygon([(a,b),(a,d),(c,d),(c,b)])
    if shape.contains(rect):
        ans2 = area
print(ans1, ans2)

Pas trop d'intérêt à compacter le code puisque je n'ai pas implémenté le gros morceau qu'est le contains.

Partie 1 triviale.

Partie 2, j'ai triché en ayant recours à la bibliothèque shapely qui permet de faire, entre autres, des opérations sur les polygones.

Le code dans le commentaire ci-dessous que vous pouvez plier ([-]) pour éviter le spoil.

ça fait des jolies illustrations

Beaucoup moins académique que Guillaume, très itératif, les deux parties en 22 lignes:

boxes = [tuple(map(int, line.split(","))) for line in open(0).read().strip().split('\n')]
clusters = dict()
for c, (_,(i,j)) in enumerate(
    sorted(((x-l)**2+(y-m)**2+(z-n)**2, (i,i+1+j))
        for i, (x,y,z) in enumerate(boxes)
            for j, (l,m,n) in enumerate(boxes[i+1:]))):
    icl = [[k for (k,v) in clusters.items() if i in v] or ["ALONE"]][0][0]
    jcl = [[k for (k,v) in clusters.items() if j in v] or ["ALONE"]][0][0]
    match (icl == "ALONE", jcl == "ALONE", icl == jcl):
        case (False, False, False): # both belongs to different clusters, merge clusters
            clusters[f'{i}_{j}'] = clusters[icl] | clusters[jcl]
            del clusters[icl]
            del clusters[jcl]
        case (False, True, _):
            clusters[icl].add(j)
        case (True, False, _):
            clusters[jcl].add(i)
        case (True, True, _): # both out of clusters, create a new cluster with them
            clusters[f'{i}_{j}'] = {i, j}
        # else (False, False, True), i and j are in the same cluster
    if c == 1000:
        s = sorted(map(len, clusters.values()))
        print(s[-1]*s[-2]*s[-3])
    if c > 1000 and len(clusters) == 1:
        print(boxes[i][0]*boxes[j][0]) # 5267 conns
        break

J'étais ravi d'ouvrir un problème en 3D, ça fait des jolies illustrations.

J'ai trouvé rapidement l'algo mais j'ai perdu énormément de temps sur:

1/ une mauvaise lecture du calcul qu'il fallait produire pour la première partie ; my bad

2/ le fait qu'il fallait compter comme un connexion le fait de ne rien faire :/
à force de tâtonner, j'ai finit par incrémenter dans tous les cas pour voir et je suis tombé sur la solution ; pas agréable

La deuxième partie après cela était triviale.

Ca consiste à compter le nombre de chemins dans un graphe orienté acyclique

Exactement

et ça se fait en temps linéaire.

Je n'ai pas l'impression que networkx propose cet algorithme

Il propose all_simple_path(source, destination) et je voulais juste les compter mais du coup, ça explose en combinatoire.

ça se fait aussi … par programmation dynamique :)

Je suis tristement pas très familier de cette technique mais de ma compréhension, un algo récursif avec mise en cache, ça s'en rapproche grandement.

Première partie très simple, pour chaque line, à chaque fois qu'on split, incrémenter de 1.

Seconde partie, je n'ai pas vu la technique de programmation dynamique que vous évoqués.

J'ai vu un parcours de graphe.

Par flemme de l'implémenter moi même, j'ai voulu le faire avec une lib. Grosse erreur, elle a tournée pendant des plombes et de retour de promenade, je l'ai killé (heureusement que c'est l'hiver et qu'on chauffe).

J'ai finalement implémenté moi même et ça s'est bien passé. Pour éviter l'explosion combinatoire, j'ai utilisé un cache.

Et comme le jour 6 ne m'a pas plu, je me suis vengé avec cette version de la partie 2 du jour 5 en une ligne de 199 caractères :

print(__import__("functools").reduce(lambda a,r:(a[0]+r[1]-max(r[0]-1,a[1]),r[1])if r[1]>a[1]else a,sorted(tuple(map(int,i.split("-")))for i in open(0).read().split("\n\n")[0].split("\n")),(0,0))[0])

🏌️

Je ne suis pas très fan du problème de ce jour. Je préfère les problèmes avec des astuces algorithmiques (enfin, il y en a peut-être mais je ne les ai pas vu).

Tout pareil.

Je mets le code de la partie 1, c'est le moins laid des deux:

from operator import mul, add
from functools import reduce
*N, O = open(0).read().strip().split('\n')
N = [list(map(int,l.split())) for l in N]
print(sum(reduce(add if o=='+' else mul, [N[j][i] for j in range(len(N))]) for i,o in enumerate(O.split())))

Et en 4 lignes en utilisant reduce:

I,J = open(0).read().strip().split("\n\n")
t, *R = sorted(tuple(map(int,i.split("-"))) for i in I.split("\n"))
print(sum(any(a <= int(i) <= b for (a,b) in [t]+R) for i in J.split("\n")))
print(__import__("functools").reduce(lambda a, r: a if r[1] <= a[1] else (a[0] + (r[1]-r[0]+1 if r[0]>a[1] else r[1]-a[1]), r[1]), R, (t[1]-t[0]+1,t[1]))[0])

Pour comprendre, l'accumulateur est, à tout moment de la réduction, un tuple[la somme accumulé, le max atteint].

Tu ne crois pas si bien dire.

Les deux parties en 11 linges :

I, J = open(0).read().strip().split("\n\n")
t, *R = sorted(tuple(map(int,i.split("-"))) for i in I.split("\n"))
print(sum(any(a <= int(i) <= b for (a,b) in [t]+R) for i in J.split("\n")))
ans = 0
for r in R:
    if t[0] <= r[0] <= t[1]:
        t = (t[0], max(t[1],r[1]))
    else:
        ans += t[1]-t[0]+1
        t = r
print(ans + t[1]-t[0]+1)

Partie 1:

I = open(0).read().strip().split("\n\n")
R = [i.split("-") for i in I[0].split("\n")]
R = [(int(a),int(b)) for (a,b) in R]
I = [int(i) for i in I[1].split("\n")]
print(sum(any(a <= i <= b for (a,b) in R) for i in I))

Partie 2

I = open(0).read().strip().split("\n\n")
R = [i.split("-") for i in I[0].split("\n")]
R = sorted((int(a),int(b)) for (a,b) in R)
ans = 0
t = R[0]  # tail
for r in R[1:]:
    (a,b) = t
    (c,d) = r
    if a <= c <= b: # if can merge
        t = (a, max(b,d))  # extend
    else:  # count range
        ans += b-a+1
        t = r
(a,b) = t
ans += b-a+1
print(ans)

Pas sur de voir une différence de difficulté entre ces cinq premiers jours.

Aujourd'hui, première partie en oneshot. Par contre j'ai trop ramé pour faire l'algo de fusion des intervalles alors que c'est tout bête au final 😕

Je mets le code dans le commentaire en dessous. Vous pouvez le fermer en appuyant sur [-] pour éviter le spoil.

Je te confirme que c'est plus rapide. C'était ma première version, celle avec laquelle j'ai validé les étoiles.
Mais ça ne tient pas en 6 lignes 😄

Très bon jour.

Première partie en one shot, sans passer par l'exemple ; deuxième partie en 1 essai ; en moins de 10 minutes.

Je suis passé par des sets, très facile à manipuler en python et plutôt efficaces en perf.

Voici le code, un peu refactoré pour tenir en 6 lignes:

rolls0 = rolls = {(i,j) for i,line in enumerate(open(0)) for j,c in enumerate(line) if c == '@'}
l = 999999999
while len(rolls)<l:
    l = len(rolls)
    rolls = {(x,y) for (x,y) in rolls 
        if 3<sum(((x+dx,y+dy) in rolls)
            for (dx,dy) in [(0,-1),(1,0),(0,1),(-1,0),(1,1),(-1,-1),(1,-1),(-1,1)])}
    print(len(rolls0)-len(rolls))

Cela prend 16MB de RAM et 0.7s de CPU.

C'était un produit déjà compliqué à l'époque. La migration v2 vers v3 avait été très pénible. Et là on peut constater qu'ils prennent un virage très entreprise donc plus vraiment intéressant pour du selfhosting.

Va falloir que je me trouve un autre object storage …