Animating the Separation of Fluids by Density

Question

Let the characters 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ represent the particles of 36 immiscible fluids, each more dense than the last. So the 0 fluid is the least dense and floats on all the others, while Z is the densest and always sinks.

Let # represent a solid particle that cannot move at all..

Consider a rectangular grid of some of these 37 characters, with anything out of bounds treated as #. Gravity will want to stabilize them with the least dense fluids on top and the most dense on the bottom.

Our procedure for stabilization is:

1. Choose a random grid cell c that is not a # and has a density greater than that of at least one of the 3 neighboring cells on the layer below it (southwest, south, and southeast) that is not a #.
   Stop procedure if no such choice exists.
2. Let d be a cell randomly sampled from these valid neighboring cells with the least densities.
3. Swap the values at c and d.
4. Repeat procedure until it has stopped.

Example

Running the procedure on

A01
#10
020

might start out step 1 by selecting the A. There is only one cell below it with smaller density so the next grid would be

101
#A0
020

The procedure might continue on as

101 100 000 000
#00 #01 #11 #01
A20 A20 A20 A21

The last arrangement being stable.

Challenge

Write a program that takes in a rectangular string of the 37 characters via stdin, command line, or function call. Initially, the given grid should be printed to stdout, but each time Enter is hit, one swap (step 3) should be done and the grid reprinted, separated from the last grid by an empty line. When the grid with no more possible swaps is printed (the end of the procedure) the program immediately ends.

• Grid dimensions will be 1×1 at minimum, and have no maximum size (as limited by Int.Max or computer memory). The grid is not always square.
• You can assume valid input. The grid will always be perfectly rectangular, containing only uppercase alphanumeric characters and #.
• You may use a key besides Enter if it is more convenient.
• Your program must follow [something equivalent to] the stabilization procedure, including using [pseudo]randomness for steps 1 and 2.
• In the input (but not the output) underscores (_) may be used instead of newlines.

Scoring

This is code-golf, so the shortest code in bytes wins. There are bonuses however.

Bonus 1 - Horizontal periodic boundary conditions: (minus 30 bytes)

Instead of treating the left and right out of bounds areas as #, connect them with PBC. There should be an option in your code where changing something like 0 to 1 or False to True enables or disables the PBC.

Bonus 2 - Graphics instead of text: (minus 100 bytes)

Instead of using blocks of text, use images (of any common truecolor format). Represent 0...Z with 36 distinct but related colors, e.g. a gradient from white to dark blue, and # with some other distinct color like dark red.

The program behaves the same way except now an image is either saved to a file (it may be the same file each time) or displayed to the screen for each grid swap in place of any textual output. The input may still be textual or some valid image, your choice.

Whether you do this bonus or not, giving output examples is highly encouraged.

Answer 1

Python, 300 298 chars

import random
C=random.choice
R=raw_input
G=list(R().replace('_','\n'))
S=w=G.index('\n')
while S:
 print''.join(G);S=[];R()
 for i,c in enumerate(G):
    B=[(d,j)for j,d in enumerate(G[i+w:i+w+3])if'/'<d<c]
    if B:S+=[(i,[i+w+j for d,j in B if d==min(B)[0]])]
 if S:i,B=C(S);j=C(B);G[i],G[j]=G[j],G[i]

Run it like cat inputfile - | fluid.py. The input file should be a single line using _ as a line separator.