Journal Advent of code 2024

Posté par  . Licence CC By‑SA.
Étiquettes :
9
30
nov.
2024

Comme chaque année, certains attendent avec impatience le jour suivant pour découvrir la prochaine case de leur calendrier de l'Avent, espérant y trouver du chocolat ou d'autres produits imaginés par les marketeurs.

Pour ma part, je préfère les petits défis de programmation proposés par Advent of Code 2024.
https://adventofcode.com/2024

Chaque jour, en résolvant ces petits problèmes de code, vous aurez la satisfaction de sauver Noël. En réalité, l'histoire importe peu. Ce qui compte, c'est de relever chaque jour un nouveau défi de programmation qui vous procurera votre dose quotidienne de dopamine. Ces défis sont organisés par difficulté croissante. Traditionnellement, on y trouve :

des problèmes de tri,
des problèmes arithmétiques (somme de suites, résolution de systèmes linéaires, etc.),
des problèmes de recherche de chemin,
de la trigonométrie en 2D, puis en 3D,
et bien d'autres.
Pour chaque problème, il y a deux étoiles à gagner. La première est généralement simple, tandis que la deuxième représente souvent une mise à l'échelle du même problème qui remet complètement en cause votre manière d'aborder le sujet.

Advent of Code est aussi une compétition. Les plus courageux se lèveront à 6h (heure de Paris) pour gagner les étoiles. Personnellement, je commence à 8h00. À ce sujet, il y a un leaderboard actif depuis 2 ans que vous pouvez rejoindre : 1844559-f65dbf07.

