C++

Forum

 
Wierd Problem

Pages: 12
Script Coder (1468)
I have coded a solution to the following problem http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110106&format=html

I have inserted a test at line 35 and get a weird output (output given after code).
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
 
#include <iostream>
#include <string>
#include <sstream>
using namespace std;

int main() {
	int reg[10], ram[1000], n;
	string s;
	getline(cin, s);
	istringstream ss(s);
	ss>>n;
	getline(cin, s); getline(cin, s);
	
	for(int i=0; i<10; ++i) reg[i]=0;
	for(int c=0; c<n; ++c) {
		for(int i=0; i<1000; ++i) {
			getline(cin, s);
			if(s=="") {
				for(int j=i; j<1000; ++j) ram[j]=0;
				break;
			}
			istringstream ss(s);
			ss>>ram[i];
		}
		
		int ip=0, exec=1;
		while(ram[ip]!=100) {
			++exec;
			int opcode=ram[ip]/100,
			op1=(ram[ip]%100)/10,
			op2=ram[ip]%10;
			switch(opcode) {
				case 0:
					if(!(reg[op2])) ip=reg[op1];
					cout<<ip<<' '<<reg[op1]<<'\n';
					break;
				case 2:
					reg[op1]=op2;
					++ip;
					break;
				case 3:
					reg[op1]+=op2;
					reg[op1]%=1000;
					++ip;
					break;
				case 4:
					reg[op1]*=op2;
					reg[op1]%=1000;
					++ip;
					break;
				case 5:
					reg[op1]=reg[op2];
					++ip;
					break;
				case 6:
					reg[op1]+=reg[op2];
					reg[op1]%=1000;
					++ip;
					break;
				case 7:
					reg[op1]*=reg[op2];
					reg[op1]%=1000;
					++ip;
					break;
				case 8:
					reg[op1]=ram[reg[op2]];
					++ip;
					break;
				case 9:
					ram[reg[op2]]=reg[op1];
					++ip;
					break;
			}
		}
		if(c>0) cout<<'\n';
		cout<<exec<<'\n';
	}
	return(0);
}

10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 9
(continuing forever)


The output doesn't make sense to me, should the two outputted numbers not be the same? Thanks for any help on the problem.
kbw (9488)
Pehaps you begin by telling us what the program ought to be doing.
Script Coder (1468)
Please refer to the link I posted in my first post.

myself wrote:
I have coded a solution to the following problem http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110106&format=html
TheIdeasMan (6817)
Just my 2 cents worth:

Are you testing with the same input as in the example?

Your code could do with some comments - each of the cases, line 27 handles the halt etc.

case 0: couts the ip which is 10, because these are probably all empty ram locations. Presumably the last op1 was a 9.

case 0: is the only one with a cout, except for line 76.

HTH

Edit - the debugger is the best way of finding runtime errors, but I managed to squeak this one out of the ole noodle.
Last edited on
eklavya sharma 2 (170)
The link is not working
Script Coder (1468)
Are you testing with the same input as in the example?

Yes, as far as I can see.

each of the cases, line 27 handles the halt etc.

Just to clear this statement up, you mean that I should comment in those areas?

Referring to Lines 34-36:
1
2
3
 
if(!(reg[op2])) ip=reg[op1];
					cout<<ip<<' '<<reg[op1]<<'\n';
					break;

In line 1, if the register number #second_operand is not equal to zero, then set the ip to the value in register #first_operand. In instructions 7 and 8 (in the sample input, assuming instruction 299 is the 0th instruction) the values of registers 7-9 is (9; 3 999). This means that in line 1 above (which is executed when instruction #10 is decoded) the ip should be set to equal to the value in register 7 which is 9. Then on the next line when the ip is outputted its value is 10, not the correct 9.

EDIT: Sorry if the above is hard to follow.
Last edited on
Script Coder (1468)
The link is not working


I have tested the link from a different pc, and it seems to be working. I could post the info, here, but the formatting might be off.
keskiverto (10402)
Debug by printing out ip, ram[ip], and value of every register at the beginning of every iteration. Pause every x iterations, in case you have infinite loop.
Script Coder (1468)
Debug by printing out ip, ram[ip], and value of every register at the beginning of every iteration. Pause every x iterations, in case you have infinite loop.


I know where the problem is, I do not know what is causing it. From what I can see, this is happening:
1
2
3
 
int j, i=9;
j=i;
cout<<j<<' '<<i<<'\n';


10 9
TheIdeasMan (6817)
Yes, I meant put comments in your code for those areas - it just make it easier to understand, and might have helped you see your problem:

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


Did you see what I was saying about why your program isn't working as you expected?

