20

コードゴルフ:回転迷路


迷路からなるファイルを取り込むプログラムを作成します。迷路にはによって与えられた壁があり#ます。迷路には、aで指定された単一のボールと、で指定されたo任意の数の穴が含まれている必要があります@。迷路ファイルは、コマンドラインから入力するか、標準入力から1行として読み込むことができます。ソリューションでどちらを指定してください。

次に、プログラムは次のことを行います。

1: If the ball is not directly above a wall, drop it down to the nearest wall.
2: If the ball passes through a hole during step 1, remove the ball.
3: Display the maze in the standard output (followed by a newline).
   Extraneous whitespace should not be displayed.
   Extraneous whitespace is defined to be whitespace outside of a rectangle 
   that fits snugly around the maze.
4: If there is no ball in the maze, exit.
5: Read a line from the standard input. 
   Given a 1, rotate the maze counterclockwise. 
   Given a 2, rotate the maze clockwise. 
   Rotations are done by 90 degrees. 
   It is up to you to decide if extraneous whitespace is allowed.
   If the user enters other inputs, repeat this step.
6: Goto step 1.

すべての入力迷路が閉じていると想定できます。注:この点で、穴は効果的に壁として機能します。

すべての入力迷路に余分な空白がないと想定することができます。

文字数で最短のソースコードが優先されます。


javascriptで書かれた例:http: //trinithis.awardspace.com/rotatingMaze/maze.html


迷路の例:

######
#o  @#
######

###########
#o        #
# ####### #
###@      #
  #########

###########################
#                         #
#       #     @           #
#       #         #      ##
#       #         ####o####
 #      #                 #
  #                       #
   #              #########
    #                     @
     ######################
4

7 に答える 7

14

Perl、143(128)文字

172 152 146 144 143文字、

sub L{my$o;$o.=$/while s/.$/$o.=$&,""/meg;$_=$o}$_.=<>until/

/;{L;1while s/o / o/;s/o@/ @/;L;L;L;print;if(/o/){1-($z=<>)||L;$z-2||L&L&L;redo}}

改行は重要です。

標準入力を使用し、入力に迷路が含まれ、その後に空白行が続き、その後に命令(1または2)が続き、1行に1つの命令が含まれることを期待します。

説明:

sub L{my$o;$o.="\n"while s/.$/$o.=$&,""/meg;$_=$o}

Lは、正規表現を使用して、複数行の式を$_反時計回りに90度回転させる関数です。正規表現は、私のお気に入りのコードゴルフソリューションでホブによって有名に使用されていました。

$_.=<>until/\n\n/;

連続する改行の最初のペア(つまり、迷路)までの入力をにスラップします$_

L;1 while s/o / o/;s/o@/ */;
L;L;L;print

ボールを落とすにoは、その下にスペースがあるので、キャラクターを1行下に移動する必要があります。これは単一のスカラー式ではやや難しいので、代わりに迷路を反時計回りに回転させ、ボールを「右」に移動します。ボールの「右」に穴が表示された場合、ボールはその穴に落ちます(仕様には含まれていませんが、に変更し@*、ボールがどの穴に落ちたかを示すことができます)。次に、印刷する前に、ボードを時計回りに90度(または反時計回りに3回)回転させて、下が再び「下」になるようにする必要があります。

if(/o/) { ... }

迷路にまだボールがある場合は続行します。それ以外の場合、ブロックは終了し、プログラムは終了します。

1-($z=<>)||L;$z-2||L+L+L;redo

命令をに読み込み$zます。ボードを反時計回りに1回回転させて、命令「1」を実行し、3回回転させて命令「2」を実行します。

さらに3文字を使用して、+s/o[@*]/ */の代わりに言った場合;s/o@/ */、複数のボールをサポートできます。

このプログラムのより単純なバージョンでは、迷​​路を時計回りに回転させるための命令は「2」であり、反時計回りに回転させるための他の命令は128文字で実行できます。

sub L{my$o;$o.=$/while s/.$/$o.=$&,""/meg;$_=$o}$_.=<>until/

