Guillaume.B a écrit 79 commentaires

En fait, il y avait encore plus simple.

On peut totalement de pas prendre en compte la forme des tuiles et juste regarder combien de carrés 3x3 qu'on peut mettre dans la grille. Donc une simple division par 3 suffit.
Totalement bidon comme problème (mais vraiment compliqué si on ne fait pas cette supposition et qu'on veut une solution générale).

Voici mon code

pub fn solve(input: &str) -> (usize, u32) {
    let p1 = input
        .lines()
        .skip(30)
        .filter(|&line| {
            let mut it = line.iter_unsigned::<u32>();
            let (x, y) = it.next_tuple().unwrap();
            (x / 3) * (y / 3) >= it.sum() 
        }).count();
    (p1, 0)
}

Déjà, il faut remarquer que le graphe est acyclique.

Du coup, on peut faire un tri topologique dessus.
C'est à dire que chaque arête va d'un sommet vers un sommet plus grand selon cet ordre.

A partir de là, c'est facile de compter le nombre de chemins.
En pseudo-code.

fonction nb_chemins(graphe, source, dest):
   initialiser un tableau t de graphe.len() éléments à 0
   t[source] = 1
   pour chaque sommet i du graphe selon l'ordre topologique
       pour chaque voisin j de i
           t[j] += t[i]
   renvoyer t[dest]

Pour la partie 2, on peut le trouver avec la formule suivante

c(svr, dac) * c(dac, fft) * c(fft, out) + c(svr, fft) * c(fft, dac), c(dac, out)

où c(a, b) est le nombre de chemins de a à b.
sachant qu'une des parties de la somme est forcément nulle.

50 microsecondes pour les deux parties.

Pour la partie 1, il faut remarquer que l'ordre d'appui sur les boutons importe peu et qu'il ne sert à rien d'appuyer deux fois sur le même bouton.

Donc on peut tout encoder sous forme de bitset et faire un parcours en largeur sur les configurations possibles.

J'ai pris beaucoup de temps mais je suis finalement arrivé à avoir une solution pour la partie 2 sans utiliser de solveurs externes (j'ai d'abord utilisé Z3).

L'idée est qu'il faut résoudre un système d'équations linéaires comme dit dans un post plus haut en cherchant une solution avec des valeurs entières positives et qui minimisent la somme totale.

Le problème, c'est que la matrice n'est forcément carrée, pas forcément invertible donc il peut y avoir une infinité de solutions.
Le pivot de Gauss peut nous donner une solution mais ce n'est pas forcément la bonne.

Imaginons qu'on est ce système d'équations

1 1 1 0 1 1 0 1 1 0 0 0 55
1 1 0 1 0 1 0 0 0 0 0 0 42
1 0 1 1 0 0 1 0 0 0 1 1 71
1 0 1 1 0 0 1 0 1 1 0 1 79
1 0 1 1 0 1 1 0 0 0 0 1 70
0 0 1 1 0 1 0 1 0 0 0 0 41
1 1 1 0 1 0 1 0 0 1 0 1 60
0 0 1 0 1 1 0 0 0 1 0 1 45
1 0 1 1 0 0 1 1 0 1 0 0 58
0 1 0 0 0 1 1 0 0 1 0 1 53

On va appliquer le pivot de gauss sur cette matrice et obtenir la matrice "échelonnée":

1  1  1  0  1  1  0  1  1  0  0  0  55 
0 -1  0  1 -1 -1  1 -1 -1  0  1  1  16 
0  0 -1  1 -1  0  0 -1 -1  0  0  0 -13 
0  0  0 -2  1 -1  0  0  1  0  0  0 -28 
0  0  0  0  1  1  0 -2 -1  2  0  2  36 
0  0  0  0  0 -1  1 -1 -1  1  0  1  5 
0  0  0  0  0  0  1 -1 -1  1 -1  1  4 
0  0  0  0  0  0  0 -1  0 -1  1  1  13 
0  0  0  0  0  0  0  0 -1 -1  1  0  -8 
0  0  0  0  0  0  0  0  0  2 -8 -2 -114

Si on oublie la dernière colonne, on dit qu'une colonne est pivot si l'élément non nul le plus bas de cette colonne a la propriété suivante, il y a que des 0 à gauche et en dessous.
Donc, on voit ici que toutes les colonnes sont pivots sauf les deux avant-dernières.

L'algorithme se base sur le fait qu'il y a peu de colonnes non pivots.

Si la matrice n'a aucune colonne non pivot alors il existe une solution et donc on n'a pas besoin de cherche plus loin.
Sinon, on va partir d'en bas à droite et affectant les valeurs de la solution de droite à gauche.
Si une colonne j est pivot et que les variables à droite ont déjà affectés alors il n'y a qu'une seule valeur possible pour la variable x_j.

Par contre, si la colonne j n'est pas pivot, il peut y avoir plusieurs valeurs affectables à la variable x_j. On va donc affecter à cette variable, une valeur entre 0 et une certaine limite et faire du backtracking.
Comme il y a au plus 3 colonnes non pivots dans chaque matrice du jeu de données, il n'y pas une grande profondeur de backtracking.

Pour la limite, j'ai choisi une valeur qui allait bien pour le jeu de données, à savoir 200 si il y a au plus de colonnes non pivots et 30 si il y a 3 colonnes non pivots.

En parallélisant, le temps d'exécution est 4ms.

Je ne vois pas le rapport avec les polynômes mais avec l'espace vectoriel je le vois clairement.

Le problème consiste à résoudre un système d'équations linéaire MX = B
où
- X est le vecteur inconnu que l'on cherche, c'est à dire X[i] est le nombre de fois qu'on a appuyé sur le bouton i.
- B est le vecteur des "joltage levels"
- M est une matrice telle M[(i, j)] = 1 si le bouton i active le compteur j et 0 sinon.

On veut que les valeurs de X soient entière et positives et on veut minimiser la somme des valeurs de X.

On peut résoudre le système d'équations en utilisant par exemple le pivot de Gauss.
Le problème est que la solution obtenue ne contient pas forcément des valeurs positives et entières.

Du coup, je suis passé par un solveur de programmation linéaire en nombre entiers.
Mais je suis en train de travailler sur une solution qui ne nécessite pas de librairies externes. En espérant que ça marche …

Je ne l'ai pas fait mais je connais des gens qui arrivent à répondre au problème (sur 5 inputs différentes) en ne lisant que 8 lignes bien choisies de l'input.
La réponse se fait en quelques nanosecondes.

Oui, tu as raison, je n'avais pas pensé à ce cas de figure.
J'ai été chanceux sur l'input.
Va falloir que je corrige mon algo si je veux qu'il soit correct dans le cas général.
Je pense qu'ajouter les points (x+1, y) et (x, y+1) doit suffire à régler le problème.

que l'extérieur soit connexe, ce qui est garanti si on a étendu la zone de tous les côtés.

Oui, c'est ce que je fais.
Et en effet, peindre l'intérieur, c'est compliqué même si on connait un point à l'intérieur.

Pour ma part, j'ai essayé de ne pas utiliser de librairies externes même si c'est très pratique.
La partie 1 est facile.
J'ai mis beaucoup de temps à débugguer la partie 2 à cause de bugs stupides.

Voici l'idée pour la partie 2.
Bien sûr, on ne peut pas représenter la grille des points de l'input car elle est beaucoup trop grande.
Ce qu'on va faire, c'est qu'on va utiliser une grille plus petite.
On trie les coordonnées x et y par ordre croissant et dans la grille au lieu d'utiliser la position (x, y), on va utiliser la position (i, j) où i est la position de x dans son tableau trié et j est la position de y dans son tableau trié.
Ce qui nous permet d'avoir une grille de taille environ 250x250, ce qui est raisonnable.
Ensuite, on trace des lignes dans la grille en fonction des segments données en input et on remplit le polygone en utilisant le classique flood-filling.

Maintenant, il y a une astuce pour déterminer en temps constant si un rectangle est contenu dans le polygone.
L'idée est de calculer, par programmation dynamique, un tableau empty_table qui pour chaque (x, y) donne combien de cases vides contient le rectangle (0, 0) -- (x, y).
A partir de là, on peut déterminer déterminer le nombre de cellules vides dans un rectangle (x1, y1, x2, y2) en faisant le calcul
empty_table[x2, y2] - empty_table[x1-1, y2] - empty_table[x2, y1-1] + empty_table[x1-1, y1-1].
Si le nombre de cellules vides est 0, cela signifie que le rectangle est contenu dans le polygone.

Ca donne un algorithme en temps O(n²) et un temps d'exécution de 650 microsecondes pour les deux parties.
Je ne fais pas de supposition sur l'input, on peut sans doute faire mieux en en faisant.

Oui, la récursion avec cache, c'est assez similaire à la programmation dynamique.
La différence c'est qu'en version récursive, on part du problème initial pour descendre dans l'arbre des appels récursifs alors qu'avec la programmation dynamique, on dérécursifie l'algorithme en partant des feuilles de l'arbre et en remontant à la racine (le problème initial).

En général, un algorithme en programmation dynamique est un peu plus rapide que sa version récursive avec cache (car pas de récursion et on utilise en général un tableau dont l'accès est plus rapide qu'un cache qui est en général implémenté par un hashset).
C'est aussi parfois beaucoup plus économe en mémoire.

J'ai trouvé ce problème assez intéressant.

Mon défi était d'avoir un temps d'exécution inférieur à 1ms.

Première approche, on calcule toutes les paires de sommets et leur distance euclidienne (en fait, on a pas besoin de faire la racine carrée qui est coûteuse en temps).
Ensuite, on fait un algorithme similaire à Kruskal.
https://fr.wikipedia.org/wiki/Algorithme_de_Kruskal

On utilise une structure union-find
https://fr.wikipedia.org/wiki/Union-find
et on rajoute progressivement chaque arête en faisant un join sur les deux extrémités de l'arête. Pour la partie 2, on a besoin de trier les arêtes ce qui est vraiment le goulot d'étranglement de l'algo. Pour la partie 1, on a juste besoin de garantir que les 1000 premières arêtes aient la distance euclidienne la plus petite. En Rust, cela peut être fait avec la méthode select_unstable(1000) et c'est beaucoup plus efficace que trier le tableau. Avec cette approche, 2ms pour la partie 1 et 15ms pour la partie 2.

Deuxième approche uniquement pour la partie 2.
On cherche un arbre couvrant de poids minimum mais cette fois, au lieu de se baser sur Kruskal qui est en temps O(m log n) = O(n² log n) comme le graphe est dense, on se base sur l'algorithme de Prim qui est en temps O(n²).https://fr.wikipedia.org/wiki/Algorithme_de_Prim
Du coup, on réduit le temps à 3ms.

Dernière approche, on revient sur Kruskal mais cette fois, on ne va pas considérer toutes les arêtes.
On va diviser l'espace en blocs 8x8x8 et pour chaque sommet, on va regarder les sommets qui sont dans le même bloc ou dans un bloc voisin (diagonal compris).
On passe de (1000*999) / 2 ~ 500_000 paires d'arêtes à environ 10000.
En appliquant le même principe que la première méthode, on obtient un temps d'exécution de 650 microsecondes pour les deux parties.
Ca ne marche pas tout le temps, il ne faut pas qu'il y ait de gros trous dans l'espace de points mais ça semble être le cas dans les différentes inputs car les points sont uniformément répartis.

Ca peut, en effet, être vu comme un algorithme sur un graphe.

Ca consiste à compter le nombre de chemins dans un graphe orienté acyclique et ça se fait en temps linéaire.

Je n'ai pas l'impression que networkx propose cet algorithme mais ça se fait aussi … par programmation dynamique :)