Je vous souhaite une bonne fin d’année et de joyeuses lignes de code à tous !

  • # J'y participe

    Posté par  . Évalué à 3 (+3/-0).

    Comme les années précédentes, j'y participe.

    Cette année, ce sera en Rust contrairement aux années précédentes où c'était en Haskell.

    Je ne me lèverai pas non plus à 6h. Trop tôt pour moi.

  • # 1er jour

    Posté par  . Évalué à 3 (+1/-0).

    D'habitude, je commence avec AWK et je poursuis en Python plus tard quand ça devient plus compliqué. Là, j'ai dû sortir Python le premier jour. Ce n'est pas de bon augure pour la suite.

    • [^] # Re: 1er jour

      Posté par  (site web personnel) . Évalué à 5 (+3/-0). Dernière modification le 01 décembre 2024 à 13:30.

      En vrai, une fois que t'as le prototype python, c'est assez facile de faire la version awk

      (désolé, y'a pas de balise spoiler)

      {
    left_list[NR] = $1
    right_list[NR] = $2
}

END {
    asort(left_list)
    asort(right_list)

    distance = 0
    for (i = 1; i <= NR; i++) {
        d = left_list[i] - right_list[i]
        if (d < 0) {
            d = -d
        }
        distance += d
    }
    print distance
}
      $ cat dataset_exemple.txt
3   4
4   3
2   5
1   3
3   9
3   3
$ awk -f day1.awk dataset_exemple.txt
11

      • [^] # Re: 1er jour

        Posté par  . Évalué à 3 (+1/-0).

        En effet, si je regarde mon code python, ça donnerai le code que tu proposes.
        Cependant asort est spécifique GNU AWK et pas dispo dans mawk. Je pense que c'est ce qui m'a inconsciemment fait partir sur Python.

        • [^] # Re: 1er jour

          Posté par  (site web personnel) . Évalué à 3 (+3/-0).

          Voici un code de asort pour mawk que j'utilise depuis 2012.

          function alength(A, n, val) {
          n = 0
          for (val in A) n++
          return n
          }
          function asort(A, hold, i, j, n) {
          n = alength(A)
          for (i = 2; i <= n ; i++) {
          hold = A[j = i]
          while (A[j-1] > hold) {
          j--
          A[j+1] = A[j]
          }
          A[j] = hold
          }
          delete A[0]
          return n
          }

        • [^] # Re: 1er jour

          Posté par  (site web personnel) . Évalué à 2 (+0/-0). Dernière modification le 03 décembre 2024 à 19:48.

          maintenant je suis curieux. Une raison de ne pas utiliser gawk ? Pas de sectarisme de ma part, j'utilise très peu awk et je me contente d'utiliser celui installé par défaut :D

          • [^] # Re: 1er jour

            Posté par  . Évalué à 2 (+0/-0).

            Gawk a des fonctionnalités supplémentaire : support du csv, fonctions de tri, support des extensions - ce qui peut permettre de traiter du xml par exemple, paramétrage du tri des énumérations de clé des tableaux associatifs.

            Tout ceci n'est pas présent dans la spécification d'origine.

      • [^] # Re: 1er jour

        Posté par  . Évalué à 4 (+2/-0).

        C'est moins la possibilité que pour le fait de ne pas tirer parti du fonctionnement de awk que je ne suis pas parti là dessus.

        Première étoile je l'ai fais avec un tableur, seconde étoile je n'ai pas compris comment me servir correctement du tableur donc c'était en shell (awk/grep/awk), les premiers jours pour moi c'est toujours juste histoire de trouver le résultat sans chercher à faire du "vrai" code.

        J'ai même pas décidé quel sera mon langage cette année. J'avais pensé à julia, mais je ne l'ai même pas encore installé.

        https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll

  • # vous aurez la satisfaction de sauver Noël

    Posté par  . Évalué à 5 (+4/-0).

    même pas sûr qu'on y arrive :

    papa noel

  • # 2ème jour - on apprend à lire l’énoncé

    Posté par  . Évalué à 3 (+1/-0). Dernière modification le 02 décembre 2024 à 10:49.

    La différence max est 3, pas 2. Une différence de 0 est "unsafe".

    En AWK aujourd'hui avec quelques boucles imbriquées. Pour éviter celle que rajoute la partie 2, je pré-processe l'input pour faire des blocs.

    # emit a report and its variants as a bloc, separated by empty line
{
  print
  for (i=1;i<=NF;i++) {
    r = ""
    for (j=1;j<=NF;j++) {
      if (i!=j) {
        r = r $j " "
      }
    }
    print r
  }
  print ""
}

  • # 3ème jour

    Posté par  . Évalué à 5 (+3/-0).

    Je crois que c'est la première fois que je fais le troisième jours encore en CLI (je commence à CLI tant que je trouve artificiel d'utiliser un langage plus sophistiqué). Première et seconde étoiles avec un one-liner chacun.

    https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll

    • [^] # Re: 3ème jour

      Posté par  . Évalué à 3 (+1/-0).

      Pareil, petit coup de "oulah on va soufrir" en regardant l'input puis en lisant les instruction, un coup de regexp et awk et c'est torché.

  • # 4ème jour - on attaque le parcours de grille

    Posté par  . Évalué à 2 (+0/-0).

    Ça me paraît tôt :D

    Mais ça se fait bien en le faisant calmement.

    • [^] # Re: 4ème jour - on attaque le parcours de grille

      Posté par  . Évalué à 4 (+2/-0).

      Moi j'ai finalement commencé à utiliser julia que je ne connaissais pas du tout.

      Il y a des trucs très confortables, la lecture du fichier par exemple se fait en une ligne avec la bibliothèque standard (sans même un import), et des pièges, comme les indices qui commencent à 1.

      Mais il y a des parties sympathiques comme la gestion des arbres à N-dimension dans le langage et comme en python on a les comprehension list

      https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll

  • # 7ème jour, un peu de répit

    Posté par  . Évalué à 4 (+2/-0).

    Celui d'hier avait une partie deux très facile, mais une partie deux qui m'a donné beaucoup de mal.

    Aujourd'hui, une petite fonction récursive et c'est torché, partie deux aussi.

    • [^] # Re: 7ème jour, un peu de répit

      Posté par  . Évalué à 3 (+3/-0).

      Pour ma part, comme les problèmes des premiers jours sont assez faciles, j'essaie d'optimiser au maximum le temps d'exécution.

      Pour le jour 7, j'ai trouvé une petite astuce.

      Au lieu d'explorer toutes les combinaisons possibles en allant de gauche à droite, je pars de la valeur cible et j'essaie de remonter jusqu'à la première valeur en allant de droite à gauche et en inversant les opérations si celles-ci sont possibles. Cela réduit énormément l'arbre d'exploration.

      Cela me donne 240 microsecondes au lieu de 15 millisecondes avec une approche brute-force.

      • [^] # Re: 7ème jour, un peu de répit

        Posté par  . Évalué à 2 (+0/-0).

        Je suis arrivé à peu près aux mêmes conclusions, avec comme toujours de légères variantes dans l'approche.

        Pour la première partie, étant donné que chaque signe était soit « + », soit « × », on pouvait utiliser du binaire pour les marquer et j'ai donc utilisé une boucle qui comptait de 0 à 1 << n pour obtenir les combinaisons, et on obtenait donc directement une fonction itérative plutôt que récursive.

        En outre, en comptant de deux en deux, on peut forcer le bit0 à être toujours nul et donc à imposer un « + » sur le premier nombre, ce qui permet de l'ajouter directement à un accumulateur vide plutôt que faire une exception rien que pour lui.

        Pour la deuxième partie, j'ai effectivement réécrit une fonction récursive mais là encore, étant donné que l'on traite des entiers strictement positifs, le cumul ne peut être que croissant étant donné les opérations à utiliser (ici +, - et ||). Donc, j'ai effectivement passé la cible à la fonction récursive parallèlement aux autres arguments et interrompu la procédure chaque fois qu'une « branche » dépassait la cible. C'est la même chose mais dans l'autre sens.

        Cela me donne 240 microsecondes au lieu de 15 millisecondes avec une approche brute-force.

        Tu as oublié de remettre les arguments à l'endroit en sortie… :-)

        • [^] # Re: 7ème jour, un peu de répit

          Posté par  . Évalué à 2 (+0/-0).

          J'ai tenté votre optimisation, mais je ne divise le temps que par 2, pas par 10…

          • [^] # Re: 7ème jour, un peu de répit

            Posté par  . Évalué à 1 (+1/-0). Dernière modification le 09 décembre 2024 à 13:40.

            Je n'ai pas l'impression que l'optimisation d'Obsidian soit la même que la mienne.

            Je vais illustrer mon algo par mon exemple pour la partie 2.

            Supposons qu'on a la liste [2345, 23, 35, 10] avec 2345 comme valeur cible.

            On part de 2345 et on regarde le dernier nombre à savoir 10.
            2345 n'est pas divisible par 10 et 10 n'est pas un suffixe du mot 2345.
            Donc la seule opération que l'on peut faire est l'addition.
            On va donc chercher récursivement si la liste [2345-10=2335, 23, 35] admet une solution.
            Regardons de nouveau le dernier nombre 35.
            35 est un suffixe de 2335 mais 35 ne divise pas 2335.
            Donc on peut faire une addition ou une concaténation.
            Si on fait une addition, on va chercher si [2335 - 35, 23] admet une solution et
            si on fait une concaténation, on va chercher si [23, 23] admet une solution.
            [2335 - 35, 23] n'admet pas de solution mais [23, 23] admet clairement une solution donc la liste [2345, 23, 35, 10] admet une solution.

            J'obtiens un gain non pas de x10 mais de x60.

  • # Advent en JavaScript par Mozilla

    Posté par  . Évalué à 2 (+0/-0).

    https://tech.slashdot.org/story/24/12/04/0138255/mozilla-announces-javascriptmas---daily-coding-challenges-with-a-chance-at-prizes

  • # 9ème jour

    Posté par  . Évalué à 3 (+3/-0). Dernière modification le 09 décembre 2024 à 14:12.

    Le neuvième jour n'était pas si simple mais c'est surtout que j'ai cherché à obtenir un algo linéaire pour les deux parties.

    Pour la partie 1, j'ai obtenu un algorithme linéaire sans devoir allouer plus de mémoire que l'entrée.
    L'idée est de maintenir un indice sur le bloc de fichier qu'on est en train de déplacer et un indice sur l'endroit où on est en train de le déplacer.
    On va progressivement décrémenter le premier indice et incrémenter le second jusqu'à ce que le premier soit plus petit que le second.

    Pour la partie 2, on va faire un peu la même chose. On va utiliser un indice sur le fichier qu'on est en train de déplacer et 10 indices, le i-ème indice pointant vers le prochain endroit où il y a au moins i blocs disponibles.
    De même que pour la partie 1, on va progressivement décrémenter le premier indice et incrémenter les 10 indices ainsi que mettre à jour le nombre de blocs disponibles qu'on a fait un déplacement.
    Contrairement à la partie 1, on a besoin de de mémoire supplémentaire pour indiquer à quel point une séquence de blocs vides a été remplie.

    50 microsecondes pour la partie 1 and 380 microsecondes for la partie 2.

    • [^] # Re: 9ème jour

      Posté par  . Évalué à 2 (+0/-0).

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

    • [^] # Re: 9ème jour

      Posté par  . Évalué à 2 (+0/-0).

      J'ai enfin fini le jour 9 j'ai pas fais comme toi.

      Le jour 1 j'ai l'indice en cours uniquement et je décrémente mes compteurs, je cherche le fichier à déplacer car c'est le slot fichier non égale à 0. C'est moins efficace qu'avoir l'indice, mais au final c'est très pratique pour la seconde étape où je replace ma condition de recherche par fichier qui rentre dans le slot vide en cours.

      J'ai dû faire un peu de maths pour éviter des itérations : je fais une itération par slot au lieu d'une itération par "bit" et ça simplifie l'étape 2.

      Le dernier piège que j'ai eu à l'étape 2 vient du fait que le résultat n'est pas contigüe donc il faut mémoriser la valeur d'un fichier déplacer pour incrémenter l'indice qui sert au checksum. Du coup quand un fichier est déplacé au lieu de la passer à 0 je le passe en négatif.

      Je cherche pas le même niveau de performance que toi. J'ai vu à l'un des jours précédent que j'arrivais pas en julia à les atteindre, mais julia est vraiment cool comme langage.

      (oui je suis à la bourre ^^)

      https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll

  • # 10ème jour

    Posté par  . Évalué à 1 (+1/-0). Dernière modification le 10 décembre 2024 à 15:15.

    Je ne sais pas si beaucoup de gens lisent encore ce topic mais je vais quand même continuer.

    Quand j'ai vu le problème du jour, je me suis dit "encore un problème avec un parcours en largeur".
    Cependant, ce problème a quelques propriétés intéressantes.
    - On cherche des chemins avec valeurs croissantes donc pas la peine de se soucier de la détection de cycle.
    - Pour une source donnée, le nombre de chemins possibles partant de cette source est très faible.

    Du coup, on peut faire un parcours en profondeur (qui est un peu plus rapide qu'un parcours en largeur) sans se soucier des sommets déjà vus. Ce qui économise une table de hash ou autre structure pour les stocker.
    On obtient donc un algorithme potentiellement exponentiel alors qu'un parcours en largeur est linéaire mais en pratique, ça va plus vite.

    Quelques autres optimisations que j'ai faite.
    - pour la partie 1, j'utilise une table de hash pour stocker les sommets finaux (de valeur 9) accessibles depuis la source. Je ne suis pas sûr que ce soit le mieux.
    - j'utilise un tableau 1 dimension pour stocker la grille. J'ajoute +1, -1, +width, -width à un index pour obtenir les sommets adjacents.
    - pour éviter de tester si un voisin du sommet courant se trouve à l'intérieur de la grille, je rajoute sur les bords de la grille des caractères '#'.

    Chose surprenante, la partie 2 se résout plus vite que la partie 1.

    65 microsecondes pour la partie 1 + partie 2.

    • [^] # Re: 10ème jour

      Posté par  . Évalué à 2 (+1/-0). Dernière modification le 11 décembre 2024 à 09:40.

      Hier, je l'ai pris de travers :)
      J'ai fait un dijkstra pour résoudre la première partie.

      Ce qui n'était pas du tout adapté à la partie 2, j'ai du repasser en récursion basique ensuite.
      Si j'avais pris ce choix, je pense que je faisais les 2 parties en moins de 20min

      Pour la partie 2 : 134ms (jvm lancé)

    • [^] # Re: 10ème jour

      Posté par  . Évalué à 4 (+2/-0).

      Je ne sais pas si beaucoup de gens lisent encore ce topic mais je vais quand même continuer.

      ça fait une semaine que je n'ai pas eu le temps d'avancer, mais je continue de suivre ici sans me spoil et je regarderais plus en détail quand je m'y frotterais. J'espère pouvoir reprendre dès aujourd'hui :)

      https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll

  • # 11ème jour

    Posté par  . Évalué à 2 (+1/-0).

    Si je l'avais fait en python. Je pense que j'aurai été plus vite environ 40min.
    J'ai été obligé de repasser tout en BigInteger pour la 2ème partie.

    La partie 2 : je mets 191ms pour trouver la solution ;-)

    • [^] # Re: 11ème jour

      Posté par  . Évalué à 2 (+2/-0).

      Pour le problème du jour, j'ai anticipé la partie 2 et j'ai donc préparé directement un truc efficace pour cette partie.

      A chaque itération de blink, je stocke un HashMap qui associe à chaque valeur (pierre) le nombre d’occurrences de cette valeur.

      Quelques optimisations:
      - j'alloue un hashmap d'une capacité double de la taille du précédent arrangement.
      Ca évite de réallouer le hashmap quand celui ci grossit.
      - J'utilise la librairie ahash comme fonction de hash à la place de celle par défaut,
      ce changement a quasiment divisé le temps d'exécution par 2.
      - Pour calculer les deux parties des chiffres d'un nombre, j'utilise la méthode ilog10 ainsi qu'une division et un modulo plutôt que convertir le nombre en string et le reconvertir en entier.

      fn split_number(n: u64) -> Option<(u64, u64)> {
    let m = n.ilog10() + 1;
    if m & 1 == 0 {
        let p = 10u64.pow(m >> 1);
        Some((n / p, n % p))
    } else {
        None
    }
}

      Je pense que ça aurait été encore plus rapide en faisant plein de if pour chaque puissance de 10 mais ça aurait été très moche.

      J'ai essayé d'utiliser des u32 au lieu de u64 comme clé du hashmap mais j'ai des overflows. Par contre, je n'ai pas eu besoin d'utiliser de big integers.

      Du coup, un peu moins de 3ms: partie 1 + partie 2.

      • [^] # Re: 11ème jour

        Posté par  . Évalué à 3 (+2/-0). Dernière modification le 11 décembre 2024 à 13:48.

        u64, c'est pour unsigned 64 ?
        Car en Java, j'ai été obligé de passer tout en BigInteger car j'avais un dépassement et j'obtenais des chiffres négatifs

        Mais bon Java , tu ne peux pas faire de unsigned … donc peut être qui me manquait uniquement le 264 :)

        • [^] # Re: 11ème jour

          Posté par  . Évalué à 1 (+1/-0).

          Oui, u64, c'est unsigned 64.

          La plus grande valeur que j'ai obtenue pour une valeur de pierre est 36_024_470_028_800 soit à peut près 3*1013 et ma solution est de l'ordre de 1015.
          Donc ça tient sur unsigned 64 et même un signed 64.

          Peut être que tu n'as pas eu de chance sur l'input.

          • [^] # Re: 11ème jour

            Posté par  . Évalué à 2 (+1/-0). Dernière modification le 11 décembre 2024 à 17:39.

            En fait, c'est moi qui avait du faire un cast en Int. Cela tenait bien dans un Long.

  • # 12ème jour

    Posté par  . Évalué à 2 (+2/-0).

    200 microsecondes pour la partie 1 + partie 2, je suis assez fier de moi au niveau des optimisations.
    L'idée consiste pour chaque lettre non déjà parcourue de faire un parcours en profondeur (plus rapide qu'en largeur) et de calculer en une seule passe l'aire, le périmètre et le nombre de cotés.

    • Comme pour la question 10, j'utilise un tableau à une seule dimension avec des symboles # sur les bords. Ce qui me permet de faire grid[index-1], grid[index+1], grid[index+width], grid[index-width] pour accéder aux sommets adjacents tout en garantissant que je ne sorte pas de la grille.
    • Pour éviter de créer un nouveau tableau ou autre structure pour noter les sommets déjà visités, j'utilise le bit de poids fort de chaque élément de ma grille. C'est possible car les éléments sont sur 8 bits et seuls 7 bits sont utilisés en ASCII.
    • Pour la partie 2, compter le nombre de cotés revient à compter le nombre de coins.

    Voici le code

    pub fn solve(input: &str) -> Result<(u32, u32)> {
    let grid = Grid::parse_with_padding(input, b'.')?;
    let width = grid.width;
    let mut grid = grid.vec;
    let mut stack = Vec::with_capacity(500);
    let mut p1 = 0;
    let mut p2 = 0;

    for i in 0..grid.len() {
        let start = grid[i];
        if start.is_ascii_uppercase() {
            let mut area = 0;
            let mut perimeter = 0;
            let mut sides = 0;
            stack.push(i);
            while let Some(current) = stack.pop() {
                if grid[current] != start {
                    continue;
                }
                grid[current] |= 128;
                area += 1;
                for (next, side) in [(current-1, width), (current+1, width), (current-width, 1), (current+width, 1)] {
                    stack.push(next);
                    if grid[next] & 127 != start {
                        perimeter += 1;
                        let c1 = grid[current+side];
                        let c2 = grid[next+side];
                        if c1 & 127 != start || c2 & 127 == start {
                            sides += 1;
                        }
                    }
                }
            }
            p1 += area * perimeter;
            p2 += area * sides;
            stack.clear();
        }
    }
    Ok((p1, p2))
}

    • [^] # Re: 12ème jour

      Posté par  . Évalué à 2 (+1/-0).

      compter le nombre de cotés revient à compter le nombre de coins.

      Je n'y avais pas pensé. J'ai utilisé une méthode différentes

      J'identifie les pièces sous forme d'un Set.

      Pour identifier les côtés, je détermine la bordure & la direction qui a servi à déterminer cette bordure. Cela me donne un Set

      Je regroupe les éléments de ce Set par exploration des adjacents de même directions. Le nombre groupe identifié correspond à mon nombre de côté.

          private static int computeSides(Set<Point> pieces) {
        Set<SidePart> set = new HashSet<>();
        int sides = 0;
        for (Point p : pieces) {
            for (Point d : Point.DIRECTIONS) {
                Point i = p.add(d);
                if (!pieces.contains(i)) {
                    set.add(new SidePart(p, d));
                }
            }
        }

        Set<SidePart> counted = new HashSet<>();
        for (SidePart sidePart : set) {
            if (counted.contains(sidePart)) {
                continue;
            }

            Set<SidePart> groups = new HashSet<>();
            buildGroup(set, sidePart, groups);

            counted.addAll(groups);
            sides++;
        }
        return sides;
    }

    private static void buildGroup(Set<SidePart> set, SidePart sidePart, Set<SidePart> groups) {
        if (!set.contains(sidePart)) {
            return;
        }

        if (groups.contains(sidePart)) {
            return;
        }
        groups.add(sidePart);

        Point direction = sidePart.direction;
        Point source = sidePart.source;
        if (direction.x != 0) {
            buildGroup(set, new SidePart(source.add(new Point(0, 1)), direction), groups);
            buildGroup(set, new SidePart(source.add(new Point(0, -1)), direction), groups);
        } else {
            buildGroup(set, new SidePart(source.add(new Point(1, 0)), direction), groups);
            buildGroup(set, new SidePart(source.add(new Point(-1, 0)), direction), groups);
        }

    }

    record SidePart(Point source, Point direction) {
    }

      • [^] # Re: 12ème jour

        Posté par  . Évalué à 1 (+0/-0).

        193ms première évaluation
        1,3ms pour la 100ème évaluation (Java , c'est du Diesel)

    • [^] # Re: 12ème jour

      Posté par  . Évalué à 2 (+0/-0). Dernière modification le 13 décembre 2024 à 21:27.

      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.

  • # 13ème jour

    Posté par  . Évalué à 3 (+2/-0).

    Aujourd'hui, je me suis dit que c'était le bon jour pour essayer une IA. Voir ce que cela donnerai.

    Je l'ai fait d'abord en Java en utilisant un Mistral (medium) car j'étais persuadé qu'il arriverait à me donner la bonne réponse.
    Après 10min à debug le code, j'avais la bonne réponse pour la première partie.

    Pour la deuxième partie , je lui ai demandé d'utiliser Apache Commons Math. En soit ,le code était correcte.
    Il y avait juste < 100 qui était resté, et il y avait un problème de cast à la sortie Apache Commons Math , où on sort des Double qu'il faut arrondir et non trunc.

    Vu que j'étais persuadé que j'aurai été plus vite avec Python. J'ai fait aussi l'exercice en python avec numpy :)
    J'ai aussi utilisé une IA pour voir et çà fonctionne.
    Par contre, bizarrement, il gérait encore plus mal la lecture des données que j'ai du aussi réecrire complétement.

    def solve_for_machine(xA, yA, xB, yB, xPrize, yPrize):
    # Set up the matrix and vectors
    coefficients = np.array([[xA, xB], [yA, yB]])
    constants = np.array([xPrize, yPrize])

    try:
        # Solve the system of equations
        solution = np.linalg.solve(coefficients, constants)
        a, b = solution

        a = round(a)
        b = round(b)

        verifyX = a*xA + b*xB
        verifyY = a*yA + b*yB

        # Check if the solution is valid
        if 0 <= a and 0 <= b and verifyX == xPrize and verifyY == yPrize:
            return int(3 * a + b)
    except np.linalg.LinAlgError:
        pass

    return -1  # No valid solution found

    • [^] # Re: 13ème jour

      Posté par  . Évalué à 4 (+2/-0).

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

    • [^] # Re: 13ème jour

      Posté par  . Évalué à 2 (+2/-0).

      Ouh la, vous avez utilisé l'artillerie lourde :)

      Comme c'est un système de 2 équations à 2 inconnus, j'ai utilisé la méthode de Kramer.
      Désolé pour le nommage des variables.

      fn tokens(ax: i64, ay: i64, bx: i64, by: i64, px: i64, py: i64) -> i64 {
    let det1 = bx * py - by * px;
    let det2 = bx * ay - ax * by;
    if det1 % det2 != 0 {
        return 0;
    }
    let x = det1 / det2;
    let p = px - x * ax;
    if p % bx != 0 {
        return 0;
    }
    let y = p / bx;
    if x < 0 || y < 0 {
        return 0;
    }
    3 * x + y
}

  • # 14ème jour

    Posté par  . Évalué à 3 (+3/-0).

    La partie 1 est assez facile car on peut calculer directement la position d'un robot à 100ème seconde sans avoir à calculer les précédentes secondes.

    La partie 2 n'est pas très claire et il faut d'abord visualiser l'image.
    En discutant un peu, il y a plein de manières différentes de détecter cette image mais pour ma part, j'ai utilisé l'heuristique suivante.
    J'ai cherché le premier moment où toutes les positions de robots étaient distinctes.

    Pour cela, j'ai utilisé un tableau grid de tailles 101x103 et pour savoir si les positions sont distinctes à la seconde i, je regarde pour chaque position (px, py) de robots, si grid[px*101+py] == i. Si c'est le cas, j'ai deux positions non distinctes.
    Sinon, j'affecte grid[px*101+py] = i.

    L'avantage de cette méthode est que je peux réutiliser mon tableau à chaque itération sans avoir à le réinitialiser ou en créer un autre.

    J'ai également parallélisé le processus avec des threads.
    Un thread va travailler sur un segment de 20 secondes. Si il trouve une solution, on s'arrête. Sinon, il va travailler sur le prochain segment de 20 secondes pas encore attribué à un thread.

    440 microsecondes pour les deux parties.

    • [^] # Re: 14ème jour

      Posté par  . Évalué à 4 (+2/-0).

      Je viens de finir le 14ème jour à mon tour et en effet, le plus difficile dans la deuxième partie était de savoir ce que l'on cherche. Oui, certes, il y a bien une description claire de ce que c'est censé représenter, mais rien qui concerne la façon dont c'est construit dans les faits.

      Ce qui était intéressant ici, c'est qu'en examinant les dimensions de la grille, on pouvait en déduire relativement facilement, de proche en proche, que tous les robots reviennent tous à leur position initiale en « largeur × hauteur » secondes, ni plus ni moins.

      Ça permet de savoir qu'il y a 10403 images à examiner, ce qui est envisageable mais reste très long si on les fait défiler dans un fichier texte, par exemple. À raison d'une dizaine d'images par seconde, il y en aurait pour vingt bonnes minutes à condition de ne pas la rater quand elle passe…

      On ne savait pas non plus si la figure était évidée ou pleine. Dans le second cas, il suffit de chercher une séquence de robots consécutifs suffisamment longue. Six à huit robots consécutifs dépassent largement ce que le hasard peut produire et si cette séquence existe, l'éditeur la trouvera forcément. C'est assurément cette voie qu'il faut suivre, à mon avis.

      Malheureusement, pour une raison qui m'échappe un peu, et probablement en considérant le nombre limité de robots par rapport à la taille de la grille, j'ai estimé que la figure devait être constituée de segments non verticaux ni horizontaux et je suis parti directement sur l'examen des images. J'ai fini par générer un gros img.raw à peu près carré, l'ouvrir avec GIMP et chercher l'image dedans.

      J'ai cherché le premier moment où toutes les positions de robots étaient distinctes.

      C'était une bonne idée, même si elle n'était pas garantie car l'image n'utilise pas la totalité des robots sur la carte. Mais si on considère que les données initiales sont obtenus en partant du résultat, ça fait sens.

      Rétrospectivement, on voit aussi que la fameuse colonne médiane peut apporter beaucoup d'infos également… :-)

    • [^] # Re: 14ème jour

      Posté par  . Évalué à 1 (+1/-0).

      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.

      • [^] # Re: 14ème jour

        Posté par  . Évalué à 1 (+0/-0).

        Pour la partie 2, j'ai opté pour un algo simple.

        Je compte le nombre de sapin avec au moins un autre adjacent.

        Ce nombre change à chaque tour. A chaque fois que je trouvai un maximum. J'affiche la carte.

        A un momemt le premier maximum affiche le sapin.

  • # jour 16

    Posté par  . Évalué à 4 (+2/-0).

    Un classic parcours de graphe, vive didi dijkstra.

    • [^] # Re: jour 16

      Posté par  . Évalué à 3 (+3/-0).

      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.

      • [^] # Re: jour 16

        Posté par  . Évalué à 3 (+1/-0).

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

        • [^] # Re: jour 16

          Posté par  . Évalué à 1 (+0/-0).

          Ce n'est pas un simple Dijkstra.

          Perso , j'ai du combiner le déplacement & la rotation.
          Au final même pour simplifier la partie 2, j'ai revu mon algo pour considérer la rotation comme un mouvement.

          Ensuite pour la partie 2, j'utilise la map de poids de la partie 1.

          Je pars du start et je parcours en profondeur ma map de poids.

          Je passe d'un poids à l'autre récursivement , si le poids d déplacement ou une rotation correspond au poids minimum que j'avais constaté.

          • [^] # Re: jour 16

            Posté par  . Évalué à 3 (+3/-0).

            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.

  • # 17ème jour

    Posté par  . Évalué à 2 (+2/-0).

    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
}

    • [^] # Re: 17ème jour

      Posté par  . Évalué à 2 (+1/-0).

      Hello,

      J'ai procédé de cette manière pour la partie 2.

      Ce matin pendant le travail, j'ai tenté de brute-force, je suis monté à plusieurs milliard de possibilité testé :O)

      Ce midi:
      J'ai modifié mon Engine pour qu'elle affiche le code Java équivalent à chaque opération.

      Sur la base du code Java et l'impression du résultat en binaire
      Que le bit de A était consommé progressivement par le programmme pour construire la sortie.
      J'ai alors compris que le programme avançait par paquet de 3 à 6 bits.

      J'avais presque la réponse ce midi. Je trouvais un A qui me donnait le bon résultat un chiffre de plus ",2" :)

      Ce soir:
      J'ai revu plein de fois de mon algo pour m’apercevoir que j'avais merdé un <= en < dans ma fonction de contrôle progressif.
      Résultat, il me trouvait toujours un resultat matchant avec un chiffre de plus :O)

  • # 18ème jour

    Posté par  . Évalué à 1 (+1/-0). Dernière modification le 18 décembre 2024 à 15:32.

    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.

    • [^] # Re: 18ème jour

      Posté par  . Évalué à 2 (+1/-0).

      Pour la première partie, j ai fait un simmle dijkstra.
      Pour la deuxième partie, j ai brute force ce dernier à chaque pixel. J étais un peu déçu car je m attendais à une deuxième bien plus complexe.

      Si le problème de performance aurait été plus complexe. En demultipliant la map d input. J aurai probablement tenter. De conserver le path dans mon dijkstra. De cette manière, j aurai pu déterminer rapidement les cases à mettre en jour quand c est dernier sont affecté par la mise à jour…

      • [^] # Re: 18ème jour

        Posté par  . Évalué à 4 (+2/-0).

        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.

  • # jour 19 - on souffle

    Posté par  . Évalué à 4 (+2/-0).

    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.

    • [^] # Re: jour 19 - on souffle

      Posté par  . Évalué à 2 (+2/-0).

      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.

      • [^] # Re: jour 19 - on souffle

        Posté par  . Évalué à 5 (+3/-0).

        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 …

      • [^] # Re: jour 19 - on souffle

        Posté par  . Évalué à 3 (+1/-0). Dernière modification le 22 décembre 2024 à 18:13.

        Après avoir naïvement tenté une approche récursive, qui donne malgré tout de bons résultats pour la première partie (durant laquelle il s'agit juste de savoir si un motif peut être composé ou non, donc où il suffit de s'arrêter à la première solution, qui arrive assez vite), j'ai fini par faire exactement la même chose :

        def find_prefixes_2(string, towels):
    positions = [ 1 ] + [ 0 ] * len(string)

        En Python sur une machine de 2008, j'obtiens 0m0,182s avec l'affichage des résultats dans un terminal Gnome.

  • # 20ème jour

    Posté par  . Évalué à 2 (+2/-0).

    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.

  • # 21ème jour

    Posté par  . Évalué à 3 (+3/-0). Dernière modification le 21 décembre 2024 à 19:29.

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

    • [^] # Re: 21ème jour

      Posté par  . Évalué à 2 (+1/-0). Dernière modification le 23 décembre 2024 à 10:03.

      J'ai lutté sur celui-ci… presque 9h.

      Pour la partie 1, j'ai tenté trouver un ordre dans les mouvements qui était toujours valide via un sort.
      Finalement, je m'étais rabattu sur une fonction qui donnait tous les mouvements possibles.

      Pour la partie 2, mon code de la partie 1 explosait même pour un chiffre à profondeur de 4.
      Je me suis donc douté qu’il fallait faire un min. J’ai rapidement résolut ce problème avec un cache pour la programmation dynamique.
      Par erreur, je pensai que çà exploserai en temps. Si je considérai tous les mouvements d’une case à l’autre.
      Donc, j’ai tenté de chercher une distribution qui marchait dans tous les cas. J’ai réussi à trouver une combinaison qui valider pour la profondeur 2 et 3 pour les 2 jeux de test (j’ai obtenu la validation à 3 avec mon code de la partie 1) mais bien sûr, çà ne fonctionnait pas en profondeur 25. Il y a un cas non optimum qui doit apparaitre.
      J’ai finalement tenté d’envisager tous les chemins possibles et j’ai été surpris de voir que cela marchait.
      Comme quoi, quand on part sur une mauvaise piste, on bloque dessus.

          private static long processDoors(List<String> doors) {
        long sum = 0;
        for(String door : doors) {
            long messageLength = 0;
            String previous = "A";

            for(char c : door.toCharArray()) {  
                messageLength += recurse(0, handleNumPad.get(previous + c));
                previous = String.valueOf(c);
            }

            System.out.println(door + ":" +  messageLength);
            sum += messageLength * Long.valueOf(door.substring(0, door.length()-1));
        }
        return sum;
    }

    private static long recurse(int i, List<String> paths) {
        long sum = 0;

        Seek seek = new Seek(i, paths);
        Long cached = cacheResult.fromCache(seek);

        if(cached != null) {
            return cached;
        }

        if(i <= LIMIT) {
            long minPath = Long.MAX_VALUE;
             for(String path: paths) {
                 char previous = 'A';
                 long currentPath = 0;
                 for(char c: path.toCharArray()) {                   
                     currentPath += recurse(i + 1, handleArrowPad.get("" + previous + c));                   
                     previous = c;
                 }
                 if(currentPath < minPath) {
                     minPath= currentPath;
                 }
             }
             sum+= minPath;
        } else {
            sum = 1;
        }
        cacheResult.setInCache(seek, Long.valueOf(sum));
        return sum;
    }

  • # 22ème jour

    Posté par  . Évalué à 2 (+2/-0).

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

    • [^] # Re: 22ème jour

      Posté par  (site web personnel, Mastodon) . Évalué à 5 (+2/-0).

      Merci pour la persévérance. Cela peut paraître idiot, mais, je continue à lire tout ça même si je ne comprends pas grand chose.

      « Tak ne veut pas quʼon pense à lui, il veut quʼon pense », Terry Pratchett, Déraillé.

    • [^] # Re: 22ème jour

      Posté par  . Évalué à 1 (+0/-0). Dernière modification le 23 décembre 2024 à 10:16.

      Il n’était pas vraiment intéressant.
      Pareil, j’ai suivi les instructions. J’ai été dessus quand je me suis rendu compte que le but de la deuxième partie n’était pas de trouver le secret initial ou un truc du genre.

      Je n’ai pas cherché à optimiser, j’ai tout stocker dans un new long[2500][2001]

      Puis, j’ai distribué dans une map 

      Map<Sequence, Map<Integer, SequenceResult>> firstGainsByBuyerBySequence;
