Good morning! It is a foggy Sunday morning in the Twin Cities of Minneapolis and St. Paul. In the past week or so the mornings have been sunny. That said, the forecasted high for the day is 76F. If the fog clears and with sun shine we might be a couple degrees warmer.
Yesterday the high temperature was forecasted to be 70F. My wife and I stopped by our older son place. He lives in Lakeville which is about 15 minutes away by car from our place.
We spent a few hours outside chatting and drinking a couple adult drinks while he was cooking some delicious burgers. He enjoys grilling and smoking meats. In the past couple weeks he decided to meet or better yet, improve on a butter burger sandwich from Culver’s.
I am not going to get into the details but in my opinion the burgers he made were a notch better than the ones from the food chain. That said, my wife and I would have cooked them no more than one minute per side. My son likes burgers very well done while we prefer them just done. He did not only cook the burgers, but in addition served them with all the trimmings and in waxed paper in the shape of a bag. We all had a good time. Today my wife and I will grill steaks but next week, we will do burgers with all the trimmings. We will be skipping the paper bag!
Yesterday morning I watched Donald Knuth: Algorithms, Complexity, and The Art of Computer Programming | Lex Fridman Podcast #62. It was interesting listing to the answers to the very well selected questions. Seems like Knuth really likes what he does which is not the case with most people. The main things in his professional life are algorithms and writing about them. How he does both was interesting to learn about. I also learned about a different podcast in which Lex Fridman chats with his dad. I will leave it for next week. If not mistaken it is quite a long podcast (over 3 hours long).
In this post I will cover solving a HackerRank problem named Roads and Libraries.
Determine the minimum cost to provide library access to all citizens of HackerLand. There are n cities numbered from 1 to n. Currently there are no libraries and the cities are not connected. Bidirectional roads may be built between any city pair listed in cities. A citizen has access to a library if: o Their city contains a library. o They can travel by road from their city to a city containing a library.
The description of the problem suggests the use of a graph.
We need to balance the cost of building a library in each town versus the cost of building libraries in a few towns and connecting them by roads. All is based on the cost of building a library versus the cost of repairing a road. When all is said and done, one should be able to get to a library from any city in the graph.
We could use:
* DFS (Depth First Search)
o BFS (Breadth First Search)
In this case we will use DFS in a bidirected graph since the roads are bidirectional.
Our algorithm will have three parts. The first is the definition of the graph for the cities. We will consider using a linked list adjacency map. We could also have considered using a matrix adjacency map. I believe we have used these two representations in previous posts. The second part would be the number of connected cities which we will address using a DFS approach. The last part will deal with the specifics to this problem which is to compute the minimum cost.
/*
* Complete the 'roadsAndLibraries' function below.
*
* The function is expected to return a LONG_INTEGER.
* The function accepts following parameters:
* 1. INTEGER n
* 2. INTEGER c_lib
* 3. INTEGER c_road
* 4. 2D_INTEGER_ARRAY cities
*/
public static long roadsAndLibraries(int n, int c_lib, int c_road, List<List<Integer>> cities) {
// Write your code here
}
The description of the signature for our problem indicates that we are provided the number of cities (nodes in the graph), the cost to build a library in any city, the cost to build / repair a road between connected cities and finally a list of the cities that are connected.
1 3 3 2 1 1 2 3 1 2 3 <<< visited: [false, false, false, false] <<< city: 0 <<< city: 1 -> 2 -> 3 <<< city: 2 -> 1 -> 3 <<< city: 3 -> 1 -> 2 <<< city: 3 cost: 1 <<< city: 2 cost: 2 <<< city: 1 cost: 3 main <<< minCost: 4 1 6 6 2 5 1 3 3 4 2 4 1 2 2 3 5 6 <<< visited: [false, false, false, false, false, false, false] <<< city: 0 <<< city: 1 -> 3 -> 2 <<< city: 2 -> 4 -> 1 -> 3 <<< city: 3 -> 1 -> 4 -> 2 <<< city: 4 -> 3 -> 2 <<< city: 5 -> 6 <<< city: 6 -> 5 <<< city: 2 cost: 1 <<< city: 4 cost: 2 <<< city: 3 cost: 3 <<< city: 1 cost: 4 <<< city: 6 cost: 1 <<< city: 5 cost: 2 main <<< minCost: 12
HackerRank provides two sample test cases. We will be solving the problem using Java and the VSCode IDE on a Windows 10 computer. We will use a slightly modified version of the test code provided by HackerRank so we can easily run it on our local computer. The first number indicates the number of tests. As you can see I have split the two tests into separate tests. This was done for simplicity. The input data is defined in the HackerRank web site. Since the explanation provided by HackerRank is clear, there is little we need to add here. It seems that we are using an array of visited cities. The array is zero based and the number of cities starts with 1. This is why we have four entries in the array. The same will hold for the mechanism used to describe the cities in the graph. This will become clear when we look at the actual code. It seems that we implement a linked list adjacency map. As expected there is no city 0 so there are no adjacent cities associated with it. The rest of the cities are properly connected based on the data. HackerRank provides a diagram which helps visualize the graph. It seems that from each city we compute costs to build a library and repair roads. The result is displayed. In the first example it seems our cost to be 4 while for the second example it seems that the minimum cost would be 12.
/**
* Test scaffold.
*
* NOT PART OF SOLUTION
*
* @throws IOException
* @throws NumberFormatException
*/
public static void main(String[] args) throws NumberFormatException, IOException {
// **** open buffered reader and writer ****
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
// **** get the number of queries ****
int q = Integer.parseInt(bufferedReader.readLine().trim());
// **** ****
IntStream.range(0, q).forEach(qItr -> {
try {
String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
int n = Integer.parseInt(firstMultipleInput[0]);
int m = Integer.parseInt(firstMultipleInput[1]);
int c_lib = Integer.parseInt(firstMultipleInput[2]);
int c_road = Integer.parseInt(firstMultipleInput[3]);
List<List<Integer>> cities = new ArrayList<>();
IntStream.range(0, m).forEach(i -> {
try {
cities.add(
Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList())
);
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
// **** compute result ****
long result = roadsAndLibraries(n, c_lib, c_road, cities);
// **** display result ****
bufferedWriter.write("main <<< minCost: " + String.valueOf(result));
bufferedWriter.newLine();
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
// **** close buffered reader and writter ****
bufferedReader.close();
bufferedWriter.close();
}
This is the slightly modified test scaffold provided by HackerRank. I am using the console and like to refer to it directly. This is reflected by the modified specifications for the buffered reader and buffered writer.
I also modified the way the result is displayed.
/**
* Determine the minimum cost to provide library access to all citizens of HackerLand.
* Nodes start with 0.
*/
public static long roadsAndLibraries(int n, int c_lib, int c_road, List<List<Integer>> cities) {
// **** initialization ****
boolean[] visited = new boolean[n + 1];
ArrayList<Integer> comps = new ArrayList<>();
long minCost = 0;
// ???? ????
System.out.println("<<< visited: " + Arrays.toString(visited));
// **** create graph adjacency list ****
ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(n + 1);
for (int i = 0; i < (n + 1); i++) {
adj.add(new ArrayList<Integer>());
}
// **** populate adjacency list ****
for (int i = 0; i < cities.size(); i++) {
// **** for eade of use ****
List<Integer> city = cities.get(i);
// **** add bidirectional edge ****
addEdge(adj, city.get(0), city.get(1));
}
// ???? ????
printGraph(adj);
// **** update cost of components (uses dfs) ****
for (int i = 1; i <= n; i++) {
if (adj.get(i).size() >= 0 && !visited[i]) {
comps.add(dfs(adj, i, visited));
} else {
if (adj.get(i).size() == 0) {
comps.add(1);
}
}
}
// **** compute minimal cost (road + library) ****
for (int i = 0; i < comps.size(); i++) {
minCost += Math.min((comps.get(i) - 1) * c_road + c_lib, comps.get(i) * c_lib);
}
// **** return minimum cost ****
return minCost;
}
We start by initializing some variables. We then display the initial state of the visited array.
Next we create and populate the graph adjacency map. Note that since roads are bidirectional we need to connect cities in both directions. This is done by the addEdge() method.
We then display the graph. This is NOT PART OF THE SOLUTION.
We then perform DFS operations to get to the connected cities and to compute the cost components associated with each city.
Finally we compute the minimal cost of building a library and fixing a road or just building a library in each city. The minimum result is returned.
/**
* Utility function to add edge in directed graph.
*/
static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v) {
adj.get(u).add(v);
adj.get(v).add(u);
}
This method / function adds bidirectional edges between adjacent cities.
/**
* Compute the cost for a connected library for a city.
* Recursive function.
* Execution complexity: O(c + e)
*/
static int dfs(ArrayList<ArrayList<Integer>> adj, int city, boolean[] visited) {
// **** initialization ****
int cost = 1;
// **** flag as visited ****
visited[city] = true;
// **** visit adjacent nodes (if not visited) ****
for (int i = 0; i < adj.get(city).size(); i++) {
if (!visited[adj.get(city).get(i)]) {
cost += dfs(adj, adj.get(city).get(i), visited);
}
}
// ???? ????
System.out.println("<<< city: " + city + " cost: " + cost);
// **** return cost ****
return cost;
}
This method implements the DFS approach to visit all adjacent cities. The structure of this function is quite typical for a DFS approach.
/**
* Print adjacency list.
*
* NOT PART OF SOLUTION
*/
static void printGraph(ArrayList<ArrayList<Integer>> adj) {
for (int i = 0; i < adj.size(); i++) {
// **** ****
System.out.print("<<< city: " + i);
// **** print adjacent nodes ****
for (int j = 0; j < adj.get(i).size(); j++) {
System.out.print(" -> " + adj.get(i).get(j));
}
// **** end of line ****
System.out.println();
}
}
This method is NOT PART OF THE SOLUTION. It is used to display the adjacency list describing the graph of the cities.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John