10033 - Interpreter

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Algoritmo
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:

Re: 10033 Interpreter is not Interpreting

Post by Algoritmo » Wed Oct 15, 2003 12:40 pm

You did not make a program that handles multiple test cases. Remember that first input value is for the number of test cases and that blank lines tell when a case (bock of ram) finishes and when the next starts.

I have checked my program hundred of times and I don't se nothing possibly wrong. Probably I also have a problem with the input:

Code: Select all

gets(S);
sscanf(S, "%d", &Cases);
gets(S);
while (Cases--) {
	for (i=0;i<10;i++) Reg[i] = 0;
	for (i=0;i<1000;i++) Word[i] = 0;
	Words=0;
	while (*(gets(S))) sscanf(S, "%d", &Word[Words++]);
My program worked perfectly with the sample input, counting 16 executions, as expected. I also tested with a file containing 2 test cases, by DOS:
Interp.exe < testfile.txt

Whe submitted, I get sigsegv. Sigsegv is avoited if program aborts when Address gets bad address.

I have even done a macro that converts values to long before making multiplications, and only converts them back to int after the modulus of 1000 has been applied.
Would it make a difference if I converted everything to long?
Can gets() work different there than here?

Help please

ravingavin
New poster
Posts: 21
Joined: Sun Sep 14, 2003 11:44 pm
Location: USA
Contact:

Solved

Post by ravingavin » Wed Oct 15, 2003 8:46 pm

I fixed my error and got the problem solved!

Thanks everyone who replied!


GCS

ravingavin
New poster
Posts: 21
Joined: Sun Sep 14, 2003 11:44 pm
Location: USA
Contact:

Solved

Post by ravingavin » Wed Oct 15, 2003 8:48 pm

I fixed my error and got the problem solved!

Thanks everyone who replied!


GCS

ravingavin
New poster
Posts: 21
Joined: Sun Sep 14, 2003 11:44 pm
Location: USA
Contact:

Wrong post

Post by ravingavin » Wed Oct 15, 2003 8:50 pm

The above posts goes somewhere else....Sorry!

I'm spamming the thing

Kentaro
New poster
Posts: 19
Joined: Thu Feb 05, 2004 4:41 am
Location: Canada, eh?

I'm confused too...

Post by Kentaro » Sat Feb 28, 2004 3:01 am

I understand this problem pretty well but the problem statement doesn't say anything about what should happen if the interpreter comes across an illegal instruction. Should the interpreter halt? Will a case like this even occur?
Computer Science is no more about computers than Astronomy is about telescopes.
-- E. W. Dijkstra

Salmin Sultana
New poster
Posts: 16
Joined: Sun Mar 07, 2004 12:19 pm
Location: Dhaka

10033

Post by Salmin Sultana » Tue Mar 09, 2004 9:54 am

why it is wa?i am confused about input 000.will i then increase instruction?

[cpp]#include<stdio.h>
#include<string.h>

long int ram[1001],r[11];

int main()
{
long int test,n,ip,i,k;
int f,d,s;

scanf("%ld",&test);

for(k=0;k<test;k++)
{
i=0;
ip=0;
while(1==(scanf("%ld",&ram[i++])));

for(i=0;;)
{
n=ram[ip++];
s=n%10;
d=(n/10)%10;
f=n/100;

if(f==0)
{
if(r[s]!=0)
{
ip=r[d];
i++;
}
}
else if(f==1)
{
i++;
break;
}
else if(f==2)
{
r[d]=s;
i++;
}
else if(f==3)
{
r[d]=(r[d]+s)%1000;
i++;
}
else if(f==4)
{
r[d]=(r[d]*s)%1000;
i++;
}
else if(f==5)
{
r[d]=r[s];
i++;
}
else if(f==6)
{
r[d]=(r[d]+r[s])%1000;
i++;
}
else if(f==7)
{
r[d]=(r[d]*r[s])%1000;
i++;
}
else if(f==8)
{
r[d]=ram[r[s]];
i++;
}
else if(f==9)
{
ram[r[s]]=r[d];
i++;
}
}
printf("%ld\n",i);
memset(r,0,(sizeof(int))*10);
memset(ram,0,(sizeof(int))*1000);
}
return 0;
}[/cpp]

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

10033 - TLE

Post by minskcity » Thu May 06, 2004 10:18 pm

Can anybody post some critical imputs that will break my code? I get TLE... :cry: :cry:
[cpp]#include <iostream>
#include <string>
#include <sstream>
//#include <fstream>
using namespace std;

long r[10], m[1000];
string s;
long test, ind, n1, n2, n3, ans;

int main(){
// ifstream cin("in.txt");
cin >> test;
getline(cin, s);
getline(cin, s);

while(test--){
memset(r, 0, sizeof(r));
memset(m, 0, sizeof(m));

ind = 0;
getline(cin, s);
while(s[0]){
istringstream sin(s);
sin >> m[ind++];
getline(cin, s);
}

ans = ind = 0;
ans++;

while(m[ind] / 100 != 1){
ans++;
n1 = m[ind] / 100;
n3 = m[ind] % 10;
n2 = (m[ind] % 100) / 10;
ind = (ind + 1) % 1000;
switch(n1){
case 2: r[n2] = n3; break;
case 3: r[n2] += n3; break;
case 4: r[n2] *= n3; break;
case 5: r[n2] = r[n3]; break;
case 6: r[n2] += r[n3]; break;
case 7: r[n2] *= r[n3]; break;
case 8: r[n2] = m[r[n3]]; break;
case 9: m[r[n3]] = r[n2]; break;
case 0: if(r[n3]) ind = r[n2]; break;
}
r[n2] %= 1000;
}

cout << ans << endl << endl;
}
return 0;
}[/cpp]

Crunchy Death
New poster
Posts: 3
Joined: Wed Jun 30, 2004 6:15 am

Post by Crunchy Death » Wed Jun 30, 2004 7:01 am

nm

Crunchy Death
New poster
Posts: 3
Joined: Wed Jun 30, 2004 6:15 am

10033 - Newbie plea for help

Post by Crunchy Death » Wed Jun 30, 2004 9:10 pm

I've redone this several times and keep geting WA. I'd like to see if anyone here can spot my problem or perhaps give some testing hints

Here's my last version in C.

[c]#include <stdio.h>
#include <memory.h>
#include <assert.h>

typedef int BOOL;
#define FALSE 0
#define TRUE !FALSE

/* machine state: memory, registers, and instruction pointer */
int mem[1000];
int reg[10];
int ip;

/* reset machine state */
void initialize()
{
ip = 0;
memset(mem, 0, sizeof(mem));
memset(reg, 0, sizeof(reg));
}

/* decode the current command */
void decode(int *opcode, int *arg1, int *arg2)
{
int inst = mem[ip];
*opcode = inst / 100;
*arg2 = inst % 10;
*arg1 = (inst - *arg2 - 100*(*opcode)) / 10;
}


/* Process the program in memory */
int process()
{

#define SETREG(destAddr, sourceValue) (reg[(destAddr)] = (sourceValue) % 1000);
#define SETMEM(destAddr, sourceValue) (mem[(destAddr)] = (sourceValue) % 1000);

int opcode, arg1, arg2;

int count = 0;
BOOL done = FALSE;
do {
decode(&opcode, &arg1, &arg2);
++count;
ip = (ip + 1) % 1000;

/* Depending on the opcode perform the required operation */
switch (opcode) {
case 1:
done = TRUE;
break;
case 2:
SETREG(arg1, arg2);
break;
case 3:
SETREG(arg1, reg[arg1] + arg2);
break;
case 4:
SETREG(arg1, reg[arg1] * arg2);
break;
case 5:
SETREG(arg1, reg[arg2]);
break;
case 6:
SETREG(arg1, reg[arg1] + reg[arg2]);
break;
case 7:
SETREG(arg1, reg[arg1] * reg[arg2]);
break;
case 8:
SETREG(arg1, mem[ reg[arg2] ]);
break;
case 9:
SETMEM(arg2, reg[arg1]);
break;
case 0:
if (reg[arg2] != 0)
ip = reg[arg1];
break;
}

} while (!done);
return count;
}

int main()
{
#define LEN(x) (sizeof(x) / sizeof(x[0]))
#define GETLINE(line, input) { memset(line, 0, sizeof(line)); \
fgets(line, LEN(line), input); }

FILE *input = stdin;

int i;
int numcases;
char line[100];

/* if (!(input = fopen("test.txt", "r"))) {
perror(NULL);
input = stdin;
}
*/

/* Eat number of cases */
GETLINE(line, input);
sscanf(line, "%d", &numcases);

/* Eat newline */
GETLINE(line, input);

/* For each case */
while (numcases--) {

/* zero memory and registers */
initialize();

/* read in memory */
i = 0;
while ( TRUE ) {
GETLINE(line, input);
if ( sscanf(line, "%d", &mem[i++]) != 1 )
break;
}

/* process and print output */
printf("%d\n", process());
}

}[/c]

