Flatland Space Stations

Please do not be shocked by the introductory sentences. I was born into an Italian family. My parents moved from Italy to Peru in the 1930’s. Growing up in Peru we were introduced to have wine with weekend meals. In particular wine was only served for lunch. My sisters and I started drinking lemonade with wine. After a few years we moved to have a desert that is made of fresh strawberries with sugar and wine. You just mix the ingredients and let them sit for a couple hours in the fridge. If you try it this summer, make sure it is served chilled. As we got older we had weekend lunch with a couple bottles of wine. None of us ever had issues with alcohol. Different cultures have different approaches to solve the same issue. We just need to make sure that what we do works to solve the problem. If it does not, learn and put practice different approaches. This philosophy can and should be applied to life and software development.

My wife and I belong to the WSJwine club. We get four deliveries a year. Sometimes we complement a delivery with additional bottles. Earlier today we received a case. It comes via FedEx and is delivered to the door. An adult age 21 or older must sign for it.

We have been members of two different wine clubs. Today we only subscribe to WSJwine. When we started we selected mostly red wines. Today we let the company decide on the brands and types. They try to keep a mix of 6 whites and 6 reds. That works very well for us. OK, today is Thursday so no alcohol.

Depending on where you live, alcohol purchase and consumption may only be allowed for individuals who are 21 years of age or older. Please follow the laws of your city, county and state.

I received an email message from HackerRank with the Flatland Space Stations challenge. I like to read the requirements and make sure I have an idea on how to solve them before writing code. While I write code I use the Test-Driven Development (TDD). That said; I do not over think solutions before starting to code. I try to avoid analysis paralysis. By using TDD I am able to get to solid and efficient solutions on challenges and most important for work.

It seems that the requirements call for returning the maximum distance from any city to its nearest space station. The cities are in order e.g., 0, 1, 2 … and there are no loops. The idea is to put in order the cities with a space station and determine the distance between them. The maximum distance is the required answer.

That is good and by using the TDD approach all looked well. We still need to take care of end conditions. There are two of them. The first condition is to check the distance from the first city to the first space station, and the second condition the distance from the last city to the last space station.

Allow me to display the screen console output for the different tests I used:

5 2
0 4

2


6 6
0 1 2 4 3 5

0


6 2
0 5

2


8 2
1 3

4

Take a look at the test cases and make sure you are able to get an idea of the general approach and the two end conditions.

The code for the method of interest written in Java 8 using the Eclipse IDE follows:

   // **** Complete the flatlandSpaceStations function below. ****
    static int flatlandSpaceStations(int n, int[] c) {

    	// **** variable initialization ****
    	int dist 	= 0,
    		maxDist = 0;
    	
    	// **** sort the cities with space stations ****
    	Arrays.sort(c);
    	
    	// ???? ????
    	System.out.print("c: [ ");
    	for (int i : c)
    		System.out.print(i + " ");
    	System.out.println("]");
    	    	
    	// **** check the first city ****
    	dist = c[0] - 0;
    	
    	// ???? ????
		System.out.println("dist: " + dist);
    	
		// **** update the max distance (if needed) ****
    	if (dist > maxDist)
    		maxDist = dist;

    	// **** traverse the cities ****
    	for (int i = 0; i < c.length - 1; i++) { dist = c[i + 1] - c[i]; dist /= 2; // ???? ???? System.out.println("dist: " + dist); // **** update the max distance (if needed) **** if (dist > maxDist)
    			maxDist = dist;
    	}
    	
    	// **** check the last city ****
    	dist = (n - 1) - c[c.length - 1];
    	
    	// ???? ????
		System.out.println("dist: " + dist);

		// **** update the max distance (if needed) ****
    	if (dist > maxDist)
    		maxDist = dist;

    	// **** return max distance ****
    	return maxDist;
    }

We start by sorting the array of cities that have a space station. Note the comments with ???? are the ones I added during the TDD process to make sure all is going well.

Skip the code for the first and last cities. We make use of two variables. One computes the current distance and the other is updated with the maximum distance as we loop. The first two lines in the loop could be combined into one. We could also have taken the last line and combine them. The problem with such approach is that the resulting code is harder to read and during updates issues can be introduced. Of course, in this case it does not matter. I like to always code using the same set of steps regardless of the programming language.

Now let’s go back to the first case which is the distance from the first city with a space station to the first city. That could easily be the case. The second case is similar to the first but this time we need to take into account the last city (represented by n – 1) and the last city with a space station.

Hope this makes sense. My entire solution follows:

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

/*
 * 
 */
public class Solution {

    // **** Complete the flatlandSpaceStations function below. ****
    static int flatlandSpaceStations(int n, int[] c) {

    	// **** variable initialization ****
    	int dist 	= 0,
    		maxDist = 0;
    	
    	// **** sort the cities with space stations ****
    	Arrays.sort(c);
    	
    	// ???? ????
    	System.out.print("c: [ ");
    	for (int i : c)
    		System.out.print(i + " ");
    	System.out.println("]");
    	    	
    	// **** check the first city ****
    	dist = c[0] - 0;
    	
    	// ???? ????
		System.out.println("dist: " + dist);
    	
		// **** update the max distance (if needed) ****
    	if (dist > maxDist)
    		maxDist = dist;

    	// **** traverse the cities ****
    	for (int i = 0; i < c.length - 1; i++) { dist = c[i + 1] - c[i]; dist /= 2; // ???? ???? System.out.println("dist: " + dist); // **** update the max distance (if needed) **** if (dist > maxDist)
    			maxDist = dist;
    	}
    	
    	// **** check the last city ****
    	dist = (n - 1) - c[c.length - 1];
    	
    	// ???? ????
		System.out.println("dist: " + dist);

		// **** update the max distance (if needed) ****
    	if (dist > maxDist)
    		maxDist = dist;

    	// **** return max distance ****
    	return maxDist;
    }

    
    // **** open scanner ****
    private static final Scanner scanner = new Scanner(System.in);

    
    // **** test scaffold ****
    public static void main(String[] args) throws IOException {
    	
    	// **** open buffer writer ****
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] nm = scanner.nextLine().split(" ");

        int n = Integer.parseInt(nm[0]);

        int m = Integer.parseInt(nm[1]);

        int[] c = new int[m];

        String[] cItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < m; i++) {
            int cItem = Integer.parseInt(cItems[i]);
            c[i] = cItem;
        }

        int result = flatlandSpaceStations(n, c);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        // **** close buffered writer ****
        bufferedWriter.close();

        // **** close scanner ****
        scanner.close();
    }
}

If you are interested my solution can be found in my GitHub repository.

If you have comments or questions regarding this or any other post in this blog, or if you would like me to help with any phase in the SDLC (Software Development Life Cycle) of a product or service, please do not hesitate and leave me a note below. Requests for help will remain private.

Keep on reading and experimenting. It is the best way to learn!

John

Follow me on Twitter:  @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.