Solution to sigma2012 (Stone-Wall) by codility

23 Jan


Question Name: sigma2012 or StoneWall

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

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!