Bricks and Stability Defined
This question uses the same definition of bricks and stability as Is the brick structure stable?
Let [__] represent a masonry brick and
.
.
.
BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK? . . .
BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK?
represent an arbitrary arrangement or structure of these bricks, with every other row offset by half a brick, as is usual in brick construction. The structure can extend up and to the right indefinitely, but the string representation will always be a perfectly rectangular text block (having trailing spaces where necessary) whose width is divisible by 4.
Each BRK? in the structure may either be a brick ([__]) or empty space (4 spaces).
For example, one possible (unstable - read on) structure is
[__] [__] [__]
[__] [__]
[__][__] [__]
A structure's stability is important, and a structure is only stable if every single one of its bricks is stable.
There are three ways an individual brick may be stable:
- Any brick on the ground (the lowest line of bricks) is stable.
Any brick that has two bricks directly below it is stable:
[__] <- this brick is stable [__][__] <- because these bricks hold it upAny brick that has a brick both above and below it on the same side is stable:
[__] [__] [__] [__] <- these middle bricks are stable [__] [__] because the upper and lower bricks clamp them in [__] [__] [__] [__] <- these middle bricks are NOT stable [__] [__]
(Yes, I know these rules aren't physically accurate.)
The last challenge was about determining if a structure was stable. This one is about stabilizing those that aren't.
Challenge
Write a program that takes in a potentially unstable arrangement of bricks and adds new bricks into empty brick spaces to make everything stable, printing the result. This is to be done without increasing the overall dimensions of the input text block.
The goal is to create an algorithm that makes the structure stable by adding as few bricks as possible.
This JSFiddle (source) lets you generate random arrangements of bricks for use while testing your program. (Wish I could stack snippets instead.) Width is the number of bricks on the base layer, Height is the number of brick layers, and Density is the fraction of filled brick spaces.
For example, with Width = 5, Height = 3, Density = 0.6 a possible output is
....[__]....[__]....
..[__]....[__]......
[__]............[__]
A way to stabilize this with 4 new bricks is
....[__]....[__]....
..[__][__][__][__]..
[__][__]....[__][__]
Your program must be able to stabilize any brick structure the JSFiddle can generate.
- This includes the empty string (which is considered stable).
- The brick will always be
[__]. Periods (.) are only used for clarity. Your program may use periods or spaces for empty space. - The structure may already be stable, in which case nothing needs to be done (besides printing it).
- The JSFiddle always generates structures that can be stabilized (by avoiding
Width = 1and bricks in the top corners). You can rely on this. (Filling all but the top corners is sure to stabilize things but this is clearly not optimal.) - Assume no invalid input. Take input as string however you like. Print the stabilized structure to stdout or similar.
- Remember that the text block dimensions should not change size.
- Preexisting bricks cannot be moved or removed. Placement of new bricks must follow the offset-every-other-row grid pattern. All bricks must be completely in bounds.
- It is encouraged (but not required) that you print the preexisting bricks as
[XX]instead of[__], so people can better see how your solution works.
Scoring
At the bottom of the JSFiddle are 8 predefined unstable brick arrangements. (They use [__] and . and should stay that way unless you're using [XX] and/or instead.) Some are random and some I created myself. To calculate your score, run your program on each of them in turn and sum the number of new bricks added to each.
The less new bricks you've added the better. The submission with the lowest score wins. In case of ties the oldest answer wins.
If things get contentious I may add a few more predefined cases and judge the winner based on them.
Further Notes
- Your program needs to run on the order of minutes on a modern computer for brick grid width and height less than 100. (Max 10 minutes on a computer like this.)
- You may not hardcode your output for the 8 predefined structures. Your program must treat them as it would treat any other arrangement.
- Please include an example output or two, or any interesting structures you'd like to share. :)
- This problem is somewhat related to finding a minimum spanning tree.
