New To Java - HackerRank Graphing Algorithm

Question

In order to learn java, I have been working through some HackerRank problems. The one I am asking about is here:

• There are cities that we can connect together by repairing some destroyed roads, provided by integer pairs
• We can build a library in one or more cities
• There is a cost to the roads and a different cost to the libraries
• All cities must be part of a group that contains a library, i.e. you can get there by a repaired road -we are trying to minimize cost

I am certain that my code works, through testing on Hackerrank, however I am not certain I don't have conventions wrong, poor variable names, poor commenting, using Long instead of long or Integer instead of int etc. Do you see any opportunities for improvement ?

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;

/** This is a solution to
* https://www.hackerrank.com/challenges/torque-and-development/problem
* class must be name Solution to run on Hackerrank 
*/

public class Solution {

private static List<List<Integer>> adjCities;
private static boolean[] visited;

// do a dfs to find every city that can be connected to any given group of cities
private static void dfs(int city){
    visited[city] = true;
    for (int c=0; c< adjCities.get(city).size(); c++){
        if(!visited[ adjCities.get(city).get(c)])  {
            dfs( adjCities.get(city).get(c) );
        }
    }
}


public static void main(String[] args) {

    Scanner in = new Scanner(System.in);
    //Scanner in = new Scanner(new File("test_4.txt"));  // sample input file

    int queries = in.nextInt();

    // loop through each of the blocks which represent separate problems
    for(int cntQueries = 0; cntQueries < queries; cntQueries++){

        int numCities = in.nextInt();
        int numRoads = in.nextInt();
        long costLibrary = in.nextLong();  // these must be long, not int to avoid
        long costRoad = in.nextLong();     // overflow in the totalCost
        long totalCost;                    // totalCost must also be long, not int

        // make the adjacency list as a list of null length lists
        adjCities= new ArrayList<>();
        for (int c = 0; c <= numCities; c++) {
            adjCities.add(new ArrayList<>());
        }


        // read in the data on the connecting roads.  add each road to the adjacency list
        // for both cities
        int city1;
        int city2;
        for(int cntRoads = 0; cntRoads < numRoads; cntRoads++){
            city1 = in.nextInt();
            city2 = in.nextInt();

            adjCities.get( city1).add(city2);     // add to the adjacency list
            adjCities.get( city2).add(city1);
        }


        if(costLibrary <= costRoad){
            // if the cost of building a library is less than the cost of repairing a road
            // we just build a library in every city, without repairing any roads
            totalCost = (long) (costLibrary * numCities);
        }
        else{
            // if the cost of repairing a road is less than building a library,
            // we need to do a search to see how many cities can be connected.  i.e.
            // we want the fewest number of groups possible.
            // Each group gets a single library.  Count the number of libraries made

            // do a depth first search on our cities, to see which cities can be grouped together
            int librariesBuilt=0;
            visited = new boolean[numCities+1];
            for (int c=1; c <= numCities; c++){
                if(!visited[c]) {
                    dfs(c);
                    librariesBuilt++;
                }
            }

            // the total number of roads build plus the number of libraries built will always equal
            // the number of cities.  Therefore the number of roads built will always be the number
            // of cities less the number of libraries built
            totalCost = librariesBuilt * costLibrary + (numCities-librariesBuilt) * costRoad;
        }


        //System.out.println("The total cost is ");
        System.out.println(totalCost);
    }

}
}

Answer 1

Thanks for sharing your code!

Naming

Finding good names is the hardest part in programming, so always take your time to think about the names of your identifiers.

avoid single character names

Since the number of characters is quite limited in most languages you will soon run out of names. This means that you either have to choose another character which is not so obviously connected to the purpose of the variable. And/or you have to "reuse" variable names in different contexts. Both makes your code hard to read and understand for other persons. (keep in mind that you are that other person yourself if you look at your code in a few month!)

On the other hand in Java the length of identifier names is virtually unlimited. There is no penalty in any way for long identifier names. So don't be stingy with letters when choosing names.

avoid abbreviations

In your code you use some abbreviations such as the method dfs. Although this abbreviation makes sense to you (now) anyone reading your code being not familiar with the problem (like me) has a hard time finding out what this means.

If you do this to save typing work: remember that you way more often read your code than actually typing something. Also for Java you have good IDE support with code completion so that you most likely type a long identifier only once and later on select it from the IDEs code completion proposals.

