steph1978 a écrit 3342 commentaires

Le problème étant très simple aujourd'hui, je me suis permis une résolution en C pour tenter de faire de la perf.

Mais j'arrive péniblement à 2ms.

En même temps pour seulement lire chaque caractère de l'input (inlined), ça prend déjà 520µs ; du coup, je vois pas trop quoi améliorer …

La bonne pratique est de toujours créer un virtualenv pour un projet.
On utilise pas le profile user et surtout pas le profile du système.

En tenant compte de la forme du graphe, j'utilise uniquement la théorie des sets et je descends à 17ms. Et même à 4ms si je coupe à la première occurrence.

import sys
from collections import defaultdict as DD
from itertools import combinations as comb

D = DD(set)
for i in sys.stdin.read().strip().split('\n'):
    a, b = i.split("-")
    D[a].add(b)
    D[b].add(a)

for k, v in D.items():
    for i in v:
        w = v - {i}
        if all(b in D[a] for a,b in comb(w,2)):
            print(",".join(sorted({k}|w)))
            #sys.exit(0)

Je sais il est tard mais bon je pouvais pas rester avec un prod aussi lent.

Je parle pas de la partie 1, plutôt triviale.

Pour la partie 2, j'ai voulu ne pas succomber à la tentation d'utiliser d'une bibliothèque logicielle de graphes, genre Networkx.

J'ai implémenté un truc très peu optimal, rendu possible que par l'ajout d'un cache pour ne par ré-explorer un sous graphe en arrivant par un autre de ses noeuds.

J'ai perdu beaucoup trop de temps à chercher un bug qui n'existait pas car j'avais juste pas fait attention qu'il fallait séparer les noms des neouds par des virgules dans la réponse :/

Au final, 36s en python ; pas vraiment d'amélioration en compilant - 30s ; parce que ce n'est pas très calculatoire, juste très grand à explorer.

En corrigeant une petite bourde et en compilant le code, je descends à 33ms pour les deux parties.
Mais je suis bien tenté d'essayer d'implémenter ton algo …

J étais un peu déçu car je m attendais à une deuxième bien plus complexe

Je me suis fait la même réflexion : est-ce qu'il n'espérait pas que la partie 2 ne soit pas brute forçable mais en fait avec une pc un peut violent et en compilant le code, ça passe.

Cela faisait longtemps que la solution ne tenait plus en quelques lignes, et que la partie 2 ne pétait pas complètement la partie 1.

Aujourd'hui, avec du récursif et du cache, ça tient en 4 lignes.

import sys
from functools import cache
f = cache(lambda s: 1 if len(s)==0 else sum(f(s[len(r):]) for r in R if s.find(r) == 0))
R, I = sys.stdin.read().strip().split("\n\n")
R = R.split(", ")
print(sum(f(i)>0 for i in I.split("\n")))
print(sum(f(i) for i in I.split("\n")))

Il n'y a qu'une seule ligne intéressante : la fonction récursive.
En gros : pour une chaîne, si on trouve un préfixe valide, on refait un appel avec la chaîne amputée du préfixe. Si on arrive à une chaîne vide, on a pu faire le pattern demandé, sinon, non (la somme d'un générateur vide vaut 0).

Pour s'en convaincre, il faut regarder les différents cas.

• si la chaîne est vide, elle peut trivialement être réalisée avec n’importe quelle règle (retourne Vrai ou 1)
• si la chaîne ne commence par aucune des règles, elle ne peut pas être réalisé (retour Faux ou 0)
• si plusieurs règles constituent un préfixe de la chaîne, il faut examiner toutes les pistes pour construire la sous-chaîne et sommer ces possibilités.

La combinatoire explosant très vite, on met les résultats en cache pour pouvoir les réutiliser. Plus la chaîne est petite, plus le cache fera effet, c'est à dire en bout de chaîne ; dans l'exemple "gbr" est réalisé de trois façons différente ("g-b-r","gb-r", "g-br") ; on met en cache "bgbr" -> 3 et on a plus à le recalculer.

Pour "rrbgbr", on sait qu'on peut faire "rrb" de deux façons ("r-rb" ou "r-r-b"), on a donc 3+3=6 façons de faire la chaîne complete. Plus on avance dans l'exercice, plus on a des bouts réutilisables.

Dans mon cas, il y a 841E12 branches valides ce qui serait impossible à explorer ; mais avec le cache, seulement 53E3 appels à f et 18E3 entrées dans le cache.

ça mérite un journal

Un wiki gitlab est un repo git.

git clone git@mongitlab.net:monorg/monprojet.wiki.git

Even after Automattic acquired it, the site continued to lose money at a rate of $30 million each year

3M de blog, 30M$ de perte. 10$/blog/an ; ça me parait vraiment beaucoup.

Surtout que j'imagine qu'ils mettent de la pub et que donc ça peut rapporter.

Et pour se construire un environnement de dev par projet, je conseille asdf, quelque soit le langage. À combiner avec un virtualenv en ce qui concerne python.

Si c'est pour exécuter, il est tout à fait possible (contrairement aux FUD "inexactitudes" régulièrement diffusées par les fanboys utilisateurs d'autres langages) de construire un exécutable python.