tkat
New poster
Posts: 2
Joined: Tue Sep 14, 2004 5:56 pm

10033 - Explanation of the problem?

Post by tkat » Tue Sep 14, 2004 6:26 pm

Hi, I'm trying to understand what the problem accomplishes. As far as I can tell, the sample input is doing the following:

1 There is one case below

299 Set register 9 to 9 // R9=9
492 Multiply register 9 by 2 // R9=18
495 Multiply register 9 by 5 // R9=90
399 Add 9 to register 9 // R9=99
492 Multiply register 9 by 2 // R9=198
495 Multiply register 9 by 2 // R9=990
399 Add 9 to register 9 // R9=999
283 Set register 8 to 3 // R8=3
279 Set register 7 to 9 // R7=9
689 Add register 9 value to register 8 // R8=2 (b/c mod 1000 happens)
078 Go to location in register 7 // I'm @ 9 again but I'm not sure where that is
100 Halt
000
000
000

My questions are:

(1) When RAM gets initialized with this input, does location 0 get 1, location 1 get blank line, location 3 get 299, and so forth?

(2) When it says there is a blank line between consecutive inputs, does that mean that if there was another case, the input would be the above followed by a blank line and the second case, but then the number in location 0 would say 2 instead of the 1.

***(3) Why does the output say that there are 16 instructions executed including the halt line? I'm assuming there's some kind of loop that happens, but I'm not seeing it.