/;L;{1while s/o / o/+s/o@/ @/;L,L,L;print;if(/o/){2-<>&&L,L;redo}}
于 2010-06-15T19:45:01.353 に答える
8

GolfScript-97文字

n/['']/~{;(@"zip-1%":|3*~{{." o"/"o "*"@o"/"@ "*.@>}do}%|~.n*."o"/,(}{;\~(2*)|*~\}/\[n*]+n.+*])\;

これは私が望んでいたようには行われていません(多分後で)。

(これらは私のメモであり、説明ではありません)

n/['']/~                             #[M I]
{
;(@                                  #[I c M]
"zip-1%":|3*~                        #rotate
{{." o"/"o "*"@o"/"@ "*.@>}do}%      #drop
|~                                   #rotate back
.n*                                  #"display" -> [I c M d]
."o"/,(                              #any ball? -> [I c M d ?]
}{                                   #d is collected into an array -> [I c M]
;\~(2*)|*~                           #rotate
\                                    #stack order
}/
\[n*]+n.+*])\;                       #output
于 2010-06-16T02:04:45.057 に答える
8

Rebmu:298文字

私はコードゴルフの言語デザインで自分の実験をいじっています!私はまだマトリックストリックを標準のバッグに入れていません。GolfScriptのアイデアをコピーすることはおそらく役立つでしょう。しかし、今は基本的なギミックの改良に取り組んでいます。

とにかく、これが私の最初の試みです。コードには4つの内部スペースがそのまま必要ですが、改行は必要ありません。

