Guillaume.B a écrit 66 commentaires

La partie 1 est facile.
La partie 2 n'est pas compliqué algorithmiquement mais j'ai un galéré à bien l'implémenter.
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).

Les deux parties se font en temps linéaire avec un espace proportionnel au nombre de lignes (en plus de l'input).
25 microsecondes pour les deux parties.

J'envoie que la partie 1. J'enverrai la partie 2 quand j'aurais un peu nettoyé le code.

fn part1(lines: &[&[u8]]) -> u64 {
    let mut numbers: Vec<_> = lines[..lines.len()-1]
        .iter()
        .map(|line| line.iter_unsigned::<u64>())
        .collect();
    let operators = lines.last().unwrap().iter().filter(|&&c| c != b' ');

    operators.map(|&op|
        if op == b'+' {
            numbers.iter_mut().map(|it| it.next().unwrap()).sum::<u64>()
        } else {
            numbers.iter_mut().map(|it| it.next().unwrap()).product()   
        }
    ).sum()
}

Pour la première partie 1, je trie les intervalles par ordre de début et je fais de la recherche dichotomique pour chaque ingrédient.

Pour la partie 2, j'avais déjà une fonction sous le coude que j'avais implémenté pour un aoc d'une année précédente donc ça a été rapide.

20 microsecondes pour les deux parties

A vrai dire, je ne construis pas vraiment le graphe, je déduis les voisins à partir de la grille.
Par contre, j'ai besoin de stocker un tableau des degrés.
Je me demande si je ne peux pas réutiliser le tableau de la grille et le modifier.
Mais je ne suis pas sûr que je gagne vraiment en temps de calcul.

Les sommets stockés dans la pile ne le sont qu'une seule fois car ils sont insérés seulement quand leur degré vaut exactement 3 et par la suite le degré sera inférieur à 3.

Sinon, pour les curieux, j'ai appris aujourd'hui que ce problème s'appelle k-core.
Plus précisément, le k-core d'un graphe est le plus grand sous-graphe H où tous les sommets ont au moins k sommets voisins à l'intérieur H.
Donc on cherche ici à trouver le nombre de sommets n'appartenant pas au 4-core.

La partie 1 est facile.
La partie 2 est un problème sur les graphes et peut être obtenu en temps linéaire de la manière suivante.

On maintient un tableau deg qui pour chaque sommet associe le nombre de @ adjacents.
On maintient aussi une pile des sommets à traiter.
Pour chaque sommet v à traiter dans pile, et pour chaque voisin u de v, on décrémente deg[u] et si deg[u] == 3, on ajoute u à la pile.

En pseudo code ça donne ça

compteur = 0
pile = []
Calculer le tableau deg

pour chaque sommet v tel que grid[v] == @ et deg[v] <= 3
   pile.push(v)

tant que pile non vide
   v = pile.pop()
   compteur += 1
   pour chaque voisin u de v tel que grid[u] == @
      deg[u] -= 1
      si deg[u] == 3
         pile.push(u)
renvoyer compteur

160 microsecondes pour les deux parties

Non, si tu utilises une pile, ça se fait en temps constant (quand je dis retirer c2, je voulais dire juste retirer l'élément en haut de la pile).

Ton algorithme ressemble beaucoup à l'algorithme en temps linéaire O(n) que j'ai obtenu.
Je fais plus ou moins la même chose mais où cells est une pile.
Je parcours ma liste de chiffres et pour chaque chiffre c, je retire du haut de ma pile tous les chiffres plus petits que c, si celle ci reste suffisamment grande pour qu'il reste 12 chiffres à la fin.
Ensuite je rajoute c à ma pile seulement si celle ci a moins de 12 éléments.
C'est bien en temps linéaire car chaque élément retiré de la pile ne le sera qu'une seule fois.
En pseudo-code ça donne

cells = []
pour chaque (i, c) de enumerate(ligne)
   reste = taille(ligne) - i - 1
   tant que cells n'est pas vide
        c2 = dernier élément de cells
        si c2 < c et taille(cells) + reste >= 12
           retirer c2 de cells
        sinon
           break
   si taille(cells) < 12
       ajouter c à la fin de cells
renvoyer cells

mais comme je disais, c'est moins rapide (du moins, mon implémentation) que celle en 12 passes.

J'ai écrit un algorithme similaire aux deux plus haut (en version itérative).

J'ai aussi obtenu un algorithme linéaire, en une seule passe sur la chaîne, mais celui s'avère plus lent sur le jeu de données que l'algorithme initial.

J'aurais aimé trouver un algorithme plus efficace mais tant pis.

Pour le problème du jour, ma première approche a consisté à énumérer chaque id de chaque intervalle et tester s'il est invalide ou non.
Ca prend 100ms, c'est raisonnable mais j'ai cherché une solution plus efficace.

Je fais 2 suppositions sur l'input:

• Tous les intervalles sont deux à deux disjoints
• Chaque nombre contient au plus 10 chiffres

Pour la partie 1:
Pour l'exemple, on considère un intervalle [start, end] où start et end sont tous les deux des entiers à 6 chiffres.
Alors, les ids invalides pour cet intervalle sont les entiers multiples de 1001 dans cet intervalle.
Il faut donc faire la somme d'une suite arithmétique et ça peut se faire de manière efficace (en temps constant) sans avoir à itérer sur les valeurs de l'intervalle.

Pour la partie 2, c'est un peu plus compliqué.
Gardons le même exemple. La somme des ids invalides est la somme des multiples de 1001 (comme dans la partie 1) et des multiples de 10101 (si on coupe l'entier en 3).
Le problème, c'est qu'on a pu compter des ids en double (ceux à la fois multiples de 1001 et de 10101, ce qui correspond aux multiples de 111111).
Il faut donc retirer la somme de ces ids du total.
Les entiers posant ce problème sont ceux à 6 chiffres et ceux à 10 chiffres.

Je ne vais pas poster mon code car il est peu long et très moche.

Ca prend moins d'une microseconde soit 100_000 fois plus rapide que la première approche.

Tu mets où ton critère entre efficacité du code et efficacité du développement? Est-ce que > tant que tu es en O(n) tu es bon?

Ca dépend des années.
La première fois que j'ai fait l'aoc, je cherchais la lisibilité et réutilisabilité du code.
Mais cette année comme l'année dernière, je vise la vitesse d'exécution.

Alors, qui participe cette année?

Le jour 1 est facile comme chaque année mais la partie 2 demande un peu de réflexion si on cherche mieux que la solution naïve.

Ha oui, désolé.

Si j'en crois les années précédentes, le code pour accéder au leaderboard de linuxfr est
1844559-f65dbf07.

Merci d'avoir signalé l'erreur. J'ai l'impression que je ne peux plus modifier le texte maintenant (je ne connais pas très bien linuxfr).

Je suis assez d'accord avec toi.

Le problème du jour 17 n'est pas vraiment l'assembleur mais plutôt qu'une grosse partie du calcul peut être fait à l'avance (à la compilation).
Mais, la majorité des problèmes ne sont pas ainsi, même si les auteurs des solutions ont tendance à faire de grosses suppositions sur les inputs.

Je pense que ça doit beaucoup dépendre de la manière de mesurer le temps.
520 microsecondes juste pour lire l'input me parait excessivement lent.

Personnellement, je fais 1000 itérations de mon code et je prend le temps médian. Je ne prend pas en compte le temps de chargement du programme, ni le temps pour lire le fichier en mémoire (mais je prend en temps le compte pour faire le parsing).
J'utilise la fonction Instant::now et la méthode elapsed().
https://doc.rust-lang.org/std/time/struct.Instant.html

Mes temps n'ont rien de fantaisistes. Sur un salon Discord consacré à Rust, certains ont des solutions bien plus rapides que les miennes.

Sinon, pour ceux que ça intéresse, voici le dépôt des mes solutions.
https://github.com/gbagan/advent-of-code-rust

Oui, je suis assez d'accord avec toi au niveau de la difficulté de cette année.

Pour le jour 25, j'ai trouvé une petite astuce qui consiste à encoder la grille sur un entier de 32 bits.

Par exemple, pour la grille

#####
##.##
.#.##
...##
...#.
.....
.....

je vais encoder le nombre de # par colonnes par des séquences de 4 bits.
sous forme de liste, ça donne [1, 2, 0, 4, 3] (je retire 1 à chaque colonne car il y a forcément un # par colonne).
et sous forme d'entiers 0001_0010_0000_0100_0011

De même, pour une grille partant du bas.

.....
...#.
...#.
..##.
.###.
.###.
#####

J'encode par la liste [2, 4, 5, 7, 2] (j'ajoute 2 à chaque colonne pour la somme avec le complément fasse 7).
ce qui donne en binaire 0010_0100_0101_0111_0010

Du coup, si il y a un overlap entre 2 colonnes, la somme des 4 bits les représentant va dépasser 7 et le bit de poids fort va être 1.

Donc pour tester si deux grilles g1 et g2 matchent ensemble, il faut que
(x + y) & MASK == 0 où x est l'encodage de g1, y est l'encodage de g2 et MASK=0b1000_1000_1000_1000_1000.

9 microsecondes pour ce problème et 4.6 millisecondes pour le temps cumulés de tous les problèmes de cette année.

Pour la partie 2, j'ai utilisé 2 propriétés de l'input
- les labels sont composés de deux lettres entre 'a' et 'z', ça me permet de parser plus rapidement et de faire quelques optimisations. Notamment pouvoir me passer de table de hash.
- et la plus importante: chaque sommet a exactement 13 voisins et on cherche une clique de taille 13.

Grace à la seconde propriété, pour trouver une clique maximum, je dois trouver un sommet v de voisinage N(v) tels que tous les sommets u de N(v) à l'exception d'un, qu'on appellera z, ont exactement 11 voisins en commun avec N(v). La clique sera donc {v} U N(v) \ {z}.

45 microsecondes pour les deux parties. Je pense pouvoir faire mieux en utilisant une représentation du voisinage par bitset. J'y travaille.

Ce jour-ci était globalement assez facile. Il suffisait de suivre ce qu'on nous disait.
Par contre, je n'ai pas vraiment trouvé de manière d'optimiser la solution de manière globale.

J'ai surtout fait des micro-optimisations comme:
- utiliser un tableau de taille 19⁴ plutôt qu'une table de hash pour représenter les prix par quadruplet ainsi que les quadruplets déjà vu;
- utiliser les bons types d'entiers: u32 pour stocker les secrets, u16 pour stocker les prix et les différences.
- réutiliser le même tableau pour les quadruplets déjà vus entre chaque secret sans le réinitialiser en utilisant l'astuce d'affecter avec seen[index] = i et de tester si seen[index] == i où i est l'indice du secret qu'on est en train de traiter.

En parallélisant le tout, je suis arrivé à 1.7ms alors que j'étais à 70ms sur mon premier jet.

De souvenir, les 23èmes jours sont assez difficiles. Voyons voir ce que cela donne demain.

Le jour le plus compliqué pour moi jusqu'à présent. J'ai mis beaucoup de temps à comprendre l'énoncé.

L'idée pour résoudre le problème est de remarquer que la complexité (la valeur qu'on cherche) ne dépend que des paires consécutives de lettres dans une séquence.
L'ordre de ces paires n'importe où.
Donc au lieu de représenter la séquence par une chaîne à caractères, on va le représenter par un tableau qui a une paire donnée associe son nombre d’occurrences dans la séquence.
Cela fait un tableau de 11x11 pour les séquences du clavier numérique et 5x5 pour les séquences du clavier analogique.
Ensuite il faut écrire deux fonctions numpad_step et dirpad_step qui a une paire de touches (x, y) donnée respectivement par le clavier numérique et le clavier de direction, associe la séquence de lettres pour passer de x à y à la profondeur +1.
Étant donné un tableau d'occurrences pour la profondeur p, on peut trouver le tableau d’occurrences pour la profondeur suivante de la manière suivante.

Soit current le tableau d'occurrences pour la profondeur p
créer un tableau next de 25 éléments initialisés à 0  
pour x dans ['<', '>', 'v', '>', A']
    pour y dans ['<', '>', 'v', '>', A']
         pour chaque paire consécutive (x2, y2) de dirpad_step(x, y):
             next[(x2, y2)] += current[(x, y)]
renvoyer next

En optimisant un peu, je suis arrivé à 6 microsecondes de temps d'exécution.
J'ai essayé d'aller plus loin en remarquant qu'on pouvait précalculer à la compilation un tableau qui à chaque paire du clavier numérique associe la longueur pour obtenir cette paire à profondeur 2 et à profondeur 25.
Avec cette approche, je suis arrivé à 70 nanosecondes de temps d'exécution, sans utiliser de code unsafe et en restant générique sur l'input (je ne suppose par exemple pas que chaque ligne fait exactement 4 caractères).

Aujourd'hui, j'ai pas trouvé de manière maligne de faire la partie 2.
Du coup, brute-force.
Pour chaque sommet u du chemin, je regarde tous les sommets v à distance au plus 20 et je teste si dist[u] <= dist[v] - 100 - manhattan(u, v). Si c'est le cas, j'incrémente le compteur représentant le nombre de cheats.

Une remarque cependant: le graphe de la grille est juste un chemin entre S et E.
Du coup, ça simplifie le calcul des distances. Pas besoin de BFS, DFS ou Dijkstra.
On part de S et on suit le chemin jusqu'à arriver à E.

Pour la partie 2, j'ai parallélisé en utilisant des threads. 640 microsecondes (et 4ms en séquentiel). Mon plus long temps d'exécution de cet AOC 2024 pour l'instant.

Jusqu'à présent, je suis un peu déçu de cet AOC par rapport aux années précédentes.
A quelques exceptions, tous les problèmes peuvent se résoudre par brute-force. J'ai l'impression que c'était moins le cas dans les années précédentes.

Comme d'habitude, j'essaie de trouver le meilleur algorithme pour résoudre le problème même si ce n'est pas nécessaire.

Aujourd'hui, la structure donnée à utiliser m'a paru naturelle: les prefix trees (également appelés tries).

https://fr.wikipedia.org/wiki/Trie_(informatique)

J'ai passé pas mal de temps à bien optimiser mon implémentation.
Au début, j'avais également fait une fonction récursive avec cache mais de la programmation dynamique s'est avérée plus rapide (3x fois plus rapide pour être précis).

L'algo en pseudo-code est le suivant

fonction(trie, design):
   initialiser t un tableau de (len(design)+1) entiers à 0
   t[0] = 1
   pour i de 0 à len(design) - 1:
      pour chaque prefixe p de design[i..] dans trie:
         t[i + len(p)] += t[i]
   renvoyer t[design]

La structure de données trie permet de très efficacement trouver les préfixes d'un mot appartenant à une liste.
170 microsecondes partie + partie 2.

La première était un juste un parcours en largeur classique.

Pour la seconde partie, j'ai plusieurs idées de plus en plus efficaces.

• l'approche brute-force. Tester pour tous les moments t si on peut trouver un chemin alors que es t premiers bytes sont tombés. Ca fonctionne mais c'est assez long.

• l'approche recherche binaire/dichotomique. On part d'un intervalle [0, nombre de bytes], on teste pour la valeur au milieu de l'intervalle et on divise à l'intervalle par deux à chaque itération.
  Ca donne un algorithme en temps O(N log M) où N est la taille de la grille et M le nombre de bytes. 70 microsecondes pour mon implémentation.

• l'approche union-find. On part de la grille complètement remplie par les bytes. On calcule les composantes connexes. On retire progressivement les bytes dans le sens inverse et on met à jour les composantes en utilisant une structure union-find.
  https://fr.wikipedia.org/wiki/Union-find
  30 microsecondes pour mon implémentation.

• La dernière approche consiste encore de partir de la grille complètement remplie par les bytes et de retirer progressivement les bytes dans le sens inverse.
  Sauf que cette fois ci, on va faire un parcours en profondeur depuis le sommet de départ, noter les sommets visités.
  Pour chaque byte (dans le sens inverse), si celui est adjacent à au moins un sommet déjà visité, on reprend le parcours en profondeur à partir de la position du byte en gardant les sommets déjà visités. On s'arrête dès que le sommet final est visité.
  Ca donne un algorithme en temps linéaire.
  14 microsecondes pour mon implémentation.

On peut utiliser un Dijkstra classique mais pas sur le graphe classique de la grille.
On peut construire un graphe où les nœuds sont des couples (sommet de la grille, direction) où direction est horizontal ou vertical.

La partie 1 est assez simple. On peut faire une optimisation en remarquant que diviser par 2^n revient à décaler les bits de n donc de faire l'opération a >> n.

Pour la partie 2, j'ai regardé la sortie pour les première valeurs de a.
On remarque la chose suivante.
La dernière valeur de sortie est déterminée par les 3 bits de poids forts.
L'avant-dernière par les 6 bits de poids forts.
L'avant-avant-dernière par les 9 bits de poids forts
etc

Donc on peut chercher les 3 bits de poids forts en simulant le programme avec a variant de 0 à 7 et pour chaque valeur ai dont la sortie correspond au dernier élément du programme chercher les 3 bits suivants en prenant a = ai * 8 + j pour j variant de 0 à 7.
On fait ainsi de suite en faisant des appels récursifs.
Voici le code de cette partie en Rust.
Comme on regarde d'abord les bits de poids forts, on est garanti de trouver sur une solution minimale si elle existe.
J'ai compté qu'il y avait 5 quines possibles pour mon entrée.

fn quine(program: &[u64], a: u64, idx: usize) -> Option<u64> {
    if idx == 0 {
        return Some(a)
    }
    for i in 0..8 {
        let ai = a << 3 | i;
        if let Some(output) = run_first_value(program, ai, 0, 0) {
            if output == program[idx-1] {
                if let Some(q) = quine(program, ai, idx-1) {
                    return Some(q)
                }
            }
        }
    }
    None
}

Oui, facile si on connaît Dijkstra.

Pour la partie 2, on peut lancer un second Dijkstra en partant du sommet final.
J'ai préféré faire un parcours en profondeur (beaucoup plus rapide qu'un Dijkstra) et remonter jusqu'au sommet de départ en suivant les poids données par le Dijkstra de la partie 1.
260 microsecondes pour les 2 parties, la partie 2, utilisant les informations de la partie 1, ne prend que 5 microsecondes.
Je vais voir si je peux optimiser mon Dijkstra mais je ne vois pas trop comment faire pour l'instant.

En consultant d'autres forums, je suis tombé sur une idée que j'ai trouvé astucieuse et élégante.

L'idée est que la position horizontale des robots cycle chaque 101 secondes et celle verticale chaque 103 secondes.
Donc, le nombre de robots par colonne est le même pour deux instants qui ont le même module 101.
De même , le nombre de robots par ligne est le même pour deux instants qui ont le même modulo 103.

Si on peut détecter si un instant t fait apparaître l'image juste en consultant le nombre de robots par ligne ou juste le nombre de robots par colonne alors il suffit de faire ce test seulement pour les instants de 0 à 101 (pour les colonnes) et de 0 à 103 (pour les lignes).
A partir de ça, on est capable d'extrapoler le moment t où l'image apparaît en utilisant le théorème des restes chinois.
Plus précisément, notons t le moment où l'image apparait
si t1 est le moment entre 0 et 101 qui a le même modulo 101 que t
et t2 est le moment entre 0 et 103 qui a le même modulo 103 que t.

Alors t = (t1 * 51 * 103 + t2 * 51 * 101) % (101 * 103)

Pour tester si l'image apparaît en regardant les colonnes, j'ai vu plusieurs approches notamment calculer la variance mais c'est un peu long à calculer.
J'ai essayé de calculer la somme des carrés des nombres de robots qui apparaissent sur chaque colonne mais c'est également un peu long à calculer.
Finalement, j'ai utilisé l'approche suivante.
Je divise mes colonnes en 4 parties Q1 | Q2 | Q3 | Q4 et comme l'image est assez dense et qu'elle fait moins de la moitié des colonnes, j'en déduis que le nombre de robots dans Q1 ou dans Q4 sera assez faible. Donc, je cherche l'instant t entre 0 et 101 qui minimise ce nombre.
Je fais de même pour les lignes.

50 microsecondes pour mon implémentation.