Write better code: Day 8 - Shortest route

Recent Articles:

1. What are sales pipeline stages
2. Salesforce CRM Training tutorial for beginners

--

I found this one interesting...

Problem:

Given information about active users on a network, find the shortest route for a message from one user (the sender) to another (the recipient). Return an array of users that make up this route.

There might be a few shortest delivery routes, all with the same length. For now, let's just return any shortest route.

Your network information takes the form of a hash mapping username strings to an array of other users nearby:

network = {
  'Min'     => ['William', 'Jayden', 'Omar'],
  'William' => ['Min', 'Noam'],
  'Jayden'  => ['Min', 'Amelia', 'Ren', 'Noam'],
  'Ren'     => ['Jayden', 'Omar'],
  'Amelia'  => ['Jayden', 'Adam', 'Miguel'],
  'Adam'    => ['Amelia', 'Miguel', 'Sofia', 'Lucas'],
  'Miguel'  => ['Amelia', 'Adam', 'Liam', 'Nathan'],
  'Noam'    => ['Nathan', 'Jayden', 'William'],
  'Omar'    => ['Ren', 'Min', 'Scott'],
  ...
}

For the network above, a message from Jayden to Adam should have this route:
['Jayden', 'Amelia', 'Adam']

-

If you want to follow along, feel free to post your answers in the comment.
My answers are in the comments. This problem is from InterviewCake.

Comments

[Idan Arye]

Isn't this just a simple BFS?

play.rust-lang.org/?version=stable...

The function(+data type used for search) is:

#[derive(Debug)]
struct NoRoute;

#[derive(Debug)]
struct NodePath<'a> {
    node: &'a str,
    prev: Option<Rc<NodePath<'a>>>,
}

impl<'a> NodePath<'a> {
    fn new(node: &str) -> NodePath {
        NodePath { node, prev: None }
    }

    fn resolve(&self) -> Vec<&'a str> {
        let mut result = vec![self.node];
        let mut path_node = &self.prev;
        loop {
            path_node = if let Some(path_node) = path_node {
                result.insert(0, path_node.node);
                &path_node.prev
            } else {
                return result;
            }
        }
    }
}

fn send_a_message<'a>(
    network: &'a HashMap<String, HashSet<String>>,
    sender: &'a str,
    receiver: &'a str,
) -> Result<Vec<&'a str>, NoRoute> {
    let _ = (network, sender, receiver);
    let mut tried = HashSet::new();
    let mut to_try = VecDeque::new();
    to_try.push_back(Rc::new(NodePath::new(sender)));

    while let Some(path_node) = to_try.pop_front() {
        if path_node.node == receiver {
            return Ok(path_node.resolve());
        }
        let routes = if let Some(routes) = network.get(path_node.node) {
            routes
        } else {
            continue;
        };
        for next_node in routes.iter() {
            if tried.contains(next_node) {
                continue;
            }
            tried.insert(next_node);
            to_try.push_back(Rc::new(NodePath {
                node: next_node,
                prev: Some(path_node.clone()),
            }));
        }
    }
    Err(NoRoute)
}

[Arjun Rajkumar]

Nice. Yes it is.

[Arjun Rajkumar]

Logic:

• Check to see if any of the senders direct neighbours is the receiver.
• If not, check to see if any of neighbours neighbours is the receiver.
• Keep doing this until there is a match.
• Else no match.

-If there is a match, also store the path - who is directly connected to whom?
-That way in the end, you just have to go back the path from receiver to sender.

The code below could be cleaned up more.. But here it is.

def send_a_message(network, sender, receiver)
  neighbours = network[sender]

  already_seen = []
  neighbours_to_check = []
  path_to = {}
  path_exists = false

  neighbours_to_check << sender
  already_seen << sender
  path_to[sender] = nil

  until neighbours_to_check.empty?
    current = neighbours_to_check.pop

    if current == receiver
      path_exists = true
      break
    end

    network[current].each do |person|
      next if already_seen.include? person

      already_seen << person
      neighbours_to_check << person
      path_to[person] = current
    end
  end

  if path_exists
    actual_path = []
    current = receiver

    while current
      actual_path << current
      current = path_to[current]
    end 

    return actual_path
  else
    nil
  end
end