Golf Code: Running Water

Question

A task

The shortest code by number of characters to identify and mark water depressions in the ASCII view of the land from the entrance.

The input will be an ASCII representation of a landscape with hills, valleys and flat lands. The program should imitate what the landscape would look like if it were flooded - filling all the valleys with water (symbol x ).

The landscape will always start and stop with the symbol _ and will contain at least 2 characters, making the shortest input __ .

A hill is defined as rising and should not be filled with water:

  __ _/ \_ 

The valley is defined as depression and is filled with water until a flat surface meets:

 _ _ \__/ 

Input can be considered clean and will consist only of a character space ( ), newline ( \n ), underscore ( _ ), and forward and backward slashes ( / and \ ). An input can be thought of as a continuous line, and any input containing ambiguous line inputs, such as _/_ or

 _ _ \_/ / \ 

It is considered invalid.

For underwater caves, the water level should be maintained if the cave level exceeds the water level.

Test cases

 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\ 

The number of codes includes input / output (i.e., a complete program).

Answer 1

C - 741 621 600 characters (but correctly handles new cases)

 $ 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

Additional test cases: http://pastie.org/708281 and http://pastie.org/708288 and http://pastie.org/708310

Compressed except indent:

 def gi,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

Handles DigitalRoss test cases as well as large test cases such as http://pastie.org/708764 .

Execution example

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

The 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 

This handles all the test cases I have seen. Newlines are optional and are for formatting purposes only.

Name it, for example. perl water.pl test.txt .

Here is another case of a ridiculous edge (for my algorithm anyway) not in any of the previous examples:

 __ _ \__ / /_/ 

The extended version that I installed earlier still does not work.