The link works for me, if it doesn't for others then that is a good reason to put easy comments in. I just copy / pasted them from the web page.

You comment things like for loops //iterating through ram array and for things like initialising everything to zero. Might seem over kill & bad from some people's POV but it's easier for tired old baastards 8+) like me looking at your code at 1:00AM !! In industry it could be a maintenance programmer, who is likely to complain about no comments at all.
Last edited on
TheIdeasMan (6817)
I know where the problem is, I do not know what is causing it.


Was my explanation / solution invalid?
Script Coder (1468)
Was my explanation / solution invalid?

I did not see it, sorry.
Is this it:
1
2
3
 
case 0: couts the ip which is 10, because these are probably all empty ram locations. Presumably the last op1 was a 9.

case 0: is the only one with a cout, except for line 76.

I do not understand what you are trying to say.
TheIdeasMan (6817)
The other thing is, you are not doing anything with the results of the calculations (not even printing them) - shouldn't you be implementing an RPN stack to do the maths?
Last edited on
Script Coder (1468)
@TIM I do not understand your statements:
case 0: couts the ip which is 10, because these are probably all empty ram locations. Presumably the last op1 was a 9.

case 0: is the only one with a cout, except for line 76.
shouldn't you be implementing an RPN stack to do the maths?

The task is to simulate the instructions of the virtual cpu, and count the number of instructions executed until the program halts.
TheIdeasMan (6817)
None of the other cases print anything. The only places in your program that prints anything is on lines 35 (case 0) and 76.

The cout on line 35 is happening thousands of times because of the nested for loops. There is nothing to stop looping when a 000 instruction is reached?

case 0 is for any goto instruction or empty ram. At this stage ip is 10 because you have processed 10 instructions, and ip1 is 9 because that is what it was set to last, should have been 7 though?

So, for now, put a cout statement in each case: so you can see what is going on.

Sorry , the stuff about RPN stack is all wrong - I read the problem properly just now.

So, you just need to print the number instructions executed - which will vary because of any goto's.

In the final program, perhaps you should not have a cout on line 35, because this will prints values thousands of times nested 3 levels of for loop. Line 76 should print the answer, which is what you intended.

I need to go to bed - hopefully I haven't been too much of a nuisance !!
Script Coder (1468)
TIM wrote:
In the final program, perhaps you should not have a cout on line 35, because this will prints values thousands of times nested 3 levels of for loop. Line 76 should print the answer, which is what you intended.
me wrote:
I have inserted a test at line 35


EDIT:
The cout on line 35 is happening thousands of times because of the nested for loops

Nested for loops?
There is only a while nested in a for loop, and a for nested in a for loop.
Last edited on
Script Coder (1468)
Hopefully this will shed some light on the subject. It goes through each instruction of the sample program, and give cometary as to what is happening.
0	299		reg#9=9
1	492		reg#9=18
2	495		reg#9=90
3	399		reg#9=99
4	492		reg#9=198
5	495		reg#9=990
6	399		reg#9=999
7	283		reg#8=3
8	279		reg#7=9
9	689		reg#8=(3+999)%1000=2
10	078		if(reg#8!=0) goto intruction pointed to in reg#7  
			at first iteration reg#8=2 and reg#7=9
			so the ip should now be at instruction 9, but my program sets
			it to 10 and thus the infinite loop
11	100		halt
TheIdeasMan (6817)
Alright - what is the output when you remove the cout on line 35?

Something is making it loop thousands of times:


10 9
10 9
(continuing forever)


What happens when you send the output to a file - anything different at the start?

Apart from that - back to using the debugger - probably the most sane thing to do.

I AM going to bed now - will see how you got on tomorrow zzzzzZZZZZzzzzz......


keskiverto (10402)
Fascinating.

1. How many empty lines are in the input between the number of cases and first case (aka program)? I think you should recount your getlines. Not related to OP issue.

2. "if(reg#8!=0) goto intruction pointed". Where do you go, if reg#8==0? This made you loop.

3. Will !(reg[op2]) be true, if reg[op2] != 0 ? No. This explains why the ip did not equal to value of register.
Script Coder (1468)
How many empty lines are in the input between the number of cases and first case (aka program)? I think you should recount your getlines. Not related to OP issue.

I was unclear as to how many lines there will be between the no. of test cases and the first test case.
2. "if(reg#8!=0) goto intruction pointed". Where do you go, if reg#8==0? This made you loop.

3. Will !(reg[op2]) be true, if reg[op2] != 0 ? No. This explains why the ip did not equal to value of register.

That seems to be the problem, let me quickly test it...
Pages: 12