Write better code: Day 8 - Shortest route

Arjun Rajkumar Dec 12 '18 Updated on Jul 02, 2019 ・1 min read

#challenge

This post originally appeared on Arjun Rajkumar's blog. Arjun is a web developer based in Bangalore, India.

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.

DISCUSS (3)

Arjun Rajkumar

I’m a software developer primarily building web apps using Ruby on Rails.

Idan Arye

Dec 13 '18

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

Author

Dec 13 '18

Nice. Yes it is.

Arjun Rajkumar

Author

Dec 12 '18

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