# Find nearest clone

(Hackerrank ‘Find the nearest clone’ problem.)

One advantage of a breadth-first search over a depth-first search is that we can extract the shortest distance between two nodes. One way of doing this (at the cost of a little extra space) is to use a queue whose elements consist not simply of nodes but of pairs `(d, n)` where `n` is a node and `d` is an integer recording the distance from the start node.

where we have assumed that we are given a function `is_end_node` that tells us if a particular node is the one we are searching for. Consider the following problem (from Hackerrank):

The idea is to find the first node `n1` of the correct colour `c` and find the shortest path starting at that node to another node `n2` of colour `c`. Then – marking the nodes `n1` and `n2` as visited – find the nearest `n3` of colour `c` to `n2` that is not marked as visited. Repeating we will take into account every node of colour `c` because the graph is connected. Then we can record the shortest of the lengths of the paths we calculated. The full solution might look like: