Navegando exitosamente un campo de asteroides

36

Introducción

Todos saben que la posibilidad de navegar con éxito un campo de asteroides es de aproximadamente 3,720 a 1. Pero a pesar de su advertencia, Han Solo todavía está dispuesto a probar suerte.

Temiendo por su vida artificial, decide codificar, en el peculiar dialecto de la nave ( lea: su lenguaje preferido de Code Golf ), un programa de evitación de asteroides que decidirá qué camino tomar en un laberinto ASCII de campo de asteroides.

Entrada

El Millenium Falcon tiene un programa de mapeo de campo de asteroides, que proporciona datos similares a este:

|   #####           #########  |
| ######  #          ###   #   |
|   # #  #  #  ####   #        |
@              ##    ####       
|#   #   #       ###   ##      |
|##      ##      ####   #  #   |
|####           ##### #   ##   |

Las filas superiores quedan a la izquierda del Halcón, las filas inferiores están a la derecha del Halcón y las columnas representan lo que está frente al barco.

  • Cada uno #es un obstáculo.
  • Cada espacio es un espacio vacío en el que la nave puede volar.
  • La entrada siempre tiene 7 caracteres de altura. Este es el límite de ancho de mapeo de asteroides.
  • La entrada siempre tiene 32 caracteres (30 para el campo en sí y 2 para los límites inicial y final). Este es el límite de profundidad de mapeo de asteroides. Las barras verticales |marcan el comienzo y el final de la asignación.
  • @Es el halcón. Siempre está en la fila central (cuarta fila) y la primera columna en la entrada.
  • El espacio que queda en las barras verticales en la última columna es el lugar al que debe llegar el barco. Siempre está en la fila central (cuarta fila) y la última columna en la entrada.

La entrada se puede tomar como una cadena de varias líneas, una matriz de cadenas, desde STDIN o parámetros de una función, o leer desde un archivo.

Posibles maniobras

Usted es perseguido por TIE-Fighters, por lo tanto, siempre debe avanzar. Por lo tanto, hay tres formas en que el barco puede volar en cada paso:

  • - Adelante

  • / Adelante y gire a la izquierda

  • \ Adelante y gire a la derecha

Por ejemplo, estas son rutas válidas:

@---

  --
 /  \ /
@    -

   -
  / \
 /   \
@     \

Como puede ver, siempre hay exactamente un movimiento por columna. El Halcón es un pedazo de basura, por lo tanto, no puede hacer giros violentos. Lo que significa movimientos como /\o no\/ están permitidos . Debe haber al menos un puro hacia adelante -entre dos turnos opuestos. Por otro lado, es posible girar en una dirección para varios pasos seguidos, como se ve arriba.

El Halcón se estrella si un movimiento lleva a la nave a un lugar donde hay un obstáculo. Por ejemplo, estos movimientos conducen a bloqueos:

@-#

@
 \
  #

  #
 /
@

Tenga en cuenta que esto no es un bloqueo:

@-#
  \
   -

Salida

Debe generar el mismo campo de asteroide ASCII, con una ruta válida hasta el final. El Falcon debe imprimirse en el punto final en lugar del punto inicial.

Por ejemplo, una salida válida para el ejemplo de entrada dado anteriormente sería:

|   #####           #########  |
| ######  #--------  ###   #   |
|   # #  #/ #  ####\  #        |
 ---------      ##  \ #### ----@
|#   #   #       ### \ ## /    |
|##      ##      #### \ #/ #   |
|####           ##### #-- ##   |

Tu camino solo necesita no estrellar al halcón. No necesita ser el camino más corto posible.

Puede suponer que siempre habrá al menos un camino posible hacia el final.

Puede enviar a STDOUT, en un archivo o cualquier equivalente, siempre que el campo de asteroides se imprima exactamente como en esta publicación (por ejemplo, enviar una lista de coordenadas para la ruta no es válido).

Casos de prueba

  • Un campo de asteroides normal.

    |   #####           #########  |
| ######  #          ###   #   |
|   # #  #  #  ####   #        |
@              ##    ####       
|#   #   #       ###   ##      |
|##      ##      ####   #  #   |
|####           ##### #   ##   |

    Salida posible

    |   #####           #########  |
| ######  #--------  ###   #   |
|   # #  #/ #  ####\  #        |
 ---------      ##  \ #### ----@
|#   #   #       ### \ ## /    |
|##      ##      #### \ #/ #   |
|####           ##### #-- ##   |

  • Campo de asteroides hiperregulares

    |# # # # # # # # # # # # # # # |
