R – Code Golf: Running Water

code-golflanguage-agnosticrosetta-stone

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

Best Answer

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

Perl, 134 characters

All linebreaks may be removed.

@s=unpack"C*",~"P\xdbLI\xc3a`[\@AB\xe0t\xc8df";
$_=<>;for$s(6,3,0){print map$s[hex$&]&1<<$_+$s?$_%2?"_":"|":" ",
0..2while/./g;print$/}

Explanation

@s stores the bits for each segment. The entries are in order from 0 to F (thanks to hex()) and the bits map to segments in this order:

6 7 x
3 4 5
0 1 2

with 0 being the LSB. (Bit 6 is unused). The values are stored packed in the string bit-inverted so there are a lot more printable characters; the ~ operator flips the bits and unpack gives me numbers (perl's bitwise operators are much clumsier when it comes to strings).

With the data in hand I read the input and proceed to loop over it three times; the only difference between the three loops is the bitmask required. For each character of input three characters of output are printed. The character to be printed is

$s[ hex $& ] & (1 << ($_ + $s) )
? ($_ % 2 ? "_" : "|" )
: " "

where @s is the lookup table, $s is the shift in effect depending on the row, and $_ is whether we're printing the 1st, 2nd, or 3rd character in the row. If the right bit in the lookup table entry is false it prints a space; otherwise it prints a "|" on the sides or a "_" in the middle.

Code Golf: Lasers

Perl, 166 160 characters

Perl, ~~251~~ ~~248~~ ~~246~~ ~~222~~ ~~214~~ ~~208~~ ~~203~~ ~~201~~ ~~193~~ ~~190~~ ~~180~~ ~~176~~ ~~173~~ ~~170~~ 166 --> 160 chars.

Solution had 166 strokes when this contest ended, but A. Rex has found a couple ways to shave off 6 more characters:

s!.!$t{$s++}=$&!ge,$s=$r+=99for<>;%d='>.^1<2v3'=~/./g;($r)=grep$d|=$d{$t{$_}},%t;
{$_=$t{$r+=(1,-99,-1,99)[$d^=3*/\\/+m</>]};/[\/\\ ]/&&redo}die/x/?true:false,$/

The first line loads the input into %t, a table of the board where $t{99*i+j} holds the character at row i,column j. Then,

%d=split//,'>.^1<2v3' ; ($r)=grep{$d|=$d{$t{$_}}}%t

it searches the elements of %t for a character that matches > ^ < or v, and simultaneously sets $d to a value between 0 and 3 that indicates the initial direction of the laser beam.

At the beginning of each iteration in the main loop, we update $d if the beam is currently on a mirror. XOR'ing by 3 gives the correct behavior for a \ mirror and XOR'ing by 1 gives the correct behavior for a / mirror.

$d^=3*/\\/+m</>

Next, the current position $r is updated accoring to the current direction.

$r+=(1,-99,-1,99)[$d] ; $_ = $t{$r}

We assign the character at the current position to $_ to make convenient use of the match operators.

/[\/\\ ]/ && redo

Continue if we are on a blank space or a mirror character. Otherwise we terminate true if we are on the target ($_ =~ /x/) and false otherwise.

Limitation: may not work on problems with more than 99 columns. This limitation could be removed at the expense of 3 more characters,