Code De Golf: L'Eau Courante

Question

Le défi

Le plus court code par le nombre de caractères d'identifier et de marquer l'eau des dépressions dans la représentation ASCII de terre de l'entrée.

L'entrée sera une représentation ASCII d'un paysage, d'avoir les collines, les vallées et les terres plates. Le programme doit simuler ce que le paysage pourrait ressembler si elle était inondée de remplissage de tous les vallées avec de l'eau (caractère x).

Le paysage sera toujours démarrer et arrêter avec le caractère _ et sera au moins 2 caractères, ce qui en fait le plus court de l'entrée __.

Une colline est définie comme une augmentation, et ne doit pas être rempli avec de l'eau:

  __
_/  \_

Une vallée est définie comme la dépression et sera rempli avec de l'eau jusqu'à ce qu'un flatland est rencontré:

_    _
 \__/

L'entrée peut être supposé propre et sera composé uniquement de caractères de l'espace ( ), saut de ligne (\n), le trait de soulignement (_), et en avant et en arrière des barres obliques (/ et \). L'entrée peut être vu comme une ligne continue, et toutes les entrées qui contiennent ambigu entrée de ligne comme _/_ ou

_   _
 \_/
 / \

Est considéré comme invalide.

Concernant les grottes sous-marines, le niveau de l'eau devrait être maintenu si la grotte de niveau passe au-dessus du niveau de l'eau.

Des cas de Test

Input:
    __/\__
          \__              
             \       ___       ___________
             /      /   \_     \_
             \_____/      \__  _/
                             \/
Output:

    __/\__
          \__              
             \       ___       ___________
             /xxxxxx/   \xxxxxx\_
             \xxxxx/      \xxxxx/
                             \/

---

Input:
                                         __       ___
                                        /  \_____/
                                       / _______
                         ________     /  \     /
                   _____/        \   /__  \    \_
    ____          /               \    /__/   __/
        \_       /                 \     ____/
          \______\                 /____/

Output:
                                         __       ___
                                        /  \xxxxx/
                                       / _______
                         ________     /  \     /
                   _____/        \xxx/__  \xxxx\_
    ____          /               \xxxx/__/xxxxx/
        \xxxxxxxx/                 \xxxxxxxxx/
          \xxxxxx\                 /xxxx/

---

Input:
                                                      __     _
    _       ____                    ____        _____/  \   /
     \     /    \        __________/    \    __/  ___   /___\
      \___/      \       \               \   \___/  /_
                 /________\               \___________\

Output:
                                                      __     _
    _       ____                    ____        _____/  \xxx/
     \xxxxx/    \xxxxxxxxxxxxxxxxxx/    \xxxxxx/  ___   /xxx\
      \xxx/      \xxxxxxx\               \xxx\___/xx/_
                 /xxxxxxxx\               \xxxxxxxxxxx\

Code de comptage d'entrée/de sortie (j'.e programme complet).

Answer 1

C - 741 621 600 caractères (mais gère les nouveaux cas correctement)

$ gcc water.c && ./a.out < test6.txt 
                                     __       ___    
                                    /  \xxxxx/       
                                   / _______         
                     ________     /  \     /         
               _____/        \xxx/__  \xxxx\_        
____          /               \xxxx/__/xxxxx/        
    \xxxxxxxx/                 \xxxxxxxxx/           
      \xxxxxx\                 /xxxx/                

#include<stdio.h>
char d[99][99],*p,*e,*z,*s=d,c,S=' ',D='-',O='.',U='_';n,w,x,N=99,i;
g(y){for(i=0;!i;p+=N,e+=N){i=*p==D;for(z=p;z!=e;z+=y){if(*z!=O&&*z!=
D)break;*z=*z==O?S:U;}}}f(char*n,int r){if(*n==O||*n==D){*n=r>0?'x':
S;int k;for(k=0;k<9;k++)f(n+k/3*N-N+k%3-1,r+k/3-1);}}main(){for(p=s;
gets(p);p+=N,n++){x=strlen(p)-1;w=x>w?x:w;}for(p=s,e=d[N];p<s+N;p++)
{for(i=1,z=p;z<e;z+=N)c=*z,c==0?*z=c=S:0,i?c==S?*z=O:c==U?*z=D:0:0,(
c=='/'&&z[1]!=U)||(c=='\\'&&z[-1]!=D)||c==U?i=1-i:0;}p=s;e=s+w;g(1);
p=s+w;e=s;g(-1);for(p=s;p<s+w;p++){for(z=p;*z==S;z+=N);f(z,1);}for(i
=0;i<n;i++)printf("%.*s\n",w+1,d[i]);}

Answer 2

Ruby, 794 759 769 752 715 692 663 655 626 616

D'autres tests: http://pastie.org/708281 et http://pastie.org/708288 et http://pastie.org/708310

Comprimé, sauf pour le retrait:

def g i,j,&f
  t=[-1,0,1]
  t.each{|r|next if@w[i][j,1]=='_'&&r>0
    t.each{|c|a=i+r
      b=j+c
      if a>=0&&b>=0&&a<@r&&b<@c
        @t[a]||=[]
        if r!=0&&c!=0
          k=@w[a][j,1]
          l=@w[i][b,1]
          next if/[\/\\]/=~k+l&&((k!=l)||((r<=>0)==(c<=>0)?k!='\\': k!='/'))
        end
        e=@w[a][b,1]
        z,@t[a][b]=@t[a][b],1
        return 1if !z&&(e==' '||r>=0&&e=='_')&&yield(a,b,f)
      end}}
  nil
