Decode the Coding Interview in Rust: Real-World Examples/

...

/

Feature #3: Plot and Select Path

Feature #3: Plot and Select Path

Implementing the "Plot and Select Path" feature for our "Uber" project.

We'll cover the following...

Description

After obtaining the closest drivers and calculating the cost of traveling on different roads, we need to build a functionality to select a path from the driver’s location to the user’s location. All the drivers have to pass through multiple checkpoints to reach the user’s location. Each road between checkpoints will have a cost, which we learned how to calculate in the previous lesson. It is possible that some of the k chosen drivers might not have a path to the user due to unavailability. Unavailability can occur due to a driver already being in a ride that has ended but not reached its location. In some cases, the driver can also get booked by another user and become unavailable. The driver that has the path to the user’s location with the minimum accumulated cost will be selected.

We’ll be given a city map gmap as a list of different checkpoints. Another list path_costs, at each index, will represent the cost of traveling between the corresponding checkpoints in gmap. We are also given some drivers, where each drivers[i] represents a single driver node. We need to determine whether a path from the driver node drivers[i] to a user node exists or not. If the path exists, return the accumulated sum of the checkpoints between the two nodes. Otherwise, return -1.

In the above example,

  • gmap has the values [["a","b"],["b","c"],["a","e"],["d","e"]].

  • path_costs has the values [12,23,26,18].

  • drivers has the values ["c", "d", "e", "f"].

  • user has a value "a".

After calculating the total cost of each driver’s route to the user, we’ll select that driver that has a path to the user with the lowest cost. Here, the driver f has no path to the user due to unavailability.

Solution

The main problem comes down to finding a path between two nodes, if it exists. If the path exists, return the cumulative sums along the path as the result. Given the problem, it seems that we need to track the nodes where we come from. DFS (Depth-First Search), also known as the backtracking algorithm, will be applicable in this case.

Here is how the implementation will take place:

  1. Build the graph using the city map list gmap.

  2. Assign the cost to each edge while building the graph.

  3. Once the graph is built, evaluate each driver’s path in the drivers list by searching for a path between the driver node and the user node.

  4. Return ...

Press + to interact
use std::collections::HashMap;
use std::collections::HashSet;
fn backtrack_evaluate(city: HashMap<String, HashMap<String,f64>>, curr_node: String, target_node: String, acc_sum: f64, mut visited: &mut HashSet<String>)->f64 {
      // mark the visit
      visited.insert(curr_node.clone());
      let mut ret = -1.0;
      let neighbors: HashMap<String, f64> = city.get(&curr_node.clone()).unwrap().clone();
      if neighbors.contains_key(&target_node) {
          ret = acc_sum + neighbors.get(&target_node).unwrap();
      }
      else {
          for (next_node, val) in neighbors.iter()
          {
              if visited.contains(next_node)
                 { continue;}
              ret = backtrack_evaluate(city.clone(), next_node.to_string(), target_node.clone(),
                      acc_sum + val, &mut visited);
              if ret != -1.0
                  {break;}
          }
      }
      // unmark the visit, for the next backtracking
      visited.remove(&curr_node);
       return ret;
 }
fn get_total_cost( gmap: Vec<Vec<String>>, path_costs: Vec<f64>, drivers: Vec<String>, user: String, results:&mut Vec<f64>) {
    let mut city: HashMap<String, HashMap<String,f64>> = HashMap::new();
    // Step 1). build the city from the gmap
    for i in 0..gmap.len() {
      let check_points: Vec<String> = gmap[i].to_vec();
      let source_node: String = check_points[0].to_string();
      let dest_node: String = check_points[1].to_string();
     let path_cost:f64 = path_costs[i];
      let c: HashMap<String, f64> = HashMap::new();
      if !city.contains_key(&source_node) {
        city.insert(source_node.clone(),c.clone());
      }
      if !city.contains_key(&dest_node){
        city.entry(dest_node.clone()).or_insert(c.clone());
      }
      if !city.get_mut(&source_node).unwrap().contains_key(&dest_node.clone()){
        *city.get_mut(&source_node).unwrap().entry(dest_node.clone()).or_insert(path_cost); 
      }
      else{
        *city.get_mut(&source_node).unwrap().get_mut(&dest_node.clone()).unwrap() = path_cost;
      }
      if !city.get_mut(&dest_node).unwrap().contains_key(&source_node.clone()){
        *city.get_mut(&dest_node).unwrap().entry(source_node.clone()).or_insert(path_cost); 
      }
      else{
        *city.get_mut(&dest_node).unwrap().get_mut(&source_node.clone()).unwrap() = path_cost;
      }
    }
    // Step 2). Evaluate each driver via bactracking (DFS)
    // by verifying if there exists a path from driver to user
    for i in 0..drivers.len() {
      let driver: String = drivers[i].to_string();
      if !city.contains_key(&driver) || !city.contains_key(&user){
          results[i] = -1.0;
      }
      else {
        let mut visited: HashSet<String> = HashSet::new();
          results[i] = backtrack_evaluate(city.clone(), driver, user.clone(), 0.0,&mut visited);
      }
    }
}
fn main() {
    // Driver code
    let gmap: Vec<Vec<String>> = vec![vec!["a".to_string(),"b".to_string()], vec!["b".to_string(),"c".to_string()], vec!["a".to_string(),"e".to_string()], vec!["d".to_string(),"e".to_string()]];
    let path_costs: Vec<f64> = vec![12.0,23.0,26.0,18.0];
    let drivers: Vec<String> = vec!["c", "d", "e", "f"].into_iter().map(String::from).collect();
    let user = "a".to_string();
    let mut all_path_costs: Vec<f64>  = vec![0.0;4];
    get_total_cost(gmap, path_costs, drivers, user, &mut all_path_costs);
    println!("{}{:?}","Total cost of all paths ",all_path_costs);
}

Complexity measures

...