DEV Community

Discussion on: Advent of Code 2019 Solution Megathread - Day 20: Donut Maze

Collapse
 
neilgall profile image
Neil Gall • Edited

Ok time to do something different. I've done part 1 for this one in Rust! Scanning the maze for the labels was the tricky bit as I just did a row-by-row scan looking for capital letters. The route finding was easy - just count portal partners as neighbours and do a standard flood-fill or dijkstra type search.


    fn neighbours(&self, pos: &Pos) -> Vec<Pos> {
        let mut ns = Vec::new();
        for dir in Dir::iter() {
            match self.go(&pos, dir) {
                Some(p) => ns.push(p),
                None => {}
            }
        }
        match self.portals.get(pos) {
            Some(p) => ns.push(*p),
            None => {}
        }
        ns
    }

    fn find_routes(&self) -> Vec<Route> {
        self.search(&self.start, &HashSet::new())
    }

    fn search(&self, pos: &Pos, visited: &HashSet<Pos>) -> Vec<Route> {
        let mut routes: Vec<Route> = Vec::new();
        if *pos == self.end {
            routes.push(Route::new());
        } else {
            for n in self.neighbours(pos) {
                if self[&n] == '.' && !visited.contains(&n) {
                    let mut v = visited.clone();
                    v.insert(n);
                    self.search(&n, &v).into_iter().for_each(|mut r| {
                        r.add(&pos);
                        routes.push(r)
                    });
                }
            }
        }
        routes
    }

Full code here. I'll come back for part 2.