3D Surface Area

Good morning. It is Monday January 06, 2020. Last year’s holiday season was rather long. Christmas fell on Wednesday so most companies gave Tuesday as a holiday. On the following week, most companies do not give New Years Eve day as a holiday but most people take it as a personal holiday or vacation day. I work every day (included weekends and holidays). Granted that on weekends and holidays I only sit in front of my computer for only two 2-hour blocks.

If you are new to this blog, I use the Deep Work method by Cal Newport to break up the day into manageable and more important, productive segments (or blocks). If interested in Deep Work, Cal has published several books on the subject. I typically do five 2-hour blocks on workdays. On weekends I only do two. After each block a take a few minutes to walk and get something to drink. Breaks take on average 15 minutes each.

The reason that I have time for five blocks is because I am a morning person. I wake up no later than 05:00 AM, have breakfast with my wife, get ready for work and start the five cycles. The lunch break (third break after the first three blocks) is lunch. That tends to take 30 to 45 minutes. In the afternoon I do the last two blocks of the day.

Typically I am done for the day around 05:00 PM. At that time, my wife and I sit down in the living room to chat about the events of day while looking at photos from different albums on Google Home on the TV using Google Chromecast, or watch a movie (i.e., Amazon Prime, Netflix).

My end of day is around 07:00 PM. Typically around 08:00 PM we are both asleep.

Of course if something changes on the schedule (i.e., party, trip, get together) typically on weekends, the schedule changes. When I am away from home, I just read. I used to haul a laptop, but found that it is not convenient and it is good to get completely away from work when the occasion arises.

Yesterday I selected the HackerRank problem 3D Surface Area. If interest you can read the description at the HackerRank web site.

The idea is to compute all the exposed surface areas from a structure built using cubes of 1 x 1 x 1 units. HackerRank describes a sample using a 3 x 3 matrix. My suggestion is to first concentrate on the 1 x 1 example to figure out what needs to be done.

1 1
1

widthView <<< area: 2
heightView <<< area: 2
verticalView <<< area: 2
6

If we look at a 1 x 1 x 1 cube we have six perpendicular possible views. These are horizontal right and left, vertical top and bottom, and depth in and out. It seems that we could add the exposed areas of the 1 x 1 x 1 cubes by only using one pass per dimension.

Let’s take a look at an array of one row and five columns  as illustrated by the following example:

1 5
4 1 3 5 2

widthView <<< area: 16
heightView <<< area: 30
verticalView <<< area: 10
56

The first column contains 4 cubes, the second 1, the third column 3, the fourth column 5 and the last column 2 cubes.

Now let’s traverse the object from the width view, the horizontal view and finally from the vertical view. On each traversal let’s count the exposed areas of the 1 x 1 x 1 cube.

On the width view we traverse from left to right. On the first column we are looking at 4 areas. On the second column we are looking at the 3 areas on the back of the first column so be add 3 to the total area. On the third column we see 2 areas so we add them to the total area. On the fourth column we see 2 areas. Finally on the last column we see 3 areas. But wait, we also need to add the area of the last column which is 2. We have an area of  4 + 3 + 2 + 2 + 3 + 2 = 16 for this view.

On the height view we look at the blocks from front to back. Since we only have a single row, we add the areas we see which correspond to the heights of the blocks. The front area is  4 + 1 + 3 + 5 + 2 = 15, but we also need to take into account the area in the back which is also 15 so the total area for this view is 15 + 15 = 30.

On the vertical view we have a single row of 5 cubes. The top area is 5 units and the bottom area is another 5 units so the total area is 5 + 5 = 10.

The total area of all exposed faces is: 16 + 30 + 10 = 56 units.

3 3
1 3 4
2 2 3
1 2 4

widthView <<< area: 22
heightView <<< area: 20
verticalView <<< area: 18
60

In the last screen capture from the Visual Studio Code IDE run of the software, we can verify that the solution returns the proper result for the second example presented and discussed by HackerRank.

3 5
5 1 5 1 5
1 4 1 4 1
0 3 1 3 0

widthView <<< area: 50
heightView <<< area: 46
verticalView <<< area: 26
122

