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:

1. Any brick on the ground (the lowest line of bricks) is stable.
2. Any brick that has two bricks directly below it is stable:

  [__]   <- this brick is stable
[__][__] <- because these bricks hold it up

3. Any 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 = 1 and 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.
• I should point out that the "stabilized" example under "Challenge" isn't actually stable per the stated criteria.
– COTO
Commented Oct 11, 2014 at 8:20
• @COTO Indeed. Fixed. Commented Oct 11, 2014 at 8:27
• in your example the middle bottom brick is not needed to stabilise the structure. Commented Oct 11, 2014 at 11:03
• @JanDvorak: It states "a way" to stabilize, not "the optimal way", so technically it's not an error. But I agree that taking the middle bottom brick out might help drive home the fact that physical intuition isn't our friend in this problem. ;)
– COTO
Commented Oct 11, 2014 at 14:40
• @JanDvorak COTO is right, it didn't matter that it wasn't optimal, but I've changed it nonetheless. Commented Oct 11, 2014 at 15:14

Java - 5,056 bricks

• 20x20, 0.03 - 75
• 15x81, 0.05 - 431
• 50x50, 0.20 - 882
• 99x99, 0.01 - 2,567
• Plain Pedestal - 269
• Simple House - 129
• Criss-Cross Tower - 323
• Bridge Beginnings - 380

Source code is viewable here.

The code runs in a few milliseconds for any of the 8 scoring inputs. There are some noticeably suboptimal outputs, particularly in the criss-cross tower and 99x99 cases. I have several ideas on how to improve the routine, but it's fairly bulky as-is, and hence I'll let it alone for now.

The outputs massacre the laws of physics to a comedic extent. :D

Some samples are shown below.

20x20, 0.03 Output

................................................................................
..........[XX]..................................................................
........[  ][  ]................................................................
..........[  ]..................................................................
............[  ]................................................................
..........[  ]..................................................................
............[  ]....................[XX]........................................
..........[  ]....................[  ][  ]......................................
....[XX]....[  ]....................[  ]........................................
..[  ][  ][  ][  ]................[  ]..........................................
....[XX]....[  ][XX]................[  ]........................................
..[  ]........[  ]................[XX]..........................................
....[  ]........[  ]............[  ][  ]........................................
..[  ]........[  ]................[  ]..........................................
....[  ]........[  ]............[XX]................................[XX]........
..[  ]........[  ]....[XX]........[  ]................[XX]........[  ][XX][  ]..
....[  ]........[  ][  ][  ]....[  ]....[XX]........[  ][  ]........[  ][  ][XX]
..[  ][  ]....[  ]....[  ]........[XX][  ][  ]........[  ]........[  ]....[  ]..
....[  ]........[  ]....[  ]....[  ]....[  ]............[  ]........[  ]....[  ]
......[XX]....[  ]....[  ]........[  ][  ]............[  ]........[  ]....[  ]..
....[  ]........[  ]....[  ]....[  ]....[  ]....[XX]....[  ]........[  ]....[  ]


Simple House Output

