964 - Custom Language

[rio]

I'm quite stuked in this problem. I can't understand the specification well.

Here are few quetions:

1. Does the arithmetic operations cause an overflow with long long?

2. If there is an invalid inustruction (not defined instruction, too many args,
too long variable name ...), is it supposed to print "ABORTED"? Or if the
interpreter doesn't execute that inustruction, doesn't care?

3. Same quetion as 2 for invalid data in data section.

4. what is "something wrong happens"? I assumed like below.
- undefine instruction, too many args, too few args, too long variable name
- invalid data
- if the stack is empty with instruction POP, DUP, WRITE, JUMPPOS, JUMPZERO
- if the stack doesn't have more than 2 item with instruction ADD, SUB, DIV, MUL
- zero divide
- READ when no more inputs.
- if the variable has no associated value with insturction PUSH, JUMP(POS, ZERO)

5. Does the instruction JUMPPOS, JUMPZERO removes the top of the stack?


Answer of the quetions or some i/o helps me.

Thanks in advance.
----
Sory for my poor English.

[little joey]

I had to go by the same description when writing the testset, and had the same type of questions as you have. So I took the description as literally as possible, making sure the input was correct (as should be with any testset), and clarifying the interpretation choices in the examples.

Since the input consists of a code section and a data section, the following conclusions can be made:
- The code section consists of a program, and a program is defined as a list of instructions, and an instruction is defined as being one from the list given. So to be valid, the code section should not contain instructions not defined by the list. In other words, a parser should not fail when parsing the code section. This answers your question 2, and part of question 4.
- The data section consists of a list of integers. This answers your question 3, and part of question 4.

There is some vagueness in the description about the concepts 'integer' and 'variable'. For 'integer' I took the 'normal' interpretation as being a 32-bit signed number, but took care that the input would not cause arithmetic overflow/underflow when the program was executed correctly (NB: division by zero is not arthimetic overflow). This answers your question 1.
Nothing is said in the description about declaring and initialising variables, so I made what I think is the most sensible choise: a variable doesn't exist before it's assigned a value, an attempt to read a variable before it is initialised, causes and error. I illustrated that in the 4th and 5th sample case. You should note that only the interpreter can decide wether a variable is initialised or not, not the parser because the parser doesn't know the flow of events.

There are two ways a program can end:
- Normally: an implicit or explicit jump to an address outside the range of the list of instructions. In that case the program should print a list of all output generated by WRITE instructions. By implicit I mean the jump to the next instruction after successfully executing an instruction or not taking a conditional jump.
- Abnormally: 'something wrong happens'. It should then only print the word 'ABORTED', as in the second sample case. As what that 'something wrong' consists of, the problemsetter leaves us in the dark, so we're left with common sense. I think your list in question 4, apart for the first two items, sums it up quite nicely.

About your question 5: I think the last sentence of the description answers that and the 3rd sample case illustrates it.

There is one issue I didn't cover in the samples: not all instructions are atomic.
In most instructions this makes no difference for the flow of events, but for the conditional jumps it does. So let me add the following I/O to illustrate my choices:
Input

Code: Select all

PUSH 1
JUMPZERO addr
PUSH 12345
WRITE
#
#

Output

Code: Select all

12345
#

An equally valid choice would have led to printing 'ABORTED' in this case, but I chose the former.

I hope this clarifies matters, if not please say so.

[rio]

Thanks four your reply, joey.

I think i understood the problem. But still gettig WA..
Seems theres an bug some where ..

I'll try it more.

----
Sory for my poor English

[avm]

After removing checking variable syntax I receive AC

Code: Select all

bool check_token(const char *p)
{
//A variable s is a string in [a-z][1-9a-z]*
if (!islower(p[0])) return false;
for(int i=1;p[i];i++)
  {
  if (!islower(p[i]) && !isdigit(p[i])) return false;
  if (p[i] == '0') return false;
  }
return true;
}

So, perhaps judge data contains illegal variables like : "a0","A", etc.

[little joey]

Why does someone always reads what one expects to read... You're absolutely right, there were variable names with zeros in them. I corrected this mistake and sent the updated input to the judge.

[rio]

Thanks, joey and avm.

After removing checking variable syntax, i got AC.

[Jan]

Can anyone tell me whats the output of the folowing input set

Input:

Code: Select all

PUSH 12345
POP x
PUSH 0
PUSH 1
PUSH 0
PUSH 0
POP abdvdhsjashgdhgasdhgajdgashdgjasghdajdgh
JUMPZERO 10
JUMP 9
PUSH 1
WRITE
JUMPPOS 5
#
#
PUSH 12345
POP x
PUSH 1
PUSH 0
PUSH 0
POP abdvdhsjashgdhgasdhgajdgashdgjasghdajdgh
JUMPZERO 9
JUMP 8
PUSH 1
WRITE
JUMPPOS 4
#
#
PUSH 1
JUMPZERO abcde
PUSH 1
WRITE
#
#
PUSH 1
JUMPZERO abcde
PUSH 1
WRITE
WRITE
#
#
READ
#
#
PUSH 0
JUMPZERO abcde
PUSH 1
WRITE
#
#
JUMPZERO 1
#
#
JUMPPOS 1
#
#

Thanks in advance.

[rio]

For you input, my code ouput below

Code: Select all

1
1
#
ABORTED
#
1
#
ABORTED
#
ABORTED
#
ABORTED
#
ABORTED
#
ABORTED
#

[Jan]

Thanks rio. My code produces same output. But I am still getting TLE. I have to check it again.

[Jan]

I have tried all day long, but cant figure out my error . I m still getting TLE. Here is my code. Its quite long. Sorry for posting the code. Hope anybody helps.

Code: Select all

Removed...

Thanks in advance.

[little joey]

Hmm, there are some errors, and the code is too slow. I think the slowness is due to your juggling strings upto the lowest level; try tokenisation instead.
One error is that you can't handle negative arguments:

Code: Select all

PUSH -7
PUSH 1
ADD
WRITE
#
#

Should print '-6', not 'ABORTED'. As I said above, I took 'interger' as meaning signed 32-bit (the type 'int' in C, 'integer' in Pascal) and the sample input contains a negative number.
There's another error, but I'm not going to add too many spoilers .

[Jan]

Thanks Joachim. I have to save the input in a different way. And yes, the isdigit() function should be rewritten.

There's another error, but I'm not going to add too many spoilers .

I think you leave me in dark. But thats the best way to help . Thanks again.

[Jan]

I have changed my code. But now I m getting WA. . This problem made me mad.

Code: Select all

Removed... Checking

Hope anyone helps. Thanks in advance.

[little joey]

There remains one little error, vanishingly small... but I still don't want to spoil it. PM me if you realy want to know, but I'm sure you can find it.

[Jan]

Thank you very^(inf) much Joachim. I have got it Accepted. . Finally, hard time passed.