Code Golf: Labyrinthe Rotatif

Code Golf: Maze Rotative


Faire un programme qui prend un fichier constitué d'un labyrinthe. Le labyrinthe a des murs donnés par # . Le labyrinthe doit comporter une seule bille, donnée par un o et un nombre quelconque de trous donnés par un @ . Le fichier maze peut être entré en ligne de commande ou lu en ligne à l'aide d'une entrée standard. Veuillez préciser dans votre solution.

votre programme fait alors ce qui suit:

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.

vous pouvez supposer que tous les labyrinthes d'entrée sont fermés. Remarque: un trou agit efficacement comme un mur à cet égard.

vous pouvez supposer que tous les labyrinthes d'entrée n'ont pas d'espace libre.

le code source le plus court selon le nombre de caractères gagne.


exemple écrit en javascript: http://trinithis.awardspace.com/rotatingMaze/maze.html


exemples de labyrinthe:

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

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

###########################
#                         #
#       #     @           #
#       #         #      ##
#       #         ####o####
 #      #                 #
  #                       #
   #              #########
    #                     @
     ######################
20
demandé sur Thomas Eding 2010-06-14 03:41:24

7 réponses

GolfScript-97 chars

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

ce n'est pas fait aussi bien que je l'espérais (peut-être plus tard).

(ce sont mes notes et non une explication)

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
8
répondu Nabb 2010-06-16 02:04:45

Perl, 143 (128) char

172 152 146 144 143 les caractères,

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

les retours à la ligne sont importants.

utilise l'entrée standard et s'attend à ce que l'entrée contienne le labyrinthe, suivi d'une ligne vide, suivi des instructions (1 ou 2), une instruction par ligne.

explication:

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

L est une fonction qui utilise des expressions régulières pour faire tourner l'expression $_ dans le sens antihoraire de 90 degrés. L'expression régulière a été utilisée par hobbs dans mon préféré solution de golf de code de tous les temps .

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

Slurps l'entrée jusqu'à la première paire de lignes consécutives (c'est-à-dire, le labyrinthe) dans $_ .

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

pour lancer la balle, nous avons besoin de déplacer le o sur une ligne est il ya un espace sous elle. C'est un peu difficile à faire avec une seule expression scalaire, donc ce que nous allons faire à la place est de tourner le labyrinthe dans le sens inverse des aiguilles d'une montre, déplacer la balle vers la "droite". Si un trou apparaît jamais à la "droite "de la balle, alors la balle va tomber dans le trou (ce n'est pas dans la spécification, mais nous pouvons changer le @ en un * pour montrer dans quel trou la balle est tombée). Alors avant de Nous imprimons, nous avons besoin de tourner la planche dans le sens des aiguilles d'une montre 90 degrés (ou dans le sens contraire des aiguilles d'une montre 3 fois) de sorte que le bas est "vers le bas" à nouveau.

if(/o/) { ... }

continuer s'il y a encore une balle dans le labyrinthe. Sinon, le bloc se terminera et le programme se terminera.

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

lire une instruction dans $z . Tourner la planche dans le sens contraire des aiguilles d'une montre une fois pour l'instruction "1" et trois fois pour l'instruction "2".

si nous avons utilisé 3 plus caractères et dit +s/o[@*]/ */ au lieu de ;s/o@/ */ , alors nous pourrions supporter plusieurs balles.

une version plus simple de ce programme, où les instructions sont" 2 " pour la rotation du labyrinthe dans le sens des aiguilles d'une montre et toute autre instruction pour la rotation dans le sens contraire des aiguilles d'une montre, peut être faite en 128 caractères.

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}}
14
répondu mob 2017-05-23 10:32:43

Rebmu : 298 Caractères

je bricole avec ma propre expérience dans la conception de langage de Golf de Code! Je n'ai pas encore jeté matrix tricks dans le sac standard, et copier les idées de GolfScript aidera probablement. Mais en ce moment, je travaille à affiner le truc de base.

en tout cas, voici ma première tentative. Les quatre espaces internes sont nécessaires dans le code tel qu'il est, mais les sauts de ligne ne sont pas nécessaires:

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

on dirait qu'un chat était sur mon clavier. Mais une fois que vous avez passé un petit truc pour économiser de l'espace (littéralement sauver des espaces) appelé "mushing", ce n'est pas si mal. L'idée est que Rebmu n'est pas sensible à la casse, donc l'alternance des cycles de majuscules est utilisée pour compresser les symboles. Au lieu de faire FooBazBar => foo baz bar j'applique des significations distinctes. FOObazBAR => foo: baz bar (où le premier jeton est une cible d'assignation) vs fooBAZbar => foo baz bar (tous les jetons ordinaires).

