Su tarea es escribir un intérprete RoboZZle. Si no está familiarizado con el juego, mire el video en robozzle.com o lea mi descripción a continuación.

Un robot vive en una cuadrícula rectangular de cuadrados de color rojo, verde, azul o negro. Los cuadrados negros son inaccesibles. Los otros son accesibles y algunos contienen una estrella. El objetivo es recoger todas las estrellas sin pisar los cuadrados negros o caerse del mapa. El robot ocupa un cuadrado y se enfrenta a una dirección particular: izquierda, derecha, arriba o abajo. Sigue las instrucciones de ensamblaje agrupadas en las subrutinas F1, F2, ..., F5. Una instrucción es un par de predicados ("ninguno", "si está en rojo", "si está en verde", "si está en azul") y una acción ("ir hacia adelante", "girar a la izquierda", "girar a la derecha", "pintar el cuadrado actual de rojo", "pintarlo de verde", "pintar de azul", "no hacer nada", "llamar a F1", ..., "llamar a F5"). Las llamadas a subrutinas usan una pila y pueden ser recursivas. Al igual que en la programación convencional, después de completar la última instrucción de una subrutina, la ejecución continúa desde el punto donde se llamó a la subrutina. La ejecución comienza desde la primera instrucción de F1 y continúa hasta que el robot ha visitado todos los cuadrados con estrellas, o cuando el robot pisa un cuadrado negro o fuera del mapa, o se han ejecutado 1000 instrucciones (predicados fallidos y acciones de "no hacer nada" no cuenta), o no hay más instrucciones para ejecutar (flujo inferior de la pila).

Entradas:

• a- una matriz de 12x16 caracteres (como generalmente se representa en su idioma, por ejemplo, una serie de cadenas) que codifica un mapa - '#'para cuadrados inaccesibles (negros), '*'para cuadrados con una estrella, '.'para el resto

• c- una matriz de 12x16 caracteres que describe los colores de los cuadrados accesibles: 'R'(rojo), 'G'(verde) o 'B'(azul). Los cuadrados inaccesibles serán representados por una letra arbitraria de los tres.

• yy x- la fila y columna basadas en 0 del robot; a[y][x]está garantizado para ser'.'

• d- la dirección que el robot se Orientación: 0 1 2 3para la derecha, abajo, izquierda, arriba, es decir hacia (y,x+1), (y+1,x), (y,x-1),(y-1,x)

• f- una sola cadena, las implementaciones concatenadas de F1 ... F5. Cada implementación es una secuencia (posiblemente vacía) de pares de predicado-acción (como máximo 10 pares por subrutina), terminada con a '|'.

  • predicados: '_'ninguno, 'r'rojo, 'g'verde, 'b'azul

  • acciones: 'F'avanzar, 'L'girar a la izquierda, 'R'girar a la derecha, 'r'pintar de rojo, 'g'pintar de verde, 'b'pintar de azul, '1'llamar a F1, ..., '5'llamar a F5, '_'no hacer nada

No tiene que nombrar sus entradas como las anteriores, pero sus valores deben ser los especificados.

Salida: 1(o true) si el robot recoge todas las estrellas de acuerdo con las reglas, 0( false) de lo contrario.

Ejemplo :

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)

Otro ejemplo , que implica instrucciones de "pintura":

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

Para generar su propia prueba, vaya a un rompecabezas de la lista en robozzle.com , intente resolverlo (o no resolverlo), presione F12 en su navegador, escriba la consola JS:

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

y reformatee el resultado para su idioma.

Las victorias más cortas. No hay escapatorias.

Prólogo (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.

Pruébalo en línea!

Esto define un predicado que cuando se llama tiene éxito si todas las estrellas se recogen con éxito y falla de lo contrario. El predicado toma los argumentos tales como: a+c+f+x^y^d.. ay cdebe ser una lista de cadenas entre comillas con comillas, mientras que fdebe ser una cadena entre comillas dobles.

Explicación

Este programa contiene tres predicados, */2, ^/2, y +/2. Los */2predicados que se definen en la primera línea son responsables de parte del procesamiento de entrada. El ^/2predicado calcula recursivamente cómo el robot se mueve paso a paso y tiene éxito si el robot recoge legalmente todas las estrellas y falla de otra manera. El +/2predicado es el predicado principal del programa y prepara la entrada para el ^/2predicado con alguna ayuda del */2predicado. Tenga en cuenta que cada uno de estos predicados técnicamente solo toma dos argumentos, pero al usar operadores y la coincidencia de patrones pueden comportarse como si tuvieran más argumentos (discuto este fenómeno más en profundidad aquí ).

*/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).

Este predicado toma dos argumentos. La primera es una lista de listas de códigos de caracteres (así es como Prolog analiza las cadenas entre comillas con comillas). El segundo es un mapa asociativo de puntos en el mapa de 12x16 (representado como X^Y) a 32 más el código de caracteres almacenado en ese punto en la lista de listas de códigos de caracteres. El 32 se agrega a cada uno de los códigos de caracteres para que para la matriz de color convierta los caracteres de color en mayúsculas en caracteres de color en minúsculas.

La forma en que lo hace es generar una lista de pares de puntos y los códigos de caracteres en ese punto usando findall/3. Luego se usa list_to_assoc/2para crear el mapa asociativo correspondiente de los puntos al código de caracteres en ese punto.

El findall/3predicado es un constructor que toma una "plantilla" como primer argumento, una meta como segundo argumento y una lista como tercer argumento. El predicado llena la lista con todos los valores posibles de la plantilla que hacen que el objetivo sea exitoso. Debido a la precedencia de operadores, la plantilla que se pasa findall/3en el */2que se analiza como (X^Y)-D. El -operador representa un par de dos valores en Prolog, por lo que la plantilla representa la ubicación del punto ( X^Y) emparejado con 32 más el código de caracteres del punto ( D). Tenga en cuenta que el ^utilizado para representar el punto no está conectado de ninguna manera con el ^/2predicado.

Consideremos el objetivo que se pasa al findall/3predicado.

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

El objetivo contiene tres predicados, cada uno de los cuales debe tener éxito para que el objetivo tenga éxito. El nth0/3predicado que se usa dos veces se usa para obtener el valor en un índice particular de la lista ( 0en su nombre indica que está indexado a cero). La primera llamada almacena la Yfila th de la matriz de caracteres Omientras que la segunda llamada almacena el Xcarácter th en esa fila C. El predicado final plus/3tiene éxito si sus dos primeros argumentos suman su tercer argumento. Esto se usa para hacer que el código de caracteres en el par sea 32 mayor que el código de caracteres en la matriz de caracteres que, como se indicó anteriormente, convertirá todas las letras mayúsculas en minúsculas.

Finalmente findall/3almacena todas las X^Y-Dcombinaciones que hacen que su objetivo Ltenga éxito en la lista a partir de la cual se construye el mapa asociativo.

Más muy pronto...

JavaScript (ES6), 298 276 264 bytes

Guardado 8 bytes gracias a @ngn

Toma entrada como (a,c,x,y,d,f), dónde ay cson matrices de matrices de caracteres. Devoluciones 0o 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

Casos de prueba

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

Comentado

(                                           // 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 bytes

-3 gracias a Erik the Outgolfer

Ahora que he regalado el bono, estoy publicando una solución de muestra para mi propio desafío. Aquí hay margen de mejora: siéntase libre de copiar y jugar más golf.

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

Pruébalo en línea!

Igual que el anterior, ampliado con comentarios:

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