Solution to sigma2012 (Stone-Wall) by codility

23 Replies to “Solution to sigma2012 (Stone-Wall) by codility”

1. My solution in Swift

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   func solution(heights: [Int], length: Int) -> Int {     var stack = [Int]()     var numberBlocks = 0     for height in heights {         if stack.isEmpty || stack.last > height {             while stack.last > height {                 stack.removeLast()             }             if stack.last != height {                 stack.append(height)                 numberBlocks++             }         }     }     return numberBlocks }

   Reply

   • Swift~ Cool!

     Reply

2. I don’t get the intuition for this. Why does this work? I can see that by cutting horizontally the wall/skyline by the lowest horizontal edge, you can get the correct answer, but I don’t understand how this algorithm finds the minimal amount of stone blocks to use.

   Reply

   • Please refer to the official solution: http://blog.codility.com/2012/06/sigma-2012-codility-programming.html

     Reply

     • Sheng, looks like they took down that page. If that information available somewhere else or is there a similar type problem to understand the StoneWall problem.
       Thanks

       Reply

       • Here is the new link to the official solution 🙂
         https://codility.com/media/train/solution-stone-wall.pdf

         Reply

3. hehehe, I feel bad because I defined my own Stack backed by an ArrayList so it’s a lot of code, but it works 100/100
   https://codility.com/demo/results/demoX7Z9X3-HSB/

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

   import java.util.ArrayList; import java.util.List; public class StoneWall {       public int solution(int[] H) {           int len = H.length;           Stack<Integer> stack = new Stack<>(len);           int blockCounter = 0;           for (int i = 0; i < len; ++i) {               int element = H[i];               if (stack.isEmpty()) {                   stack.push(element);                   ++blockCounter;               } else {                   while (!stack.isEmpty() && stack.peek() > element) {                       stack.pop();                   }                   if (!stack.isEmpty() && stack.peek() == element) {                      continue;                   } else {                       stack.push(element);                       ++blockCounter;                   }               }           }           return blockCounter;       }       public static class Stack<T> {           public List<T> stack;           public Stack(int capacity) {               stack = new ArrayList<>(capacity);           }           public void push(T item) {               stack.add(item);           }           public T pop() {               T item = peek();               stack.remove(stack.size() - 1);               return item;           }           public T peek() {               int position = stack.size();               T item = stack.get(position - 1);               return item;           }           public boolean isEmpty() {               return stack.isEmpty();           }       }   }

   Reply

   • I do not use Java much. But why didn’t you use java.util.Stack?

     Reply

     • To be honest I was just trying to implement my own definition of Stack to see if I was able to remember that from college, but in later examples I’ll use java.util.Stack or some class that implements Deque.

       Reply

       • Understandable.

         Reply

4. Hi again,
   Could you please explain why this is the minimum? the official solution is not very clear.

   Reply

   • Sorry, I do not know how to prove it. You could consider to build the blocks from bottom to top.

     Reply

5. A kind of not optimized and slow version, but shows how divide and conquer method might be used. The method builds the wall using horizontal blocks instead of vertical.
   https://codility.com/demo/results/training9E9TAZ-6S5/

   Reply

