Madahin's Dev

I always loved Teads challenge, not because it was hard, but because it was the first time i had to really care about optimisation. So now that i've finally beaten it, i decided it could be a great first article.

The challenge

The challenge itself isn't really hard. You build a graph by reading on the standard input the relation between each node. When that's done, your job is to find the minimum number of steps required to explore the entire graph.

Solution

Disclaimer : I'm not saying that my solution is the best one or anything like that. All i'm saying is, it's working

My first idea was to find for each node the longest path from the node to a leaf, and then return the smallest length... Let's just say that wasn't my brightest idea. That said, i'm proud to say that this shitty idea went as far as the 8th test, which is quite nice, considering the complexity is probably in Θ(n²).

My second idea, and the one who completed the challenge, was to delete the leafs step by step until there's only one or no node left. To be more accurate, we detect all the leaves, remove them, check again, rinse and repeat. So, how did you do it ?

def Compute(graph):
    depth = 0;
    while len(graph) > 1:
        deleteLeaves(graph)
        depth += 1
    return depth

I think it's pretty straightforward. As long as we have more than 1 node, we keep removing leaves. The deleteLeaves() function is pretty simple too :

def deleteLeaves(graph):
    leavesID = [key for key in graph.keys() if graph[key].isLeaf()]
    for leafID in leavesID:
        leaf = graph[leafID]
        for neighbour in leaf.childs:
            neighbour.childs.remove(leaf)
        del graph[leafID]

I used a Dict for representing my graph, each node knowing all of its neighbour. For detecting the leaves, i use a comprehensive list, these things are simply amazing.

I was struck by the simplicity of this solution. I had spent a lot of time on my first idea, hard-trying to optimise every line of code and ended with a clusterfuck of spaghetti code.

This concludes my write-up on this exercise. I hope you enjoyed it as much as i did. See you next time.