Re: Jour 7

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

pubfn solve(input: &str)-> (u32,u64){
letinput=input.as_bytes();
letwidth=input.iter().position(|&b|b==b'\n').unwrap()+1;
letstart_pos=input.iter().position(|&b|b==b'S').unwrap();
letmutp1=0;
letmutcount=vec![0;width];
count[start_pos]=1;
for(delta,line_start)in(2*width..input.len()).step_by(2*width).enumerate(){
letstart=start_pos-delta-1;
letend=start_pos+delta+2;
foriinstart..end{
ifinput[line_start+i]==b'^'{
p1+=(count[i]!=0)asu32;
count[i-1]+=count[i];
count[i+1]+=count[i];
count[i]=0;
}
}
}
letp2=count.iter().sum();
(p1,p2)
}