20

代码高尔夫:旋转迷宫


制作一个程序,接收一个由迷宫组成的文件。迷宫的墙壁由#. 迷宫必须包括一个由 a 给出的球和由 a 给出的o任意数量的洞@。迷宫文件既可以通过命令行输入,也可以通过标准输入作为一行读入。请在您的解决方案中指定哪个。

然后您的程序执行以下操作:

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),每行一条指令。

解释:

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

L是一个使用正则表达式将多行表达式$_逆时针旋转 90 度的函数。正则表达式在我最喜欢的代码高尔夫解决方案中被 hobbs 广泛使用。

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

将输入直到第一对连续换行符(即迷宫)输入$_.

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

要丢球,我们需要将o角色向下移动一行,因为它下面有一个空格。这对于单个标量表达式来说有点困难,所以我们要做的是逆时针旋转迷宫,将球移动到“右侧”。如果球的“右侧”出现了一个洞,那么球就会落入洞中(规范中没有,但我们可以将 更改@为 an*以显示球落入了哪个洞)。然后在我们打印之前,我们需要将板子顺时针旋转 90 度(或逆时针旋转 3 次),这样 down 就又是“down”了。

if(/o/) { ... }

如果迷宫中还有一个球,请继续。否则块将结束,程序将退出。

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

将指令读入$z. 指令“1”逆时针旋转电路板一次,指令“2”逆时针旋转 3 次。

如果我们多用 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 个字符

我正在修补我自己在 Code Golf 语言设计方面的实验!我还没有将矩阵技巧放入标准包中,复制 GolfScript 的想法可能会有所帮助。但现在我正在改进基本的噱头。

无论如何,这是我的第一次尝试。代码中需要四个内部空格,但不需要换行:

.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(其中第一个令牌是分配目标)与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

红宝石 1.9.1 p243

355 353 个字符

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

可能的改进领域:

  • 将迷宫读入一个干净的二维数组(目前为 55 个字符)
  • 查找和返回(x,y)球的坐标(目前为 61 个字符)

欢迎任何改进建议。

于 2010-06-14T19:16:47.803 回答
3

哈斯克尔:577 509 527 244 230 228 个字符

大规模的新方法:将迷宫保持为单个字符串!

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 - 650 638 个字符

(不确定如何计算换行符)(用于阅读的前导空格,不计算在内)

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