UVA: 10033 Programming Challenges (Skiena & Revilla) Volume-1

UVA:10033:Interpreter

Background- This problem emulates the binary execution with custom processor. This problem gives a fare idea about how the code gets executed in RAM and assembly interpretation. For more about this problem visit  UVA:10033:Interpreter. A very obvious implementation is given below which has 0.008 run time on uva. The only optimization I was looking was around N mod 1000 but couldn't get anything to replace that.

C++ Implementation -

#include <iostream>
#include <stdio.h>
#include <iterator> 
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <stack>
#include <string.h>
using namespace std;
typedef unsigned short ushort;
ushort RAM[1000];
ushort REG[10]; 
stringstream oss(stringstream::in | stringstream::out);
#define clear_register() memset(REG,0, 20);
#define init_ram() memset(RAM , 0, 2000);
#define INS(i)  ((RAM[i]/100)%10)
#define ARG1(i) ((RAM[i]/10)%10)
#define ARG2(i) ((RAM[i])%10)

void load_ram() {
    ushort pc = 0;
    string statement("");
    cin >> noskipws;
    getline(cin, statement);
    while(statement.size() < 3)
        getline(cin, statement);
    while(cin.eof() == false) {
        RAM[pc] = (statement[0]-48)*100 + (statement[1]-48) *10 + (statement[2]-48);
        pc++;
        getline(cin, statement);
        if(statement.size() < 3)
            break;
    }
}

void print_ram() {
    for(ushort i = 0; i < 1000; i++) {
        cout << RAM[i] << endl;
    }
}

/* 100 means halt
   2dn means set register d to n (between 0 and 9)
   3dn means add n to register d
   4dn means multiply register d by n
   5ds means set register d to the value of register s
   6ds means add the value of register s to register d
   7ds means multiply register d by the value of register s
   8da means set register d to the value in RAM whose address is in register a
   9sa means set the value in RAM whose address is in register a to the value of register s
   0ds means goto the location in register d unless register s contains 0
   */

ushort execute ( ushort pc) {
    ushort counter = 0;
    while( true ) {
        switch(INS(pc)) {
            case 0:
                if(REG[ARG2(pc)] != 0) { 
                    pc = REG[ARG1(pc)];
                } else {
                    pc++;    
                }
                counter += 1;
                break;
            case 1:
                counter +=1;
                goto DONE;
                break;
            case 2:
                REG[ARG1(pc)] = ARG2(pc);
                pc++;
                counter += 1;
                break;
            case 3:
                REG[ARG1(pc)] = (REG[ARG1(pc)] + ARG2(pc)) % 1000;
                pc++;
                counter += 1;
                break;
            case 4:
                REG[ARG1(pc)] = (REG[ARG1(pc)] * ARG2(pc)) % 1000;
                pc++;
                counter += 1;
                break;
            case 5:
                REG[ARG1(pc)] = REG[ARG2(pc)];
                pc++;
                counter += 1;
                break;
            case 6:
                REG[ARG1(pc)] = (REG[ARG1(pc)] + REG[ARG2(pc)]) % 1000;
                pc++;
                counter += 1;
                break;
            case 7:
                REG[ARG1(pc)] = (REG[ARG1(pc)] * REG[ARG2(pc)]) % 1000;
                pc++;
                counter += 1;
                break;
            case 8:
                REG[ARG1(pc)] = RAM[REG[ARG2(pc)]];
                pc++;
                counter += 1;
                break;
            case 9:
                RAM[REG[ARG2(pc)]] = REG[ARG1(pc)];
                pc++;
                counter += 1;
                break;
            default:
                break;
        }
        pc %= 1000;
    }
DONE:
    return counter;
}

/* main
 *  * */
int main() {
    bool exit = false;
    long no_of_programmes = 0;
    cin >> no_of_programmes;
    cin.ignore(); // changeLine
    while ( no_of_programmes > 0 ) {
        clear_register();
        init_ram();
        load_ram();
        //print_ram();
        cout << execute(0) <<endl;
        if(no_of_programmes > 1)
            cout << endl;
        no_of_programmes--;
    }
    return 0;
}

Afterthoughts-

1. My second implementation is trying to load RAM with the maximum number of programs possible but unfortunately judges test set assumes that each program is mutually executed in RAM. It was disappointment that we can not submit this optimization because of this. 

2. It was expected to clear the RAM every time new program is executed because UVA test program is trying to READ and WRITE the RAM address outside the program boundary, so again you can escape this step.   

Try this problem and let me know if it can optimized further -