Code Golf: Running WaterThe 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.
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).
ACCEPTED]
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]);}
' ' character literals! And all those local variables! I'm not sure how many of those variable declarations you can stuff into globals, but at the very least, you can #define c char to shorten all of those declarations, and change character literals to the raw numbers. #define w while could help if you didn't have a variable named w already. Also, why do you have avariable (w1) with a two-character name? I would golf it a little myself, but I have finals to do. - Chris Lutz
if(x>w)w=x; by w=x>w?x:w; ? - hexium
' ' for example) - LiraNuna
#include <string.h>. I was able to verify all test cases. Well done. - LiraNuna
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
Handles DigitalRoss's test cases, as well as large test cases such as http://pastie.org/708764.
$ 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/
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),
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 [1] still fails on that.
[1] http://pastie.org/716553
/for left shore, or `` for right shore? You know: caves under water? - Abelxor not? (i.e., it has a_and a/) - Abel