quand l'unmush est lancé, vous obtenez quelque chose de plus lisible, mais étendu à 488 caractères:

. 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 peut l'exécuter étendu aussi. Il y a aussi des mots-clés verbeux ( first au lieu de fs ) et vous pouvez mélanger et assortir. Voici les définitions de fonction avec quelques commentaires:

; 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 est la fonction de largeur et H est la hauteur des données du tableau original. Les données sont jamais tourné...mais il y a une variable j qui nous dit combien de virages à droite de 90 degrés nous devrions appliquer.

une fonction Z nous donne la taille ajustée pour quand la rotation est prise en compte, et une fonction C prend un paramètre de paire de coordonnées et retourne une position de série (un peu comme un pointeur ou un itérateur) dans les données pour cette paire de coordonnées.

il y a un itérateur de tableau G que vous passez une fonction et il va appeler cette fonction pour chaque cellule de la grille. Si la fonction que vous fournissez renvoie une valeur, elle arrêtera l'itération et la fonction d'itération retournera cette valeur. La fonction B scanne le labyrinthe pour trouver une boule et renvoie les coordonnées si trouvées, ou none .

Voici la boucle principale avec quelques commentaires:

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

il n'y a pas grand-chose de particulièrement intelligent dans ce programme. Qui est une partie de mon idée, qui est de voir quel type de compression on pourrait obtenir sur des approches simples et ennuyeuses qui ne comptent pas sur des trucs. Je pense que ça démontre un peu le potentiel novateur de Rebmu.

il sera intéressant de voir comment une meilleure bibliothèque standard pourrait affecter la brièveté des solutions!

la plus récente source commentée disponible sur GitHub: rotating-maze.rebmu

8
répondu HostileFork 2014-02-16 12:42:35

Ruby 1.9.1 p243

355 353 caractères

Je suis assez nouveau à Ruby, donc je suis sûr que cela pourrait être beaucoup plus court - il y a probablement quelques nuances que je manque.

Lorsqu'il est exécuté, le chemin d'accès au fichier est la première ligne qu'il lit. J'ai essayé de faire partie de l'exécution des arguments (aurait sauvé 3 caractères), mais a eu des problèmes :)

la version courte:

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 version détaillé:

(j'ai changé un peu dans la version compressée, mais vous avez l'idée)

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

zones d'amélioration possibles:

  • lecture du labyrinthe dans un tableau 2D propre (actuellement 55 caractères)
  • Trouver et retourner (x,y) les coordonnées de la boule (actuellement 61 caractères)

toute suggestion d'amélioration est la bienvenue.

6
répondu Jeriko 2010-06-15 10:20:30

Haskell: 577 509 527 244 230 228 chars

Massive nouvelle approche: Garder le labyrinthe comme une seule chaîne!

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

salue la solution Perl de @mobrule à l'idée de laisser tomber la balle de côté!

3
répondu MtnViewMark 2010-06-16 13:39:02

Python 2.6: ~ 284 ~ characters

il y a peut-être encore place à l'amélioration (bien que je l'ai déjà beaucoup baissé depuis les premières révisions).

Tous les commentaires ou suggestions bienvenue!

fournit le fichier map sur la ligne de commande comme premier 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
3
répondu ChristopheD 2010-06-16 19:53:53

C# 3.0 - 650 638 caractères

(Je ne sais pas comment les nouvelles lignes sont comptées) cents cinquante et une million neuf cent soixante dix mille neuf cent vingt"

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

D'après la ligne de commande, voici la ligne de test que j'ai utilisée:

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

S'appuie fortement sur la réponse Perl de mobrule pour l'algorithme.

ma méthode de Rotation (L) peut probablement être améliorée.

poignées caisse sans MUR.

1
répondu David B 2010-06-17 08:22:23