Code Golf: Running Water

Question

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).

Saree

This challenge is inspired by an idea of user @gnibbler, and the recent discovery of water on the moon. – Saree

Intriguing little challenge!, can't help thinking about arithmetic overflows.... – Arcograph

PS (first question): can input contain / for left shore, or `` for right shore? You know: caves under water? – Arcograph

Can you demonstrate what you mean? (use a pasting site) – Saree

Sorry, the broken SO code-in-comments didn't work for backslash... Here's some creativity with the above rules: pastebin.com/f6f845012 – Arcograph

Hmm, I didn't think of that, Thanks for pointing it out - I will modify the examples to show it. – Saree

Mark the bottom-left: should it become an x or not? (i.e., it has a _ and a /) – Arcograph

@Abel: Thank you for showing me an edge case I did not think about. The question had changed. – Saree

Your last example has incorrect output. The landscape changes! Earthquake! – Amontillado

It looked fine in the preview :/ – Saree

Is it just me, or does @Abel's pastebin example look a little dirty? – Surly

@Zack, yep that's elephant porn for sure – Cockeyed

I prefer the more challenging (intended) version than the trivial version that the examples originally indicated – Pyrargyrite

How about a cave that would trap an air bubble? – Aegrotat

@Zack/@dotjoe: you dirty little minds! What happened to tapirs? Air bubbles and something that even most creative minds can't see something familiar in: pastebin.com/f1330010d (not sure I filled in in correctly though) – Arcograph

@Abel, that example is invalid since the input 'line' is not continuous. A modified example would be pastebin.com/m11e08e82 – Saree

@LiraNuna: ah, you meant the little cliff I invented? Fair enough to disallow that :). Meanwhile you had edited your question to allow for trapped air bubbles (not taking difference in level as result of air pressure into account ;-). Think that by now, a simple regex won't suffice anymore and we can get to work ;-) – Arcograph

@Able: Not only that, but you had the `/` intersecting with the ground level, so I had to make it flat. – Saree

You may want to have a test case where a cave opens to the right. – Reverent

@Greg: to stop this complication madness, let's declare side caves illegal... – Saree

Okay, I'll go hide in my illegal side cave now. – Aegrotat

Just as soon as this flood of code golf questions stop, i can ask mine... Any idea when that will be? ;) – Etalon

Here are a couple more tests, pastie.org/708281 and also pastie.org/708288 – Reverent

Wow, I knew this is a hard challenge, but I didn't think people will choose the naive way... – Saree

Uh, oh, I missed the easy way? Anyway, awesome problem. One of your best! And only 1 working solution after 24 hours! – Reverent

It seems that an underscore is missing from the third test. I've pointed it out in pastie.org/708721 but didn't edit the post in case I've misunderstood the spec. – Enrollment

This solution is solvable in 300 characters. Too bad no one solved it in the short way. Oh well, next week will be easier, I guess. – Saree

@LiraNuna: Wait, do you have a solution in 300 strokes? Why don't you post it? – Museology

I was thinking that a wall follower might be shorter; I didn't look at any of the other entries to see if someone had done one. (I just did a BFI search of all possible paths.) – Reverent

Or possibly a state machine that kept track of sky, water, & dirt and just sequenced through every square. – Reverent

@A.Rex: I never post solutions to my own code golfs. It feels dirty - as the designer of those questions, I know all the tricks and ways to get short answers. To summarize, the challenge is for you - not for me. – Saree

I would agree with you but my main language is lua and A. it's not that short a language, and B. i'm not that good at golfing :) – Etalon

Answer 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]);}

Oration

Woah! Look at all those spaces! And those ' ' 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. – Amontillado

Yeah - I'm sure I could squeeze a bunch out (I'm pretty sure there's at least a little algorithmic stuff I could pull out). But I ran out of time... (and I wanted the first submission that could handle the new cases) :) – Oration

Nice job. I think you can fix it without adding too many bytes, but this fails on pastie.org/708281 and also on pastie.org/708288 – Reverent

How can you guys read it? Is there any tool to quickly reformat the code to readable? – Claudio

@Reverent - in 2D world physics is different and those passages are too small for water molecules to fit through... :) – Oration

Can you save one character by replacing if(x>w)w=x; by w=x>w?x:w; ? – Overissue

Aaron, come back, we need you! This also fails on Pär Wieslander's mega case as well as my new tests. We won't know how big this really is until you fix it! :-) – Reverent

@mqbt: running it through "indent" is a good idea: gnu.org/software/indent – Timepiece

@Reverent - okay - edited to handle all 11 test cases that I know about. Still 621 chars. – Oration

@Aaron, you can save a lot of characters by using ASCII codes instead of literals (32 instead of ' ' for example) – Saree

I cannot seem to compile this under GCC. Also users report it fails on some test cases. If you don't fix your answer soon, I will have to choose Pär Wieslander's answer. – Saree

@Saree - I don't know why you can't compile on GCC - I used GCC on cygwin to write it and it works fine (2 warnings, no errors) – Oration

@Saree - I just tried it on my linux machine. GCC 4.3.2 requires an include of <string.h> which GCC 3.4.4 (from my cygwin machine) does not. Furthermore I checked the 11 test cases I know about (from above and sprinkled around the comments from pastie) and my output matches both DigitalRoss and Par Wieslander's output. – Oration

@Aaron, I was not able to compile it so I just read the comments. You're correct by adding #include <string.h>. I was able to verify all test cases. Well done. – Saree

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

Reverent

Wow, only two solutions, about the same size, and one gets downvoted? With no comment? Hard to understand... – Reverent

Yeah - What's with all the drive-by hate? I can understand not giving an upvote, but a downvote? +1 just to offset the haters. – Oration

This one is nice, but fails with stack overflow on larger test cases such as pastie.org/708764 – Enrollment

@Pär Wieslander, your mega-case works for me on both 1.8.7 and 1.9.1p243. (A lot faster on 1.9. :-) If I run it in irb then ps(1) reports a memory growth of about 6MB during the run. Do you have a ulimit set? – Reverent

@DigitalRoss, yes, it works fine for me now. Got a "maximum recursion depth exceeded" earlier though, but can't reproduce it now. Guess I somehow must have messed something up. – Enrollment

Answer 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),

Jonejonell

Doesn't work on pastie.org/708288 pastie.org/708310 pastie.org/708310 – Reverent

Wow, an iterative solution, and with loops nested 4 deep. Interesting. – Reverent

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 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.

Warchaw