I am new to Rust Programming so I decided to implement a Maze Solver using DFS. I was wondering if there is any way to optimize this code further
use std::collections::{HashMap, HashSet, VecDeque};
// Load maze from a given file name and return an array of strings
// fn load_maze(filename: &str) -> Vec<String> {
// let mut maze = Vec::new();
// let file = File::open(filename).unwrap();
// let reader = BufReader::new(file);
// for line in reader.lines() {
// // if line is not empty
// if !line.as_ref().unwrap().is_empty() {
// maze.push(line.unwrap());
// }
// }
// maze
// }
// Use include_str! to load the maze from a file
fn include_maze() -> Vec<String> {
let mut maze = Vec::new();
// Get the file contents as a string using include_str! macro
let file_contents = include_str!("/path/to/maze.txt");
// Split the string into lines
for line in file_contents.lines() {
// if line is not empty
if !line.is_empty() {
maze.push(line.to_string());
}
}
maze
}
// Parse the maze and return an array of arrays of characters removing any whitespace
fn parse_maze(maze: &Vec<String>) -> Vec<Vec<bool>> {
let mut parsed_maze = Vec::new();
for line in maze {
let mut parsed_line = Vec::new();
for c in line.chars() {
// switch statement
match c {
// if c is a wall (#) return false
'#' => parsed_line.push(false),
// if c is a path (-) return true
'-' => parsed_line.push(true),
_ => (),
}
}
parsed_maze.push(parsed_line);
}
parsed_maze
}
fn dfs(
matrix: &Vec<Vec<bool>>,
start: (usize, usize),
end: (usize, usize),
) -> Option<Vec<(usize, usize)>> {
// Create a stack
let mut stack = VecDeque::new();
stack.push_back(start);
// Create a set to store the visited nodes
let mut visited = HashSet::new();
// Create a dictionary to store the parent of each node
let mut parent = HashMap::new();
// While the stack is not empty
while let Some(node) = stack.pop_back() {
// If the node is the end, we have found a path
if node == end {
// Create a list to store the path
let mut path = vec![];
let mut current = node;
// While the node is not the start
while current != start {
// Add the node to the path
path.push(current);
// Set the node to its parent
current = parent[¤t];
}
// Add the start node to the path
path.push(start);
// Reverse the path
path.reverse();
// Return the path
return Some(path);
}
// If the node has not been visited
if !visited.contains(&node) {
// Add the node to the visited set
visited.insert(node);
// Get the row and column of the node
let (row, col) = node;
// Get the possible moves
let moves = get_moves(matrix, row, col);
// For each move
for m in moves {
// If the move has not been visited
if !visited.contains(&m) {
// Add the move to the parent dictionary
parent.insert(m, node);
// Push the move onto the stack
stack.push_back(m);
}
}
}
}
// If we have not found a path, return None
None
}
fn get_moves(matrix: &Vec<Vec<bool>>, row: usize, col: usize) -> Vec<(usize, usize)> {
// \# is a wall and - is a path
// Get the possible moves
let mut moves = vec![];
// Check the left move
if col > 0 && matrix[row][col - 1] {
moves.push((row, col - 1));
}
// Check the right move
if col < matrix[0].len() - 1 && matrix[row][col + 1] {
moves.push((row, col + 1));
}
// Check the up move
if row > 0 && matrix[row - 1][col] {
moves.push((row - 1, col));
}
// Check the down move
if row < matrix.len() - 1 && matrix[row + 1][col] {
moves.push((row + 1, col));
}
// Return the moves
moves
}
fn main() {
// let maze = load_maze("/home/cms/fun/dfs/mazes/maze-Easy.txt");
let maze = include_maze();
let parsed_maze = parse_maze(&maze);
let start = (0, 1);
let end = (parsed_maze.len() - 1, parsed_maze[0].len() - 2);
let path = dfs(&parsed_maze, start, end).unwrap();
println!("Path: {:?}", path)
}
An example maze file:
# - # # # # # # # # # # # # # # # # # #
# - - - - - - - - - - - - - - - - - # #
# # # # # - # # - # # - # # # - # - - #
# - # # # - # - - # # - # # - - # - # #
# - # - - - # # # # # # # # # - # - - #
# - - - # - - - - # - # # - # - # # # #
# - # # # # - # - - - - - - - - - - - #
# - # # - - - # # # # # # # # # # - # #
# - - - - # - - # # - - - - - - - - - #
# # # # # # # # # # # # # # # # # # - #
This is a very small maze, but this program should solve as long as the end is in the bottom right corner. Here is a large maze
So far, the best optimization I have made is by using include_str!
which has decreased execution time by 200ms. I have tried to use threading to speed it up, but that only seemed to make it slower (I think I was making too many threads)
Any help is appreciated! :)