Robert Eisele
Engineer, Systems Architect and DBA

Codingame: CGFunge interpreter

Original Problem

Goal

CGFunge is a 2-dimensional, positional programming language. This means that execution of a CGFunge program follows a designated pattern on a grid of ASCII characters. Each command in the language is a single character. The most basic commands involve flow control:

'>' - Continue to the right
'<' - Continue to the left
'^' - Continue up
'v' - Continue down
'S' - Skip the next character and continue with the subsequent character
'E' - End the program immediately

Execution always starts on the first character of the first line and proceeds to the right. Spaces are ignored. So, for example, the following are equivalent:

11+E


vE<
1 +
>1^


SE S+1<

The execution of the program entirely revolves around a stack consisting only of integers in the range [0 - 255]. Any digit encountered (0 - 9) is pushed onto the stack. Arithmetic operators ('+', '-', '*') pop two operands from the stack and push the result onto the stack. For subtraction, the top element on the stack is subtracted from the second element on the stack. So, for example, the program "52 - E" would leave the value 3 on the stack.

The following commands perform other basic stack manipulation tasks:

'P' - Pop the top value
'X' - Switch the order of the top two stack values
'D' - Push a duplicate of the top value onto the stack

The quotation mark character ('"') toggles "string mode". When in string mode, the ASCII codes for all characters encountered are pushed onto the stack.

The following commands perform stack-based logical flow control:

'_' - Pop the top value from the stack. If it is 0, continue to the right. Otherwise, go left.
'|' - Pop the top value from the stack. If it is 0, continue down. Otherwise, go up.

Output is performed with the following commands:

'I' - Pop the top integer from the stack and print it to stdout.
'C' - Pop the top integer from the stack and interpret it as an ASCII code, printing the corresponding character to stdout.
Input
Line 1: An integer N indicating the number of lines in the program
Next N lines: One line per program input
Output
The output of the properly interpreted program
Constraints
1 ≤ N ≤ 10

Solution

The crucial part for this problem is a function which modifies the state by reading the current command. The state is represented by the stack, the position and the direction. Following the given instructions we can come up with the following implementation:

function exec(cmd) {
    
    if (inString) {
       if (cmd === '"')
          inString = !inString;
       else
          stack.push(cmd.charCodeAt(0));
       return;   
    }

   switch (cmd) {
       
    case '"':
        inString = !inString;
        break;

    // continue right       
    case '>':
        stepX=1
        stepY=0
        break;
    
    // continue left
    case '<':
        stepX=-1;
        stepY=0;
        break;
    
    // continue up
    case '^':
        stepX=0;
        stepY=-1;
        break;
    
    // continue down
    case 'v':
        stepX=0;
        stepY=1;
        break;
    
    // skip next character
    case 'S':
        gridX+= stepX;
        gridY+= stepY;
        break;

    // Switch top elements
    case 'X':
        var a = stack.pop();
        var b = stack.pop();
        stack.push(a);
        stack.push(b);
        break;
    
    // Pop top element
    case 'P':
        stack.pop();
        break;
        
    case 'D':
        stack.push(stack[stack.length - 1]);
        break;
    
    case '+':
    case '*':
    case '-':
        var b = stack.pop();
        var a = stack.pop();
        if (cmd === '+') stack.push(a + b);
        if (cmd === '*') stack.push(a * b);
        if (cmd === '-') stack.push(a - b);
        break;
        
    case '_':
        var a = stack.pop();
        if (0 === a) {stepY=0; stepX=1}
        else {stepY=0; stepX=-1}
        break;
    
    case '|':
        var a = stack.pop();
        if (0 === a) {stepY=1; stepX=0}
        else {stepY=-1; stepX=0}
        break;
    
    case 'I':
        output+= stack.pop();
        break;
        
    case 'C':
        output+= String.fromCharCode(stack.pop());
        break;
       
    case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': 
            stack.push(cmd | 0);
   }
}

That was pretty straightforward. Given this function all we need to do is setting up the initial state, reading in the grid and executing the given program step by step:

var stack = [];
var output = "";
var inString = false;

var gridX = 0;
var gridY = 0;

var stepX = 1;
var stepY = 0;

var grid = [];
var N = parseInt(readline());
for (var i = 0; i < N; i++) {
    grid.push(readline());
}

for (;;) {
    var cur = grid[gridY][gridX];
    if (cur === 'E') {
      print(output);
      break;   
    }    

    exec(cur);

    gridX+= stepX;
    gridY+= stepY;
}

« Back to problem overview