Inspirated

 
 

July 1, 2008

Programming Challenges: Interpreter

Filed under: Blog — krkhan @ 8:38 am

PC/UVa IDs: 110106/10033, Popularity: B, Success rate: low, Level: 2

Nothing extraordinarily interesting here — typical straight-outta-the-book exercise.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
 
using namespace std;
 
bool decode(int &pc, vector< int > &reg, vector< int > &ram)
{
	int inst = ram.at(pc);
	int c = inst / 100,
		a = (inst % 100) / 10,
		b = inst % 10;
 
	switch(c) {
	case 1:
		return false;
		break;
	case 2:
		reg.at(a) = b;
 
		pc++;
		break;
	case 3:
		reg.at(a) += b;
		reg.at(a) %= 1000;
 
		pc++;
		break;
	case 4:
		reg.at(a) *= b;
		reg.at(a) %= 1000;
 
		pc++;
		break;
	case 5:
		reg.at(a) = reg.at(b);
 
		pc++;
		break;
	case 6:
		reg.at(a) += reg.at(b);
		reg.at(a) %= 1000;
 
		pc++;
		break;
	case 7:
		reg.at(a) *= reg.at(b);
		reg.at(a) %= 1000;
 
		pc++;
		break;
	case 8:
		reg.at(a) = ram.at(reg.at(b));
 
		pc++;
		break;
	case 9:
		ram.at(reg.at(b)) = reg.at(a);
 
		pc++;
		break;
	case 0:
		if(reg.at(b) == 0) {
			pc++;
		} else {
			pc = reg.at(a);
		}
 
		break;
	}
 
	return true;
}
 
int main(int argc, char *argv[])
{
	string dummy;
	int ncases;
 
	cin>>ncases;
 
	// ignore two empty lines
	getline(cin, dummy);
	getline(cin, dummy);
 
	for(int n = 0; n < ncases; n++) {
		vector< int > reg(10), ram(1000);
 
		fill(reg.begin(), reg.end(), 0);
		fill(ram.begin(), ram.end(), 0);
 
		for(int i = 0; i < 1000; i++) {
			string str;
 
			getline(cin, str);
			if(str == "") {
				break;
			}
 
			istringstream iss(str);
			iss>>ram.at(i);
		}
 
		int executed = 1;
		int pc = 0;
		while(decode(pc, reg, ram)) {
			executed++;
		}
 
		if(n > 0) {
			cout<<endl;
		}
		cout<<executed<<endl;
	}
 
	return 0;
}
Tags: , , , , , , , , ,

2 Comments

  1. What’s wrong with the following code..?

    #include
    #include
    #include
    #include
    using namespace std;
    #define ud(x) (x%10)
    #define td(x) ((x/10)%10)
    #define hd(x) (x/100)
    #define mod 1000
    long long int registers[12]; /* Array for 10 registers */
    int ram[1024]={0}; /* RAM Locations */
    long long int decode(int *ram)
    {
    int i;
    long long int res=0;
    for(i=0;i<1000;i++)
    {
    switch(hd(ram[i]))
    {
    case 1: //assert(ram[i]==100);
    if(td(ram[i])==0 && ud(ram[i])==0)
    return ++res;
    else { ++res; break; }
    case 2: registers[td(ram[i])]=ud(ram[i]); ++res;
    break;
    case 3: registers[td(ram[i])]=(registers[td(ram[i])]+ud(ram[i]))%mod; ++res;
    break;
    case 4: registers[td(ram[i])]=(registers[td(ram[i])]*ud(ram[i]))%mod; ++res;
    break;
    case 5: registers[td(ram[i])]=registers[ud(ram[i])]; ++res;
    break;
    case 6: registers[td(ram[i])]=(registers[td(ram[i])]+registers[ud(ram[i])])%mod; ++res;
    break;
    case 7: registers[td(ram[i])]=(registers[td(ram[i])]*registers[ud(ram[i])])%mod; ++res;
    break;
    case 8: registers[td(ram[i])]=ram[registers[ud(ram[i])]]; ++res;
    break;
    case 9: ram[registers[ud(ram[i])]]=registers[td(ram[i])]; ++res;
    break;
    case 0: if(ram[i]) {
    if(registers[ud(ram[i])]) {
    i=registers[td(ram[i])]-1;
    break;
    }
    else { ++res; break; }
    }
    //default: assert(0);
    }
    }
    return res;
    }
    int main()
    {
    int cases,i;
    char ch;
    long long int res=0;
    scanf(“%d\n”,&cases);
    vector v;
    vector::iterator it;
    while(cases–) {
    while((scanf(“%d”,&ram[i]))!=EOF) {
    assert(ram[i]>=0);
    }
    res=decode(ram);
    v.push_back(res);
    }
    for(it=v.begin();it!=v.end();it++) {
    if(it!=v.begin()) { printf(“\n”); }
    printf(“%lld\n”,*it);
    }
    return 0;
    }

    Comment by Retrospect — March 4, 2009 @ 7:18 pm

  2. And what is wrong with this small code of mine! It seems to work all fine on my machine. UVA is such an anal judge! I hate it. You spend more time on silly things than actual algo.

    #include
    #include
    using namespace std;
    int main()
    {
    int n;
    string in;
    cin >> n;
    getline(cin,in);//and extra newline
    getline(cin,in);//an extra line
    for(int i=0;i<n;i++)
    {
    vector REG(10,0),RAM(1000,0);
    int k=0,count=0;
    while(1)
    {
    getline(cin,in);
    if(in==””) break;
    RAM[k++]=100*(in[0]-‘0’)+10*(in[1]-‘0’)+(in[2]-‘0’);
    }
    for(int j=0;j<k;j++)
    {
    int a,b,c;
    a=RAM[j]/100;
    b=(RAM[j]%100)/10;
    c=RAM[j]%10;
    count ++;
    if(a==1) break;
    switch(a)
    {
    case 2: REG[b]=c; break;
    case 3: REG[b]+=c; break;
    case 4: REG[b]*=c; break;
    case 5: REG[b]=REG[c]; break;
    case 6: REG[b]+=REG[c]; break;
    case 7: REG[b]*=REG[c]; break;
    case 8: REG[b]=RAM[REG[c]]; break;
    case 9: RAM[REG[c]]=REG[b]; break;
    case 0: if(REG[c]!=0) j=REG[b]-1; break;
    default: cout << "ERROR" << endl;
    }
    REG[b]%=1000;
    }
    cout << endl;
    cout << count << endl;
    }
    return 0;
    }

    Comment by Manish — February 14, 2010 @ 8:38 pm

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

 
Creative Commons License

This work is licensed under a Creative Commons Attribution-Share Alike 3.0 License