| # # # # # # # # # # # # # # #|
|# # # # # # # # # # # # # # # |
@ # # # # # # # # # # # # # #   
|# # # # # # # # # # # # # # # |
| # # # # # # # # # # # # # # #|
|# # # # # # # # # # # # # # # |

    Salida posible

    |# # # # # # # # # # # # # # # |
| # # # # # # # # # # # # # # #|
|# # # # # # # # # # # # # # # |
 -# #-# #-# #-# #-# #-# #-# #--@
|#\#/#\#/#\#/#\#/#\#/#\#/#\#/# |
| #-# #-# #-# #-# #-# #-# #-# #|
|# # # # # # # # # # # # # # # |

  • Núcleo de la estrella de la muerte

    |    #    #    #         #     |
|         #    #    #          |
|    #    #    #    #    #     |
@    #    #    #    #    #      
|    #    #         #    #     |
|    #    #    #    #    #     |
|    #         #    #    #     |

    Salida posible

    |    #    #    #   --    #     |
|  ---    #    #  / #\   -     |
| /  #\   #    # /  # \ /#\    |
 -   # \  #    #/   #  - # ----@
|    #  \ # ----    #    #     |
|    #   \#/   #    #    #     |
|    #    -    #    #    #     |

  • Trinchera estrella de la muerte

    |##############################|
|##############################|
|##############################|
@                               
|##############################|
|##############################|
|##############################|

    Salida

    |##############################|
|##############################|
|##############################|
 ------------------------------@
|##############################|
|##############################|
|##############################|

  • Cueva de asteroides

    |### ##########################|
|## # ############### ## ######|
|# ###  ######## ### ## # #####|
@ ###### ###### ### ## ###      
|########  ### ### ## #########|
|########## # ### ## ##########|
|###########              #####|

    Salida posible

    |###-##########################|
|##/#\############### ##-######|
|#/###--######## ### ##/#\#####|
 -######\###### ### ##/###-----@
|########--### ### ##/#########|
|##########\# ### ##/##########|
|###########--------      #####|

Tanteo

R2D2 está ocupado nadando en pantanos, por lo que tendrá que programar el controlador del Falcon usted mismo, lo cual es tedioso. Por lo tanto, el código más corto gana .

code-golf maze Fatalizar
fuente
@DJMcMayhem: Técnicamente, la primera línea es "Introducción";)
Alex A.
2
De alguna manera entiendo cómo se supone que debe verse en función de los ejemplos, pero la codificación de los movimientos sigue siendo algo confusa para mí. Si busca, por ejemplo, el ejemplo "hiperregular", a excepción del primer / último movimiento, siempre se mueve en diagonal. Sin embargo, tiene -en el camino en cada turno, que se define como un movimiento "hacia adelante". Pero los movimientos reales son siempre dos diagonales a la izquierda seguidos de dos diagonales a la derecha.
Reto Koradi
@RetoKoradi Puedo entender que no es tan obvio, pero la idea básica es que todos los movimientos te hacen recorrer el ancho de un personaje a la derecha. El camino tiene que parecer continuo, por lo que el movimiento anterior / siguiente después de los giros a la derecha y a la izquierda está una línea arriba / abajo del anterior.
Fatalize
@apsillers Ambos son válidos, si te entiendo correctamente, tu respuesta debería ser buena
Fatalize

Respuestas:

11

JavaScript (ES6), 186 201

f=([...s])=>(g=(i,l,c=k=" ")=>s[i]!=k&&s[i]!="@"?0:(i-130)?(s[i]=c,([..."/-\\"].some((c,j)=>!((--j&l&&j!=l)||!g(i+33*(l||j)+1,j,c)))||!(s[i]=k))):(s[i]="@",!console.log(s.join(""))))(99)

