Question Name: sigma2012 or StoneWall
Solution to sigma2012 (Stone-Wall) by codility
stack = 
block_count = 0 # The number of needing blocks
for height in H:
while len(stack) != 0 and height < stack[-1]:
# If the height of current block is less than
# the previous ones, the previous ones have
# to end before current point. They have no
# chance to exist in the remaining part.
# So the previous blocks are completely finished.
block_count += 1
if len(stack) == 0 or height > stack[-1]:
# If the height of current block is greater than
# the previous one, a new block is needed for
# current position.
# Else (the height of current block is same as that
# of previous one), they should be combined to
# one block.
# Some blocks with different heights are still in the stack.
block_count += len(stack)
My solution in Swift
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.
Please refer to the official solution: http://blog.codility.com/2012/06/sigma-2012-codility-programming.html
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.
Here is the new link to the official solution 🙂
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
I do not use Java much. But why didn’t you use java.util.Stack?
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.
Could you please explain why this is the minimum? the official solution is not very clear.
Sorry, I do not know how to prove it. You could consider to build the blocks from bottom to top.
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.
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:
Thanks for sharing!
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 🙂
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 = H), 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).
Thanks very much for the contribution!
A simple c# solution