public record Sequence(int[] fours){}
public record SequenceResult(int buyer, long endNumber, int[] fours){}

  • # jour 23 - cracra

    Posté par  . Évalué à 3 (+1/-0). Dernière modification le 23 décembre 2024 à 14:22.

    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.

    • [^] # Re: jour 23 - cracra

      Posté par  . Évalué à 1 (+0/-0).

      Ce n'est vraiment pas terrible comme performance :)

      En gros à la lecture, je charge mes map & mes liens.
      Puis, je regroupe mes éléments.
      A la fin, je filtre pour trouver le plus gros groupe.

          public static Map<String, Node> nodesByCode = new HashMap<>();
    public static Map<Node, List<Link>> linksByNodes = new HashMap<>();

    public record Node(String name) implements Comparable<Node> {
          //...
        }

        public record Link(Node left, Node right) {
          // ...
    }

        public record Group(TreeSet<Node> members) {
         // ...
        }

        public void main() {
         //...


         Set<Group> groups = new HashSet<>();
         for (Map.Entry<Node, List<Link>> entry : linksByNodes.entrySet()) {
                  Node a = entry.getKey();
                  TreeSet<Node> members = new TreeSet<>();
                  recurseGroup(members, a);
                  if (members.size() > 3) {
                           groups.add(new Group(members));
                  }
         }
     /* Chercher le plus grand groups */
        }

        private static void recurseGroup(TreeSet<Node> members, Node a) {
        for (Node n : members) {

            if (linksByNodes.get(a).stream().filter(l -> l.match(n)).count() == 0) {
                return;
            }

        }

        members.add(a);
        for (Link link : linksByNodes.get(a)) {
            Node b = link.getOther(a);
            if (members.contains(b)) {
                continue;
            }

            recurseGroup(members, b);
        }

    }

      Je fais 215ms
      et si je répète l'opération plusieurs fois , je descends à 15ms pour le même traitement.

      • [^] # Re: jour 23 - cracra

        Posté par  . Évalué à 4 (+2/-0).

        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.

    • [^] # Re: jour 23 - cracra

      Posté par  . Évalué à 2 (+2/-0).

      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.

      • [^] # Re: jour 23 - cracra

        Posté par  . Évalué à 2 (+0/-0).

        Alors, j'ai fini par m'y remettre APRÈS les fêtes, car il me manque actuellement les deux parties du 21 (le numpad) et les secondes parties des 22 et 23. Et alors autant, chaque année, les premiers exercices de l'AoC apparaissent « bugués » jusqu'à ce qu'on lise les petites lignes et que l'on saisisse la subtilité, autant je sèche un peu sur la deuxième partie de celui-ci.

        J'ai également constaté que le degré de chaque machine était exactement 13 partout. On ne peut pas rechercher un graphe K14 car il serait isolé du reste du réseau (mais pourquoi pas, après tout).

        Un peu fatigué à ce stade, j'ai choisi de faire une exploration en n*(n-1)/2 pour comparer toutes les paires possibles et déterminer le nombre maximum de nœuds en commun pour chaque partie, puis voir si l'on peut retrouver une clique de cette taille, quitte à redescendre dans la négative. Et je suis également arrivé à 11 voisins.

        En sélectionnant toutes les machines qui ont exactement onze voisins, et en triant ceux-ci dans chaque liste, j'obtiens ceci :

        bk [      'du', 'dv', 'gm', 'hc', 'ny', 'ot', 'um', 'xl', 'ze', 'zy',               'ie' ]
