Advent of code 2020

Coucou,

Comme chaque année, le site web Advent Of Code propose chaque jour des problèmes, de plus en plus durs, dont il faut programmer des solutions.

Si ça intérèsse des personnes de participer, j’ai créé un classement privé (private leaderboard) et on peut discuter des problèmes ici (avec spoilers quand on parle des solutions, pour éviter de divulgacher les solutions à ceux qui ne les ont pas encore trouvées).

Le code pour rejoindre le private leaderboad est le 786573-c9051ee4.

ps: pour faire des spoilers, il faut utiliser les balises [spoiler] et [/spoiler]

2 J'aime

Discussion sur le jour 4

Bon la deuxième partie était un peu chiante aujourd’hui (d’ailleurs ça se voit au ratio d’étoiles grises et d’étoiles jaunes), et j’ai dû utiliser des expressions régulières pour la couleur des cheveux et l’ID du mot de passe (oublier le $ à la fin m’a posé problème d’ailleurs).
Du coup je me demande s’il n’y a pas une méthode plus simple pour vérifier ces cas-là, qui ne fait pas appel à des expressions régulières (et sans s’embêter à recoder des mini-expressions régulières à la main). Est-ce que quelqu’un ici a des idées ?

Perso j’utilise python et j’ai fait des choses « manuelles » à chaque fois, par exemple pour les IDs:

set(passport_field[1::]).issubset(set('abcdef0123456789'))

Idem, j’ai tout fait en Rust, et j’ai juste écrit les règles manuellement. C’est trop galère de faire des comparaisons d’entiers en regex. Du coup, ça donne un truc du genre :

  • Essayer de cast les int purs
  • Manuellement tester le # en début de field et essayer de cast le reste en base 16
  • Faire des match sur les 2 derniers caractères pour différencier les in et cm

2ème partie du 10 décembre

Je suis assez content de ma solution, j’étais parti sur un truc qui prenait beaucoup trop de temps (dans l’idée récursif), puis je suis tombé sur ce meme qui m’a donné l’idée de l’algo linéaire.


1 J'aime

Du coup tu fais comment ? Ici, je fais une récursion avec de la mémoisation, et ça se passe pas trop mal, mais je trouve ça un peu moche (en tout cas la récursion).

fn count(mut memo: &mut HashMap<Vec<i64>, i64>, arr: &[i64])-> i64 {
    match memo.get(&(arr.to_vec())) {
        Some(i) => *i,
        None => {
            match arr.len() {
                2 => {
                    if arr[1] - arr[0] <= 3 {
                        memo.insert(arr.to_vec(), 1);
                        return 1
                    } else {
                        memo.insert(arr.to_vec(), 0);
                        return 0
                    }
                },
                _ => {
                    if arr[1] - arr[0] > 3 {
                        return 0;                        
                    }
                    let first: i64 = count(&mut memo, &[&arr[0..1], &arr[2..]].concat());
                    let second: i64 = count(&mut memo, &arr[1..]);
                    let count: i64 = first + second;
                    memo.insert(arr.to_vec(), count);
                    return count;
                }
            }
        }
    }
}

J’ai un peu de mal à expliquer ce que je fais, je vais essayer de le faire à peu près clairement. L’idée, c’est de parcourir la liste triée des adaptateurs, et à chaque fois de regarder à quels adaptateurs ça peut mener et compter le nombre de « chemins » qui y mènent.
Un petit exemple :
adapters = [1, 2, 3]
On part de 0, avec un compte de 1.
0 peut mener à 1, 2 et 3, donc on ajoute 1 à ceux là.
Ensuite 1 peut mener à 2 et 3, et comme un seul chemin a mené à 1, on ajoute 1 à count(1).
2 peut mener à 3, et comme count(2) = 2 chemins y mènent, on ajoute 2 à count(3).
Puis on continue pour chaque adaptateur, et le compte du plus grand adaptateur est le nombre demandé pour le puzzle.

import numpy as np

with open("input10") as f:
    L = [int(s) for s in f.readlines()]
L.append(0)

adapters = np.sort(np.array(L))

count = np.zeros(len(adapters), dtype=int)
count[0] = 1
for i,n in enumerate(adapters):
    count[i+1+np.nonzero([adapters[i+1:i+4] - n <= 3])[1]] += count[i]
print(count[-1])

J’ai la même méthode que Grode, mais en partant de la fin :
Une fois les adaptateurs triés, pour chaque adaptateur je vais compter le nombre de combinaisons qui permettent d’atteindre le but.
Pour le dernier adaptateur, il y a un seul chemin. Pour l’adaptateur précédent, soit il peut passer par l’adaptateur à jolt +1 (s’il existe), soit à jolt +2, ou jolt+3. Du coup, le nombre de chemins qui permettent d’aller de cet adaptateur au dernier, c’est la somme des chemins des adaptateurs de j+1, j+2, j+3.

Et en construisant ça jusqu’à 0, la valeur en 0 c’est « le nombre de combinaisons qui amènent au but, en partant de 0 »

fn exo2(input: &String) -> MyResult<i64> {
    let mut adaptators: Vec<i64> = input.lines().map(|v| v.parse::<i64>().unwrap()).collect();
    adaptators.push(0);
    adaptators.sort();

    let mut combi_to_goal: HashMap<i64, i64> = HashMap::new();
    combi_to_goal.insert(*adaptators.last().unwrap() + 3, 1);

    for jolt in adaptators.iter().rev() {
        let mut v = 0;
        for delta in 1..4 {
            v += combi_to_goal.get(&(jolt + delta)).unwrap_or(&(0));
        }
        combi_to_goal.insert(*jolt, v);
    }

    Ok(*combi_to_goal.get(&0).unwrap())
}

Jour 15

J’ai utilisé un dictionnaire python pour stocker le tour auquel le nombre apparait la dernière fois, et ça prend quand même 10 bonnes minutes à faire tourner, c’est normal ? Ou alors il y a quelque chose de beaucoup plus rapide que je n’ai pas vu ?
EDIT: En fait c’est parce que j’affichais quelque chose pour voir où ça en était et ça rendait le programme très lent, ça prend une quinzaine de secondes en fait, ce qui est honorable je pense.

Jour 15:

A priori, c’est des maths (ça s’appelle la séquence de Van Eck, https://oeis.org/A181391 ) et y’a pas mieux que bruteforcer la solution:

https://www.youtube.com/watch?v=etMJxB-igrc

Après, tu peux probablement accélérer ton code en utilisant des tableaux numpy de taille 30 millions pré-alloués et tout faire là dedans, tu devrais gagner un facteur 10 minimum à mon avis.