Remplissage de bacs à glaçons arbitraires

27

Supposons que cette grille d'espaces et Xreprésente la section transversale de certains bacs à glaçons vides de forme étrange :

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

Les colonnes sans Xreprésentent des trous ou des lacunes dans les plateaux qui ne peuvent pas retenir l'eau, s'écoulant dans un évier de capacité infinie. L'eau tombant du bord le plus à gauche ou le plus à droite de la grille va également dans cet évier sans fin.

Si nous devions placer un robinet au-dessus des plateaux et les laisser se remplir d'eau jusqu'à ce que le niveau d'eau dans tous les compartiments reste stable, les compartiments exacts qui se rempliraient dépendraient exactement de l'endroit où le courant d'eau était positionné au-dessus des plateaux. (Supposez un mince filet d'eau constant sans éclaboussures.)

Par exemple, si notre robinet Fétait au-dessus de la colonne de grille tout à gauche

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

l'eau tomberait au sommet Xde cette colonne et se répandrait à gauche et à droite, la moitié gauche se déversant dans l'évier ci-dessous et la moitié droite remplissant le compartiment 2 × 1. Une fois que le compartiment se remplit, la moitié droite du jet d'eau n'a nulle part où s'écouler, mais dans l'évier et le niveau d'eau partout est essentiellement stable.

En fermant le robinet, le plateau ressemble maintenant à ceci: (avec ~de l'eau)

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

De même, si nous positionnons le robinet comme ceci:

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

Il remplira les deux compartiments les plus à gauche mais le reste de l'eau s'écoulera:

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

Si nous positionnons le robinet comme ceci:

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

La moitié gauche du ruisseau coulera dans l'évier mais la moitié droite finira par remplir les trois compartiments les plus à droite car il n'y a pas de limite à la distance à laquelle l'eau peut voyager horizontalement sur une surface plane:

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

Cependant, positionné comme ceci:

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

Toute l'eau s'écoule et aucun compartiment n'est rempli:

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

Défi

Écrivez un programme ou une fonction qui prend dans une grille rectangulaire d'espaces, Xde et un F. La ligne du haut contiendra toujours le Fet sinon ne contiendra que des espaces. Le X's dans chaque colonne (s'il y en a) s'étendra en ligne continue jusqu'à la base de la grille, c'est-à-dire qu'il n'y aura pas de grottes ou de surplombs.

Imprimez ou renvoyez la grille une fois que le robinet Fa rempli ce qu'il peut avec de l'eau, ~comme décrit ci-dessus. Laissez la Fligne supérieure hors de la sortie.

  • La grille en dehors de la rangée de robinets sera de 1 × 1 au minimum afin

    F
X

    est la plus petite entrée que vous devez prendre en charge.

  • L'entrée apparaîtra sous la forme d'un rectangle de texte complet. Les espaces de début et de fin importent en entrée et en sortie. par exemple l'entrée

        F     
  X  X    
  XXXX

    devrait se traduire par

      X~~X    
  XXXX

    (notez les espaces de début et de fin)

  • Avoir une seule nouvelle ligne de fin dans l'entrée ou la sortie est très bien.

  • Vous pouvez utiliser tous les quatre distincts ASCII imprimables caractères en place de l' espace, X, F, ~.

Le code le plus court en octets gagne.

Grand exemple:

Contribution:

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

Sortie:

              X~~~~~~~~~~~~~X                     
              X~~~~~~~~~~~~~X~X                   
X~~~~~~~~~~~~XXX~~~~~~~X~~~~X~X~~~~~~~~~~~X    X  
X~~~X~~~~~XXXXXXX~~~~~~X~~~~XXX~~~~~XXXXXXX X  X  
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXX
code-golf ascii-art grid Loisirs de Calvin
la source
Oh oui, une excellente occasion pour moi d'utiliser mon bien-aimé zip()<3
cjfaure
2
Cela nécessite une réponse: / Je vais y travailler.
TheNumberOne
Il est relativement facile de faire un automate cellulaire qui simule cela, mais je ne peux pas penser à un moyen pour que cela se termine.
DanTheMan
toujours personne pour concourir? Défi si mignon. On dirait que je vais devoir me battre :)
Jakuje
ressemble à un double de ceci: codegolf.stackexchange.com/questions/2563/fill-in-the-lakes
12Me21

Réponses:

1

perl -p0, 204 + 2 octets

IDÉE

  • Si les deux côtés de l'île en dessous de F sont de même hauteur, remplacez tous les X *Xes par des X~*Xes sur cette île.
  • Si un côté est plus haut, remplacez tous les X *Xes par des X~*Xes entre le drain du côté inférieur et le point le plus proche de F qui est plus haut que le haut du côté inférieur.

Le terrain juste en dessous de F compte ici comme partie des deux côtés.

LE 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

REMARQUES

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
'

Il peut être difficile de reconnaître l'algorithme d'origine dans cette implémentation car Perl ne prend pas en charge les lookbehinds de longueur variable.

bopjesvla
la source
6

Lua 5.2, 581 octets

Encore une fois, commencez lentement avec un langage si inefficace pour le golf et avec un algorithme inefficace. Mais je vais m'améliorer :)

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

Cas de test (avec source d'eau):

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

à partir de bash, il est possible de tester de cette façon, mais ce n'est pas si joli:

$ echo "    F     
  X  X    
  XXXX   " | lua f.lua
Jakuje
la source
Utilisez here-docs pour tester cela plus facilement! Comme ça .
ravron
1

Javascript, 460 octets

Démo en ligne (dans la console, testée dans Chrome et Firefox actuels).

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

Me mettre au défi n'est pas si amusant, mais toujours possible. Même algorithme que celui de Lua, désormais en javascript.

Jakuje
la source