Use of the language

reduce visibility of variables

In your solution you have this:

    int city1;
    int city2;
    for(int cntRoads = 0; cntRoads < numRoads; cntRoads++){
        city1 = in.nextInt();
        city2 = in.nextInt();

        adjCities.get( city1).add(city2);     // add to the adjacency list
        adjCities.get( city2).add(city1);
    }

You declare the two variable before the loop. Thus this variables are visible after the loop for the rest of the method although they have no meaning there anymore. Move them inside the loop like this:

    for(int cntRoads = 0; cntRoads < numRoads; cntRoads++){
        int city1 = in.nextInt();
        int city2 = in.nextInt();

        adjCities.get( city1).add(city2);     // add to the adjacency list
        adjCities.get( city2).add(city1);
    }

beware of premature optimization

You might have declared city1 and city2 before the loop to reduce memory consumption and/or execution time. But you sacrificed readability and maintainability or at least the Java coding standards.

Always prefer readability, maintainability and Java coding standards over performance considerations unless you have proven by measurement that this particular piece of code is an actual bottleneck and violating the Java coding standards really improves the performance.

comments

Your program has lots of comments. Some of them are good others are OK because it is a beginners program and some are bad.

Comments should explain why the code is like it is as you do in

 // these must be long, not int to avoid overflow ... 

Comments should not repeat what the code already expresses as you do in

 // loop through each of the blocks which represent separate problems

Some of your comments separate the method into logical sections. You should extract this logical sections into separate methods with names derived from the comments you gave:

for(int cntQueries = 0; cntQueries < queries; cntQueries++){

    int numCities = in.nextInt();
    int numRoads = in.nextInt();
    long costLibrary = in.nextLong();  // these must be long, not int to avoid
    long costRoad = in.nextLong();     // overflow in the totalCost
    long totalCost;                    // totalCost must also be long, not int

    adjCities =  makeTheAdjacencyListAsListOfLists();
    readDataOfConnectingRoads(in, adjCities, numRoads);
    totalCost = calculate(adjCities, costLibrary, costRoad);
    System.out.println(totalCost);
}       

OOP

Your code is a procedural approach to the problem.

There is nothing wrong with procedural approaches in general, but Java is an object oriented (OO) programming language and if you want to become a good Java programmer then you should start solving problems in an OO way.

But OOP doesn't mean to "split up" code into random classes.

The ultimate goal of OOP is to reduce code duplication, improve readability and support reuse as well as extending the code.

Doing OOP means that you follow certain principles which are (among others):

• information hiding / encapsulation
• single responsibility / separation of concerns
• same level of abstraction
• KISS (Keep it simple (and) stupid.)
• DRY (Don't repeat yourself.)
• "Tell! Don't ask."
• Law of Demeter ("Don't talk to strangers!")

Although your code is an procedural approach to the problem it would benefit from some of the OO principles:

single responsibility / separation of concerns

Each method in your program should have a clear defined responsibility.

The responsibility of the mainmethod usually is to construct the object tree of the application, that is: creating the objects of your program providing the business logic, its dependencies, connecting them and finally run the business logic. This might look like this:

public static void main(String[] args) {
    Scanner in = new Scanner(System.in); // instantiate dependency
    PrintWriter out = System.out;        // instantiate dependency
    Solution solution = new Solution();  // instantiate your class
    solution.calculateTotalCosts(in,out);// call business logic passing dependencies
}
private void calculateTotalCosts(Scanner in, PrintWriter out){
   // all from your "main" after "Scanner in =..."
}

As a positive side effect of this you could test your solution without changing it by creating a second class:

class SolutionTest{
    public static void main(String[] args) {
        Scanner in = new Scanner(new File("test_4.txt"));  // sample input file
        PrintWriter out = System.out;
        new Solution().calculateTotalCosts(in,out);
    }    
}

On top this test class could do more then one test:

class SolutionTest{
    public static void main(String[] args) {
        File[] sampleInputs ={
           new File("test_1.txt"),
           new File("test_2.txt"),
           new File("test_3.txt"),
           new File("test_4.txt")
        }
        for(File sampleInput : sampleInputs){
            System.out.println("test with file :" + sampleInput);
            Scanner in = new Scanner(sampleInput);
            PrintWriter out = System.out;
            new Solution().calculateTotalCosts(in,out);
        }
    }    
}