Filling Arbitrary Ice Cube Trays

Question

Suppose this grid of spaces and X's represents the cross section of some strangely shaped empty ice cube trays:

   X     X X        
X  X X  XX X  XX   X
XXXXXX XXXXXXXXXXXXX

Columns without X's represent holes or gaps in the trays that can't hold water, draining into an infinite capacity sink. Water falling off the leftmost or rightmost edge of the grid goes into this endless sink as well.

If we were to position a faucet above the trays and let them fill with water until the water level in all compartments remains stable, the exact compartments that become filled would depend on exactly where the water stream was positioned above the trays. (Assume a thin, steady stream of water with no splashing.)

---

For example, if our faucet F were above the very left grid column

F                   
   X     X X        
X  X X  XX X  XX   X
XXXXXX XXXXXXXXXXXXX

the water would fall down to the topmost X in that column and spread left and right, the left half spilling into the sink below, and the right half filling up the 2×1 compartment. Once the compartment fills, the right half of the water stream has nowhere to flow but into the sink and the water level everywhere is essentially stable.

Turning the faucet off, the tray now looks like this: (with ~ as water)

   X     X X        
X~~X X  XX X  XX   X
XXXXXX XXXXXXXXXXXXX

---

Similarly, if we position the faucet like this:

   F                
   X     X X        
X  X X  XX X  XX   X
XXXXXX XXXXXXXXXXXXX

It will fill up the two leftmost compartments but the rest of the water will drain away:

   X     X X        
X~~X~X  XX X  XX   X
XXXXXX XXXXXXXXXXXXX

---

If we position the faucet like this:

         F          
   X     X X        
X  X X  XX X  XX   X
XXXXXX XXXXXXXXXXXXX

The left half of the stream will flow into the sink but the right half will eventually fill up the three rightmost compartments because there's no limit to how far water can travel horizontally on a flat surface:

   X     X~X        
X  X X  XX~X~~XX~~~X
XXXXXX XXXXXXXXXXXXX

Positioned like this, however:

        F           
   X     X X        
X  X X  XX X  XX   X
XXXXXX XXXXXXXXXXXXX

All the water drains away and no compartments are filled:

   X     X X        
X  X X  XX X  XX   X
XXXXXX XXXXXXXXXXXXX

---

Challenge

Write a program or function that takes in a rectangular grid of spaces, X's, and one F. The top row will always contain the F and otherwise only contain spaces. The X's in each column (if there are any) will extend in a solid line up from the base of the grid, i.e. there will be no caves or overhangs.

Print or return the grid after the faucet F has filled what it can with water ~ as described above. Leave the top F row out of the output.

• The grid apart from the faucet row will be 1×1 at minimum so

  F
  X
  

  is the smallest input you need to support.

• The input will come in as a complete text rectangle. Leading and trailing spaces do matter in the input and output. e.g. the input

      F     
    X  X    
    XXXX    
  

  should result in

    X~~X    
    XXXX    
  

  (note the leading and trailing spaces)

• Having a single trailing newline in the input or output is fine.

• You can use any four distinct printable ASCII characters in place of space, X, F, ~.

The shortest code in bytes wins.

---

Big Example:

Input:

                F                                 
              X             X                     
              X             X X                   
X            XXX       X    X X           X    X  
X   X     XXXXXXX      X    XXX     XXXXXXX X  X  
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXX

Output:

              X~~~~~~~~~~~~~X                     
              X~~~~~~~~~~~~~X~X                   
X~~~~~~~~~~~~XXX~~~~~~~X~~~~X~X~~~~~~~~~~~X    X  
X~~~X~~~~~XXXXXXX~~~~~~X~~~~XXX~~~~~XXXXXXX X  X  
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXX

Answer 1

perl -p0, 204+2 bytes

IDEA

• If both sides of the island below F are of equal height, replace all X *Xes with X~*Xes on that island.
• If one side is higher, replace all X *Xes with X~*Xes between the drain on the lower side and the point closest to F that's higher than the lower side's top.

The land directly below F counts as a part of both sides here.

GOLF

