Llenado de bandejas arbitrarias de cubitos de hielo

27

Supongamos que esta cuadrícula de espacios y X's representa la sección transversal de algunas bandejas de cubitos de hielo vacías de forma extraña :

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

Las columnas sin X's representan agujeros o huecos en las bandejas que no pueden retener agua, drenando en un sumidero de capacidad infinita. El agua que cae del borde más a la izquierda o más a la derecha de la rejilla también entra en este sumidero sin fin.

Si colocamos un grifo sobre las bandejas y dejamos que se llenen de agua hasta que el nivel de agua en todos los compartimientos permanezca estable, los compartimentos exactos que se llenen dependerán exactamente de dónde se colocó la corriente de agua sobre las bandejas. (Suponga una corriente de agua delgada y constante sin salpicaduras).


Por ejemplo, si nuestro grifo Festuviera sobre la columna de la cuadrícula muy a la izquierda

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

el agua caería hasta la parte superior Xde esa columna y se extendería a izquierda y derecha, la mitad izquierda se derramaría en el fregadero de abajo y la mitad derecha llenaría el compartimento 2 × 1. Una vez que el compartimento se llena, la mitad derecha de la corriente de agua no tiene otro lugar que fluir sino hacia el fregadero y el nivel del agua en todas partes es esencialmente estable.

Al cerrar el grifo, la bandeja ahora se ve así: (con ~agua)

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

Del mismo modo, si posicionamos el grifo de esta manera:

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

Llenará los dos compartimentos más a la izquierda, pero el resto del agua se drenará:

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

Si colocamos el grifo de esta manera:

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

La mitad izquierda de la corriente fluirá hacia el fregadero, pero la mitad derecha eventualmente llenará los tres compartimentos más a la derecha porque no hay límite en cuanto a la distancia que puede viajar el agua horizontalmente en una superficie plana:

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

Posicionado así, sin embargo:

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

Toda el agua se drena y no se llenan los compartimentos:

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

Reto

Escriba un programa o función que tome una cuadrícula rectangular de espacios, X's y uno F. La fila superior siempre contendrá Fy, de lo contrario, solo contendrá espacios. Los X's en cada columna (si hay alguno) se extenderán en una línea sólida desde la base de la cuadrícula, es decir, no habrá cuevas ni salientes.

Imprima o devuelva la cuadrícula después de que el grifo Fhaya llenado lo que pueda con agua ~como se describe anteriormente. Deje la Ffila superior fuera de la salida.

  • La cuadrícula aparte de la fila del grifo será 1 × 1 como mínimo, por lo que

    F
    X
    

    es la entrada más pequeña que necesita admitir.

  • La entrada vendrá como un rectángulo de texto completo. Los espacios iniciales y finales son importantes en la entrada y la salida. por ejemplo, la entrada

        F     
      X  X    
      XXXX    
    

    debería resultar en

      X~~X    
      XXXX    
    

    (tenga en cuenta los espacios iniciales y finales)

  • Tener una nueva línea final en la entrada o salida está bien.

  • Puede utilizar cualquiera de los cuatro distintos ASCII imprimibles caracteres en lugar del espacio, X, F, ~.

El código más corto en bytes gana.


Gran ejemplo:

Entrada:

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

Salida:

              X~~~~~~~~~~~~~X                     
              X~~~~~~~~~~~~~X~X                   
X~~~~~~~~~~~~XXX~~~~~~~X~~~~X~X~~~~~~~~~~~X    X  
X~~~X~~~~~XXXXXXX~~~~~~X~~~~XXX~~~~~XXXXXXX X  X  
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXX
Pasatiempos de Calvin
fuente
Oh sí, una gran oportunidad para mí de usar a mi amado zip()<3
cjfaure
2
Esto necesita una respuesta: / Trabajaré en ello.
TheNumberOne
Es relativamente fácil hacer un autómata celular que simule esto, pero no se me ocurre una forma de que termine.
DanTheMan
Todavía nadie para competir? Muy lindo desafío. Parece que tendré que
vencerme

Respuestas:

1

perl -p0, 204 + 2 bytes

IDEA

  • Si ambos lados de la isla debajo de F tienen la misma altura, reemplace todos los X *Xes por X~*Xes en esa isla.
  • Si un lado es más alto, reemplace todos los X *Xes con X~*Xes entre el drenaje en el lado inferior y el punto más cercano a F que sea más alto que la parte superior del lado inferior.

La tierra directamente debajo de F cuenta como parte de ambos lados aquí.

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

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
'

Puede ser difícil reconocer el algoritmo original en esta implementación, ya que Perl no admite retrospectivas de longitud variable.

bopjesvla
fuente
6

Lua 5.2, 581 bytes

Nuevamente, comience lentamente con un lenguaje tan ineficaz para jugar al golf y con un algoritmo ineficaz. Pero mejoraré :)

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 prueba (con fuente de agua):

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

desde bash es posible probar de esta manera, pero no se ve tan bien:

$ echo "    F     
  X  X    
  XXXX   " | lua f.lua
Jakuje
fuente
¡Usa here-docs para probar esto más fácilmente! Al igual que este .
ravron
1

Javascript, 460 bytes

Demostración en línea (en consola, probada en Chrome y Firefox actuales).

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

Desafiarme a mí mismo no es tan divertido, pero aún es posible. Mismo algoritmo que el Lua, ahora en javascript.

Jakuje
fuente