RoboZZle interpreter

Question

Your task is to write a RoboZZle interpreter. If you're not familiar with the game, please watch the video at robozzle.com or read my description below.

A robot lives on a rectangular grid of squares coloured red, green, blue, or black. Black squares are inaccessible. The others are accessible and some of them contain a star. The goal is to collect all the stars without stepping on the black squares or falling off the map. The robot occupies one square and faces a particular direction - left, right, up, or down. It follows assembly-like instructions grouped into subroutines F1,F2,...,F5. An instruction is a pair of a predicate ("none", "if on red", "if on green", "if on blue") and an action ("go forward", "turn left", "turn right", "paint the current square red", "paint it green", "paint it blue", "do nothing", "call F1", ..., "call F5"). Calls to subroutines use a stack and can be recursive. Just like in conventional programming, after the last instruction of a subroutine is completed, execution carries on from the point where the subroutine was called. Execution begins from the first instruction of F1 and continues until either the robot has visited all squares with stars, or when the robot steps on a black square or outside the map, or 1000 instructions have been executed (failed predicates and "do nothing" actions don't count), or there are no more instructions to execute (stack underflow).

Inputs:

• a - a 12x16 character matrix (as usually represented in your language, e.g. array of strings) that encodes a map - '#' for inaccessible (black) squares, '*' for squares with a star, '.' for the rest

• c - a 12x16 character matrix describing the colours of accessible squares - 'R'(red), 'G'(green), or 'B'(blue). Inaccessible squares will be represented by an arbitrary letter from the three.

• y and x - the robot's 0-based row and column; a[y][x] is guaranteed to be '.'

• d - the direction the robot is facing: 0 1 2 3 for right, down, left, up, i.e. towards (y,x+1),(y+1,x),(y,x-1),(y-1,x)

• f - a single string, the concatenated implementations of F1...F5. Each implementation is a (possibly empty) sequence of predicate-action pairs (at most 10 pairs per subroutine), terminated with a '|'.

  • predicates: '_' none, 'r' red, 'g' green, 'b' blue

  • actions: 'F' go forward, 'L' turn left, 'R' turn right, 'r' paint red, 'g' paint green, 'b' paint blue, '1' call F1, ..., '5' call F5, '_' do nothing

You don't have to name you inputs like the above, but their values must be as specified.

Output: 1 (or true) if the robot collects all stars according to the rules, 0 (false) otherwise.

Example:

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)

Another example, involving "paint" instructions:

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

To generate your own test, go to a puzzle from the list at robozzle.com, try to solve it (or not solve it), press F12 in your browser, type in the JS console:

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

and reformat the result for your language.

Shortest wins. No loopholes.

Answer 1

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.

Try it online!

This defines a predicate that when called succeeds if the all the stars are successfully collected and fails otherwise. The predicate takes the arguments as such: a+c+f+x^y^d.. a and c must be lists of backtick quoted strings, while f must be a double quoted string.

Explanation

This program contains three predicates, */2, ^/2, and +/2. The */2 predicates which is defined on the first line is responsible for part of the input processing. The ^/2 predicate recursively calculates how the robot moves step by step and succeeds if the robot legally collects all the stars and fails otherwise. The +/2 predicate is the main predicate of the program and prepares the input for the ^/2 predicate with some help from the */2 predicate. Note that each of these predicates technically takes only two arguments but using operators and pattern matching they can behave as if they had more arguments (I discuss this phenomenon more in depth here).

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

This predicate takes two arguments. The first is a list of lists of character codes (this is how Prolog parses backtick quoted strings). The second is a associative map from points in the 12x16 map (represented as X^Y) to 32 plus the character code stored at that point in the list of lists of character codes. The 32 is added to each of the character codes so that for the color matrix it will turn the uppercase color characters into lowercase color characters.

The way it does this is generates a list of pairs of points and the character codes at that point using findall/3. It then uses list_to_assoc/2 to create the corresponding associative map from points to the character code at that point.

The findall/3 predicate is a builtin takes a "template" as its first argument, a goal as its second argument and a list as its third argument. The predicate fills the list with all the possible values of the template that cause the goal to succeed. Due to operator precedence, the template that is passed to findall/3 in */2 is parsed as (X^Y)-D. The - operator represents a pair of two values in Prolog so the template represents the point's location (X^Y) paired with 32 plus the point's character code (D). Note that the ^ used in representing the point is in no way connected to the ^/2 predicate.

Let us consider the goal that is passed to the findall/3 predicate.

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

The goal contains three predicates each of which need to succeed for the goal to succeed. The nth0/3 predicate which is used twice is used to get the value at a particular index of the list (the 0 in its name indicates it is zero indexed). The first call to it stores the Yth row of the character matrix in O while the second call stores the Xth character in that row in C. The final predicate plus/3 succeeds if its first two arguments sum to its third argument. This is used to make the character code in the pair is 32 greater than the character code in the character matrix which as stated above will turn all uppercase letters into lowercase letters.

Finally findall/3 stores all of the X^Y-D combinations that cause its goal to succeed in the list L which the associative map is built from.

More Coming Soon...

Answer 2

JavaScript (ES6), 298 276 264 bytes

Saved 8 bytes thanks to @ngn

Takes input as (a,c,x,y,d,f), where a and c are arrays of arrays of characters. Returns 0 or 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

Test cases

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

Commented

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

Answer 3

APL (Dyalog Classic), 236 233 bytes

-3 thanks to Erik the Outgolfer

Now that I've given away the bonus, I'm posting a sample solution to my own challenge. There's room for improvement here - feel free to copy and golf further.

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

Try it online!

Same as the above, expanded with comments:

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