s/.*(F).*
//;$f=@-[1];($%,$r)=map{y///c}/(.{0,$f})\bX+?\b(.*)$/;($a,$b)=map{y///c}/[^~]*^(?(?=(.{$%,$f}X)).{$f} *|.{$f} *X(.*)).{$r}
/m;$a=$%if!$a||$b;$b+=$r;s/(?<=.{$a})\b *\b(?=.{$b})/"~"x length($&)/ge

NOTES

perl -p0e ' # slurp stdin, print the result

s/.*(F).*\n//; # remove the first line, record the index of F
$f=@-[1]; # get the index of F

($l,$r)=map{length}m/(.{0,$f})\bX+?\b(.*)$/;
# gets the distance from either side to the drains closest to F
($a,$b)=map{length}m/[^~]*^(?(?=(.{$l,$f}X)).{$f} *|.{$f} *X(.*)).{$r}\n/m;
# tries to find the lowest line that has at least one X on
# one side of the island, but none on the other
$a=$l if !$a||$b;
$b+=$r; # use the captured groups to calculate the left and right bounds
s/(?<=.{$a})\b *\b(?=.{$b})/"~" x length($&)/ge;
# replace all pools within those bounds
'

It might be hard to recognise the original algorithm in this implementation since Perl doesn't support lookbehinds of variable length.

Answer 2

Lua 5.2, 581 Bytes

Again, slow start with so ineffective language for golfing and with ineffective algorithm. But I will improve :)

r=io.read w=io.write F=r()f=F:find("F")o={[1]=F}W=#F i=2 
repeat s=r()if s==nil then break end o[i]={}for j=1,W do o[i][j]=s:sub(j,j)end i=i+1 until false
function e(i,j)
local k,l,b,c=j+1,j-1,false
if i>=#o or(o[i+1][j]==" "and e(i+1,j)==0)then return 0 end
while k<=W do
b=b or o[i][k]=="X"
if b or(o[i+1][k]==" "and e(i+1,k)==0)then break end
k=k+1 end
while l>0 do
c=c or o[i][l]=="X"
if c or(o[i+1][l]==" "and e(i+1,l)==0)then break end
l=l-1 end
if b and c then for m=l+1,k-1 do o[i][m]="~"end return 1 end
return 0 end
e(1,f)for i=2,#o do for j=1,W do w(o[i][j])end w"\n"end

Test cases (with water source):

---------
    F    
  X~~X   
  XXXX   
--------------------
         F          
   X     X~X        
X  X X  XX~X~~XX~~~X
XXXXXX XXXXXXXXXXXXX
--------------------
   F                
   X     X X        
X~~X~X  XX X  XX   X
XXXXXX XXXXXXXXXXXXX
--------------------------------------------------
                F                                 
              X~~~~~~~~~~~~~X                     
              X~~~~~~~~~~~~~X~X                   
X~~~~~~~~~~~~XXX~~~~~~~X~~~~X~X~~~~~~~~~~~X    X  
X~~~X~~~~~XXXXXXX~~~~~~X~~~~XXX~~~~~XXXXXXX X  X  
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXX

from bash it is possible to test this way, but it doesn't look so nice:

$ echo "    F     
  X  X    
  XXXX   " | lua f.lua

Answer 3

Javascript, 460 Bytes

Online demo (in console, tested in current Chrome and Firefox).

function e(i,j){var k=j+1,l=j-1,b=0,c=0,I=i+1
if(i>(O-2)||(o[I][j]==" "&&e(I,j)==0))return 0
while(k<W){b=b||(o[i][k]=="X")
if(b||(o[I][k]==" "&&e(I,k)==0))break
k++}while(l>=0){c=c||(o[i][l]=="X")
if(c||(o[I][l]==" "&&e(I,l)==0))break
l--}if(b&&c){for(m=l+1;m<k;m++)o[i][m]="~"
return 1}return 0}function f(d){o=d.split("\n")
F=o[0];s=F.indexOf("F");W=F.length;O=o.length
for(i=0;i<O;i++)o[i]=o[i].split("")
e(0,s);for(i=1;i<O;i++)console.log(o[i].join(""))}

Challenging myself is not so fun, but still possible. Same algorithm as the Lua one, now in javascript.