Solution to sigma2012 (Stone-Wall) by codility

23 Jan


Question Name: sigma2012 or StoneWall

13 thoughts on “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:

Leave a Reply

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