Hope y'all can help me out!! Thanks!! :) :)

sterblichen
New poster
Posts: 1
Joined: Wed Sep 15, 2004 1:59 am

re:

Post by sterblichen » Wed Sep 15, 2004 2:45 am

I am equally confused with this bit of code,


i have taken it such as :

(1) ram[0] = 1, the number of cases
ram[1] = the next integer (i.e. 299)

but this is merely what im assuming, since it doesnt make sense
to add a blank to ram[1]


(2)equally clueless 8) , fill me in when u find out or vice versa.


(3) the only way i can see it reaching 16 instructions is by doing the
000
000
000

after the 100, which makes me think that the 100 really doesnt do
anything, even though its supposed to halt.


edit: tkat u in the downing class eh? noticed ure name from utacm. suprised u havent posted in teh newsgroup :P

tkat
New poster
Posts: 2
Joined: Tue Sep 14, 2004 5:56 pm

Post by tkat » Tue Sep 21, 2004 5:52 pm

I thought I'd just come back to answer my own questions, in case somebody else works on this in the future. :)

1) No. RAM[0] is initialized with the first line in case, i.e. 299 in the example.
2) Correct.
3) Yes, there's a loop happening. It's basically decrementing the value in reg[8] from 3 to 0 and then once that happens instruction 078 allows us to go to the next instruction, which is halt.

Everything else was pretty straightfoward after that.

ps Sterblichen, sorry I didn't get back to this in a timely manner. I really hope you were able to figure out what was going on though! It was a really cool problem.

Crunchy Death
New poster
Posts: 3
Joined: Wed Jun 30, 2004 6:15 am

Post by Crunchy Death » Wed Jan 26, 2005 6:22 pm

yay i solved it im unstoppable

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

10033 > Interpreter > Need I/O.

Post by _.B._ » Sun Jul 31, 2005 2:41 am

Greetings!
Won't bother you asking to read my code for this problem (this time :wink:), but will ask you to tell me where to find critical I/O for this problem.
Too many WAs already! :evil:

Thanks in advance! :D
_.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Sun Jul 31, 2005 9:21 pm

Hi BLG,

http://plg.uwaterloo.ca/~acm00/000930/data/

Look for
E1.dat , E1.diff
E2.dat , E2.diff
E3.dat , E3.diff

Hope this is enough.

Post Reply

Return to “Volume 100 (10000-10099)”