Erfolgreich durch ein Asteroidenfeld navigieren

36

Einführung

Jeder weiß, dass die Möglichkeit, erfolgreich durch ein Asteroidenfeld zu navigieren, ungefähr 3.720 zu 1 beträgt. Trotz Ihrer Warnung ist Han Solo immer noch bereit, sein Glück zu versuchen.

Aus Angst um Ihr künstliches Leben, entscheiden Sie Code, in dem eigentümlichen Dialekt des Schiffs ( lesen: Ihre bevorzugten Code Golf Sprache ), ein Asteroiden Vermeidungsprogramm, welcher Weg zu nehmen in einem Asteroidenfeld ASCII - Labyrinth wird entscheiden.

Eingang

Der Millenium Falcon verfügt über ein Asteroidenfeld-Mapping-Programm, das ähnliche Daten liefert:

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

Die oberen Reihen befinden sich links vom Falken, die unteren Reihen rechts vom Falken und die Spalten repräsentieren, was sich vor dem Schiff befindet.

  • Jeder #ist ein Hindernis.
  • Jedes Feld ist ein leeres Feld, in das das Schiff fliegen kann.
  • Die Eingabe ist immer 7 Zeichen hoch. Dies ist die maximale Asteroidenkartierungsbreite.
  • Die Eingabe ist immer 32 Zeichen lang (30 für das Feld selbst und 2 für die Start- und Endbegrenzung). Dies ist die Obergrenze für die Asteroidenkartierung. Vertikale Balken |markieren den Anfang und das Ende des Mappings.
  • @ist der Falke. Es befindet sich immer in der mittleren Zeile (4. Zeile) und in der ersten Spalte der Eingabe.
  • Der in den vertikalen Balken in der letzten Spalte verbleibende Raum ist der Ort, an dem das Schiff ankommen muss. Es befindet sich immer in der mittleren Zeile (4. Zeile) und in der letzten Spalte der Eingabe.

Die Eingabe kann als mehrzeilige Zeichenfolge, als Array von Zeichenfolgen, aus STDIN oder Funktionsparametern oder aus einer Datei gelesen werden.

Mögliche Manöver

Sie werden von TIE-Fighters verfolgt, deshalb müssen Sie immer vorwärts gehen. Es gibt also drei Möglichkeiten, wie das Schiff bei jedem Schritt fliegen kann:

  • - Nach vorne

  • / Vorwärts und links abbiegen

  • \ Vorwärts und rechts abbiegen

Dies sind beispielsweise gültige Pfade:

@---

  --
 /  \ /
@    -

   -
  / \
 /   \
@     \

Wie Sie sehen, gibt es immer genau einen Zug pro Spalte. Der Falke ist ein Stück Müll, deshalb kann er keine gewaltsamen Wendungen machen. Was bedeutet, dass Bewegungen wie /\oder \/nicht erlaubt sind . Es muss mindestens ein reiner Stürmer -zwischen zwei entgegengesetzten Kurven sein. Auf der anderen Seite ist es möglich, mehrere Schritte hintereinander in eine Richtung zu drehen, wie oben gezeigt.

Der Falke stürzt ab, wenn ein Zug das Schiff an eine Stelle bringt, an der sich ein Hindernis befindet. Diese Bewegungen führen beispielsweise zu Abstürzen:

@-#

@
 \
  #

  #
 /
@

Beachten Sie, dass dies kein Absturz ist:

@-#
  \
   -

Ausgabe

Sie müssen dasselbe Asteroidenfeld ASCII mit einem gültigen Pfad bis zum Ende ausgeben. Der Falcon muss am Endpunkt statt am Startpunkt gedruckt werden.

Eine gültige Ausgabe für das zuvor angegebene Eingabebeispiel wäre beispielsweise:

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

Ihr Weg muss nur den Falken nicht zum Absturz bringen. Es muss nicht der kürzest mögliche Weg sein.

Sie können davon ausgehen, dass es immer mindestens einen möglichen Weg zum Ende geben wird.