du ['bk',       'dv', 'gm', 'hc', 'ny', 'ot', 'um', 'xl', 'ze', 'zy',               'ds' ]
dv ['bk', 'du',       'gm', 'hc', 'ny', 'ot', 'um', 'xl', 'ze', 'zy',               'ij' ]
gm ['bk', 'du', 'dv',       'hc', 'ny', 'ot', 'um', 'xl', 'ze', 'zy',               'ga' ]
hc ['bk', 'du', 'dv', 'gm',       'ny', 'ot', 'um', 'xl', 'ze', 'zy',               'ky' ]
ny ['bk', 'du', 'dv', 'gm', 'hc',       'ot', 'um', 'xl', 'ze', 'zy',               'jx' ]
ot ['bk', 'du', 'dv', 'gm', 'hc', 'ny',       'um', 'xl', 'ze', 'zy',               'lp' ]
um ['bk', 'du', 'dv', 'gm', 'hc', 'ny', 'ot',       'xl', 'ze', 'zy',               'nq' ]
xl ['bk', 'du', 'dv', 'gm', 'hc', 'ny', 'ot', 'um',       'ze', 'zy',               'kr' ]
ze ['bk', 'du', 'dv', 'gm', 'hc', 'ny', 'ot', 'um', 'xl',       'zy',               'if' ]
zy ['bk', 'du', 'dv', 'gm', 'hc', 'ny', 'ot', 'um', 'xl', 'ze',                     'kf' ]

        La diagonale correspond à la « connexion de loopback » (avec soi-même) qui bien sûr n'existe pas, et la colonne de droite est le nœud qui comble le trou en temps normal, qui permet de maintenir treize voisins et accessoirement maintient la connectivité avec le reste du réseau.

        J'ai soumis « bk,du,dv,gm,hc,ny,ot,um,xl,ze,zy » (onze nœuds, donc) mais ce n'est pas la bonne réponse…

        On remarque que les listes ci-dessus contiennent en fait onze nœuds et pas treize. En effet, la liste complète est en réalité

        bk [      'du', 'dv', 'gm', 'hc', 'ny', 'of', 'ot', 'um', 'uy', 'xl', 'ze', 'zy',               'ie' ]