Fragmento ejecutable:

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><textarea cols="33" rows="7" id="t"></textarea><br><button><b>Solve &gt;&gt;&gt;</b></button><hr><button id="1">Normal</button> <button id="2">Hyperregular</button> <button id="3">Death Star core</button> <button id="4">Death Star trench</button> <button id="5">Asteroid cave</button><script>f=(function($__0){var $__2,$__3,$__4,$__5;s = $__4 = $__0.split("");return (g = (function(i, l) {var c = arguments[2] !== (void 0) ? arguments[2] : k = " ";return s[i] != k && s[i] != "@" ? 0 : (i - 130) ? (s[i] = c, ("/-\\".split("").some((function(c, j) {return !((--j & l && j != l) || !g(i + 33 * (l || j) + 1, j, c));})) || !(s[i] = k))) : (s[i] = "@",$("#t").val(s.join("")));}))(99);});$("button").click(function() {this.id?$("#t").val(inputs[this.id]):f($("#t").val());});inputs = [,`|   #####           #########  |\n| ######  #          ###   #   |\n|   # #  #  #  ####   #        |\n@              ##    ####       \n|#   #   #       ###   ##      |\n|##      ##      ####   #  #   |\n|####           ##### #   ##   |`,`|# # # # # # # # # # # # # # # |\n| # # # # # # # # # # # # # # #|\n|# # # # # # # # # # # # # # # |\n@ # # # # # # # # # # # # # #   \n|# # # # # # # # # # # # # # # |\n| # # # # # # # # # # # # # # #|\n|# # # # # # # # # # # # # # # |`,`|    #    #    #         #     |\n|         #    #    #          |\n|    #    #    #    #    #     |\n@    #    #    #    #    #      \n|    #    #         #    #     |\n|    #    #    #    #    #     |\n|    #         #    #    #     |`,`|##############################|\n|##############################|\n|##############################|\n@                               \n|##############################|\n|##############################|\n|##############################|`,`|### ##########################|\n|## # ############### ## ######|\n|# ###  ######## ### ## # #####|\n@ ###### ###### ### ## ###      \n|########  ### ### ## #########|\n|########## # ### ## ##########|\n|###########              #####|`];$("#t").val(inputs[1]);</script
Expandir fragmento

Esta función acepta una sola cadena con nuevas líneas. La función divide la cadena en una matriz utilizando el ...operador y obtiene el índice de (x,y)coordenadas por (33 * y) + x.

La función se ejecuta de forma recursiva, probando diferentes movimientos posibles para cada espacio. Cuando encuentra un obstáculo, devuelve un valor falso, y cuando alcanza el espacio objetivo final, regresa true. (En el código de golf, esto truees creado por !console.log(...)).

Tenga en cuenta que este código no utiliza tiradas largas de movimientos de giro a la derecha, sino que las puntúa con movimientos rectos. Es decir, hace la segunda opción a continuación, no la primera:

\                       \
 \   (<= not this!)      -   (<= yes this!)
  \                       \

Esto parece ser legal, ya -que legalmente puede venir antes o después de un turno, entonces ¿por qué no ambos a la vez? Eso parece especialmente extraño al final, cuando el movimiento final es\ pero se muestra como @:

|  --#    #    #   ------#  -  |
| /  \    #    #  / #    \ / \ |
|/   #-   #    # /  #    #-   -|
     # \  #    #/   #    #     @
|    #  - # ----    #    #     |
|    #   \#/   #    #    #     |
|    #    -    #    #    #     |

Mi truco de golf desagradable favorito aquí es el abuso de argumento predeterminado con c=k=" ". Los argumentos (i,l,c=" ")dirían "use la cadena " "para csi fno se proporciona un tercer argumento". Sin embargo, al hacerlo c=k=" ", decimos "si cno se suministra, almacene " "en la variable globalk y luego almacene ese valor ctambién". Dado que la recursividad comienza con un solo argumento, ksiempre se inicializa en la primera llamada a la función.

Ligeramente no golfista:

// `i` - index in the string we're working on
// `l` - move character for this space (`/`, `\`, or `-`)
search = (i,l,c)=>{

  // not an open space; nip this recursive branch
  if(s[i]!=" "&&s[i]!="@") { return 0; }

  // we made it! the 130th space is (31,3)
  if(i==130) {
      s[i]="@";
      console.log(s.join(""));
      return true;
  }

  // fill in space with move character or a blank
  // (the space is only to blank out the initial `@`)
  s[i] = c || " ";

  // iterate through the 3 options and recursively explore the map
  return ['/','-','\\'].some((c,j)=>{
    --j;
    // if last move was sideways, and this is the opposite move, skip it
    if(l && j && j!=l) { return 0; }

    // recursively call search function on space pointed to by this move or the last move
    return search(i+33*(l||j)+1, j, c);
  })

  // if the `some` call is false (i.e. all options fail for this space)
  // then blank out this space and return false
  || !(s[i]=" ");

}
apsillers
fuente
@ vihan1086 Correcto, perdí totalmente esos espacios cuando jugaba al golf. D: Y cambiar de una matriz a una cadena dividida también es un buen cambio. Gracias. :) También hice algunos otros cambios (convirtiendo el personaje de movimiento actual en un tercer argumento en lugar de determinado dentro de la función, y almacenando " "en una variable) que redujo mi puntaje aún más bajo.
apsillers
7

C (programa completo), 249 247 235 bytes

Este es un programa completo que lee la entrada de un archivo y genera el resultado en stdout. El nombre del archivo se pasa como parámetro al programa.

