Stone Wall

Good day! Hope all is well in your neck of the woods. My wife left lunch in the oven and ran to the dentist office. She left the oven on. Not sure when I should shut it down. I think I will do it right now before the food gets burned. When she gets back we can turn on the oven back if needed.

OK, the oven is off. It is 01:00 PM. I am starving. Hope my wife returns shortly so we can have lunch.

Earlier today I worked on the Codility_ problem StoneWall which requires us to cover the “Manhattan skyline” using the minimum number of rectangles. I had a hard time understanding what the problem was about.

You are going to build a stone wall.

The wall should be straight and N meters long, 
and its thickness should be constant; 
however, it should have different heights in different places.

The height of the wall is specified by an array H of N positive integers. 
H[I] is the height of the wall from I to I+1 meters to the right of its left end. 
In particular, H[0] is the height of the wall's left end and H[N−1] is the height 
of the wall's right end.

The wall should be built of cuboid stone blocks (that is, all sides of such blocks are rectangular).

Your task is to compute the minimum number of blocks needed to build the wall.

Note that I separated the description into several paragraphs.

The second paragraph indicates that the wall is N meters in length since each block has a width of one meter. The fifth paragraph indicates that we should use less blocks than what we were given. This implies that we need to remove some blocks which will not produce a wall of N meters as stated in the second paragraph.

To solve this problem, we will be using Java and the VSCode IDE on a Windows computer. Because of this, we will need to build a test scaffold which will read in the input line holding the heights of the blocks, generate an int[] with the values, call the function of interest and display the result. Please note that the test scaffold IS NOT PART OF THE SOLUTION. If you use the Codility_ online IDE you can develop and test your code.

public int stoneWall(int[] arr) {
}

The signature for the function of interest is simple. We are given as an argument the heights of the blocks that make up the skyline and we need to return the minimum number of blocks needed to build the wall (of N blocks???).

We are provided with a single test case.

8, 8, 5, 7, 9, 8, 7, 4, 8
main <<< arr: [8, 8, 5, 7, 9, 8, 7, 4, 8]
<<< h: 8
<<< stack: []
<<< stack: [8] blockCount: 1
<<< h: 8
<<< stack: [8]
<<< h: 5
<<< stack: []
<<< stack: [5] blockCount: 2
<<< h: 7
<<< stack: [5]
<<< stack: [5, 7] blockCount: 3
<<< h: 9
<<< stack: [5, 7]
<<< stack: [5, 7, 9] blockCount: 4
<<< h: 8
<<< stack: [5, 7]
<<< stack: [5, 7, 8] blockCount: 5
<<< h: 7
<<< stack: [5, 7]
<<< h: 4
<<< stack: []
<<< stack: [4] blockCount: 6
<<< h: 8
<<< stack: [4]
<<< stack: [4, 8] blockCount: 7
<<< hc: {4=1, 5=1, 7=1, 8=3, 9=1}
main <<< result: 7

The first line contains the values that need to be read into an int[] array. Our test scaffold reads the values, populates the int[] array `arr` and displays the values. This is done to be able to check if all is well so far. Since the values match, we are ready to build the wall.

There is a set of values displayed by the function of interest. They are there to allow us to follow the algorithm.

When all is said and done, the function of interest returns the result and our test code displays it.

Please note that we are displaying some values from a hashmap named `hc`. I just added the hashmap object to track the heights of the blocks and the associated numbers which we will need to build the wall (of N blocks???).

    /**
     * Test scaffold
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open a buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read int[] arr ****
        int[] arr = Arrays.stream(br.readLine().trim().split(", "))
                        .mapToInt(Integer::parseInt)
                        .toArray();

        // **** close buffered reader ****
        br.close();
        
        // ???? ????
        System.out.println("main <<< arr: " + Arrays.toString(arr));

        // **** call function of interest and display result ****
        System.out.println("main <<< result: " + stoneWall(arr));
    }

Our test scaffold is simple and direct to the point. I do not have much to add at this point.

    /**
     * What is the minimum number of buildings required to produce the given skyline?
     * 
     * Given an array H of N positive integers specifying the height of the wall, 
     * return the minimum number of blocks needed to build it.
     * 
     * Observations:
     * 
     * o If the two horizontal edges are adjacent to the same stone block, 
     *   they must be at the same height. 
     * o The stone wall between the two edges cannot be lower than them.
     * 
     * Keep on a stack a sequence of horizontal edges, 
     * such that their heights form an increasing sequence.
     *
     * Runtime: O(n) - Space: O(n)
     */
    static public int stoneWall(int[] arr) {

        // **** initialization ****
        int blockCount                  = 0;
        Stack<Integer> stack            = new Stack<>();

        // ???? ????
        HashMap<Integer, Integer> hc    = new HashMap<>();

        // **** traverse the wall counting blocks - O(n) ****
        for (int h : arr) {

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

            // **** remove blocks higher than h ****
            while (!stack.isEmpty() && stack.peek() > h)
                stack.pop();

            // ???? ????
            System.out.println("<<< stack: " + stack.toString());
            
            // **** ****
            if (!stack.isEmpty() && stack.peek() == h)
                continue;
            else {

                // **** push this height ****
                stack.push(h);

                // **** count this block ****
                blockCount++;

                // ???? update the height count hashmap ????
                Integer c = hc.putIfAbsent(h, 1);
                if (c != null) hc.put(h, ++c);
            }

            // ???? ????
            System.out.println("<<< stack: " + stack.toString() + " blockCount: " + blockCount);
        }

        // ???? ????
        System.out.println("<<< hc: " + hc.toString());

        // **** return block count ****
        return blockCount;
    }

To start please read the comments section in the function of interest. The idea is to take the wall described by the int[] `arr` and remove some blocks in order to approximate the wall of N meters to a smaller one. We will be approximating the actual wall! This has to be done in a way that the result looks close to the original.

So how do we do this approximation? The answer is in the two points in the observation in the comment section of the function. With this information on hand, we can now write a solution that will approximate the wall with less blocks. Note that in our test case, we will be dropping two blocks. One will be with height 7 and the other with height 8. In our example we start with 9 blocks and end up with a wall with 7 which is an approximation of the original.

Our function of interest starts initializing some variables. The `hc` hashmap is there only to develop and debug the solution. The `stack` is part of the solution as we will see shortly, and the `blockCount` will be used to count the blocks that remain from the initial N (9 in our test case) down to 7.

The main loop is used to traverse the wall from left to right one block per pass.

We need to keep in the `stack` blocks in ascending order. This way we can remove the ones that are larger to the current `h`.

We then decide if we need to push `h` into the stack. If so, we count the block. Note that the blocks that we skip will not be used in the wall and will be reducing the length of the wall. In this test case, from 9 to 7.

When all is said and done, our function returns the block count.

I am not too sure that the requirements were clear enough to design a solution. Among my web searches I run into different implementations and documents. Of interest was the .pdf Stone Wall.

Hope you enjoyed solving this problem more than I did. The entire code for this project can be found in my GitHub repository.

Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different websites (i.e., HackerRank, LeetCode). This does not seem to be the case with Codility_. Perhaps I am wrong.

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 / engineering toolset.

As soon as I complete thsi post and publish it, will continue reading the book Designing Data-Intensive Applications by Martin Kleppmann.

Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.

Enjoy;

John

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.