Solution to sigma2012 (Stone-Wall) by codility

23 Jan


Question Name: sigma2012 or StoneWall

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

  1. My solution in Swift

  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.

  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

  4. 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%:

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

  5. 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 🙁

    • 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 🙂

  6. 100% python:

  7. 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).

  8. A simple c# solution

Leave a Reply

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

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!