char f[7][33];g(i,j,c){return(i<0|i>6|f[i][j]%32?0:j<31?c%45-2?g(i,j+1,c)||g(i+1,j+1,92)||g(i-1,j+1,47):g(i+c/30-2,j+1,c)||g(i+c/30-2,j+1,45):1)?f[i][j]=j?j-31?c:64:32:0;}main(int p,char**v){read(open(v[1],0),f,231);g(3,0,45);puts(f);}

Sin golf:

/* the field */
char f[7][33];

/* i - row
 * j - col
 * c - movement
 */
g(i,j,c)
{
    return
            /* if we're in bounds and not on an obstacle */
            (i >= 0 & i<7 & f[i][j] % 32 == 0 ?
                    /* if we haven't reached the end */
                    j < 31 ?
                            /* are we going straight ahead? */
                            c%45-2 ?
                                    /* try to go straight */
                                    g(i,j+1,c)
                                    /* try to turn right */
                                    || g(i+1,j+1,92)
                                    /* try to turn left */
                                    || g(i-1,j+1,47)
                            /* turning */
                            :
                                    /* try to keep turning */
                                    g(i+c/30-2,j+1,c)
                                    /* try to go straight */
                                    || g(i+c/30-2,j+1,45)
                    /* done */
                    :1 /* replace this with c==45 to better represent the last move being a turn */
            /* invalid move, fail */
            :0)
            /* add the correct movement to the field */
            ? f[i][j] = j ? j - 31 ? c : 64 : 32
            /* no path, much sads :( */
            :0;
}

main(int p,char*v[])
{
    /* read input file */
    read(open(v[1],0),f,231);

    /* calculate the path */
    g(3,0,45);

    /* print it out */
    puts(f);
}

Salida:

$ ./a.out test.inp
|   #####           #########  |
| ######  #          ###   #   |
|   # #  #  #  ####   #      --|
 ------------- ##----####   /  @
|#   #   #    \ /### \ ##  /   |
|##      ##    - #### \ # /#   |
|####           ##### #---##   |

$ ./a.out test2.inp
|# # # # #-# # # # # #-# # # # |
| # # # #/#\# # # # #/#\# # # #|
|# # # #/# #\# # # #/# #\# # # |
 -# # #/# # #\# # #/# # #\# #  @
|#\# #/# # # #\# #/# # # #\# #/|
| #\#/# # # # #\#/# # # # #\#/#|
|# #-# # # # # #-# # # # # #-# |

$ ./a.out test3.inp
|    #    #    #   ------#     |
|    -    #    #  / #    \     |
|   /#\   #    # /  #    #\    |
 --- # \  #    #/   #    # \   @
|    #  \ #    /    #    #  \ /|
|    #   \#   /#    #    #   - |
|    #    ---- #    #    #     |

$ ./a.out test4.inp
|##############################|
|##############################|
|##############################|
 ------------------------------@
|##############################|
|##############################|
|##############################|

$ ./a.out test5.inp
|###-##########################|
|##/#\############### ##-######|
|#/###--######## ### ##/#\#####|
 -######\###### ### ##/###-----@
|########--### ### ##/#########|
|##########\# ### ##/##########|
|###########--------      #####|
Cole Cameron
fuente
Parece que te perdiste el punto final en la primera prueba.
Reto Koradi
@RetoKoradi Es -seguido por un \, pero \está cubierto por el @. (Mi programa hace lo mismo.)
apsillers
1
@RetoKoradi Las iteraciones anteriores de esto manejaron mejor ese caso. Son +4 bytes. Noté que la solución de los apsillers se comportó de manera similar, así que opté por ahorrar espacio.
Cole Cameron
Veo. No me parece correcto, pero depende del OP decidir qué está permitido. Vi que dieron cierta libertad sobre cómo se representan los movimientos. Me hubiera gustado ver una definición clara y única desde el principio. Parecía un problema divertido, pero no es tan interesante con la ambigüedad.
Reto Koradi
3

Lisp común, 303 bytes

Me divertí mucho con este desafío, es la primera tarea de codegolf que hice. Básicamente, hay una función recursiva simple que intenta cada movimiento viable hasta llegar a la posición final.

Golfizado / Minificado

