steph1978 a écrit 3579 commentaires

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 …

c'est moins rapide […] que celle en 12 passes.

C'est normal, parce que l'étape retirer c2 de cells est coûteuse car il faut créer une nouvelle structure de données à chaque fois.

Alors qu'une boucle (ou de la récursivité) sur une même structure de données, ça ne coûte pas très cher.

Voici le code, 11 lignes, refactoré pour traiter les deux parties en une fois:

def findmax(bank,n):
    if n>=len(bank): return bank
    if n==0: return ""
    m = max(bank[:len(bank)-n+1])
    i = bank.find(m)
    return m + findmax(bank[i+1:], n-1)
ans1 = ans2 = 0
for bank in open(0).read().strip().split('\n'):
    ans1 += int(findmax(bank,2))
    ans2 += int(findmax(bank,12))
print(ans1, ans2)

Difficile de départager ces trois premiers jours en terme de difficulté. On est peut être sur un "hockey stick" et on attend le point d'inflexion, peut être demain.

Ce jour, première partie en one shot, sans passer par l’exemple 😎. Pour la deuxième partie, j'ai un peu ratatouillé sur les conditions d'arrêt de ma fonction récursive 😩 et perdu un peu de temps.

Pour les curieux (ou masochiste), je mets le code dans le commentaire en dessous.
Vous pouvez le fermer en appuyant sur [-] pour éviter le spoil.

Ça, ça veut dire que le navigateur ne fera plus la transformation XSTL lui-même.
Il y a eu un monde dans lequel un producteur de contenus envoyait son contenu sous format XML, peu importe lequel, et une feuille de style XSLT et le navigateur faisait la transformation - et le rendu si possible, c'est-à-dire si la transformation produisait du XHTML.

Mais ça ne veut pas dire que XSLT est déprécié en tant que tel. Tu peux toujours le faire dans une extension pour transformer sur XHTML en un autre XHTML. C'est l'idée ici.

HTML n'ayant pas fondamentalement changé ces dernières années, il y a peu de raison que XSLT ne fonctionne plus.

Ce qui a probablement beaucoup changé, c'est que le DOM est produit par du JavaScript côté client.

Mais si tu es dans un navigateur, il suffit d'attendre qu'il ait exécuté le JS pour travailler sur le DOM résultant.

En fait, le gros intérêt d'utiliser XSLT dans le moteur, c'est de pouvoir utiliser des XPath dans les fichiers de configuration.

Je mets le code, même si je ne lui trouve rien d'intéressant:

def is_invalid_p1(n):
    s = str(n)
    m = len(s) // 2
    return s[:m] == s[m:]

def chunk_str(s, l):
    for i in range(0, len(s), l):
        yield s[0+i:l+i]

def is_invalid_p2(n):
    s = str(n)
    l = len(s)
    for m in range(1,1+(l//2)):
        if (l%m) == 0:  # if str can be chunked equally
            a = chunk_str(s,m)
            b = chunk_str(s,m)
            next(b)
            if all(u==v for (u,v) in zip(a,b)):
                return True
    return False

ans1 = ans2 = 0
for line in open(0).read().split(','):
    f, t = line.split("-")
    f = int(f)
    t = int(t)
    for i in range(f, t+1):
        if is_invalid_p1(i):
            ans1 += i
        if is_invalid_p2(i):
            ans2 += i
print(ans1, ans2)

(C'est dans ces moments que j'aimerai que linuxfr supporte le details/summary).

Jour que j'ai trouvé plus facile que le précédent, mais plus laborieux.

J'ai blêmi en voyant une énoncée avec des "ranges" car j'ai un très mauvais souvenir d'un problème d'intersection de range ; mais il n'en est rien ici.

J'ai aussi pensé qu'on aurait un problème de passage à l'échelle pour la partie 2 ; mais il n'en est rien non plus.

Patience, ce sera pour la prochaine :)

Je m'étais fait un petit dessin ; ça m'a aidé.
À l'inverse, retourner le cadran pour se retrouver systématiquement sur le cas "sens des aiguilles d'une montre" (="R") m'a paru une gymnastique plus compliquée.

Exact mais je ne visite pas toujours en mode connecté. En particulier au boulot. Alors que j'ai toujours ublock 😉

o/

Premier jour facile. J'ai même pas pensé à brut-forcer la partie deux. Si j'avais galéré sur un cas limite, je l'aurai fait. Mais là c'est passé du premier coup.

En réorganisant un peu le code, la solution aux deux parties en 9 lignes :

ans1 = ans2 = 0
pos = new_pos = 50
for line in open(0):
    t,q = divmod(int(line[1:]), 100)
    new_pos += q if line[0] == "R" else -q
    ans2 += t + ((pos>0 and new_pos<=0) or new_pos>=100)
    pos = new_pos = new_pos % 100
    ans1 += (pos == 0)
print(ans1, ans2)

Le contenu qui reste en haut sur la page d'accueil. Pour moi, ça prend de la place et je l'ai la plupart du temps déjà lu. Je ne sais pas comment ça s'appelle mais dans la CSS, c'est "phare".

Pour ma part, j'utilise ublock0 pour supprimer le "phare" et les avatars.