Hi again! Today I’m going to talk about algorithmics. My favourite gym is UVa Online Judge, an automated programming judge where you can find thousands of problems. If you didn’t know about that, register and try it. Use the uHunt tool to find some easy problems to begin with.
I’m recently uploading my old solved exercices to GitHub and I’ll use it to post about the most interesting ones. Here I go with the first:
As always, I encourage you to try to solve the problem first and
avoid looking quickly at the solution after the first
Here you have the
for this one.
First of all we must think about the problem goal. In that case we are asked to find a path between two languages with the restriction of minimum words length and that two consecutive words cannot have the same first letter. This problem can be solved structuring the input data as a graph and finding the shortest path between the specified nodes. So let’s do it!
First, we must store the input as a graph (I’ll not go into details here). I’ve used a map to associate the corresponding graph index position for each language (that comes as a string). Once we have the data correctly saved, we can run a customized Dijkstra algorithm over the graph to find the shortest path.
If there are any doubts about implementation details, here is my c++ solution .
See you soon!