steph1978 a écrit 3559 commentaires

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 …

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 :)