Code Golf: Running Water
Solution 1:
C - 741 621 600 characters (but handles the new cases properly)
$ 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]);}
Solution 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 for indent:
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
Solution 3:
Python, 702 805 794 778 758 754 710 651
Handles DigitalRoss's test cases, as well as large test cases such as http://pastie.org/708764.
Example run
$ 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),
Solution 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 that I've seen. Newlines are optional and are only there for formatting.
Call it as e.g. perl water.pl test.txt.
Here's another funny edge case (for my algorithm anyway) not in any of the previous examples:
__ _
\__ /
/_/
The verbose version I'd put up earlier still fails on that.