6
\$\begingroup\$

I have posted here my working and accepted solution to the intepreter programming challenge (detailed here) for your review. The challenge is as follows:

A certain computer has 10 registers and 1000 words of RAM. Each register or RAM location holds a 3-digit integer between 0 and 999. Instructions are encoded as 3-digit integers and stored in RAM. The encodings are as follows:

  • 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

All registers initially contain 000. The initial content of the RAM is read from standard input. The first instruction to be executed is at RAM address 0. All results are reduced modulo 1000.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The input to your program consists of up to 1000 3-digit unsigned integers, representing the contents of consecutive RAM locations starting at 0. Unspecified RAM locations are initialized to 000.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

The output from your program is a single integer: the number of instructions executed up to and including the halt instruction. You may assume that the program does halt.

SampleInput

1
299
492
495
399
492
495
399
283
279
689
078
100
000
000
000

SampleOutput

16

The program recognizes the required commands:

    #include <iostream>
    #include <vector>
    #include <sstream>
    #include <fstream>

    //platform specific code. 
    #ifdef WINDOWS
    #include "stdafx.h"
    #endif

    using std::cin;
    using std::cout;
    using std::vector;
    using std::getline;
    using std::string;
    using std::istringstream;
    using std::endl;
    using std::stoi;

    static void execute_case();
    static void skip_blank_lines();
    static void fill_ram();
    static void halt();
    static void set_register(int register_address, int value);
    static void increment_register(int register_address, int value);
    static void multiply_register(int register_address, int value);
    static void copy_register(int destination_address, int source_address);
    static void sum_registers(int destination_address, int value_address);
    static void multiply_registers(int destination_address, int value_address);
    static void copy_ram_to_register(int destination_register, int source_ram);
    static void set_ram(int destination_ram, int source_register);
    static void jump_to(int register_location, int register_sentinel);
    static void initialize_memory();


    int number_of_instructions = 0;
    int line_number = 0;
    const int N_RAM_WORDS = 1000; //Number of words of ram our interpretor can store. 
    const int N_REGISTERS = 10; //Number of registers. 
    const int MAX_VALUE = 1000; //All values in registers and ram must be less than this. 
    const int DEFAULT_VALUE = 0; //default values for all registers and ram words. 

    int n_cases; //The number of input cases in input
    vector<int> registers(N_RAM_WORDS, DEFAULT_VALUE); //each element registers[i] stores the value of register i.  
    vector<int> ram_words(N_REGISTERS, DEFAULT_VALUE);  // each element ram_words[i] stores the value at memory address i. 

    int main()
    {

        //first line of input is the number of cases to follow. 
        cin >> n_cases;

        // skip two lines seperating number of cases from first case. 
        skip_blank_lines();


        for (int i = n_cases; i > 0; i--) {
            execute_case();

            // print an extra blank line for all but the last case. 
            if (i > 1) {
                cout << "\n"; 
            }

        }

    }

    //this function skips two lines seperating number of cases from first case. 
    static void skip_blank_lines() {
        string input;
        getline(cin, input);
        getline(cin, input);
    }

    static void execute_case() {
        initialize_memory();
        fill_ram();
        while (line_number < 999) {
            int instruction = ram_words[line_number] / 100;
            int parameter1 = ram_words[line_number] % 100 / 10;
            int parameter2 = ram_words[line_number] % 10;
            number_of_instructions++;

            switch (instruction) {
            case 1:
                if ((parameter1 == parameter2) && (parameter1 == 0)) {
                    halt();
                    return;
                }
                break; 

            case 2:
                set_register(parameter1, parameter2);
                break; 

            case 3:
                increment_register(parameter1, parameter2);
                break; 

            case 4:
                multiply_register(parameter1, parameter2);
                break; 

            case 5:
                copy_register(parameter1, parameter2);
                break;

            case 6:
                sum_registers(parameter1, parameter2);
                break;

            case 7:
                multiply_registers(parameter1, parameter2);
                break;

            case 8:
                copy_ram_to_register(parameter1, parameter2);
                break;

            case 9:
                set_ram(parameter1, parameter2);
                break;

            case 0:
                jump_to(parameter1, parameter2);
                break;
            }

            line_number++; 
        }
    }

    //resets all registers and ram words to their default value
    // ie. 000. 
    static void initialize_memory() {
        std::fill(registers.begin(), registers.end(), 0);
        std::fill(ram_words.begin(), ram_words.end(),0);
        number_of_instructions = 0;
        line_number = 0;
    }

    //reads all instructions executed for a case from stdin. 
    //input is terminated by a blank line. 
    static void fill_ram() {

        string input_line;
        int word_number = 0;
        while (getline(cin, input_line)) {
            if (input_line.empty()) {
                return;
            }

            //convert line into an integer which is then stored in ram_words. 
            ram_words[word_number] = stoi(input_line);
            word_number++;
        }
    }

    //prints out the number of instructions executed for input case. 
    static void halt() {
        cout << number_of_instructions << "\n" ; 
    }

    //sets the register at register_address to value. 
    void set_register(int register_address, int value) {
        registers[register_address] = value%10;
    }

    //increments the register at register_address by value. 
    static void increment_register(int register_address, int value) {
        registers[register_address] = (registers[register_address]+value) % MAX_VALUE;
    }

    //multiplies the register at register_address by value.
    static void multiply_register(int register_address, int value) {
        registers[register_address] = (registers[register_address]* value) % MAX_VALUE;
    }

    //copies the register at source_address to destination_address
    static void copy_register(int destination_address, int source_address) {
        registers[destination_address] = registers[source_address];
    }

    //sums the registers at destination_address and value_address and stores the result in register destination_address
    static void sum_registers(int destination_address, int value_address) {
        registers[destination_address] = (registers[destination_address]+registers[value_address]) % MAX_VALUE;
    }

    //multiplies the registers at destination_address and value_address and stores the result in register destination_address
    static void multiply_registers(int destination_address, int value_address) {
        registers[destination_address] = (registers[destination_address]*registers[value_address])%MAX_VALUE;
    }

    //copies the value stored at ram_word number source_ram to register number destination_register
    static void copy_ram_to_register(int destination_register, int source_ram) {
        registers[destination_register] = ram_words[registers[source_ram]];
    }

    //sets the ram_word whose address is stored in register number destination ram to the value stored in register number source_register. 
    static void set_ram(int source_register, int destination_ram) {
        ram_words[registers[destination_ram]] = registers[source_register];
    }

    //if sentinel_register is not 0 it
    //jumps to and executes the instruction stored in the ram_address stored in register location_register

    static void jump_to(int location_register, int sentinel_register) {
        if (registers[sentinel_register] == 0) {
            return;
        }
        else {
            line_number = registers[location_register]-1;

        }

    }
