12ème jour

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

pubfn solve(input: &str)-> Result<(u32,u32)>{
letgrid=Grid::parse_with_padding(input,b'.')?;
letwidth=grid.width;
letmutgrid=grid.vec;
letmutstack=Vec::with_capacity(500);
letmutp1=0;
letmutp2=0;
foriin0..grid.len(){
letstart=grid[i];
ifstart.is_ascii_uppercase(){
letmutarea=0;
letmutperimeter=0;
letmutsides=0;
stack.push(i);
whileletSome(current)=stack.pop(){
ifgrid[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);
ifgrid[next]&127!=start{
perimeter+=1;
letc1=grid[current+side];
letc2=grid[next+side];
ifc1&127!=start||c2&127==start{
sides+=1;
}
}
}
}
p1+=area*perimeter;
p2+=area*sides;
stack.clear();
}
}
Ok((p1,p2))
}