Ihre Aufgabe ist es, einen RoboZZle-Interpreter zu schreiben. Wenn Sie mit dem Spiel nicht vertraut sind, schauen Sie sich bitte das Video auf robozzle.com an oder lesen Sie meine Beschreibung unten.

Ein Roboter lebt auf einem rechteckigen Gitter aus rot, grün, blau oder schwarz gefärbten Quadraten. Schwarze Quadrate sind nicht zugänglich. Die anderen sind zugänglich und einige enthalten einen Stern. Das Ziel ist es, alle Sterne zu sammeln, ohne auf die schwarzen Quadrate zu treten oder von der Karte zu fallen. Der Roboter nimmt ein Quadrat ein und zeigt in eine bestimmte Richtung - links, rechts, oben oder unten. Es folgt montageähnlichen Anweisungen, die in den Unterprogrammen F1, F2, ..., F5 zusammengefasst sind. Eine Anweisung ist ein Paar aus einem Prädikat ("keine", "wenn auf rot", "wenn auf grün", "wenn auf blau") und einer Aktion ("vorwärts gehen", "links abbiegen", "rechts abbiegen"). "Malen Sie das aktuelle Quadrat rot", "Malen Sie es grün", "Malen Sie es blau", "Tun Sie nichts", "Rufen Sie F1", ..., "Rufen Sie F5"). Aufrufe von Unterprogrammen verwenden einen Stapel und können rekursiv sein. Genau wie bei der herkömmlichen Programmierung wird die Ausführung nach Abschluss der letzten Anweisung eines Unterprogramms an dem Punkt fortgesetzt, an dem das Unterprogramm aufgerufen wurde. Die Ausführung beginnt mit der ersten Anweisung von F1 und wird fortgesetzt, bis entweder der Roboter alle Felder mit Sternen besucht hat oder wenn der Roboter auf ein schwarzes Quadrat oder außerhalb der Karte tritt oder 1000 Anweisungen ausgeführt wurden (fehlgeschlagene Prädikate und Aktionen "Nichts tun") nicht zählen), oder es sind keine weiteren Anweisungen auszuführen (Stapelunterlauf).

Eingaben:

• a- eine 12x16-Zeichenmatrix (wie normalerweise in Ihrer Sprache dargestellt, z. B. eine Reihe von Zeichenfolgen), die eine Karte codiert - '#'für unzugängliche (schwarze) Quadrate, '*'für Quadrate mit einem Stern, '.'für den Rest

• c- eine 12x16-Zeichenmatrix, die die Farben der zugänglichen Quadrate beschreibt - 'R'(rot), 'G'(grün) oder 'B'(blau). Unzugängliche Quadrate werden durch einen beliebigen Buchstaben der drei dargestellt.

• yund x- die 0-basierte Zeile und Spalte des Roboters; a[y][x]ist garantiert zu sein'.'

• d- die Richtung der Roboter Ausrichtung 0 1 2 3für rechts, unten, links, oben, dh in Richtung (y,x+1), (y+1,x), (y,x-1),(y-1,x)

• f- eine einzelne Zeichenfolge, die verketteten Implementierungen von F1 ... F5. Jede Implementierung ist eine (möglicherweise leere) Folge von Prädikat-Aktions-Paaren (höchstens 10 Paare pro Unterprogramm), die mit a abgeschlossen sind '|'.

  • Prädikate: '_'keine, 'r'rot, 'g'grün, 'b'blau

  • Aktionen: 'F'vorwärts gehen, 'L'links 'R'abbiegen, rechts abbiegen, 'r'rot 'g'malen, grün 'b'malen, blau malen, '1'F1 anrufen, ..., '5'F5 anrufen, '_'nichts tun

Sie müssen Ihre Eingaben nicht wie oben angegeben benennen, aber ihre Werte müssen wie angegeben sein.

Ausgabe: 1(oder true) wenn der Roboter alle Sterne gemäß den Regeln sammelt, 0( false) andernfalls.

Beispiel :

a=["################","################","##*....*...*#.##","##.####.#####.##","##.####.#####.##","##.####*...*#.##","##.########.####","##*........*#.##","################","################","################","################"]
c=["RRRRRRRRRRRRRRRR","RRRRRRRRRRRRRRRR","RRRBBBBRGGGGRRRR","RRBRRRRGRRRRRRRR","RRBRRRRGRRRRRRRR","RRBRRRRRGGGBRRRR","RRBRRRRRRRRGRRRR","RRRBBBBGGGGBRBRR","RRRRRRRRRRRRRRRR","RRRRRRRRRRRRRRRR","RRRRRRRRRRRRRRRR","RRRRRRRRRRRRRRRR"]
y=2; x=6; d=2