end
w=$stdin.readlines
@c=w.map{|e|e.size}.max-1
@w=w=w.map{|e|e.chomp.ljust@c}
z=w.map{|e|e.dup}
@r=w.size
@r.times{|r|@m=r
  @c.times{|c|e=w[r][c,1]
    z[r][c]='x'if(e==' '||e=='_')&&(@t=[]
      !g(r,c){|u,v,f|u>=@m and v==0||v==@c-1||g(u,v,&f)})&&(@t=[]
      g(r,c){|u,v,f|u==0||g(u,v,&f)})}}
puts z

Answer 3

Python, 702 805 794 778 758 754 710 651

Poignées DigitalRoss du cas de test, ainsi que de grands cas de test tels que http://pastie.org/708764.

Exemple de fonctionnement

$ python runningwater.py < test4.txt                   
                                           ____________________________
                                          /           
                                   _      \        __
                                  / \xxxxx/       /  \
                  ___       _____/  /xxx/        /    \
____________     /   \xxxxx/   ____/xxx/ __     /xxxxxx\ 
            \xxx/    /xxxxx\__ \xxxxxx/ /xx\___/xxxxxxx/
                 ___/xxxxxxxxx\____    /xxxxxxxxxxxxxx/
                /xxxxx/      \xxxxx\__/x/    \xxxxxxx/
               /xxxxx/        \xxxxxxxx/      \xxxxx/
               \xxxxx\    _________            \xxx/
                  \xxx\  /xxxxxxxxx\           /xx/
                     \x\ \x\   /\ \x\         /xx/
    __________        \x\ \x\_/x/ /x/        /xx/
   /xxxxxxxxxx\        \x\ \xxx/ /x/        /xx/
  /xxxxxxxxxxxx\        \x\ \x/ /x/        /xx/
  \xxxxxxxxxxxxx\        \x\   /x/        /xx/
         \xxxxxxx\        \x\_/x/        /xx/
     ____/xxx/ \xx\        \xxx/        /xx/
     \xxxxxx/   \xx\___________________/xx/
      \xx/       \xxxxxxxxxxxxxxxxxxxxxxx/

Code

import sys
q=sys.stdin.readlines()
e=enumerate
s=type
k=int
o=[]
t=[0]*max(map(len,q))
n=1
L=[]
l={}
for p,d in e(q):
 w=a=0;o+=[[]]
 for i,c in e(d):
  T=t[i];C=[[c,T]];D=d[i+1:];b=0;o[-1]+=C;L+=C
  if c in'_ ':
   if('/'in D or '\\'in D)*(T%2-1)*w*p:
    for j in range(max(i-1,0),min(i+2,len(o[p-1]))):R=o[p-1][j][0];b=R*(k==s(R))or b
    for x in L:x[0]=b*(x[0]==a)or x[0]
    a=C[0][0]=b or a or n
  elif c in'\\/':w=1;a=0;n+=1
  D=d[i-1]+c;t[i-1]+=(D=='/_');t[i]+=(c in'_/\\')+(D=='_\\')
for i,a in e(o):
 for c,r in a:
  if(r==0)*(s(c)==k):l[c]=1
 for j,(c,r)in e(a):
  if(c in l)-1:a[j]=q[i][j],0
 print''.join((k==s(x))*'x'or x for x,r in a),

Answer 4

Perl, 534 545 550 566 569 567 578 594 596

sub i{$a=1;$a^=substr(x.$l[$_],$_[0],3)=~/^(.[_y]|.\/[^_]|[^_]\\)/for 0..$r-1;
$a}sub f{$c=$e-$s;$_=$l[$r];$f=s/(.{$s})(.{0,$c})/$1<$2>/;(/[ _x]>/&i$e-1and$f=
/>[ _xy]*[\\\/]/,$e=$+[0]-2)or/[ _]*>/,$e=$-[0]-1;(/<[ _x]/&i$s and$f&=
/[\\\/][ _xy]*</,$s=$-[0])or/<[ _]*/,$s=$+[0]-1;$f&$s<$e&&substr($l[$r],$s,$e-$s
)=~s!([\\/][ _xy]*)([\\/][ _]*)!($t=$1)=~y/ _/xy/,$t.$2!eg,$r--&&&f}$q=@l=<>;
while($q--){i$-[0]+1and substr($l[$r--],$-[1],length$1)=~y/_y/x/,$s=$-[0],$e=
$+[0],$q&&f while$l[$r=$q]=~m~\\/|[\\/]([_y]+)[\\/]~g}y/y/x/,print for@l

Elle traite tous les cas de test que j'ai vu. Les retours à la ligne sont facultatifs et ne sont là que pour la mise en forme.

L'appeler comme par exemple, perl water.pl test.txt.

Voici un autre drôle de cas de bord (pour mon algorithme de toute façon) pas dans l'un des exemples précédents:

__      _
  \__  /
    /_/

La version détaillé je l'avais mis en place plus tôt échoue encore.