Pour ma part, j'utilise PyInstaller. Avec un exemple ici qui construit un exécutable autonome pour visidata.

Si c'est pour intégrer dans un autre projet alors il faut packager pour pypi.org, de manière à ce que les utilisateurs puissent faire un pip install ma_belle_bibliotheque_logicielle. Avec un exemple ici qui est une ligne de commande pour lufi. En particulier regarder le contenu des fichier "setup.py" et "publish.sh".

Apple et Meta ne font pas de cloud publique mais tu peux ajouter alibaba, oracle, ibm, lidl.

Mais j'adore l'image des likes et des shorts.

c'est qu'il n'y a personne en ligne ?

Oui, en BFS, c'est pas rapide : 7s pour les deux parties.

Un classic parcours de graphe, vive didi dijkstra.

Cyber : Le terme réfère à une abstraction englobante et multidisciplinaire des concepts et usages relatifs aux technologies informatiques

Donc oui on peut employer ce préfixe.

Ce qui me gène dans "cyber attaque" ce n'est pas uniquement la sémantique, mais aussi que ce terme est monté en épingle par les medias (les fameux chinois du FBI) et réutilisé par les politiques pour dire "vous voyer tous ces terroristes en puissance sur internet" et justifier la surveillance générale et par défaut.

Donc le terme "vol de données" me paraît plus mesuré.

J'ai plutôt l'impression qu'on atteint les limites de cette technologie et que la suite n'est pas près de venir. Analyse parfaitement subjective entièrement basée sur le doigt mouillé™

On peut jouer sur les mots mais si le gars avait les accès, qu'il a dumpé la DB et est parti avec, je ne qualifierai pas ça d'une cyber attaque. C'est une fuite de données ; cela doit inquiéter la sécurité qui doit prendre des mesures pour que cela ne puisse pas se reproduire mais ce n'est pas une "attaque".

Si on va par là, si ton gamin pique un billet dans ton porte feuille, tu subis quoi ? un braquage ?

J'ai fait la première partie en brute force mais impossible pour la partie 2 alors j'ai aussi pivoté vers un solver (sympy).

En poussant fort en python, je suis descendu à

• construction des zones 11 ms
• calcul des périmètres +1 ms
• calcul des coins +5 ms
• total 17 ms

Mais en utilisant des set. L'idée d'utiliser le bit de poids fort est très habile.

Cette réaction exagérée […] est tout à fait irrationnelle.

Si tu confonds sarcasme et irrationalité, tu dois avoir beaucoup de faux positifs. Pas vraiment un super pouvoir alors…

En résumé, ils ont pris la grosse tête.

Moi j'ai fait le bourrin, comme tous les jours depuis de début de ce calendrier, je crois :)

Pas contre comme c'est hyper calculatoire, il y a de gros gain en compilant le code, jit ou aot.

• python (interpreter) : 2.525_s
• pypy (jit): 175_ms (14x)
• codon (aot): 29_ms (87x)

On est loin des µs quand même :/

J'ai eu à faire ça.

python3 -m pip install asciidoc  # mieux dans un virtualenv
asciidoc -b docbook README.adoc  # crée le fichier README.xml
pandoc -f docbook -t markdown_strict README.xml >> README.md

Dis nous si tu aboutis à quelque chose.