\$\endgroup\$
5
\$\begingroup\$

Here are some things that may help you improve your program.

Fix the bug

The code currently contains these two lines:

vector<int> registers(N_RAM_WORDS, DEFAULT_VALUE); 
vector<int> ram_words(N_REGISTERS, DEFAULT_VALUE);

However, it's obvious that N_RAM_WORDS and N_REGISTERS should be swapped. Being able to spot such errors is one advantage to having named constants as you do.

Eliminate global variables

In this case, eliminating global variables is easy and obvious. As @LokiAstari advises, simply wrap everything except n_cases up into a nice neat Machine object. Then n_cases can be declared within main.

Make all instruction handlers alike

All instructions except for halt look alike. They are each void functions taking two int arguments. I'd suggest making halt look like that, too, and move the parameter checking to within the body of the halt function. This makes it easier to implement the next suggestion.

Consider making the code more data driven

Right now there is a big switch with each case being almost identical except for the function called. I'd recommend instead using a table driven approach instead. In my case, I made all instruction handlers return bool which indicates "halted", so only halt() actually returns true. The call then looks like this (

if ((this->*inst[instruction])(parameter1, parameter2))
    return;

I've made all of the functions member functions of a Machine class as mentioned above. Then there is a table that is also part of that Machine class:

   bool(Machine::*inst[10])(int, int) = {
            &Machine::jump_to,
            &Machine::halt,
            &Machine::set_register,
            &Machine::increment_register,
            &Machine::multiply_register,
            &Machine::copy_register,
            &Machine::sum_registers,
            &Machine::multiply_registers,
            &Machine::copy_ram_to_register,
            &Machine::set_ram,
    };

This is simply an array named inst of 10 pointers to member functions. The syntax would be similar for C-style functions except of course they would not have a Machine:: anywhere.

Use all required #includes

The code makes use of std::string and std::stoi but does not #include <string>. It should.

Use only required #includes

It doesn't appear to me that this program actually needs anything from either <sstream> or <fstream> so these two lines can safely be deleted:

#include <sstream>
#include <fstream>
\$\endgroup\$
3
\$\begingroup\$

Overall very good.

If you are throwing away input you can use std::ignore() rather than std::getline()

https://stackoverflow.com/a/164694/14065

I know that normally self documenting code you have a function for each action. But in this specific case I think that is overkill. That's because each function is a single line. I would just manually inline each function (that is only a single line).

I don't like your global variables:

    int number_of_instructions = 0;
    int line_number = 0;

    vector<int> registers(N_RAM_WORDS, DEFAULT_VALUE); //each element registers[i] stores the value of register i.  
    vector<int> ram_words(N_REGISTERS, DEFAULT_VALUE);  // each element ram_words[i] stores the value at memory address i. 

These seem to all be part of the machine. I would wrap these in a class that represents the state of the whole machines. This can then be a single object in main() with all the functions becoming private methods.

My main() would have looked like this:

int main()
{
    cin >> n_cases;
    skip_blank_lines();

    for (int i = n_cases; i > 0; i--)
    {
        Machine   machine(std::cin);
        machine.execute();
        std::cout << machine.getInstructionCount() << "\n\n";
    }
}
\$\endgroup\$
1
\$\begingroup\$
    while (line_number < 999)

is not correct. Nothing in the spec says that falling over results in termination. Instead, it says that all results (including the program counter) are reduced modulo 1000.

I also recommend to increment the line_number before executing an instruction (like a typical hardware does). This way the jump instruction doesn't have to subtract 1 from the location_register's value.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You provide a reasonable interpretation about the program counter (that it rolls over to 0) but I'm not sure that it's necessarily incorrect to halt instead. I'd count that more as a bug in the requirements rather than the code since it doesn't explicitly say what happens in that instance. For that matter, it also doesn't say what should happen with a 123 instruction. It probably shouldn't halt, but does it count as an instruction? The spec doesn't say. \$\endgroup\$
    – Edward
    Nov 3 '16 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.