6. I drew three pages of stacks and blocks to see if my logic would be correct ;-). It is hard to explain perfectly why I did what I did (like Sheng says) but let’s try. Basically I work on levels. A new level would be created when a segment has a different height than the previous one. The new level can have a higher height or a lower height. If you draw it on paper (and even by looking at the photo on the Codility page, every time the height drops, you basically close a construction block.
   Using a stack, I add levels to it as long as the height increases. When the height decreases, I take levels out, but I increment a counter for the building blocks. I take levels out until the height of the level on the stack is lower than my current segment. In the end, when all the segments are finished, I add one construction block for each level in the stack.
   Anyway, here is my C# solution that scored 100%:
   https://codility.com/demo/results/trainingC5ZH2U-JNH/

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

   private static int solution(int[] H)   // this solution scored 100% {    int blocks = 0;    var levels = new Stack<int>();    for (int i = 0; i < H.Length; i++)    {       if (levels.Count == 0)       {          levels.Push(H[i]);       }       else       {          var lastLevel = levels.Peek();          if (lastLevel < H[i])          {             levels.Push(H[i]);          }          else if (lastLevel == H[i])          {             // nothing to do          }          else // lastLevel > H[i]          {             // keep popping levels until one is smaller than the current one             while (true)             {                levels.Pop();  // pop the last level                blocks++;      // increment the block counter                if (levels.Count == 0)                {                   // nothing left to pop                   levels.Push(H[i]);   // push current level                   break;                }                // else, there are more levels in the stack                lastLevel = levels.Peek();                if (lastLevel < H[i])                {                   // no need to pop-up any more levels                   levels.Push(H[i]);   // push current level                   break;                }                else if (lastLevel == H[i])                {                   // no need to pop-up any more levels and no need to push a new level either                   break;                }                // else, repeat the while loop             }          }       }    }    blocks += levels.Count;    return blocks; }

   Also, all the tests that I did until I got it right:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   var result = solution(new int[] {8, 8, 5, 7, 9, 8, 7, 4, 8});  // expect 7 result = solution(new int[] { 8 });  // expect 1 result = solution(new int[] { 8, 5 });  // expect 2 result = solution(new int[] { 8, 8 });  // expect 1 result = solution(new int[] { 8, 15 });  // expect 2 result = solution(new int[] { 8, 15, 17 });  // expect 3 result = solution(new int[] { 8, 17, 15 });  // expect 3 result = solution(new int[] { 8, 15, 8 });  // expect 2 result = solution(new int[] { 8, 8, 8 });  // expect 1 result = solution(new int[] { 15, 8, 17 });  // expect 3 result = solution(new int[] { 17, 8, 15 });  // expect 3 result = solution(new int[] { 9, 8, 8 });  // expect 2 result = solution(new int[] { 15, 18, 17 });  // expect 3 result = solution(new int[] { 15, 18, 14 });  // expect 3 result = solution(new int[] { 9, 9, 8 });  // expect 2

   Reply

   • Thanks for sharing!

     Reply

7. Hi Sheng. Thank you for sharing your solutions. I really admire their elegance. I tried to make myself an algorithm and used a linked hash set to simmulate a queue that has no identical elements. However, it doesn’t seem to provide correct answers in all the tested cases.
   I know you probably get these requests a lot, bout could you please take a look and explain to me why this is wrong? I don’t get it 🙁

   Reply

   • Sorry Ana, I cannot help you to debug. However, I can show how to debug with Codility 🙂 Codility platform supports to output log. So you can output the input at the beginning of your function. With the failed cases, debug locally with your preferred method. That’s what I did 🙂

     Reply

8. 100% python:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

   def solution(H):     n = len(H)     counter = 1     stack = [H[0]]          for i in range(1, n):                  if H[i] == stack[-1]:             continue         elif H[i] < stack[-1]:             while H[i] < stack[-1]:                 stack.pop()                 if (len(stack) == 0) or (H[i] > stack[-1]):                     stack.append(H[i])                     counter += 1                     break                 elif stack[-1] == H[i]:                     break         else:             stack.append(H[i])             counter += 1                        return counter

   Reply

9. Hey guys, I really struggled against that problem. I couldn’t even understand exactly what the problem wanted us to solve. After a couple of days, I finally figured out and also figured out how Sheng’s solution works. Here’s the overview for anyone that are still struggling:

   What the exercise want is to find the minimum amount of cuboid blocks to build a wall, and that wall can have different heights in different positions.

   In the exercise’s array example “H”, using “brute force” we could have 9 blocks, 1 occupying each position of the array.

   But in the statement, it’s shown that it’s possible to build that wall with 7 blocks(see the image) instead of 9. Our job is to find how.

   One way to solve this, is imagining that for each position in the array, we start drawing a block from that position, to the right.

   We don’t stop drawing them to the right until certain conditions are met. The conditions are logical based on the information that we need cuboid stone blocks.

   This becomes clear with the following example:

   If we have 2 blocks, the left block can’t keep growing to the right if the right block is shorter. We would have a block with an odd shape(like an inverted L), like this:

   _______________
   | block 1
   | _________
   | | ________
   | ||
   | || block 2
   |_____||________

   So we can’t have the configuration above, as we need cuboid stone blocks. So in that situation, we say the left block is actually finished. The second would keep being “drawn”:

   _____
   | | <–* block 1 finished
   | |
   | | ______
   | | |
   | | | <–* block 2 still being drawn
   |_____| |______

   A valid configuration of coexistence is when the left block is smaller that the right one, like this:

   ________
   |
   | block 2
   _______|________
   |
   |
   | block 1
   |
   |
   |________________

   In that configuration we can have both blocks existing, by having the right block on top of the left block.

   And finally, if we have 2 blocks with the same height(say H[0] = H[1]), we combine those two, which will form only one block.

   The key point of this solution is to grow blocks to the left to occupy the most space as possible, but not ignoring both the fact that we need cuboid blocks, and that we need certain parts with certain heights(so we "pile" the blocks).

   Reply

   • Thanks very much for the contribution!

     Reply

   • THanks!

     Reply

10. A simple c# solution

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

    public int solution(int[] A) {             int blocksCount = 0;             List<int> previousLevels = new List<int>();               for (int i = 0; i < A.Length; i++) {                 bool continuation = previousLevels.Contains(A[i]);                   previousLevels.RemoveAll(x => A[i] < x);                   if (!continuation) {                     blocksCount++;                     previousLevels.Add(A[i]);                 }             }             return blocksCount;         }

    Reply

11. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

    def solution(H):     heights = H     # geometric logic: the blocks need to be cuboid, all sides are rectagular. Nothing fancy, means that the angles     # need to be 90 deg.     # Translated into code, any time your height changes, you start a new block.     # Going up, would lead to a 270 deg angle,     # while going down, the same.     # Your ground level is 0 when you start. But doesn't have to stay that way. To reduce the number of blocks, you     # raise the ground level to the lowest common floor. You build blocks on that while you can, that is     # while you don't go     # any lower.       # Do blocks need to be individual objects? You only need to count them, so no.       blocks_count = 0     levels = [0]       for i in heights:           # Going down.         if i < levels[-1]:             # If you drop to a level already attained, there is no change of angle, so no new block. This will be the             # continuation of a block already counted. Simply dropping does not create a new block, while simply rising             # always does create a new block. This asymmetry is a consequence of moving from left to right.             levels.pop()             while i < levels[-1]:                 levels.pop()             if i > levels[-1]:                 blocks_count += 1             levels.append(i)         # Going up.         elif i > levels[-1]:             blocks_count += 1             levels.append(i)     return blocks_count

    Reply