Suponha que essa grade de espaços e X's represente a seção transversal de algumas bandejas de cubos de gelo vazias de formato estranho :

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

As colunas sem Xrepresentam buracos ou lacunas nas bandejas que não podem reter água, drenando para um coletor de capacidade infinita. A água que cai da borda mais à esquerda ou à direita da grade também entra neste coletor interminável.

Se posicionarmos uma torneira acima das bandejas e deixá-las encher de água até que o nível da água em todos os compartimentos permaneça estável, os compartimentos exatos que ficarem cheios dependerão exatamente de onde o fluxo de água foi posicionado acima das bandejas. (Suponha um fluxo fino e constante de água sem respingos.)

Por exemplo, se nossa torneira Festivesse acima da coluna da grade esquerda

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

a água cairia até o topo Xda coluna e se espalharia para a esquerda e direita, a metade esquerda derramando na pia abaixo e a metade direita enchendo o compartimento 2 × 1. Quando o compartimento se enche, a metade direita da corrente da água não tem para onde fluir, a não ser para a pia e o nível da água em todos os lugares é essencialmente estável.

Fechando a torneira, a bandeja agora fica assim: (com a ~água)

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

Da mesma forma, se posicionarmos a torneira assim:

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

Encherá os dois compartimentos mais à esquerda, mas o restante da água será drenado:

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

Se posicionarmos a torneira assim:

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

A metade esquerda do fluxo fluirá para a pia, mas a metade direita acabará preenchendo os três compartimentos mais à direita, porque não há limite para a distância que a água pode percorrer horizontalmente em uma superfície plana:

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

Posicionado assim, no entanto:

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

Toda a água escorre e nenhum compartimento está cheio:

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

Desafio

Escreva um programa ou função que consiga uma grade retangular de espaços, X's e um F. A linha superior sempre conterá os Fespaços e, de outra forma, apenas. Os Xem cada coluna (se houver) se estenderão em uma linha sólida a partir da base da grade, ou seja, não haverá cavernas ou saliências.

Imprima ou devolva a grade depois que a torneira Fenche o que puder com água, ~conforme descrito acima. Deixe a Flinha superior fora da saída.

• A grade separada da linha da torneira será de 1 × 1 no mínimo,

  F
  X
  

  é a menor entrada que você precisa oferecer suporte.

• A entrada entrará como um retângulo de texto completo. Os espaços iniciais e finais são importantes na entrada e na saída. por exemplo, a entrada

      F     
    X  X    
    XXXX    
  

  deve resultar em

    X~~X    
    XXXX    
  

  (observe os espaços à esquerda e à direita)

• Ter uma nova linha à direita na entrada ou saída é bom.

• Você pode usar qualquer quatro distintas ASCII imprimíveis caracteres no lugar do espaço, X, F, ~.

O código mais curto em bytes vence.

Grande exemplo:

Entrada:

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

Saída:

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

perl -p0, 204 + 2 bytes

IDÉIA

• Se ambos os lados da ilha abaixo de F tiverem a mesma altura, substitua todos os X *Xes por X~*Xes nessa ilha.
• Se um lado for mais alto, substitua todos os X *Xes por X~*Xes entre o dreno no lado inferior e o ponto mais próximo de F que é mais alto que o topo do lado inferior.

A terra diretamente abaixo de F conta como parte de ambos os lados aqui.

GOLFE

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

NOTAS

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
'

Pode ser difícil reconhecer o algoritmo original nesta implementação, já que o Perl não suporta visuais de comprimento variável.

Lua 5.2, 581 bytes

Novamente, comece lentamente com uma linguagem tão ineficaz para jogar golfe e com um algoritmo ineficaz. Mas vou melhorar :)

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

Casos de teste (com fonte de água):

---------
    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

do bash é possível testar dessa maneira, mas não parece tão legal:

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

Javascript, 460 bytes

Demonstração online (no console, testada no Chrome e Firefox atuais).

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(""))}

Desafiar a mim mesmo não é tão divertido, mas ainda é possível. Mesmo algoritmo que o Lua, agora em javascript.