ACM ICPC 20062007, NEERC, Moscow Subregional Contest
Moscow, October 21, 2006
Problem C. Code Checker
Time limit:
3 seconds
Memory limit:
64 MiB
Prof. Acmeroff teaches programming in the Institute of Business Management. He teaches a relatively new,
but popular language called Db. Unfortunately, program plagiarism is a serious headache for the professor,
because some students cheat when doing home exersises. So the professor has to check students' works for
plagiatrism each time. Thus a computer program, which is able to perform some sort of program comparison
might be very useful for him.
The Db language is briefly described as follows:
· The # character never appears in programs. The character \ never appears in programs outside of
strings.
· All characters with codes less or equal then 32 are whitespace characters. A sequence of whitespace
characters is called whitespace and equivalent to one space character (code 32).
· Comments starting from /* run till the first sequence of */ characters.
· A comment is equivalent to one space character.
· String literals start from " and run till the next ", except \".
· An identifier is the longest possible sequence of characters starting from latin letter or underscore
and containing latin letters, underscore and digits. For example, sequence (0x800+) contains one
identifier x800. Letter case is significant.
· Some indentifiers are reserved as keywords. The exact list of keywords depends on the language
dialect.
· There are no lexical scoping rules.
A program is processed as follows:
1. Each comment is replaced with a single space character.
2. Each whitespace (including space characters from the previous step) is replaced with a signle space
character.
3. Each string is replaced with "".
4. Space characters are removed, except those separating identifiers and keywords from each other.
Finally, if there exists an one-to-one correspondence between the identifiers of the first program and the
indentifiers of the second program, so the replacement of the identifiers in the second program with the
corresponding identifiers of the first program yelds two equal texts, such programs are called identical.
Write a program, which checks whether two given programs written in Db are identical.
Input
The input for your program consists of the list of keywords and two programs written in Db. The list of
keywords and the programs are separated from each other with a single # character. The list of keywords
section only contains keywords and whitespace. The size of input does not exceed 4MiB. The total number
of different identifiers and keywords does not exceed 65535.
Page 4 of 17
ACM ICPC 20062007, NEERC, Moscow Subregional Contest
Moscow, October 21, 2006
Output
Print the word YES, if the input programs are identical, and the word NO otherwise.
Example
stdin
stdout
int
void
YES
while if return
#
/* sizeof(int) == 4 */
int main(void) {
int max = 0x80000000, n;
while(scanf("%d", &n) == 1)
if (n > max) max = n;
printf("%d", max);
return 0;
}
#
/* sizeof(int) == 4 */
int n(void) {
int max = 0x80000000, main;
while(printf("%d", &main) ==
1)
if(main > max)
max = main;
scanf("Answer: \"%d\"", max);
return 0;
}
Page 5 of 17
решение на паскале ( fpc ) :
- Код: Выделить всё
program array1;
{$mode objfpc}
uses crt,sysutils;
type
pget = function() : byte;
pa = procedure(iii : byte);
pliteral = function(var a : ansistring): boolean;
endloop = class(exception);
ss = set of char;
var
dl,sid,id : ss;
a1 : array [1..100] of string;
bl : boolean;
pl : pliteral;
file1,file2 : AnsiString;
tstr : string;
wnum,knum : dword; { number of indifier+keyword,keyword }
pread : pget;
padd : pa;
iii,i,ii : dword;
c : char;
b : byte;
loop : dword;
f : file of byte;
procedure add1(b1 :byte); forward;
procedure add2(b1 :byte); forward;
function get2() : byte; forward;
function checkend(b1 : byte) : boolean;
var
temp : boolean;
begin
temp := ( filepos(f) >= filesize(f)) or ( b1 = byte( '#')) ;
if temp then loop :=1;
checkend := temp;
end;
function get1() : byte;
begin
read(f,b);
checkend(b);
if b>32 then
begin
pread := @get2;
padd := @add2;
end;
get1 := b;
end;
function get2() : byte;
begin
read(f,b);
checkend(b);
if b<33 then
begin
pread := @get1;
padd := @add1;
wnum += 1;
end;
get2 :=b;
end;
procedure add1(b1 :byte);
begin
end;
procedure add2(b1 :byte);
begin
tstr := char(b1);
a1[wnum] += tstr;
end;
function l2(var a : ansistring) : boolean ; forward;
function l3(var a : ansistring) : boolean ; forward;
function l1(var a : ansistring) : boolean ;
begin
i := length( a);
bl := false;
loop := 0;
while ii<=i do
begin
if a[ii] = '"' then
begin
bl := true;
ii+=1;
loop := 1;
pl := @l2;
break;
end;
ii+=1;
end;
i := ii;
l1 := bl;
end;
function l2(var a : ansistring) : boolean ;
begin
if ( a[ii-1] = '\') then
else
if (a[ii] = '"') then pl:=@l3;
ii+=1;
l2:=true
end;
function l3(var a : ansistring) : boolean ;
begin
delete(a,i,ii-1-i);
pl := @l1;
ii := i+1;
l3:=true;
end;
function l5(var a : ansistring) : boolean ; forward;
function l7(var a : ansistring) : boolean ; forward;
function l4(var a : ansistring) : boolean ;
begin
i+=1;
l4 := false;
if a[i] in id then
begin
pl := @l7;
if a[i] in sid then
begin
pl := @l5;{ id or kw begin }
end;
end;
if i<length(a) then l4:= true;
end;
function l5(var a : ansistring) : boolean ;
var tss : string;
begin
tstr:='';
while a[i] in id do
begin
tstr+=a[i];
i+=1;
end;
iii:=0;
for ii:=1 to wnum do
begin
if a1[ii] = tstr then
begin
iii:=ii;
{
writeln('keyword :',tstr,' id:',iii);
}
i-=length(tstr);
delete(a,i,length(tstr));
str(iii,tss);
insert('\',tss,1);
insert(tss,a,i);
i+=length(tss);
break;
end;
end;
if iii = 0 then
begin
wnum+=1;
a1[wnum] := tstr;
i-=length(tstr);
delete(a,i,length(tstr));
str(wnum,tss);
insert('\',tss,1);
insert(tss,a,i);
i+=length(tss);
writeln('indifier id = ',wnum,' : ',tstr);
end;
pl := @l4;
l5:=true;
end;
function l7(var a : ansistring) : boolean;
begin
write('constant : ');
while a[i] in id do
begin
write(a[i]);
i+=1;
end;
writeln();
pl:=@l4;
l7:=true;
end;
procedure preformat( var a : ansistring);
label j1,j2,j3,j4;
begin
{ delete comments }
goto j3;
j4:
delete(a,i,ii-i+2);
j3:
i:=pos('/*',a);
ii:=pos('*/',a);
if i*ii>0 then goto j4;
{ delete extra space }
goto j1;
j2:
delete(a,i,1);
j1:
i:=pos(' ',a) ;
if i>0 then goto j2;
{ delete literal }
pl := @l1;
loop := 1;
ii := 1;
while( loop > 0 ) do
begin
pl(a) ;
end;
end;
{ main }
begin
{ init }
assign(f,'pcre.c');
reset(f);
dl := [' '..'/',':'..'@','['..'`','{'..'~'];
sid := ['_','A'..'Z','a'..'z'];
id := sid + ['0'..'9'];
{ read keywords }
pread := @get1;
padd := @add1;
wnum :=1;
while loop =0 do
begin
b := pread();
padd(b);
end;
for loop := 1 to wnum do writeln('keyword id = ',loop,' : ',a1[loop]) ;
{ read 1 program }
repeat
read(f,b);
if b<32 then b :=32;
tstr := char(b);
file1 += tstr;
insert(' ',file1,1);
until b = 35 ;
delete(file1,length(file1),1);
preformat(file1);
{ indifier parse }
ii :=2;
i := 1;
pl :=@l4;
writeln('creating first program indifiers ... ');
knum:=wnum;
while pl(file1) do ii+=1;
{ read 2 program }
repeat
read(f,b);
if b<32 then b :=32;
tstr := char(b);
file2 += tstr;
until filepos(f) >= filesize(f) ;
insert(' ',file2,1);
preformat(file2);
{ indifier parse}
writeln('creating second program indifiers ... ');
{ for i:=knum to wnum do a1[i] := '';}
wnum:=knum;
ii :=2;
i := 1;
pl :=@l4;
knum:=wnum;
while pl(file2) do ii+=1;
writeln(file2);
writeln(file1);
if file1 = file2 then writeln('programs equals');
end.
пример :
вход ::
- Код: Выделить всё
printf return int
if then
#include <stdio.h>
/* coment 1 */123
include <pcre.h>
int main() {
pcre *p; /* comment 2 / * /
sldkfls sdlfj; ljkkj sldkjflk */123
/ /
printf("pcre: hello \" there\n");
p=pcre_compile("lalalal",0,0,0,0);
return 0;
#include <stdio.h>
/* coment 1 */123
include <pcre55.h>
int main() {
pcre55 *p; /* comment 2 / * /
sldkfls sdlfj; ljkkj sldkjflk */123
/ /
printf("pcre: sldkfjlk kk hello \" there\n");
p=pcre_compile("lalalal",0,0,0,0);
return 0;
выход:
- Код: Выделить всё
keyword id = 1 : printf
keyword id = 2 : return
keyword id = 3 : int
keyword id = 4 : if
keyword id = 5 : then
keyword id = 6 : #
creating first program indifiers ...
indifier id = 7 : include
indifier id = 8 : stdio
indifier id = 9 : h
constant : 123
indifier id = 10 : pcre
indifier id = 11 : main
indifier id = 12 : p
constant : 123
indifier id = 13 : pcre_compile
constant : 0
constant : 0
constant : 0
constant : 0
constant : 0
creating second program indifiers ...
indifier id = 7 : include
indifier id = 8 : stdio
indifier id = 9 : h
constant : 123
indifier id = 10 : pcre55
indifier id = 11 : main
indifier id = 12 : p
constant : 123
indifier id = 13 : pcre_compile
constant : 0
constant : 0
constant : 0
constant : 0
constant : 0
\7 <\8.\9> 123 \7 <\10.\9> \3 \11() { \10 *\12; 123 / / \1(""); \12=\13("",0,0,
0,0); \2 0;
\7 <\8.\9> 123 \7 <\10.\9> \3 \11() { \10 *\12; 123 / / \1(""); \12=\13("",0,0,
0,0); \2 0;
programs equals
на решение ушло:
- 3 часа на поиск юнита регулярных выражений
- 30 мин на изучение libboost - как оказалось написано полностью на с++
- 5 часов на изучение и попытку написать врапер к pcre - потом решил делать все вручную без бибилиотек, будет больше практики с паскалем
- 3 часа на разработку алгоритма ( выбрал за основу теорию автоматов )
- 8 часов на его реализацию, пока не понял что утратил контроль над кодом, теория автоматов плохо реализуется на паскале, во всяком случае после 32 часового знакомсва с ним
- пришлось сделать откат кода на 5 часов назад
- 6.5 часов разработка нового алгоритма ( теорию автоматов пришлось заменить на императивный, а потом процедурный стиль )
- 12 часов на реализацию
- отладки почему-то опять не потребовалось ... может быть потому-что я разучился отлаживать ?
зы я фигею за человека, способного решить эту задачу в реале на чемпионате за 2 часа !!!
несколько пришлось отойти от класического задания, тк не умел делат несколько фишек :
1. тк не знаю как считать eof со стандартного ввода, данные прога считывает из файла pcre.c
2. тк не знаю как на паскале делать релизную и отладочную версии, то отладочная информация выдается на экран
3. тк встроенные средсва языка плохо работают ( или я в них плохо разобрался ) со строками, то из-за не эффективного алгоритма прога выходит за рамки времени при 10-30 кб исходниках, при норме в 1мб кода
ну естесно накопились вопросы:
- как посмотреть узкое место выполнения?
- на базе чего удобнее решать эту задачу: теория автоматов, data-driven или что то еще ?
- где можно что нить найти по теории автоматов и по теории формальных грамматик для ньюба?