Sie können nach STDOUT, in einer Datei oder in einem gleichwertigen Format ausgeben, solange das Asteroidenfeld genau wie in diesem Beitrag gedruckt wird (z. B. ist die Ausgabe einer Koordinatenliste für den Pfad ungültig).

Testfälle

  • Ein normales Asteroidenfeld

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

    Mögliche Ausgabe

    |   #####           #########  |
    | ######  #--------  ###   #   |
    |   # #  #/ #  ####\  #        |
     ---------      ##  \ #### ----@
    |#   #   #       ### \ ## /    |
    |##      ##      #### \ #/ #   |
    |####           ##### #-- ##   |
    
  • Hyperreguläres Asteroidenfeld

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

    Mögliche Ausgabe

    |# # # # # # # # # # # # # # # |
    | # # # # # # # # # # # # # # #|
    |# # # # # # # # # # # # # # # |
     -# #-# #-# #-# #-# #-# #-# #--@
    |#\#/#\#/#\#/#\#/#\#/#\#/#\#/# |
    | #-# #-# #-# #-# #-# #-# #-# #|
    |# # # # # # # # # # # # # # # |
    
  • Der Kern des Todessterns

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

    Mögliche Ausgabe

    |    #    #    #   --    #     |
    |  ---    #    #  / #\   -     |
    | /  #\   #    # /  # \ /#\    |
     -   # \  #    #/   #  - # ----@
    |    #  \ # ----    #    #     |
    |    #   \#/   #    #    #     |
    |    #    -    #    #    #     |
    
  • Todesstern Graben

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

    Ausgabe

    |##############################|
    |##############################|
    |##############################|
     ------------------------------@
    |##############################|
    |##############################|
    |##############################|
    
  • Asteroidenhöhle

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

    Mögliche Ausgabe

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

Wertung

R2D2 ist gerade mit dem Schwimmen in Sümpfen beschäftigt, daher müssen Sie die Steuerung des Falcon selbst programmieren, was mühsam ist. Daher gewinnt der kürzeste Code .

Tödlich
quelle
@ DJMcMayhem: Technisch ist die erste Zeile "Einführung";)
Alex A.
2
Ich verstehe irgendwie, wie es aussehen soll, basierend auf den Beispielen, aber die Kodierung der Züge ist für mich immer noch etwas verwirrend. Wenn Sie sich zum Beispiel das Beispiel "hyperregular" ansehen, mit Ausnahme des ersten / letzten Zuges, bewegen Sie sich immer diagonal. Dennoch hat es -in jeder Runde den Weg, der als "Vorwärtsbewegung" definiert ist. Die tatsächlichen Bewegungen sind jedoch immer zwei diagonale-links, gefolgt von zwei diagonale-rechts.
Reto Koradi
@RetoKoradi Ich kann verstehen, dass es nicht so offensichtlich ist, aber die Grundidee ist, dass Sie bei allen Bewegungen die Breite eines Zeichens nach rechts wandern. Der Pfad muss durchgehend sein, weshalb die vorherige / nächste Bewegung nach Rechts- und Linkskurven eine Zeile über / unter der vorherigen liegt.
Fatalize
@apsillers Beide sind gültig, wenn ich Sie richtig verstehe, sollte Ihre Antwort gut sein
Fatalize

Antworten:

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)

Runnable-Snippet:

<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

Diese Funktion akzeptiert einen einzelnen String mit Zeilenumbrüchen. Die Funktion teilt den String mithilfe des ...Operators in ein Array auf und erhält den Index für die (x,y)Koordinaten von (33 * y) + x.

Die Funktion wird rekursiv ausgeführt und testet verschiedene mögliche Bewegungen für jedes Feld. Wenn es auf ein Hindernis stößt, wird ein falscher Wert zurückgegeben, und wenn es das Endzielfeld erreicht, wird es zurückgegeben true. (Im Golfcode wird dies von trueerstellt !console.log(...).)

Beachten Sie, dass dieser Code keine langen Züge nach rechts verwendet, sondern sie mit geraden Zügen interpunktiert. Das heißt, es wird die zweite Option unten ausgeführt, nicht die erste:

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