................................................................................
................................................................................
................................................................................
......................................[XX]......................................
....................................[XX][XX]....................................
..................................[XX][  ][XX]..................................
................................[XX][  ][  ][XX]................................
..............................[XX][  ]....[  ][XX]..............................
............................[XX][  ]........[  ][XX]............................
..........................[XX][  ]............[  ][XX]..........................
........................[XX][  ]................[  ][XX]........................
......................[XX][  ]....................[  ][XX]......................
....................[XX][  ]........................[  ][XX]....................
..................[XX][  ]............................[  ][XX]..................
................[XX][  ]................................[  ][XX]................
..............[XX][  ]....................................[  ][XX]..............
............[XX][  ]........................................[  ][XX]............
..........[XX][  ]............................................[  ][XX]..........
........[XX][  ]................................................[  ][XX]........
......[XX][  ]................................................[  ][  ][XX]......
....[XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX]....
......[XX][  ][  ][  ][  ][  ][  ][  ][  ][  ][  ][  ][  ][  ][  ]....[XX]......
....[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]........[XX]....
......[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[XX]......
....[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]........[XX]....
......[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[XX]......
....[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]........[XX]....
......[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ][  ][  ]....[XX]......
....[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ][  ][  ]........[XX]....
......[XX]....[XX][XX][XX][XX][  ]....[XX][XX][XX][XX][XX][XX]........[XX]......
....[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ][  ]............[XX]....
......[XX]....[XX]....[  ][XX]........[XX]....[  ]....[  ][XX]........[XX]......
....[XX]....[  ]....[  ][  ][  ]....[  ]....[  ]........[  ]............[XX]....
......[XX]....[XX]....[  ][XX]........[XX]....[  ]........[XX]........[XX]......
....[XX]....[  ]........[XX]........[  ]....[  ]........[  ]............[XX]....
......[XX]....[XX]........[XX]........[XX][XX][XX][XX][XX][XX]........[XX]......
....[XX]....[  ]........[  ]........[  ]....[  ][  ][  ][  ]............[XX]....
......[XX]....[XX]........[XX]........[  ]....[  ]....[  ]............[XX]......
....[XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX]....


Python, 18992

This is the most simplistic solution and the worst score possible. It's only for reference; the thing to beat. It fills every empty space except the two top corners with bricks, guaranteeing stability.

s = '''
....[__]....[__]....
..[__]....[__]......
[__]............[__]
'''

def brickify(structure):
structure = filter(lambda x: x, s.replace('__', 'XX').split('\n'))
if not structure:
return '', 0
if len(structure) > 1 and len(structure) % 2:
structure[0] = '----' + structure[0][4:-4] + '----'
offset = False
for i in range(len(structure)-1,-1,-1):
line = structure[i]
if offset:
line = line[2:-2]
line = line.replace('....', '[__]')
if offset:
line = '..' + line + '..'
structure[i] = line
offset = not offset
structure[0] = structure[0].replace('----', '....')

s, a = brickify(s)

#print '\nNew bricks:', a

for line in s:
print line


To use copy the initial structure into the triple quotes at the top of the program.

Here it is run on the house, adding 609 bricks:

..[__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__]..
[__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__]
..[__][__][__][__][__][__][__][__][__][XX][__][__][__][__][__][__][__][__][__]..
[__][__][__][__][__][__][__][__][__][XX][XX][__][__][__][__][__][__][__][__][__]
..[__][__][__][__][__][__][__][__][XX][__][XX][__][__][__][__][__][__][__][__]..
[__][__][__][__][__][__][__][__][XX][__][__][XX][__][__][__][__][__][__][__][__]
..[__][__][__][__][__][__][__][XX][__][__][__][XX][__][__][__][__][__][__][__]..
[__][__][__][__][__][__][__][XX][__][__][__][__][XX][__][__][__][__][__][__][__]
..[__][__][__][__][__][__][XX][__][__][__][__][__][XX][__][__][__][__][__][__]..
[__][__][__][__][__][__][XX][__][__][__][__][__][__][XX][__][__][__][__][__][__]
..[__][__][__][__][__][XX][__][__][__][__][__][__][__][XX][__][__][__][__][__]..
[__][__][__][__][__][XX][__][__][__][__][__][__][__][__][XX][__][__][__][__][__]
..[__][__][__][__][XX][__][__][__][__][__][__][__][__][__][XX][__][__][__][__]..
[__][__][__][__][XX][__][__][__][__][__][__][__][__][__][__][XX][__][__][__][__]
..[__][__][__][XX][__][__][__][__][__][__][__][__][__][__][__][XX][__][__][__]..
[__][__][__][XX][__][__][__][__][__][__][__][__][__][__][__][__][XX][__][__][__]
..[__][__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__][__]..
[__][__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__][__]
..[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]..
[__][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][__]
..[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][XX][XX][XX][XX][__][__][XX][XX][XX][XX][XX][XX][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][XX][__][__][XX][__][__][XX][__][__][__][__][XX][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][XX][__][__][XX][__][__][XX][__][__][__][__][XX][__][__][XX][__]..
[__][XX][__][__][__][__][XX][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][XX][__][__][XX][__][__][XX][XX][XX][XX][XX][XX][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][XX][__][__][XX][__][__][__][__][__][__][__][__][__][__][XX][__]..
[__][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][__]


The number of bricks it adds for each of the 8 predefined structures in order are

374 1107 2041 9627 506 609 1088 3640 (sum to 18992)

• Line 20, brick 19 is missing a left bracket. Commented Oct 11, 2014 at 13:14
• @golfer9338 Thanks for noticing. Fixed in post and jsfiddle. Commented Oct 11, 2014 at 15:19
• Not to make it too smart, but do you need to add any bricks to the top row? Commented Oct 11, 2014 at 18:28
• @Sparr No you don't. But this is intended to give the worst possible score just as a demonstration. Commented Oct 11, 2014 at 18:40