// and then depending on "f":
f="_FrLg2_1|_FbLrR_2||||" // result:1
f="_FrRg2_1|_FbLrR_2||||" // result:0 (stepped on a black square)
f="_FrLrL_1|_FbLrR_2||||" // result:0 (1000-step limit exceeded)
f="_FrLg2__|________||||" // result:0 (stack underflow)

Ein weiteres Beispiel mit Anweisungen zum Malen:

a=["#***************","#*###*###*###*##","#*###*###*###*##","***#***#***#***#","***#***#***#***#","*###*###*###*###","***#***#***#***#","***#***#***#***#","***#***#***#***#","*###*###*###*###","*.*#***#***#***#","***#***#***#***#"]
c=["RGGGGGGGGGGGGGGG","RBRRRGRRRGRRRGRR","RBRRRGRRRGRRRGRR","RBRRGGGRGGGRGGGR","BRRRGGGRGGGRGGGR","BRRRGRRRGRRRGRRR","BRRRGGGRGGGRGGGR","RBRRGGGRGGGRGGGR","BRRRGGGRGGGRGGGR","BRRRGRRRGRRRGRRR","BGRRGGGRGGGRGGGR","RBRRGGGRGGGRGGGR"]
y=10; x=1; d=0
f="_2_R_R_1|_FgRgFgFg3rRr4b2_Fgb|_F_F_R|_2_L_r||"
// result:1

Um Ihren eigenen Test zu generieren, gehen Sie zu einem Puzzle aus der Liste auf robozzle.com , versuchen Sie es zu lösen (oder lösen Sie es nicht), drücken Sie F12 in Ihrem Browser und geben Sie die JS-Konsole ein:

r=robozzle;s=JSON.stringify;with(r.level)console.log('a='+s(Items)+'\nc='+s(Colors)+'\ny='+RobotRow+'\nx='+RobotCol+'\nd='+RobotDir+'\nf='+s(r.encodeSolution()))

und formatieren Sie das Ergebnis für Ihre Sprache neu.

Kürzeste Siege. Keine Lücken.

Prolog (SWI) , 574 Bytes

