share
Stack OverflowCode Golf: Running Water
[+53] [4] LiraNuna
[2009-11-19 21:24:11]
[ language-agnostic code-golf rosetta-stone ]
[ https://stackoverflow.com/questions/1766675/code-golf-running-water ]

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

(3) This challenge is inspired by an idea of user @gnibbler, and the recent discovery of water on the moon. - LiraNuna
Intriguing little challenge!, can't help thinking about arithmetic overflows.... - Abel
PS (first question): can input contain / for left shore, or `` for right shore? You know: caves under water? - Abel
Can you demonstrate what you mean? (use a pasting site) - LiraNuna
Sorry, the broken SO code-in-comments didn't work for backslash... Here's some creativity with the above rules: pastebin.com/f6f845012 - Abel
(1) Hmm, I didn't think of that, Thanks for pointing it out - I will modify the examples to show it. - LiraNuna
Mark the bottom-left: should it become an x or not? (i.e., it has a _ and a /) - Abel
@Abel: Thank you for showing me an edge case I did not think about. The question had changed. - LiraNuna
Your last example has incorrect output. The landscape changes! Earthquake! - Chris Lutz
It looked fine in the preview :/ - LiraNuna
(8) Is it just me, or does @Abel's pastebin example look a little dirty? - Zack The Human
(1) @Zack, yep that's elephant porn for sure - dotjoe
(1) I prefer the more challenging (intended) version than the trivial version that the examples originally indicated - John La Rooy
(4) How about a cave that would trap an air bubble? - Greg Hewgill
@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) - Abel
@Abel, that example is invalid since the input 'line' is not continuous. A modified example would be pastebin.com/m11e08e82 - LiraNuna
@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 ;-) - Abel
@Able: Not only that, but you had the `/` intersecting with the ground level, so I had to make it flat. - LiraNuna
You may want to have a test case where a cave opens to the right. - DigitalRoss
@Greg: to stop this complication madness, let's declare side caves illegal... - LiraNuna
(3) Okay, I'll go hide in my illegal side cave now. - Greg Hewgill
Just as soon as this flood of code golf questions stop, i can ask mine... Any idea when that will be? ;) - RCIX
Here are a couple more tests, pastie.org/708281 and also pastie.org/708288 - DigitalRoss
And pastie.org/708310 - DigitalRoss
Wow, I knew this is a hard challenge, but I didn't think people will choose the naive way... - LiraNuna
(1) Uh, oh, I missed the easy way? Anyway, awesome problem. One of your best! And only 1 working solution after 24 hours! - DigitalRoss
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. - Pär Wieslander
@Pär: Thank you, you're correct. - LiraNuna
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. - LiraNuna
(1) @LiraNuna: Wait, do you have a solution in 300 strokes? Why don't you post it? - A. Rex
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.) - DigitalRoss
Or possibly a state machine that kept track of sky, water, & dirt and just sequenced through every square. - DigitalRoss
@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. - LiraNuna
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 :) - RCIX
[+16] [2009-11-20 03:06:18] Aaron [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]);}

(3) 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. - Chris Lutz
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) :) - Aaron
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 - DigitalRoss
(2) How can you guys read it? Is there any tool to quickly reformat the code to readable? - tranmq
(2) @DigitalRoss - in 2D world physics is different and those passages are too small for water molecules to fit through... :) - Aaron
Can you save one character by replacing if(x>w)w=x; by w=x>w?x:w; ? - hexium
(1) 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! :-) - DigitalRoss
(1) @mqbt: running it through "indent" is a good idea: gnu.org/software/indent - user181548
@DigitalRoss - okay - edited to handle all 11 test cases that I know about. Still 621 chars. - Aaron
@Aaron, you can save a lot of characters by using ASCII codes instead of literals (32 instead of ' ' for example) - LiraNuna
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. - LiraNuna
@LiraNuna - 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) - Aaron
@LiraNuna - 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. - Aaron
@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. - LiraNuna
1
[+14] [2009-11-20 12:53:39] DigitalRoss

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

(1) Wow, only two solutions, about the same size, and one gets downvoted? With no comment? Hard to understand... - DigitalRoss
(7) 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. - Aaron
This one is nice, but fails with stack overflow on larger test cases such as pastie.org/708764 - Pär Wieslander
@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? - DigitalRoss
"but this is a recursive maze solver" no it's not :( - LiraNuna
@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. - Pär Wieslander
2
[+9] [2009-11-20 23:08:23] Pär Wieslander

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

Doesn't work on pastie.org/708288 pastie.org/708310 pastie.org/708310 - DigitalRoss
(2) Wow, an iterative solution, and with loops nested 4 deep. Interesting. - DigitalRoss
3
[+8] [2009-11-26 22:28:13] mercator

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 [1] still fails on that.

[1] http://pastie.org/716553

4