Dies scheint legal zu sein, da -dies legal vor oder nach einer Wende erfolgen kann. Warum also nicht beide gleichzeitig? Das sieht am Ende besonders seltsam aus, wenn der letzte Zug \aber wie folgt angezeigt wird @:

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

Mein fieser Lieblingsgolfhack hier ist der Standardargumentmissbrauch c=k=" ". Die Argumente (i,l,c=" ")würden sagen , „die Zeichenfolge verwenden " "für , cwenn fnicht ein drittes Argument geliefert“. Allerdings , indem Sie c=k=" ", sagen wir , „wenn cnicht geliefert wird, zu speichern " "in den globalen Variablen kund dann in diesem Wert speichern cals auch“. Da die Rekursion mit nur einem Argument beginnt, kwird beim ersten Funktionsaufruf immer initialisiert.

Mild ungolfed:

// `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
quelle
@ vihan1086 Richtig, ich habe diese Plätze beim Golfspielen total verpasst. D: Und das Wechseln von einem Array zu einem geteilten String ist ebenfalls eine nette Abwechslung. Vielen Dank. :) Ich habe auch ein paar andere Änderungen vorgenommen (indem ich den aktuellen Zugcharakter zu einem dritten Argument gemacht habe, anstatt ihn in der Funktion zu bestimmen und " "in einer Variablen zu speichern ), die meine Punktzahl noch weiter gesenkt haben.
Apsillers
7

C (vollständiges Programm), 249 247 235 Bytes

Dies ist ein vollständiges Programm, das die Eingabe aus einer Datei liest und das Ergebnis an stdout ausgibt. Der Name der Datei wird als Parameter an das Programm übergeben.

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

Ungolfed:

/* 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);
}

Ausgabe:

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

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

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

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

$ ./a.out test5.inp
|###-##########################|
|##/#\############### ##-######|
|#/###--######## ### ##/#\#####|
 -######\###### ### ##/###-----@
|########--### ### ##/#########|
|##########\# ### ##/##########|
|###########--------      #####|
Cole Cameron
quelle
Sieht so aus, als hätten Sie im ersten Test den Endpunkt verpasst.
Reto Koradi
@RetoKoradi Es -folgt ein \, aber das \wird von der verdeckt @. (Mein Programm macht das gleiche.)
Apsillers
1
@RetoKoradi Frühere Iterationen dieses Artikels haben diesen Fall besser behandelt. Es sind +4 Bytes. Ich bemerkte, dass sich die Lösung von Apsillers ähnlich verhielt, also entschied ich mich, Platz zu sparen.
Cole Cameron
Aha. Es sieht für mich nicht richtig aus, aber es liegt an der OP zu entscheiden, was erlaubt ist. Ich habe gesehen, dass sie etwas Freiheit darüber gaben, wie die Bewegungen dargestellt werden. Ich hätte mir von Anfang an eine klare und eindeutige Definition gewünscht. Es sah nach einem lustigen Problem aus, ist aber bei weitem nicht so interessant mit der Mehrdeutigkeit.
Reto Koradi
3

Common Lisp, 303 Bytes

Ich hatte viel Spaß mit dieser Herausforderung, es ist die erste Codegolf-Aufgabe, die ich gemacht habe. Grundsätzlich gibt es eine einfache rekursive Funktion, die jede mögliche Bewegung versucht, bis die Endposition erreicht ist.

Golf / Minified

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

Liest Eingaben aus einer Datei i im Arbeitsverzeichnis. Ich bin mir ziemlich sicher, dass es noch Verbesserungspotenzial gibt.

Einfacher Code

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

Beispielausgabe

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

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

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

ActionScript 3, 364 Byte

Ich habe dies in zwei Funktionen aufgeteilt; eine, um das Array in ein Array von Arrays umzuwandeln, und eine rekursive, um die Flugbahn zu berechnen.

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

Ungolfed-Version in einem Programm mit einem Beispiel für ein Asteroidenfeld:

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
quelle