53

チャレンジ

入力からの土地の ASCII 表現で水のくぼみを識別してマークするための、文字数による最短コード。

入力は、丘、谷、平地を含む風景の ASCII 表現になります。プログラムは、 が浸水した場合の風景をシミュレートする必要があります。つまり、すべての谷が水で満たされます (文字x)。

ランドスケープは常に文字と共に開始および停止し、_少なくとも 2 文字の長さで、最短の入力になります__。

丘はレイズとして定義され、水で満たされるべきではありません:

  __
_/  \_

谷はくぼみとして定義され、平地に遭遇するまで水で満たされます。

_    _
 \__/

入力はクリーンであると見なすことができ、スペース ( )、改行 ( \n)、アンダースコア ( _)、スラッシュ (/および\) の文字のみで構成されます。_/_入力は連続した行と見なすことができ、またはなどのあいまいな行入力を含む入力

_   _
 \_/
 / \

無効と見なされます。

水中洞窟については、洞窟レベルが水位を上回った場合、水位を維持する必要があります。

テストケース

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\

コード カウントには、入力/出力 (つまり、完全なプログラム) が含まれます。

4

4 に答える 4

16

C - 741 621 600 文字(ただし、新しいケースは適切に処理します)

$ 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]);}
于 2009-11-20T03:06:18.993 に答える
13

ルビー、794 759 769 752 715 692 663 655 626  616

追加のテスト ケース:    http://pastie.org/708281   および   http://pastie.org/708288   および   http://pastie.org/708310

インデントを除いて圧縮:

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
于 2009-11-20T12:53:39.243 に答える
9

パイソン、702 805 794 778 758 754 710 651

http://pastie.org/708764などの大規模なテスト ケースだけでなく、DigitalRoss のテスト ケースも処理します。

実行例

$ 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),
于 2009-11-20T23:08:23.487 に答える
8

パール、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

これは、私が見たすべてのテストケースを処理します。改行はオプションであり、書式設定のためにのみ存在します。

などと呼んでくださいperl water.pl test.txt。

これは、前の例のいずれにもない別の面白いエッジケースです (とにかく私のアルゴリズムの場合):

__      _
  \__  /
    /_/

私が以前に提出した詳細なバージョンは、まだ失敗しています。

于 2009-11-26T22:28:13.973 に答える