In this screen capture we see an example that I created to verify that the code handles end conditions. As you can see the last row contains two cells with no cubes.

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

  /*
   * Test scaffolding.
   */
  public static void main(String[] args) throws IOException {

    // **** output buffered writter ****
    BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

    // **** get and parse the width and height ****
    String[] HW = scanner.nextLine().split(" ");
    int H = Integer.parseInt(HW[0]);
    int W = Integer.parseInt(HW[1]);

    // **** declare array ****
    int[][] A = new int[H][W];

    // **** populate array ****
    for (int i = 0; i < H; i++) {
      String[] ARowItems = scanner.nextLine().split(" ");
      scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

      // **** ****
      for (int j = 0; j < W; j++) {
        int AItem = Integer.parseInt(ARowItems[j]);
        A[i][j] = AItem;
      }
    }

    // **** computer the surface area ****
    int result = surfaceArea(A);

    // **** display the result ****
    bufferedWriter.write(String.valueOf(result));
    bufferedWriter.newLine();

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

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

The modified test scaffolding shows the edited code with some comments. I always like to understand how the data is being prepared and presented to the function / method that needs to be filled in with the base for the solution.

Also note that the scanner definition line has been edited. I replaced the use of an environment variable with sending the output directly to an Output Stream Writer using System.out. Starting on my next post I decided that I will use a system environment variable. Once properly set and defined I will not have to edit the line in question.

  /*
   * Complete the surfaceArea function below.
   */
  static int surfaceArea(int[][] A) {

    // **** ****
    int area = 0;

    // **** compute width view area ****
    area += widthView(A);

    // **** compute height view area ****
    area += heightView(A);

    // **** compute vertical view area ****
    area += verticalView(A);

    // **** ****
    return area;
  }

This is the function that needs to hold the solution. You could just write all the code in it or implement it with additional functions. I decided to use the second approach. In retrospect we could refactor the first two calls into one with additional arguments. For testing and maintenance (not in this case) I prefer simple and straightforward code with is easy to maintain.

  /*
   * Compute width (horizontal) view area.
   */
  static int widthView(int[][] A) {

    // **** ****
    int H = A.length;
    int W = A[0].length;

    // **** loop once per row ****
    int area = 0;
    for (int row = 0; row < H; row++) {

      // **** area of first column ****
      area += A[row][0];

      // **** compute area(s) for each column ****
      for (int col = 1; col < W; col++) {
        area += Math.abs(A[row][col] - A[row][col - 1]);
      }

      // **** area of last column ****
      area += A[row][W - 1];
    }

    // ???? ????
    System.out.println("widthView <<< area: " + area);

    // **** ****
    return area;
  }

What we wish to compute is the sum of all areas exposed by all cubes when we view the structure from a horizontal perspective. If we do it right, we will get the sum of exposed areas in both directions (i.e., left to right and right to left).

We loop once per row. We add the area exposed by the first column and then loop adding the differences in all the exposed areas for each of the remaining columns. After the loop, we consider the exposed areas of the last column. Using such approach we achieve the complete sum of areas using a single function. We could have addressed each direction using two functions, but it seems more elegant to use one. The single function is easy to understand and follow.

  /*
   * Compute the area for height (vertical) view.
   */
  static int heightView(int[][] A) {

    // **** ****
    int H = A.length;
    int W = A[0].length;

    // **** loop once per column ****
    int area = 0;
    for (int col = 0; col < W; col++) {

      // **** area of first row ****
      area += A[0][col];

      // **** compute areas(s) for each row ****
      for (int row = 1; row < H; row++) {
        area += Math.abs(A[row][col] - A[row - 1][col]);
      }

      // **** area of last row ****
      area += A[H - 1][col];
    }

    // ???? ????
    System.out.println("heightView <<< area: " + area);

    // **** ****
    return area;
  }

In this function we compute the area of all exposed cubes when looking at the structure in the height (vertical) perspective. The function is very similar to the previous one. We have just swapped the rows with the columns.

So far we have computed the sum for four of the six views.

  /*
   * Compute area for vertical view.
   */
  static int verticalView(int[][] A) {

    // **** ****
    int H = A.length;
    int W = A[0].length;

    // **** ****
    int area = 0;
    for (int row = 0; row < H; row++) {
      for (int col = 0; col < W; col++) {
        if (A[row][col] != 0)
          area++;
      }
    }

    // **** duplicate for opposite direction ****
    area *= 2;

    // ???? ????
    System.out.println("verticalView <<< area: " + area);

    // **** ****
    return area;
  }

In this function we are only interested in counting the cubes that are exposed from the top or the bottom of the structure. We count all columns in all rows with cubes or all rows in all columns with cubes. That gives us the area viewed from the top or the bottom in the structure. By multiplying it by 2 we get the last dimension.

Hope you enjoyed this problem. Make sure you define the WIDTH and the HEIGHT properly. Both samples provided by HackerRank work if the associated definitions are swapped (i.e., 1 x 1 and 3 x 3) because they are the same.

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, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a message using the following address:  john.canessa@gmail.com. All messages will remain private.

Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!

John

Twitter:  @john_canessa

Leave a Reply

Your email address will not be published.

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