17ème jour

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>{
ifidx==0{
returnSome(a)
}
foriin0..8{
letai=a<<3|i;
ifletSome(output)=run_first_value(program,ai,0,0){
ifoutput==program[idx-1]{
ifletSome(q)=quine(program,ai,idx-1){
returnSome(q)
}
}
}
}
None
}