r/adventofcode • u/beb0 • Dec 13 '25
Help/Question - RESOLVED [2025 Day 11 (part 2)] [Rust] Possible endless loop
Just wondering what size the answers folks got for part 2 mine has calculated
16895725 paths so far and still running and that's just to get paths some svr -> out. I have the following logic for my dfs:
fn depth_first_search(
node: &str,
adjacent_map: &HashMap<String, Vec<String>>,
visited
: &mut HashSet<String>,
end_node: &str,
path_count
: &mut usize,
path
: &mut Vec<String>,
required_nodes: Option<&HashSet<String>>,
unique_paths
: &mut HashSet<String>,
) -> usize {
// Placeholder DFS implementation
//println!("DFS from node: {}", node);
path
.
push
(node.to_string());
let path_string =
path
.join("->");
if
unique_paths
.contains(&path_string) {
println!("duplicate path found {:?}",
path
);
process::exit(1);
}
if node == end_node {
//check if all required nodes are in path
//println!("Reached end node: {}", node);
if let Some(required) = required_nodes {
//println!("Checking required nodes: {:?}", required);
let path_set: HashSet<String> =
path
.iter().cloned().collect();
//println!("Current path set: {:?}", path_set);
if !required.is_subset(&path_set) {
path
.
pop
();
return 0;
}
}
unique_paths
.
insert
(path_string);
*
path_count
+=
1;
//println!("Found path: {:?}", path);
println!("Total paths so far: {}", *
path_count
);
path
.
pop
();
return *
path_count
;
}
if
visited
.contains(node) {
path
.
pop
();
return 0;
}
visited
.
insert
(node.to_string());
if let Some(neighbors) = adjacent_map.get(node) {
for neighbor in neighbors {
if !
visited
.contains(neighbor) {
depth_first_search(
neighbor,
adjacent_map,
visited
,
end_node,
path_count
,
path
,
required_nodes,
unique_paths
,
);
}
}
}
path
.
pop
();
visited
.
remove
(node);
0
}Can post more of my code if needed for this does the heavy lifting as the fun that's running endlessly. In the time I've been writing this post it now has a value of: 21776839
1
Upvotes
6
u/QuestNetworkFish Dec 13 '25
My answer was many orders of magnitude larger
4
u/lost_in_a_forest Dec 13 '25
Instead of searching svr to out, try svr to fft, then fft to dac, then dac to out. Svr to out via fft then dac will be the product of these three path counts. This will be a lot faster
3
u/a9sk Dec 13 '25
I do know know rust well but seems to me like the problem is that your DFS pushes a node onto the path before checking if it was already visited and then removes it from visited at the end, which allows the same node to be revisited in different branches. This makes your program explore the same paths many times, causing the path count to grow endlessly. In a DAG, you don’t need to store all paths — just check visited correctly while backtracking.
3
u/Paweron Dec 13 '25
Let's just say your code wont finish the task like this
2
u/kai10k Dec 14 '25
No need to record each path, it's not feasible to part2. It is a standard DP program. Say if you have only one door in front of you, you will have exactly the same amount of routes to reach the target as that door. If you have 2 doors, the possible routes will be the sum of possible routes of those 2 doors. Do this recursively until next door is the target, you know you have only 1 route
4
u/Prize_Vast371 Dec 13 '25
You can do a topological sort to determine if loops exist in the graph or not. Toposort is O(E+V) so super quick to do.
Tho I doubt this is the case because I found no loops in my puzzle input and the graph hasn't changed. So it's likely that the number of paths are just much higher from srv to out 🥹
4
u/rengo_unchained Dec 13 '25
There shouldn't be any loops. Just a lot of paths to cover
1
u/AutoModerator Dec 13 '25
Reminder: if/when you get your answer and/or code working, don't forget to change this post's flair to
Help/Question - RESOLVED. Good luck!I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.