language agnostic - Código de golf: Laberinto giratorio
language-agnostic code-golf (7)
Código de golf: Laberinto giratorio
Haga un programa que tome en un archivo que consiste en un laberinto. El laberinto tiene paredes dadas por # . El laberinto debe incluir una sola bola, dada por una o y cualquier número de agujeros dados por una @ . El archivo del laberinto se puede ingresar a través de la línea de comando o leer como una línea a través de la entrada estándar. Por favor, especifique cuál en su solución.
Tu programa entonces hace lo siguiente:
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.
Puedes asumir que todos los laberintos de entrada están cerrados. Nota: un agujero actúa efectivamente como una pared en este sentido.
Puede suponer que todos los laberintos de entrada no tienen espacios en blanco extraños.
El código fuente más corto por número de caracteres gana.
Ejemplo escrito en javascript: http://trinithis.awardspace.com/rotatingMaze/maze.html
Ejemplo de laberintos:
######
#o @#
######
###########
#o #
# ####### #
###@ #
#########
###########################
# #
# # @ #
# # # ##
# # ####o####
# # #
# #
# #########
# @
######################
C # 3.0 - 650 638 caracteres
(no estoy seguro de cómo se cuentan las nuevas líneas) (espacios en blanco para la lectura, no se cuentan)
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());
}
}
}
Lee desde la línea de comandos, aquí está la línea de prueba que utilicé:
"###########" "#o #" "# ####### #" "###@ #" " #########"
Confió en gran medida en la respuesta de Mobrule Perl para el algoritmo.
Mi método de rotación (L) probablemente se puede mejorar.
Manijas de caja sin pared.
Haskell: 577 509 527 244 230 228 caracteres
Nuevo enfoque masivo: ¡Mantén el laberinto como una sola cuerda!
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: ¡la idea de dejar caer la pelota de lado!
Ruby 1.9.1 p243
355 353 caracteres
Soy bastante nuevo en Ruby, así que estoy seguro de que esto podría ser mucho más corto, probablemente hay algunos matices que me faltan.
Cuando se ejecuta, la ruta al archivo de mapa es la primera línea que lee. Intenté hacerlo parte de los argumentos de ejecución (habría guardado 3 caracteres), pero tuve problemas :)
La versión corta:
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
La versión verbosa:
(He cambiado un poco en la versión comprimida, pero entiendes la 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
Posibles áreas de mejora:
- Leyendo el laberinto en una matriz 2D limpia (actualmente 55 caracteres)
- Encontrar y devolver
(x,y)coordenadas de la pelota (actualmente 61 caracteres)
Cualquier sugerencia para mejorar son bienvenidas.
GolfScript - 97 caracteres
n/['''']/~{;(@"zip-1%":|3*~{{." o"/"o "*"@o"/"@ "*.@>}do}%|~.n*."o"/,(}{;/~(2*)|*~/}//[n*]+n.+*])/;
Esto no se hace tan bien como esperaba (quizás más tarde).
(Estas son mis notas y no una explicació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
Perl, 143 (128) char
172 152 146 144 143 caracteres,
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}}
Las nuevas líneas son significativas.
Utiliza la entrada estándar y espera que la entrada contenga el laberinto, seguido de una línea en blanco, seguido de las instrucciones (1 o 2), una instrucción por línea.
Explicación:
sub L{my$o;$o.="/n"while s/.$/$o.=$&,""/meg;$_=$o}
L es una función que usa expresiones regulares para rotar la expresión de varias líneas $_ sentido contrario a las agujas del reloj en 90 grados. La expresión regular fue utilizada de forma famosa por hobbs en mi solución de código de golf favorita de todos los tiempos .
$_.=<>until//n/n/;
Absorbe la entrada hasta el primer par de nuevas líneas consecutivas (es decir, el laberinto) en $_ .
L;1 while s/o / o/;s/o@/ */;
L;L;L;print
Para dejar caer la pelota, necesitamos mover el carácter o hacia abajo una línea si hay un espacio debajo. Esto es un poco difícil de hacer con una sola expresión escalar, por lo que lo que haremos es rotar el laberinto en sentido contrario a las agujas del reloj, mover la bola a la "derecha". Si alguna vez aparece un agujero a la "derecha" de la bola, entonces la bola caerá en el agujero (no está en la especificación, pero podemos cambiar el @ a un * para mostrar en qué agujero cayó la bola). Luego, antes de imprimir, necesitamos rotar la tabla 90 grados en el sentido de las agujas del reloj (o 3 veces en el sentido contrario a las agujas del reloj) para que la posición hacia abajo vuelva a estar "abajo".
if(/o/) { ... }
Continuar si todavía hay una bola en el laberinto. De lo contrario el bloque terminará y el programa saldrá.
1-($z=<>)||L;$z-2||L+L+L;redo
Lea una instrucción en $z . Gire la placa en sentido antihorario una vez para la instrucción "1" y tres veces para la instrucción "2".
Si usamos 3 caracteres más y dijimos +s/o[@*]/ */ lugar de ;s/o@/ */ , entonces podríamos soportar múltiples bolas.
Una versión más simple de este programa, donde las instrucciones son "2" para girar el laberinto en el sentido de las agujas del reloj y cualquier otra instrucción para girar en el sentido contrario a las agujas del reloj, se puede realizar en 128 caracteres.
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}}
Python 2.6: ~ 284 ~ personajes
Es posible que todavía haya margen de mejora (aunque ya lo tengo mucho desde las primeras revisiones).
Todos los comentarios o sugerencias más entonces bienvenidos!
Suministre el archivo de mapa en la línea de comando como primer argumento:
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
Rebmu : 298 personajes
Estoy jugando con mi propio experimento en Code Golf Language Design. Todavía no he introducido trucos de matriz en la bolsa estándar, y copiar las ideas de GolfScript probablemente ayude. Pero ahora mismo estoy trabajando en refinar el truco básico.
De todos modos, aquí está mi primer intento. Los cuatro espacios internos se requieren en el código tal como es, pero los saltos de línea no son necesarios:
.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]
Puede parecer que un gato estaba en mi teclado. Pero una vez que pasas un pequeño truco para ahorrar espacio (literalmente, para guardar espacios) llamado "mushing" no es tan malo. La idea es que Rebmu no distingue entre mayúsculas y minúsculas, por lo que se utiliza la alternancia de mayúsculas para comprimir los símbolos. En lugar de hacer FooBazBar => foo baz bar aplico significados distintos. FOObazBAR => foo: baz bar (donde el primer token es un objetivo de asignación) vs fooBAZbar => foo baz bar (todas las fichas comunes).
Cuando se ejecuta el desenmascaramiento, obtiene algo más legible, pero ampliado a 488 caracteres:
. 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 puede ejecutarlo expandido también. También hay palabras clave detalladas ( first lugar de fs ) y puedes combinarlas y combinarlas. Aquí están las definiciones de funciones con algunos comentarios:
; 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 es la función de ancho y H es la altura de los datos de la matriz original. Los datos nunca se rotan ... pero hay una variable j que nos dice cuántos giros a la derecha de 90 grados debemos aplicar.
Una función Z nos da el tamaño ajustado para cuando se toma en cuenta la rotación, y una función C toma un parámetro de par de coordenadas y devuelve una posición de serie (algo así como un puntero o iterador) en los datos para ese par de coordenadas.
Hay un iterador G matriz al que le pasas una función y llamará a esa función para cada celda de la cuadrícula. Si la función que proporciona devuelve un valor, detendrá la iteración y la función de iteración devolverá ese valor. La función B escanea el laberinto en busca de una bola y devuelve las coordenadas si las encuentra, o none .
Aquí está el bucle principal con algunos comentarios:
; 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
]
No hay nada particularmente inteligente acerca de este programa. Que es parte de mi idea, que es ver qué tipo de compresión se puede obtener con enfoques simples y aburridos que no se basan en ningún truco. Creo que demuestra algo del potencial novedoso de Rebmu.
¡Será interesante ver cómo una mejor biblioteca estándar podría afectar la brevedad de las soluciones!
Última fuente comentada actualizada disponible en GitHub: rotating-maze.rebmu