Z*A:-findall(X^Y-D,(nth0(Y,Z,O),nth0(X,O,C),plus(32,C,D)),L),list_to_assoc(L,A).
N^C^G^[P,I|R]^F^X^Y^D:-map_assoc(\=(74),G);N<1e3,get_assoc(X^Y,G,J),J>67,put_assoc(X^Y,G,78,H),T=N+1,((I\=95,(P=95;get_assoc(X^Y,C,P)))->(between(49,53,I),plus(48,M,I),nth1(M,F,Q),append(Q,R,S),T^C^H^S^F^X^Y^D;member(I,`RL`),E is(D-I//3)mod 4,T^C^H^R^F^X^Y^E;I=70,(D=0,U is X+1;D=1,V is Y+1;D=2,U is X-1;D=3,V is Y-1),(U=X;V=Y),T^C^H^R^F^U^V^D;I>97,put_assoc(X^Y,C,I,W),T^W^H^R^F^X^Y^D);N^C^H^R^F^X^Y^D).
A+C+F+L:-A*G,C*B,split_string(F,"|","",P),maplist(string_codes,P,[M|N]),0^B^G^M^[M|N]^L.

Probieren Sie es online aus!

Dies definiert ein Prädikat, das beim Aufruf erfolgreich ist, wenn alle Sterne erfolgreich gesammelt wurden, und ansonsten fehlschlägt. Das Prädikat nimmt die Argumente als solche : a+c+f+x^y^d.. aund cmuss eine Liste von Zeichenfolgen mit Backtick-Anführungszeichen sein, während fes sich um eine Zeichenfolge mit doppelten Anführungszeichen handeln muss.

Erläuterung

Dieses Programm enthält drei Prädikate */2, ^/2und +/2. Die */2in der ersten Zeile definierten Prädikate sind für einen Teil der Eingabeverarbeitung verantwortlich. Das ^/2Prädikat berechnet rekursiv, wie sich der Roboter Schritt für Schritt bewegt, und ist erfolgreich, wenn der Roboter legal alle Sterne sammelt und ansonsten fehlschlägt. Das +/2Prädikat ist das Hauptprädikat des Programms und bereitet die Eingabe für das ^/2Prädikat mit Hilfe des */2Prädikats vor. Beachten Sie, dass jedes dieser Prädikate technisch nur zwei Argumente akzeptiert, sich jedoch mithilfe von Operatoren und Mustervergleich so verhalten kann, als hätten sie mehr Argumente (ich diskutiere dieses Phänomen hier ausführlicher ).

*/2

Z*A:-findall(X^Y-D,(nth0(Y,Z,O),nth0(X,O,C),plus(32,C,D)),L),list_to_assoc(L,A).

Dieses Prädikat benötigt zwei Argumente. Die erste ist eine Liste von Listen mit Zeichencodes (so analysiert Prolog Backtick-Zeichenfolgen in Anführungszeichen). Die zweite ist eine assoziative Zuordnung von Punkten in der 12x16-Zuordnung (dargestellt als X^Y) zu 32 plus dem Zeichencode, der an diesem Punkt in der Liste der Listen von Zeichencodes gespeichert ist. Die 32 wird zu jedem der Zeichencodes hinzugefügt, so dass für die Farbmatrix die Großbuchstaben in Kleinbuchstaben umgewandelt werden.

Auf diese Weise wird eine Liste von Punktpaaren und die Zeichencodes an diesem Punkt mithilfe von generiert findall/3. Anschließend wird list_to_assoc/2die entsprechende assoziative Zuordnung von Punkten zum Zeichencode an diesem Punkt erstellt.

Das findall/3Prädikat ist ein eingebautes Prädikat, das als erstes Argument eine "Vorlage", als zweites Argument ein Ziel und als drittes Argument eine Liste verwendet. Das Prädikat füllt die Liste mit allen möglichen Werten der Vorlage, die zum Erfolg des Ziels führen. Aufgrund der Priorität des Operators wird die Vorlage, an die findall/3in übergeben */2wird, als analysiert (X^Y)-D. Der -Operator repräsentiert ein Paar von zwei Werten in Prolog, sodass die Vorlage die Position ( X^Y) des Punktes ( ) zusammen mit 32 plus dem Zeichencode ( D) des Punktes darstellt . Beachten Sie, dass das ^zur Darstellung des Punkts verwendete Element in keiner Weise mit dem ^/2Prädikat verbunden ist.

Betrachten wir das Ziel, das an das findall/3Prädikat übergeben wird.

nth0(Y,Z,O),nth0(X,O,C),plus(32,C,D) % Note that the O (oh) is not a 0 (zero)

Das Ziel enthält drei Prädikate, von denen jedes erfolgreich sein muss, damit das Ziel erfolgreich ist. Das nth0/3Prädikat, das zweimal verwendet wird, wird verwendet, um den Wert an einem bestimmten Index der Liste abzurufen (der 0in seinem Namen gibt an, dass er mit Null indiziert ist). Der erste Aufruf speichert die Ydritte Zeile der Zeichenmatrix in, Owährend der zweite Aufruf das dritte XZeichen in dieser Zeile speichert C. Das letzte Prädikat ist plus/3erfolgreich, wenn die ersten beiden Argumente das dritte Argument ergeben. Dies wird verwendet, um den Zeichencode im Paar 32 größer als den Zeichencode in der Zeichenmatrix zu machen, wodurch, wie oben angegeben, alle Großbuchstaben in Kleinbuchstaben umgewandelt werden.

Schließlich findall/3speichert alle der X^Y-DKombinationen , die ihr Ziel führen in der Liste um erfolgreich zu sein , Ldie die assoziative Karte von gebaut wird .

Mehr folgt bald...

JavaScript (ES6), 298 276 264 Byte

8 Bytes dank @ngn gespeichert

Nimmt Eingaben als (a,c,x,y,d,f), wo aund csind Arrays von Arrays von Zeichen. Rückgabe 0oder 1.

(a,c,x,y,d,f,k=1e3)=>(g=(F,p=0,s=f.split`|`[F],r=a[y])=>!k|!r|x&16||r[x]<'$'?2:/\*/.test(a)?(r[x]=o=0,(I=s[p+1],P=s[p])&&(P<'b'|P==c[y][x].toLowerCase()&&I!='_'&&k--?+I?o=g(I-1):I=='L'?d--:I=='R'?d++:I<'b'?y+=(d&=3,x-=~-d%2,2-d)%2:c[y][x]=I:0,o||g(F,p+2))):1)(0)&1

Testfälle

let f =

(a,c,x,y,d,f,k=1e3)=>(g=(F,p=0,s=f.split`|`[F],r=a[y])=>!k|!r|x&16||r[x]<'$'?2:/\*/.test(a)?(r[x]=o=0,(I=s[p+1],P=s[p])&&(P<'b'|P==c[y][x].toLowerCase()&&I!='_'&&k--?+I?o=g(I-1):I=='L'?d--:I=='R'?d++:I<'b'?y+=(d&=3,x-=~-d%2,2-d)%2:c[y][x]=I:0,o||g(F,p+2))):1)(0)&1

getA = _ => [
  "################",
  "################",
  "##*....*...*#.##",
  "##.####.#####.##",
  "##.####.#####.##",
  "##.####*...*#.##",
  "##.########.####",
  "##*........*#.##",
  "################",
  "################",
  "################",
  "################"
].map(s => [...s]);

getC = _ => [
  "RRRRRRRRRRRRRRRR",
  "RRRRRRRRRRRRRRRR",
  "RRRBBBBRGGGGRRRR",
  "RRBRRRRGRRRRRRRR",
  "RRBRRRRGRRRRRRRR",
  "RRBRRRRRGGGBRRRR",
  "RRBRRRRRRRRGRRRR",
  "RRRBBBBGGGGBRBRR",
  "RRRRRRRRRRRRRRRR",
  "RRRRRRRRRRRRRRRR",
  "RRRRRRRRRRRRRRRR",
  "RRRRRRRRRRRRRRRR"
].map(s => [...s]);

y=2; x=6; d=2;

[
  "_FrLg2_1|_FbLrR_2||||", // result:1
  "_FrRg2_1|_FbLrR_2||||", // result:0 (stepped on a black square)
  "_FrLrL_1|_FbLrR_2||||", // result:0 (1000-step limit exceeded)
  "_FrLg2__|________||||"  // result:0 (stack underflow)
]
.forEach(code => console.log('Example #1', code, '-->', f(getA(), getC(), x, y, d, code)));

getA = _ => [
  "#***************",
  "#*###*###*###*##",
  "#*###*###*###*##",
  "***#***#***#***#",
  "***#***#***#***#",
  "*###*###*###*###",
  "***#***#***#***#",
  "***#***#***#***#",
  "***#***#***#***#",
  "*###*###*###*###",
  "*.*#***#***#***#",
  "***#***#***#***#"
].map(s => [...s]);

getC = _ => [
  "RGGGGGGGGGGGGGGG",
  "RBRRRGRRRGRRRGRR",
  "RBRRRGRRRGRRRGRR",
  "RBRRGGGRGGGRGGGR",
  "BRRRGGGRGGGRGGGR",
  "BRRRGRRRGRRRGRRR",
  "BRRRGGGRGGGRGGGR",
  "RBRRGGGRGGGRGGGR",
  "BRRRGGGRGGGRGGGR",
  "BRRRGRRRGRRRGRRR",
  "BGRRGGGRGGGRGGGR",
  "RBRRGGGRGGGRGGGR"
].map(s => [...s]);

y=10; x=1; d=0;

[
  "_2_R_R_1|_FgRgFgFg3rRr4b2_Fgb|_F_F_R|_2_L_r||" // result:1
]
.forEach(code => console.log('Example #2', code, '-->', f(getA(), getC(), x, y, d, code)));

Kommentiert

(                                           // main function taking:
  a, c, x, y, d, f,                         //   - input variables
  k = 1e3                                   //   - k = instruction counter
) => (                                      //
  g = (                                     // g = recursive execution function, taking:
    F,                                      //   - F = subroutine id
    p = 0,                                  //   - p = instruction pointer
    s = f.split`|`[F],                      //   - s = instruction string
    r = a[y]                                //   - r = current row in a[]
  ) =>                                      //
    !k |                                    // if we've executed 1000 instructions
    !r | x & 16 ||                          // or we've felt out of the map
    r[x] < '$' ?                            // or we've reached a black square:
      2                                     //   exit with error code 2
    :                                       // else:
      /\*/.test(a) ? (                      //   if there are still some stars:
        r[x] = o = 0,                       //     mark the current cell as visited
        (I = s[p + 1], P = s[p]) &&         //     I = instruction, P = predicate
        (                                   //     if P is defined:
          P < 'b' |                         //       if the predicate is '_'
          P == c[y][x].toLowerCase()        //       or it matches the color of the cell
          && I != '_'                       //       and the instruction is not '_',
          && k-- ?                          //       then decrement k and:
            +I ?                            //         if I is '1' ... '5':
              o = g(I - 1)                  //           process call to subroutine
            :                               //         else:
              I == 'L' ?                    //           if I is 'L':
                d--                         //             turn left
              :                             //           else:
                I == 'R' ?                  //             if I is 'R':
                  d++                       //               turn right
                :                           //             else:
                  I < 'b' ? (               //               if I is not a color:
                    y += (                  //                 I must be 'F',
                      d &= 3,               //                 so make the bot advance
                      x -= ~-d % 2,         //                 by updating x
                      2 - d                 //                 and y
                    ) % 2                   //
                  ) :                       //               else:
                    c[y][x] = I             //                 paint the current cell
          :                                 //       else:
            0,                              //         do nothing
          o ||                              //       provided that o is equal to 0,
          g(F, p + 2)                       //       go on with the next instruction
        )                                   //     end of instruction execution
      ) :                                   //   else:
        1                                   //     success: return 1
  )(0) & 1                                  // initial call to the subroutine F1

APL (Dyalog Classic) , 236 233 Byte

-3 danke an Erik den Outgolfer

Nachdem ich den Bonus verschenkt habe, veröffentliche ich eine Beispiellösung für meine eigene Herausforderung. Hier gibt es Raum für Verbesserungen - Sie können gerne weiter kopieren und Golf spielen.

a c r d f←⎕⋄c←819⌶c⋄F←0,('|'=¯1⌽f)/⍳≢f⋄t←n←0
{~(⊂r)∊⍳⍴a:0⋄'#'=r⌷a:0⋄p q←2↑f↓⍨⊃⌽t⋄(_←p≡'|')∧×≢t:0⋄_:∇t↓←¯1⋄(⊃⌽t)+←2⋄~p∊'_',r⌷c:∇0⋄n+←1⋄n>999:0⋄(r⌷a)←'.'⋄~'*'∊a:1⋄r+←(q≡'F')×11 9○0j1*d⋄d+←4|'.R.L'⍳q⋄q∊'rgb':∇(r⌷c)←q⋄q∊⎕d:∇t,←F[⍎q]⋄∇0}0

Probieren Sie es online aus!

Gleich wie oben, erweitert mit Kommentaren:

⎕io←0                   ⍝ 0-based indices (not counted in the score)
a c r d f←⎕             ⍝ decompose eval'ed input (⎕) into variables
c←819⌶c                 ⍝ make c lowercase
F←0,('|'=¯1⌽f)/⍳≢f      ⍝ split f at the '|'-s
t←n←0                   ⍝ t:stack, n:step counter
{                       ⍝ lambda
  ~(⊂r)∊⍳⍴a:0           ⍝ if the robot is off the map, return 0
  '#'=r⌷a:0             ⍝ if the robot is on a wall, return 0
  p q←2↑f↓⍨⊃⌽t          ⍝ current instruction - p:predicate, q:action
  (_←p≡'|')∧1≥≢t:0      ⍝ if at end of func and stack is empty, return 0
  _:∇t↓←¯1              ⍝ if at end of func, pop from stack and recurse
  (⊃⌽t)+←2              ⍝ increment program counter (top of stack)
  ~p∊'_',r⌷c:∇0         ⍝ if predicate doesn't match cell colour, recurse
  n+←1⋄n>999:0          ⍝ if too meany steps, return 0
  (r⌷a)←'.'             ⍝ consume star
  ~'*'∊a:1              ⍝ if no more stars left, return 1
  r+←(q≡'F')×11 9○0j1*d ⍝ if action is F, move forward
  d+←4|'.R.L'⍳q         ⍝ if action is L or R, turn left or right
  q∊'rgb':∇(r⌷c)←q      ⍝ if action is paint (r,g,b), do it
  q∊⎕d:∇t,←F[⍎q]        ⍝ if action is F1...F5, push on stack and recurse
  ∇0                    ⍝ action is nop (_), recurse
}0                      ⍝ call the lambda (argument will be ignored)