.fFS.sSC L{#o@}W|[l?fM]H|[l?m]Z|[Tre[wH]iOD?j[rvT]t]
Ca|[st[xY]a KrePC[[yBKx][ntSBhXbkY][ntSBhYsbWx][xSBwY]]ntJskPCmFkSk]
Ga|[rtYsZ[rtXfZ[TaRE[xY]iTbr]iTbr]t]B|[gA|[ieSlFcA[rnA]]]
MeFI?a[rlA]aFV[NbIbl?n[ut[++n/2 TfCnIEfLtBRchCbSPieTHlTbrCHcNsLe?sNsZ]]
gA|[TfCaEEfZfA[prT][pnT]nn]ulBbr JmoADjPC[3 1]rK4]

猫が私のキーボードに乗っているように見えるかもしれません。しかし、「マッシング」と呼ばれる小さなスペース節約のトリック(文字通りスペースを節約する)を乗り越えれば、それほど悪くはありません。Rebmuは大文字と小文字を区別しないため、大文字と小文字を交互に使用して記号を圧縮します。そうする代わりに、FooBazBar => foo baz bar私は明確な意味を適用します。 FOObazBAR => foo: baz bar(最初のトークンが割り当てターゲットである場合)vs fooBAZbar => foo baz bar(すべての通常のトークン)。

unmushを実行すると、読みやすくなりますが、488文字に拡張されます。

. f fs . s sc l: {#o@} w: | [l? f m] h: | [l? m] z: | [t: re [w h] i od? 
j [rv t] t] c: a| [st [x y] a k: re pc [[y bk x] [nt sb h x bk y] [nt sb 
h y sb w x] [x sb w y]] nt j sk pc m f k s k] g: a| [rt y s z [rt x f z 
[t: a re [x y] i t br] i t br] rn t] b: | [g a| [ie s l f c a [rn a]]] 
m: e fi? a [rl a] a fv [n: b i bl? n [ut [++ n/2 t: f c n ie f l t br 
ch c b sp ie th l t br ch c n s l e? s n s z]] g a| [t: f c a ee f z f 
a [pr t] [pn t] nn] ul b br j: mo ad j pc [3 1] r k 4]

Rebmuはそれを拡張して実行することもできます。first(の代わりに)冗長なキーワードもあり、fs組み合わせることができます。コメント付きの関数定義は次のとおりです。

; shortcuts f and s extracting the first and second series elements
. f fs
. s sc 

; character constants are like #"a", this way we can do fL for #"#" etc
L: {#o@}

; width and height of the input data
W: | [l? f m] 
H: | [l? m]

; dimensions adjusted for rotation (we don't rotate the array)
Z: | [t: re [w h] i od? j [rv t] t] 

; cell extractor, gives series position (like an iterator) for coordinate
C: a| [
    st [x y] a 
    k: re pc [[y bk x] [nt sb h x bk y] [nt sb h y sb w x] [x sb w y]] nt j 
    sk pc m f k s k
] 

; grid enumerator, pass in function to run on each cell
G: a| [rt y s z [rt x f z [t: a re [x y] i t br] i t br] t] 

; ball position function
B: | [g a| [ie sc l f c a [rn a]]]

Wは幅関数で、Hは元の配列データの高さです。jデータが回転することはありません...ただし、90度の右折を何回適用するかを示す変数があります。

関数Zは、回転が考慮されるときに調整されたサイズを提供し、関数Cは座標ペアパラメーターを受け取り、その座標ペアのデータに一連の位置(ポインターやイテレーターのようなもの)を返します。

関数を渡す配列イテレータがありG、グリッド内の各セルに対してその関数を呼び出します。指定した関数が値を返す場合、反復を停止し、反復関数はその値を返します。この関数Bは迷路をスキャンしてボールを探し、見つかった場合は座標を返しますnone

コメント付きのメインループは次のとおりです。

; if the command line argument is a filename, load it, otherwise use string
m: e fi? a [rl a] a 

; forever (until break, anyway...)
fv [
    ; save ball position in n 
    n: B

    ; if n is a block type then enter a loop
    i bl? n [

        ; until (i.e. repeat until)
        ut [
            ; increment second element of n (the y coordinate)
            ++ n/2 

            ; t = first(C(n))
            t: f C n

            ; if-equal(first(L), t) then break
            ie f l t br

            ; change(C(B), space)
            ch C B sp

            ; if-equal(third(L),t) then break 
            ie th L t br 

            ; change(C(n), second(L))
            ch C n s L 

            ; terminate loop if "equals(second(n), second(z))"
            e? s n s z
         ]
     ] 

     ; iterate over array and print each line
     g a| [t: f c a ee f z f a [pr t] [pn t] nn]

     ; unless the ball is not none, we'll be breaking the loop here...
     ul b br 

     ; rotate according to input
     j: mo ad j pc [3 1] r k 4
]

このプログラムについては、それほど賢いことはありません。これは私の考えの一部であり、トリックに依存しない単純で退屈なアプローチでどのような圧縮を行うことができるかを確認することです。Rebmuの斬新な可能性を示していると思います。

より良い標準ライブラリがソリューションの簡潔さにどのように影響するかを見るのは興味深いでしょう!

GitHubで入手可能な最新のコメント付きソース:rotating-maze.rebmu

于 2010-06-17T09:29:02.060 に答える
6

Ruby 1.9.1 p243

355353文字

私はRubyにかなり慣れていないので、これはもっと短くなる可能性があると確信しています-おそらく私が見逃しているニュアンスがいくつかあります。

実行すると、マップファイルへのパスが最初に読み取られます。私はそれを実行引数の一部にしようとしましたが(3文字節約できたでしょう)、問題がありました:)

短いバージョン:

def b m;m.each_index{|r|i=m[r].index(?o);return r,i if i}end;def d m;x,y=b m;z=x;
while z=z+1;c=m[z][y];return if c==?#;m[z-1][y]=" "; return 1 if c==?@;m[z][y]=?o;end;end;
def r m;m.transpose.reverse;end;m=File.readlines(gets.chomp).map{|x|x.chomp.split(//)};
while a=0;w=d m;puts m.map(&:join);break if w;a=gets.to_i until 0<a&&a<3;
m=r a==1?m:r(r(m));end

詳細バージョン:

(私は圧縮バージョンで少し変更しましたが、あなたは考えを理解します)

def display_maze m
 puts m.map(&:join)
end

def ball_pos m
  m.each_index{ |r|
    i = m[r].index("o")
    return [r,i] if i
  }
end

def drop_ball m
  x,y = ball_pos m
  z=x
  while z=z+1 do
    c=m[z][y]
    return if c=="#"
    m[z-1][y]=" "
    return 1 if c=="@"
    m[z][y]="o"
  end
end

def rot m
  m.transpose.reverse
end

maze = File.readlines(gets.chomp).map{|x|x.chomp.split(//)}

while a=0
  win = drop_ball maze
  display_maze maze
  break if win
  a=gets.to_i until (0 < a && a < 3)
  maze=rot maze
  maze=rot rot maze if a==1
end

考えられる改善領域:

  • 迷路をきれいな2D配列(現在55文字)に読み込む
  • (x,y)ボールの座標(現在61文字)を見つけて返す

改善のための提案は大歓迎です。

于 2010-06-14T19:16:47.803 に答える
3

Haskell :577 509 527 244230228 文字

大規模な新しいアプローチ:迷路を単一の文字列として保持します!

import Data.List
d('o':' ':x)=' ':(d$'o':x)
d('o':'@':x)=" *"++x
d(a:x)=a:d x
d e=e
l=unlines.reverse.transpose.lines
z%1=z;z%2=l.l$z
t=putStr.l.l.l
a z|elem 'o' z=t z>>readLn>>=a.d.l.(z%)|0<1=t z
main=getLine>>=readFile>>=a.d.l

ボールを横に落とすというアイデアについては、@ mobruleのPerlソリューションにうなずきます!

于 2010-06-15T04:48:59.667 に答える
3

Python 2.6:〜284〜文字

おそらくまだ改善の余地があります(最初の改訂以来、私はすでにそれをかなり落としていますが)。

すべてのコメントや提案は大歓迎です!

最初の引数として、コマンドラインでマップファイルを指定します。
python rotating_maze.py input.txt

import sys
t=[list(r)[:-1]for r in open(sys.argv[1])]
while t:
 x=['o'in e for e in t].index(1);y=t[x].index('o')
 while t[x+1][y]!="#":t[x][y],t[x+1][y]=" "+"o@"[t[x+1][y]>" "];x+=1
 for l in t:print''.join(l)
 t=t[x][y]=='o'and map(list,(t,zip(*t[::-1]),zip(*t)[::-1])[input()])or 0
于 2010-06-15T20:57:07.653 に答える
1

C#3.0-650638文字

(改行がどのようにカウントされるかわからない)(読み取り用の先頭の空白、カウントされない)

using System.Linq;
using S=System.String;
using C=System.Console;
namespace R
{
class R
{
static void Main(S[]a)
{
S m=S.Join("\n",a);
bool u;
do
{
 m=L(m);
 int b=m.IndexOf('o');
 int h=m.IndexOf('@',b);
 b=m.IndexOf('#',b);
 m=m.Replace('o',' ');
 u=(b!=-1&b<h|h==-1);
 if (u)
  m=m.Insert(b-1,"o").Remove(b,1);
 m=L(L(L(m)));
 C.WriteLine(m);
 if (!u) return;
 do
 {
  int.TryParse(C.ReadLine(),out b);
  u=b==1|b==2;
  m=b==1?L(L(L(m))):u?L(m):m;
 }while(!u);
}while(u);
}
static S L(S s)
{
return S.Join("\n",
 s.Split('\n')
 .SelectMany(z => z.Select((c,i)=>new{c,i}))
 .GroupBy(x =>x.i,x=>x.c)
 .Select(g => new S(g.Reverse().ToArray()))
 .ToArray());
}
}
}

コマンドラインから読み取ります。これが私が使用したテストラインです。

"###########" "#o        #" "# ####### #" "###@      #" "  #########"

アルゴリズムについては、mobruleのPerlの回答に大きく依存していました。

私の回転法(L)はおそらく改善できるでしょう。

壁のないケースを処理します。

于 2010-06-17T07:54:56.537 に答える