Code Golf: Rotating Maze

问题:

Code Golf: Rotating Maze

---

Make a program that takes in a file consisting of a maze. The maze has walls given by #. The maze must include a single ball, given by a o and any number of holes given by a @. The maze file can either be entered via command line or read in as a line through standard input. Please specify which in your solution.

Your program then does the following:

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.

You may assume all input mazes are closed. Note: a hole effectively acts as a wall in this regard.

You may assume all input mazes have no extraneous whitespace.

The shortest source code by character count wins.

---

Example written in javascript: http://trinithis.awardspace.com/rotatingMaze/maze.html

---

Example mazes:

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

---

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

---

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

回答1:

GolfScript - 97 chars

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

This isn't done as well as I hoped (maybe later).

(These are my notes and not an explanation)

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

回答2:

Perl, 143 (128) char

172 152 146 144 143 chars,

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}}

Newlines are significant.

Uses standard input and expects input to contain the maze, followed by a blank line, followed by the instructions (1 or 2), one instruction per line.

Explanation:

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

L is a function that uses regular expressions to rotate the multi-line expression $_ counterclockwise by 90 degrees. The regular expression was used famously by hobbs in my favorite code golf solution of all time.

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

Slurps the input up to the first pair of consecutive newlines (that is, the maze) into $_.

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

To drop the ball, we need to move the o character down one line is there is a space under it. This is kind of hard to do with a single scalar expression, so what we'll do instead is rotate the maze counterclockwise, move the ball to the "right". If a hole ever appears to the "right" of the ball, then the ball is going to fall in the hole (it's not in the spec, but we can change the @ to an * to show which hole the ball fell into). Then before we print, we need to rotate the board clockwise 90 degrees (or counterclockwise 3 times) so that down is "down" again.

if(/o/) { ... }

Continue if there is still a ball in the maze. Otherwise the block will end and the program will exit.

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

Read an instruction into $z. Rotate the board counterclockwise once for instruction "1" and three times for instruction "2".

If we used 3 more characters and said +s/o[@*]/ */ instead of ;s/o@/ */, then we could support multiple balls.

A simpler version of this program, where the instructions are "2" for rotating the maze clockwise and any other instruction for rotating counterclockwise, can be done in 128 chars.

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}}

回答3:

Rebmu: 298 Characters

I'm tinkering with with my own experiment in Code Golf language design! I haven't thrown matrix tricks into the standard bag yet, and copying GolfScript's ideas will probably help. But right now I'm working on refining the basic gimmick.

Anyway, here's my first try. The four internal spaces are required in the code as it is, but the line breaks are not necessary:

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

It may look like a cat was on my keyboard. But once you get past a little space-saving trick (literally saving spaces) called "mushing" it's not so bad. The idea is that Rebmu is not case sensitive, so alternation of capitalization runs is used to compress the symbols. Instead of doing FooBazBar => foo baz bar I apply distinct meanings. FOObazBAR => foo: baz bar (where the first token is an assignment target) vs fooBAZbar => foo baz bar (all ordinary tokens).

When the unmush is run, you get something more readable, but expanded to 488 characters:

. 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 can run it expanded also. There are also verbose keywords as well (first instead of fs) and you can mix and match. Here's the function definitions with some comments:

; 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 is the width function and H is the height of the original array data. The data is never rotated...but there is a variable j which tells us how many 90 degree right turns we should apply.

A function Z gives us the adjusted size for when rotation is taken into account, and a function C takes a coordinate pair parameter and returns a series position (kind of like a pointer or iterator) into the data for that coordinate pair.

There's an array iterator G which you pass a function to and it will call that function for each cell in the grid. If the function you supply ever returns a value it will stop the iteration and the iteration function will return that value. The function B scans the maze for a ball and returns coordinates if found, or none.

Here's the main loop with some commenting:

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

There's not all that much particularly clever about this program. Which is part of my idea, which is to see what kind of compression one could get on simple, boring approaches that don't rely on any tricks. I think it demonstrates some of Rebmu's novel potential.

It will be interesting to see how a better standard library could affect the brevity of solutions!

Latest up-to-date commented source available on GitHub: rotating-maze.rebmu

回答4:

Ruby 1.9.1 p243

355 353 characters

I'm pretty new to Ruby, so I'm sure this could be a lot shorter - theres probably some nuances i'm missing.

When executed, the path to the map file is the first line it reads. I tried to make it part of the execution arguments (would have saved 3 characters), but had issues :)

The short version:

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

The verbose version:

(I've changed a bit in the compressed version, but you get the idea)

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

Possible improvement areas:

• Reading the maze into a clean 2D array (currently 55 chars)
• Finding and returning (x,y) co-ordinates of the ball (currently 61 chars)

Any suggestions to improve are welcome.

回答5:

Haskell: 577 509 527 244 230 228 chars

Massive new approach: Keep the maze as a single string!

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

Nods to @mobrule's Perl solution for the idea of dropping the ball sideways!

回答6:

Python 2.6: ~ 284 ~ characters

There is possibly still room for improvement (although I already got it down a lot since the first revisions).

All comments or suggestions more then welcome!

Supply the map file on the command line as the first argument:
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

回答7:

C# 3.0 - 650 638 characters

(not sure how newlines being counted) (leading whitespace for reading, not counted)

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

Reads from commandline, here's the test line I used:

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

Relied heavily on mobrule's Perl answer for algorithm.

My Rotation method (L) can probably be improved.

Handles wall-less case.