Perl Weekly Challenge 129: Root Distance

Tree:
        1
       / \
      2   3
           \
            4
           / \
          5   6

Node: 6
Output: 3 as the distance of given node 6 from the root (1).

Node: 5
Output: 3

Node: 2
Output: 1

Node: 4
Output: 2

Tree:
        1
       / \
      2   3
     /     \
    4       5
     \     /
      6   7
     / \
    8   9

Node: 7
Output: 3 as the distance of given node 6 from the root (1).

Node: 8
Output: 4

Node: 6
Output: 3

Once again a challenge where we take a tree as input, without a clue on how the input looks like, except for some tiny examples which don't scale. And this time, we're not even given we have a binary tree — just a tree. I mean, it's all fine and dandy if we have a tree where no node has more than two children, and many have just one. But what if a node has 27 children?

Therefore, we'll just magic will gives us the tree, and we're not going to waste time writing code reading input. Magic will give us the tree at the start of the program. We'll assume the tree is given as a hash: each node of the tree is a key in the hash, and the values of the hash are arrays, where each element of the hash represents an edge from the node to one of its neighbours. (This means, we treat edges in the tree to not be directed).

The specification states we're given a tree, and a node. Yet, the examples have several nodes per tree.

We can only conclude that the input specification is utterly useless, and, yet again, we assume magic which gives us the node.

To find the shortest path between two nodes in a graph, one can use a bog standard breadth-first search. A tree is a (connected) graph without loops, but that doesn't give us any benefits, so we just assume we have a graph. A breadth-first search takes time \(\mathcal{O}(|V| + |E|)\), where \(V\) is the set of vertices, and \(E\) the set of edges. Since our input is a tree, we have \(|E| < |V|\), hence our algorithm runs in \(\mathcal{O}(|V|)\), which is optimal.

Using magic to read in the input, assuming for each input, the root is labeled \(1\).

my $graph  = do {...};
my $target = do {...};
my $root   = 1;

For our search, we're using a queue (named @todo), where each element of the queue consists of a node to be processed, and the distance of the root to that node. We initialize the queue with the root node itself, which has distance 0. We use a hash %seen to keep track of the nodes we have processed:

my @todo = ([$root, 0]);
my %seen;

While our queue is non-empty, we pop off the first element. If this is our target, we report the distance, and we're done. If we have already processed this node, we continue with the next node in the queue. Else, for each of the neighbours of the current node, we push this node to the queue, with a distance which is one more than the distance of the root to the current node:

while (@todo) {
    my ($node, $distance) = @{shift @todo}
    if ($node == $target) {
        say $distance;
        exit;
    }
    next if $seen {$node} ++;
    push @todo => map {[$_, $distance + 1]} @{$$graph {$node}}
}

If we haven't found the target node, either the target doesn't exist, or the graph isn't connected, and the target node and the root are not in the same component:

say "$target does not exist, or is not connected to the root node";

Find the full program on GitHub.