964 - Custom Language

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

Moderator: Board moderators

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

964 - Custom Language

Post by rio » Tue Oct 31, 2006 4:04 am

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Oct 31, 2006 11:37 am

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.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Wed Nov 01, 2006 4:31 am

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
New poster
Posts: 33
Joined: Sat Aug 20, 2005 9:59 pm
Location: St. Petersburg

Judge data: bug report.

Post by avm » Wed Nov 01, 2006 12:30 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Nov 01, 2006 1:17 pm

:oops: :oops: :oops:

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.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Wed Nov 01, 2006 3:05 pm

Thanks, joey and avm.

After removing checking variable syntax, i got AC.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Nov 02, 2006 12:11 am

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.
Ami ekhono shopno dekhi...
HomePage

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Thu Nov 02, 2006 2:29 am

For you input, my code ouput below

Code: Select all

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Nov 02, 2006 8:58 am

Thanks rio. My code produces same output. But I am still getting TLE. I have to check it again.
Ami ekhono shopno dekhi...
HomePage

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Nov 02, 2006 12:58 pm

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.
Last edited by Jan on Thu Nov 02, 2006 7:07 pm, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Nov 02, 2006 1:56 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Nov 02, 2006 7:06 pm

Thanks Joachim. I have to save the input in a different way. And yes, the isdigit() function should be rewritten.
little joey wrote: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.
Ami ekhono shopno dekhi...
HomePage

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Nov 02, 2006 9:23 pm

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

Code: Select all

Removed... Checking
Hope anyone helps. Thanks in advance.
Last edited by Jan on Thu Nov 02, 2006 10:11 pm, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Nov 02, 2006 10:03 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Nov 02, 2006 11:01 pm

Thank you very^(inf) much Joachim. I have got it Accepted. :D. Finally, hard time passed.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 9 (900-999)”