Code Golf: Running Water
Language AgnosticCode GolfRosetta StoneLanguage Agnostic Problem Overview
The challenge
The shortest code by character count to identify and mark water depressions in the ASCII representation of a land from input.
Input will be an ASCII representation of a landscape, having hills, valleys and flat lands. The program should simulate what the landscape would look like if if was flooded - filling all valleys with water (character x).
The landscape will always start and stop with the character _ and will be at least 2 characters long, making the shortest input __.
A hill is defined as a raise, and should not be filled with water:
__
_/ \_
A valley is defined as a depression and will be filled with water until a flatland is encountered:
_ _
\__/
Input can be assumed clean and will be composed only from the characters space ( ), newline (\n), underscore (_), and forward and backward slashes (/ and \). Input can be seen as a continuous line, and any input that contains ambiguous line input such as _/_ or
_ _
\_/
/ \
Is considered invalid.
Regarding underwater caves, water level should be maintained if cave level goes above 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\
Code count includes input/output (i.e full program).
Language Agnostic Solutions
Solution 1 - Language Agnostic
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 - Language Agnostic
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 - Language Agnostic
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 - Language Agnostic
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.