du ['bk',       'dv', 'gm', 'hc', 'ny', 'of', 'ot', 'um', 'uy', 'xl', 'ze', 'zy',               'ds' ]
dv ['bk', 'du',       'gm', 'hc', 'ny', 'of', 'ot', 'um', 'uy', 'xl', 'ze', 'zy',               'ij' ]
gm ['bk', 'du', 'dv',       'hc', 'ny', 'of', 'ot', 'um', 'uy', 'xl', 'ze', 'zy',               'ga' ]
hc ['bk', 'du', 'dv', 'gm',       'ny', 'of', 'ot', 'um', 'uy', 'xl', 'ze', 'zy',               'ky' ]
ny ['bk', 'du', 'dv', 'gm', 'hc',       'of', 'ot', 'um', 'uy', 'xl', 'ze', 'zy',               'jx' ]
of ['bk', 'du', 'dv', 'gm', 'hc', 'ny',       'ot', 'um',       'xl', 'ze', 'zy',               'fp', 'kv' ] *********
ot ['bk', 'du', 'dv', 'gm', 'hc', 'ny', 'of',       'um', 'uy', 'xl', 'ze', 'zy',               'lp' ]
um ['bk', 'du', 'dv', 'gm', 'hc', 'ny', 'of', 'ot',       'uy', 'xl', 'ze', 'zy',               'nq' ]
uy ['bk', 'du', 'dv', 'gm', 'hc', 'ny',       'ot', 'um',       'xl', 'ze', 'zy',               'ce', 'pp' ] *********
xl ['bk', 'du', 'dv', 'gm', 'hc', 'ny', 'of', 'ot', 'um', 'uy',       'ze', 'zy',               'kr' ]
ze ['bk', 'du', 'dv', 'gm', 'hc', 'ny', 'of', 'ot', 'um', 'uy', 'xl',       'zy',               'if' ]
zy ['bk', 'du', 'dv', 'gm', 'hc', 'ny', 'of', 'ot', 'um', 'uy', 'xl', 'ze',                     'kf' ]

        On remarque que les colonnes of et uy sont partagées par presque tous les nœuds sauf deux (matérialisés par les trous hors diagonale). Ces deux trous correspond précisément à un seul lien manquant entre ces deux machines, ce qui suffit à briser la clique.

        J'ai malgré tout ajouté ces deux machines à la liste ci-dessus (en préservant l'ordre alphabétique), mais ce n'est pas la bonne réponse non plus.

        À ce stade, je veux bien un indice si quelqu'un voit la faille.

  • # Jour 24

    Posté par  . Évalué à 1 (+0/-0).

    Pour la partie 1, il suffit de suivre les instructions et valider les TU.

    Pour la partie 2, je pense que je n'ai pas choisie la solution la plus rapide. Je mets environ 1min pour trouver la solution.

    Je fais une fonction recursive qui va descendre à une profondeur de 44.

    En gros, je vais valider l'addition de 2 entiers en commençant par les bits de poids faible jusqu'au bit de poids fort.
    Quand j'identifie une erreur j'applique une permutation de sortie.

    Pour valider, l'addition de 2 entiers, je ne considère pas tous les entiers 244. çà serait trop long.
    Je construits des additions particulières en binaires qui vont valider toutes les retenus à la profondeur ou je suis. A chaque addition , je valide la commutativité de mon addition.
    Par exemple , à la profondeur 3
    1
    1

    1
    11

    1
    111

    Mais je vais aussi valider le merge de nombre binaire sans retenu et je vérifie encore la commutativité.
    1
    0

    10
    101

    Bien paramétré cette fonction de validation a été déterminant car c'est elle qui garantit qu'au fur et à mesure de l'exploration des combinatoire possible , je n'engendre pas de régression dans les chiffres et çà me permet de déterminer rapidement une impasse dans le choix de la permutation

    L'autre point important, c'est quand on détecte une anomalie, je vais déterminer les bits concernés et en déduire les portes éligibles à la permutation.
    çà limite mon exploration.

        public static long wrongBit(long expected , long result) {
        return (expected ^ result);
    }

    public static long isOk(long current) {
        report.start("isOk");
        long wrong = 0;
        long mask = current;

        long x = 0;
        long r ;
        while(current > 0) {
            long expectedAddOne = 1l + current;         
            r = evaluateNetwork(1l, current);
            if(r < 0) {
                return -1;
            }
            wrong = wrong | wrongBit(expectedAddOne, r);
            r = evaluateNetwork( current, 1l);
            if(r < 0) {
                return -1;
            }
            wrong = wrong | wrongBit(expectedAddOne, r);
            r = evaluateNetwork( current, 0l);
            if(r < 0) {
                return -1;
            }
            wrong = wrong | wrongBit(current, r);

            r = evaluateNetwork( 0l, current);
            if(r < 0) {
                return -1;
            }
            wrong = wrong | wrongBit(current, r);

            long a = 1l << x;
            long b = mask - a;
            r = evaluateNetwork( a, b);
            if(r < 0) {
                return -1;
            }
            wrong = wrong | wrongBit(mask, r);

            r = evaluateNetwork( b, a);
            if(r < 0) {
                return -1;
            }
            wrong = wrong | wrongBit(mask, r);

            current = current >> 1l;
            x++;
        }

        report.end("isOk");
        return mask & wrong;



    }



    private static void recurseFixGates(Set<String> validated, int x) {

        if(x > maxDepth) {
            System.out.println(x + " " + validated.size() );
            maxDepth = x;
        }
        if(validated.size() % 2 == 1) {
            System.out.println("Whats");
        }
        if (x == 44) {      

            if(validate()) {                        
                String resultsAsString = validated.stream().sorted().collect(Collectors.joining(","));
                if (!availablesResults.contains(resultsAsString)) {
                    availablesResults.add(resultsAsString);
                    System.out.println(resultsAsString);
                }
                System.exit(0);
            }

            return;

        }
        if(validated.size() > 8) {
            return;
        }

        long right = 1l << (x+1);


        // System.out.println(x + ":" + left.toString(2) + " + " + right.toString(2) + "
        // =>" + z.toString(2));
        long wrong = isOk(right);
        if(wrong < 0) {
            System.out.println("There is a loop : " +x);
            return;
        }

        if (wrong != 0) {

            // System.out.println("Need fix to get " + expect.toString(2));
            Set<Gate> changes = computeRelated(wrong);

            for (Gate a : changes) {
                if (validated.contains(a.wireOutput)) {
                    continue;
                }
                for (Gate b : gates) {
                    if (a.equals(b) || validated.contains(b.wireOutput) || lessZ(b.wireOutput, x)) {
                        continue;
                    }

                    String tmp = b.wireOutput;
                    b.wireOutput = a.wireOutput;
                    a.wireOutput = tmp;
                    try {
                        if (isOk(right) == 0l || (x <= 2 && isOk(right) == -1)) {
                            validated.add(a.wireOutput);
                            validated.add(b.wireOutput);

                            recurseFixGates(validated, x + 1);
                            validated.remove(a.wireOutput);
                            validated.remove(b.wireOutput);

                            if(validated.size() % 2 == 1) {
                                System.out.println("Whats");
                            }
                        }
                    } finally {
                        tmp = b.wireOutput;
                        b.wireOutput = a.wireOutput;
                        a.wireOutput = tmp;
                    }

                }
            }
        } else {
            recurseFixGates(validated, x + 1);
        }
    }

    private static boolean validate() {

        for(long x=0;x < 43;x++) {
            long a = (1l << x)-1;
            long b = 13;            
            if((a+b) != evaluateNetwork(a, b)) {
                return false;
            }
        }
        return true;
    }

    public static boolean lessZ(String name, int x) {
        if(! name.startsWith("z")) {
            return false;
        }

        return Integer.valueOf(name.substring(1)) <= x;
    }

    public static Gate findByOutput(String name) {
        return gates.stream().filter(g->g.wireOutput.equals(name)).findFirst().orElse(null);
    }

    private static Set<Gate> computeRelated(long wrong) {
        if(wrong == -1) {
            return new HashSet<Aoc2024s24p2.Gate>(gates);
        }
        Set<Gate> related = new HashSet<Aoc2024s24p2.Gate>();
        for(int x=0;x < 45;x++) {
            long mask = 1l << x;
            if((wrong & mask)> 0) {
                Gate gate = findByOutput(zindex(x));
                recurseRelated(related, gate);                                                                  
            }
        }

        return related;
    }

    private static void recurseRelated(Set<Gate> related, Gate gate) {
        if(related.contains(gate) || gate == null) {
            return;
        }
        related.add(gate);              
        recurseRelated(related, findByOutput(gate.wireLeft.name));
        recurseRelated(related, findByOutput(gate.wireRight.name));


    }

    private static long evaluateNetwork(Long left, Long right) {
        report.start("evaluateNetwork");
        if(left != null) {
            initiate("x", left);
        }
        if(right != null) {
            initiate("y", right);
        }

        Map<Gate, AtomicInteger> updated = new HashMap<Aoc2024s24p2.Gate, AtomicInteger>();
        /*for(Wire wire : wireByName.values()) {
            if(! (wire.name.startsWith("x") || wire.name.startsWith("y"))) {
                wire.state = null;
            }
        }*/
        boolean haveUpdate = false;
        do {
            haveUpdate = false;

            for (Gate gate : gates) {
                if (gate.update()) {

                    int count = updated.computeIfAbsent(gate, k->new AtomicInteger()).incrementAndGet();                                        
                    if (count > 2) {
                        report.end("evaluateNetwork");
                        return -1;
                    }
                    haveUpdate = haveUpdate || true;                    
                }

            }
        } while (haveUpdate);

        int x = 0;

        long z = 0;
        while(wireByName.get(zindex(x)) != null) {
            //System.out.println(x + " => " + wireByName.get(zindex(x)).state );
            Wire wire = wireByName.get(zindex(x));
            if(wire.state != null && wire.state) {
                long v =  1l << x;

                //System.out.println(v);
                z = z + v;
            }
            x++;
        }

        report.end("evaluateNetwork");
        return z;
    }

    private static void initiate(String s, long left) {

        for (long x = 0; x < 45; x++) {
            long mask = 1l << x;
            if ((mask & left) > 0) {
                wireByName.get(index(s, x)).state = true;
            } else {
                wireByName.get(index(s, x)).state = false;
            }
        }

    }

    public static String index(String s, long x) {
        return (x < 10 ? s + "0" : s) + x;

    }

    public static String zindex(long x) {
        return (x < 10 ? "z0" : "z") + x;
    }

  • # Jour 25

    Posté par  . Évalué à 1 (+0/-0).

    C'est null. D'un point de vue niveau, c'est digne des premiers jours.

    Dans l'ensemble, l'ensemble les exos sont beaucoup plus simple que les autres années.

    Hormis le 21, je n'ai eu aucune difficultés. Et encore, c'est de ma faute. Je me suis bloqué sur une mauvaise piste.

    Je regrette qu'il n'y a eu aucun exercice avec de la 3D du niveau du 24 de 2023 ou du niveau 22 de 2021.
    Pareil, on n'a pas eu de traditionnel problème de séquence de motif sur un plan 2D …
    Aucun problème de plan infini.

    • [^] # Re: Jour 25

      Posté par  . Évalué à 2 (+2/-0). Dernière modification le 25 décembre 2024 à 10:37.

      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.

      • [^] # Re: Jour 25

        Posté par  . Évalué à 2 (+0/-0).

        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 …

        • [^] # Re: Jour 25

          Posté par  . Évalué à 1 (+1/-0).

          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

          • [^] # Re: Jour 25

            Posté par  . Évalué à 2 (+0/-0).

            Mes temps n'ont rien de fantaisistes.

            Je n'en doute pas, j'ai vu des temps comparable en Rust et en Zig.

            Mais comme tu dis il faut mesurer la même chose.

  • # Rust power

    Posté par  . Évalué à 3 (+1/-0).

    https://github.com/indiv0/aoc-fastest

    Les 49 problèmes en moins de 1ms, c'est-à-dire en moins de un millions de nanosecondes.

    • [^] # Re: Rust power

      Posté par  . Évalué à 2 (+0/-0).

      Pardon mais ça https://github.com/indiv0/aoc-fastest/blob/c3a2c3fa992441a481e6c15927b2cca28d715040/2024%2Fd17p2.rs

      C'est pas du rust, si le fichier a bien l'extension rs, c'est quasiment uniquement de l'assembleur.

      C'est le problème à se concentrer uniquement sur les performances, on fini par tordre les problèmes à des niveaux qui n'ont aucun sens.

      Pour donner un autre exemple, je mettais amusé à résoudre une quinzaine d'exercices du projet Euler en meta programmation C++. Le binaire final n'avait pas d'autres instructions que return la valeur solution. Est-ce que ça veut dire que le C++ est le langage le plus performant ? Certainement pas.

      C'est rigolo pour l'exercice et c'est un travail très complexe qui a été abattu, mais est-ce que pour autant ça permet de montrer "la puissance de rust" ? Personnellement je ne crois pas

      https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll

      • [^] # Re: Rust power

        Posté par  . Évalué à 2 (+1/-0).

        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.

        • [^] # Re: Rust power

          Posté par  . Évalué à 2 (+0/-0).

          C'est pour ça que je le mettais en parallèle avec la méta programmation du C++ qui permet de faire faire le calcul à la compilation.

          https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll

Envoyer un commentaire

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.