Finalement, j'ai essayé de vectoriser mon code pour la partie 1 via instruction SIMD.
L'idée est de stocker chaque ligne sous forme de bitset de 192bits.
On peut les extraire de manière très rapide en utilisant des instructions SIMD qui vont travailler sur les caractères par pack de 64.
On stocke aussi un tableau de beams (i.e beams[i] = true s'il passe un beam à la position i.

Cela donne le code suivant en oubliant les détails.

pub fn part1(input: &str) -> u32 {
    let input = input.as_bytes();
    let mut beams = U192::new(0, 0, 0);
    beams.second |= 1 << (MID - 64);

    (2*WIDTH..input.len()).step_by(2*WIDTH).map(|line_start| {
        let splits = U192::from_slice(&input[line_start..line_start+WIDTH-1]);
        let beam_on_split = beams & splits;
        beams = (beams | beam_on_split.shift_left() | beam_on_split.shift_right()) & !splits;
        beam_on_split.count_ones()
    }).sum()
}

Il n'y a au final pas tant de SIMD que ça mais plutôt un travail sur les bitsets.
250 nanosecondes, en dessous de la microsecondes :)

Même approche ici. C'est de la programmation dynamique mais assez facile.

Je stocke un tableau timelines qui pour chaque indice i d'une ligne me donne le nombre de timelines à la position (j, i) où j est à la ligne en cours.
Je pensais qu'il faudrait stocker un tableau des timelines de la ligne précédente mais en fait ça ne sert à rien.

Petite astuce, lorsque l'on traite la ligne i, on a besoin juste de regarder les indices [start_pos-i-1..start_pos+i+1] ce qui accélère un peu les choses.

Je pense que la partie 1 doit se vectoriser très bien mais je ne suis pas compétent en SIMD.
https://fr.wikipedia.org/wiki/Single_instruction_multiple_data

Le code pour les deux parties (~3 microsecondes).

pub fn solve(input: &str) -> (u32, u64) {
    let input = input.as_bytes();
    let width = input.iter().position(|&b| b == b'\n').unwrap() + 1;
    let start_pos = input.iter().position(|&b| b == b'S').unwrap();
    let mut p1 = 0;
    let mut count = vec![0; width];
    count[start_pos] = 1;
    for (delta, line_start) in (2*width..input.len()).step_by(2*width).enumerate() {
        let start = start_pos - delta - 1;
        let end = start_pos + delta + 2;
        for i in start..end {
            if input[line_start+i] == b'^' {
                p1 += (count[i] != 0) as u32;
                count[i-1] += count[i];
                count[i+1] += count[i];
                count[i] = 0;
            }
        }
    }

    let p2 = count.iter().sum();

    (p1, p2)
}

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