(let((s(open "i"))(n nil)(f(make-string 231)))(read-sequence f s)(labels((r(p s u d)(and(< 0 p 224)(find(aref f p)" @")(setf(aref f p)(cond((= 130 p)#\@)((or(unless d(r(- p 32)#\/ t n))(unless u(r(+ p 34)#\\ n t))(r(+ p(cond(u -32)(d 34)(t 1)))#\- n n))s)((return-from r)))))))(r 99 #\- n n)(princ f)))

Lee la entrada de un archivo i en el directorio de trabajo. Estoy bastante seguro de que todavía hay margen de mejora.

Código simple

(defun run-test (file)
  (let ((stream (open file)) ;;should use with-open-file for autoclose..
        (no nil) ;; alias for brevity
        (field (make-string 231)))
    (read-sequence field stream)
    (labels ((doit (pos sym going-up going-down)
               (and
                 (< 0 pos 224)
                 (find (aref field pos) " @")
                 (setf (aref field pos)
                       (cond
                         ((= 130 pos) #\@)
                         ((or
                            (unless going-down (doit (- pos 32) #\/ t no))
                            (unless going-up (doit (+ pos 34) #\\ no t))
                            (doit (+ pos (cond (going-up -32)
                                               (going-down 34)
                                               (t 1)))
                                  #\- no no))
                          sym)
                         ((return-from doit)))))))
      (doit 99 #\- no no)
      (princ field)
      nil)))

Salida de muestra

|   #####       --  #########  |
| ######  #    /  \  ###   # - |
|   # #  #  # /####\  #     / \|
--   -       / ##   \####  /   @
|#\ /#\  #  /    ### \ ## /    |
|##-   \ ##/     #### \ #/ #   |
|####   ---     ##### #-- ##   |

|  --#    #    #   --    #-    |
| /  \    #    #  / #\   / \   |
|/   #\   #    # /  # \ /#  \  |
-    # \  #    #/   #  - #   \ @
|    #  \ # ----    #    #    -|
|    #   \#/   #    #    #     |
|    #    -    #    #    #     |

|# #-# # # # # #-# # # # # #-# |
| #/#\# # # # #/#\# # # # #/#\#|
|#/# #\# # # #/# #\# # # #/# #\|
--# # #\# # #/# # #\# # #/# #  @
|# # # #\# #/# # # #\# #/# # # |
| # # # #\#/# # # # #\#/# # # #|
|# # # # #-# # # # # #-# # # # |
Florian Patzl
fuente
2

ActionScript 3, 364 bytes

Divido esto en dos funciones; uno para cambiar la matriz en una matriz de matrices, y uno recursivo para calcular la ruta de vuelo.

function m(f){for(var i=0;i<f.length;i++){f[i]=f[i].split("");}n(f,0,3,0);return f;}function n(f,x,y,m){var P=f[y][x],X=x+1,A=y-1,B=y,C=y+1,T=true,F=false,E='-';if (y<0||y>6||P=='#'||P=='|')return F;if (x==31){f[y][x]='@';return T;}if(m<0&&y>0){B=A;C=9;E='/';}else if(m>0&&y<6){A=9;B=C;E='\\';}if (n(f,X,B,0)||n(f,X,A,-1)||n(f,X,C,1)){f[y][x]=E;return T;return F;}

Versión sin golf en un programa con un campo de asteroides de muestra definido:

package
{
    import flash.display.Sprite;

    public class AsteroidNavigator extends Sprite
    {
        var field:Array;
        public function AsteroidNavigator()
        {
            field = [
"|   #####           #########  |",
"| ######  #          ###   #   |",
"|   # #  #  #  ####   #        |",
"@              ##    ####       ",
"|#   #   #       ###   ##      |",
"|##      ##      ####   #  #   |",
"|####           ##### #   ##   |"];
            m(field);
            printField();
        }

        function m(f){
            for(var i=0;i<f.length;i++){
                f[i]=f[i].split("");\
            }
            n(f,0,3,0);
            return f;
        }

        private function n(field,x,y,m) {
            var C = field[y][x];
            if (x > 31 || C == '#' || C == '|') {
                return false;
            }
            if (x == 31 && y == 3) {
                field[y][x] = '@';
                return true;
            }
            if (m == 0) {
                if (n(x+1, y, 0) || ((y>0) && n(x+1, y-1, -1)) || ((y<6) && n(x+1, y+1, 1))) {
                field[y][x] = '-';
                return true;
                }
            } else if ((m<0) && (y>0)) {
                if ((n(x+1, y-1, -1) || n(x+1, y-1, 0))) {
                    field[y][x] = '/';
                    return true;
                }
            } else if ((m>0) && (y<6)) {
                if ((n(x+1, y+1, 1) || n(x+1, y+1, 0))) {
                    field[y][x] = '\\';
                    return true;
                }
            }
            return false;
        }

        private function printField() {
            var sb = "";
            for each (var row:Array in field) {
                sb += row.join("") + "\n";
            }
            trace(sb);
        }
    }
}
Brian
fuente