rust bfs garder trace des parents

Bonjour,

j’explore le défis https://projecteuler.net/problem=736, même si je n’ai pas grand espoir de le résoudre.

J’ai fait un code qui me génère les pairs équivalents, maintenant j’aimerais observer les chemins menant à ces égalités. J’aimerai donc stocker dans un set les éléments visités ainsi que l’élément précédent.

use std::collections::{BTreeSet, VecDeque};
type Node = (u32,u32);

fn r((x,y) : Node) -> Node {
    (x + 1, 2 * y)
}
fn s((x,y) : Node) -> Node {
    (2 * x, y + 1)
}

fn solve_path_to_equality((a,b) : Node) -> bool {
    let mut to_visit: VecDeque<Node> = VecDeque::with_capacity(2_usize.pow(10));
    let mut visited = BTreeSet::new();
    to_visit.push_back((a, b));
    let mut n = 1_usize;
    loop {
        let (a, b) = to_visit.pop_front().unwrap();
        if !visited.insert((a,b)) { //it's not a new element
            continue;
        }
        
        let child1 = s((a, b));
        let child2 = r((a, b));
        n = n + 1;
        if child1.0 == child1.1 {
            println!("({}, {}) generated with s(x,y) | {}",child1.0, child1.1, (n as f64).log2().floor()+1f64);
        }
        n = n + 1;
        if child2.0 == child2.1 {
            println!("({}, {}) generated with r(x,y) | {}",child2.0,child2.1,(n as f64).log2().floor()+1f64);
        }
        to_visit.push_back(child1);
        to_visit.push_back(child2);
    }
}
fn main() {
    solve_path_to_equality((45, 90));
}

Le code est assez simple : je pars de (45,90) je génère les deux enfants : r(45,90) et s(45,90) je les ajoute à la fin de ma queue d’exploration je continue d’explorer en prenant de ma queue le premier élément.

je parcours ainsi en BFS les pairs. je chercher maintenant à construire le chemin de (45,90) à x,y avec x==y.

le problème c’est que je ne sais pas vraiment comment avoir une reférence / pointeur sur l’élément qui a générer la solution dans mon set l’idée est que chaque élément de mon set aille un pointeur sur son parent et lorsque je trouve une solution x==y je retrace la chaine comme une linkedlist.

Mais avec rust j’ai de la peine a déclarer les lifetimes de mes iterateurs (et la syntaxe pour déclarer un iterateur) qui doivent avoir une durée de vie équivalent à mon set.

est-ce que vous pourriez me donner un coup de main pour déclarer un iterateur de type I sur un tuple (u32,u32, I) contenu dans un BTreeMap. Est-ce qu’en ajoutant les éléments, l’arbre va s’équilibré et donc un itérateur peut devenir invalide selon l’implémentation ?

Sinon vous conseillez-quoi comme manière de stocker la chaine des parents, avoir un vec<u32> pour chaque élément retraçant le chemin en entier me semble très inefficace. Surtout que j’essaie d’être efficace car l’algo est exponentiel.

Salut, Ça m’intéresse aussi

Hello,

en effet je n’avais pas pensé à ça, je vais regarder pour ne plus utiliser le set mais uniquement la map sinon je stock 2 fois mon noeud.

@buffalo974 Voilà à quoi je suis arrivé, il y a encore le set, mais l’affichage des chemins fonctionne

use std::collections::{BTreeMap, BTreeSet, VecDeque};
use std::io::Write;
type Node = (u32, u32);

fn r((x, y): Node) -> Node {
   (x + 1, 2 * y)
}
fn s((x, y): Node) -> Node {
   (2 * x, y + 1)
}
#[inline]
fn find_function(child: Node, parent: Node) -> char {
   if child.0 - 1 == parent.0 {
       'r'
   } else {
       's'
   }
}

//using W:Write for file use
fn retrace_path<W: Write>(child: &Node, parents: &BTreeMap<Node, Node>, output:&mut W) -> std::io::Result<()>{
   match parents.get(child) {
       Some(parent) => {
           retrace_path(parent, parents,output)?;
           write!(output,"{} {:?} ", find_function(*child, *parent),*child)
       }
       None => {write!(output,"{:?} ",child)}
   }
}

fn solve_path_to_equality((a, b): Node) {
   let mut to_visit: VecDeque<Node> = VecDeque::with_capacity(2_usize.pow(10));
   let mut visited = BTreeSet::new();
   let mut parents = BTreeMap::new();
   to_visit.push_back((a, b));

   let mut n = 1_usize;
   loop {
       let (a, b) = to_visit.pop_front().unwrap();
       if !visited.insert((a, b)) {
           continue;
       }
       let child1 = s((a, b));
       let child2 = r((a, b));
       parents.insert(child1, (a, b));
       parents.insert(child2, (a, b));
       n += 1;
       if child1.0 == child1.1 {
           println!(
               "\n\n{:?} with length {} :",
               child1,
               (n as f64).log2().floor() + 1f64
           );
           retrace_path(&child1, &parents,&mut std::io::stdout()).expect("Unable to write path");
       }
       n += 1;
       if child2.0 == child2.1 {
           println!(
               "\n\n{:?} with length {} :",
               child2,
               (n as f64).log2().floor() + 1f64
           );

           retrace_path(&child2, &parents,&mut std::io::stdout()).expect("Unable to write path");
       }
       to_visit.push_back(child1);
       to_visit.push_back(child2);
   }
}
fn main() {
   solve_path_to_equality((45, 90));
}

1. Je ne suis pas sur de saisir, tu supprimerais le BTreeSet et pour vérifié si le noeud n a déjà été visité tu regarderais dans la map<enfant:Node,parent:Node> si la valeur n à un clé associée ?
   A ce moment, il faut vérifié toutes les valeurs car il n’y a pas de moyen efficace de savoir si la valeur est associée dans la map ou non, ou alors on stock de cette manière map<parent:Node,enfant:Node>, mais à ce moment c’est lors de la construction du chemin qu’on devrait regarder chaque valeur pour trouver la clé (le parent) donc O(n).
   L’avantage du set c’est que la recherche est O(log(n))
2. le compteur n est très moche, il existe car dans ma première version, je trouvais uniquement les pairs et j’avais pas le chemin pour compter la longueur du chemin, je vais amélioré ça.
3. Pas encore, mais c’est l’objectif
4. Avec cette technique, chaque échange représente une nouvelle génération d’enfants c’est bien ça donc tu comptes les échanges entres les deux queue pour compter la longeur, je ne connaissais pas cette manière, merci de la remarque
5. Je pensais que c’était plus efficace, mais si tu me le conseil, je me trompe surement ?
6. C’est temporaire, la boucle est infinie, en ce moment j’essaie de trouver des patterns dans les chemin menant a des solutions pairs (car c’est les seuls que je trouve) et tenter de déduire une meilleur approche pour générer les solutions. Si j’arrive à générer facilement les solutions directement sans faire tout le chemin, il me suffit de trouver un moyen de compter la longeur à partir de la solution (ça aussi rapidement) (oui oui, j’ai de l’espoir ahahha)