DEV Community

loading...

Discussion on: Write better code: Day 8 - Shortest route

Collapse
arjunrajkumar profile image
Arjun Rajkumar Author

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