UVa - 10507 - Waking up brain

Link to pdf version on UVa OJ

What happened on my mind : There are two ways to think about this. First, when a node is adjacent to 3 nodes it will wake up. Second, when does a node can "help" wake up another node? When it is awake. Thinking in the second way helped me think about Queue data structure. As soon as a node is awaken it is added to a queue, when it is popped from a queue it "helps" adjacent slept nodes (increases their awakeNeighborCount by one). When some nodes awakeNeighborCount becomes 3 it is awaken, so it is added to the queue. I don't know what to call this algorithm :D maybe BFS, maybe Bellman-Ford, why Bellman-Ford? Because at each iteration, those nodes that has gotten awaken, help other nodes.

Again I used multiple functions to solve the problem.
Take a look at my solve() function for more details.

My code on github.

UVa - 10662 - The Wedding

Link to pdf on UVa OJ

In the middle of reading the problem I thought I may need to use some kind of backtracking or dynamic programming, but when I saw the constraints it was obvious I need to do nested for loops in order to solve it. Three nested for loops will do the job.
Here we only have travel agency, restaurant and hotels, if this number increases or it is not a static number we have to use recursion to check all combinations.
I solved it using recursion as well. Take a look at my code for the details.

1 - My iterative solution on github
2 - My recursion solution on github

UVa - 12592 - Slogan Learning of Princess

Link to pdf on UVa OJ

This is a use-case for map data structure. At first I wanted to define another class that included a map in it :D haha, then I thought now that all the functionality I need is save and retrieve pairs, I have to use the map itself, getting rid of boilerplate code that doesn't add any advantage to my code.

Link to my code on github.

UVa - 11280 - Flying to Fredericton

Link to pdf version on UVa OJ

The problem asks us to find the shortest path from source to destination with at most maxStop+1 edges. If you have read about Bellman-Ford algorithm this must not be unfamiliar for you.
In Bellman-Ford algorithm there is a main loop that iterates n-1 times (n being the number of nodes).
At i-th iteration those nodes that their shortest path from source to them consists of i intermediate nodes is fixed, the same thing we want here.
We need to customize Bellman-Ford algorithm and relax Edges maxStop+1 times, instead of n-1 times.

I tried to write the code using a class and some functions.
This is how my main function looks like :



I have a class Graph that inputs the graph and answers the queries for that graph. In terms of clean code and separation of concern, there is at least one problem with this code. Class Graph gets input from standard input like this :



the problem is that if we want to change source of input (let's say instead of standard input, we want to generate random graph, or we want to analyze a picture and generate the graph from that picture), then this Graph class won't be usable. We have hard-coded source of input in this class.

I have a solve() function which it's responsibility is to read input and prepare the graph, then reads queries and uses another function calculateMinDistance() to find the answer for that query.



About 20 lines of code, not that hard to follow what is happening!



I have some data structures in my class, of which the most important one is cityIndex, which is a map of string to ints. Whenever I have a graph that it's nodes are strings, I convert them to integers and work with them.
I use this function to map a string to integer, if it is in the map I return it's index, otherwise I map the size of my map to this city and then return that.



For more details look at my code on github.