ACM ICPC 2006 Moscow Subregional Contest -- Problem C. Code Checker

[Mayor]

на всякий случай напомню условия 3й задачи:

ACM ICPC 2006­2007, 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 2006­2007, 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 или  что то еще ?
- где можно что нить найти по теории автоматов и по теории формальных грамматик для ньюба?
- какие языки более подходят для этой задачи?
- как можно решить 1мб исходников за 1 секунду?

[Dimka]

Во-первых, использован не классический Pascal, а его более развитая версия, в частности, библиотеки.

Во-вторых, в классическом Pascal программа не случайно начинается с заголовка

Код:

PROGRAM <имя программы>(Input, Output);

Поскольку Input и Output - текстовые файлы, по-умолчанию привязанные к стандартным потокам ввода-вывода. Таким образом, чтение входного потока до конца реализуется предельно просто:

Код:

WHILE NOT Eof(Input) DO
	BEGIN
		Read(<буфер чтения>);
		<прочие действия>
	END;

И, сколь мне известно, работу с этими двумя файлами поддерживает любая версия, любой компилятор Pascal.

В-третьих, я смотрю уже не первую тему в этом разделе, и постоянно удивляюсь, как можно судить об удобствах языков программирования, если не уметь проектировать (т.е. составлять внятные алгоритмы или модели)?

В частности, я не понял, зачем для этой задачи использовать какой-либо сторонний парсер?

Также я не понял, почему на Pascal плохо пишутся автоматы? У нас даже студенты легко пишут автоматы в курсе о компиляторах на любых алгоритмических и объектно-ориентированных языках, в частности, на Pascal.

В-чевёртых, при должной тренировке и грамотном разделении труда (в олимпиадной команде 3 участника) такая задача за пару часов решается, и тренер команды нашего университета, посмотрев эту тему, не нашёл в задаче ничего особо сложного.

Я бы решал задачу методом конвейерной обработки, определив в качестве интерфейса между частями конвейера:
- передаваемый символ,
- управляющие работой конвейера сигналы.
Это позволит разбить задачу на модули (которых, правда, нет в классическом Паскале, но которые, начиная с Turbo Pascal, поддерживаются многими современными компиляторами этого языка). Модули хорошо инкапсулированы, что позволяет вести их параллельную разработку разными участниками команды.

1) Основная программа организует циклические чтение символов из входного потока, которые посылает в конвейер обработки. Также по исчерпании потока в конвейер посылается сигнал о завершении работы.

2) На первом шаге работает анализатор блоков входной информации, который представляет собой простейший автомат, последовательно переходящий между состояниями "Ключевые слова", "Первая программа", "Вторая программа" в момент чтения разделительного символа #. Текущее состояние (текущий блок) и входной символ, кроме разделителя блоков, передаются далее по конвейеру для последующей обработки. Также в конвейер транслируется внешний сигнал о завершении работы и генерируется внутренний сигнал о смене режима работы (текущего блока).

3) На втором шаге работает фильтр, который анализирует входной поток, очищает его от комментариев, строковых констант и лишних пробельных символов, замещает любые пробельные символы на пробел и подаёт обработанные символы на выход. Для работы фильтра требуется буфер глубиной 2 символа, работающий по схеме FIFO, который принудительно выталкивается при получении сигналов заверешения работы и смены режима (текущего блока). На выход подаётся очередной символ и текущий блок обработки. Транслируются далее по конвейеру сигналы завершения работы и смены режима. Фильтр можно разложить на три последовательных фильтра: в начале комментариев, затем строковых констант и, в конце, пробельных символов. Каждый фильтр представляет собой простейший автомат, который опознаёт начало фильтруемой последовательности, и переходит в активное состояние; в нём он пропускает все символы, пока не будет опознан конец фильтруемой последовательности, после чего подаёт на выход замещающий последовательность символ (если нужно).

4) На третьем шаге действует анализатор идентификаторов. Для работы анализатора требуется буфер неопределённого размера, в котором посимвольно накапливается очередной идентификатор. По окончании идентификатора, либо по сигналу о смене режима, либо по сигналу о завершении работы выделенный идентификатор помещается в справочник идентификаторов (отдельный для каждого блока). В режимах первой и второй программ идентификаторы, не опознанные как ключевые слова, удаляются из буфера, но в соответствующем списке для каждой программы сохраняется, в каком порядке эти идентификаторы следовали. Ключевые слова остаются в буфере. После обработки очередного идентификатора буфер выталкивается далее в конвейер. Символы, не относящиеся к идентификаторам, подаются на выход, минуя буфер. На выход подаётся очередной символ, текущий блок обработки и списки позиций идентификаторов программ. Далее по конвейеру транслируются сигналы смены режима (текущего блока) и завершения работы.

5) На четвёртом шаге действует компаратор программ. Он накапливает в буфере неопределённого размера текст первой программы, а при начале получения текста второй программы производит посимвольное сравнение второй программы с текстом первой, выталкивая из буфера первой программы символы по схеме FIFO. Поскольку тексты очищены от специфических идентификаторов, строк и комментариев, сжаты по пробелам, они по условию задачи должны быть идентичны. Если встретится различие в символах, в выходной поток записывается NO, и работа программы завершается. Если поступил сигнал о завершении работы, а различий не встретилось, считается, что тексты программ идентичны и начинается сравнение идентификаторов. Списки идентификаторов проходятся параллельно, и каждый элемент одного списка сохраняется вместе с соответствующим элементом другого списка в справочник соответствия при условии, что элемента первого списка в справочнике ещё нет; если же элемент в справочнике находится, то проверяется, равна ли пара этого элемента справочника элементу из второго списка. Если равенство отсуствует, в выходной поток записывается NO, и работа программы завершается. Если списки порядка идентификаторов программ закончились, в выходной поток записывается YES, и работа программы завершается.

Конвейер в принципе можно реализовать и на едином буфере, но, по-моему, это менее удобно для фильтров. В качестве справочников можно использовать любую структуру данных, ориентированную на быстрый поиск, например, сбалансированное бинарное дерево. Можно исключить справочники идентификаторов для программ, сохраняя в списках сами идентификаторы - ограничение по памяти и ограничения входного файла позволяют это сделать, но процесс сравнения строк более долгий, чем сравнение указателей на элемент справочника. Поскольку сбалансированные бинарные деревья в библиотеках языка Pascal не всегда встречаются, а написание их достаточно трудоёмко, можно их заменить на более простые в программировании структуры, но это будет стоить уменьшения производительности программы.

[Mayor]

Код:

PROGRAM <имя программы>(Input, Output);
WHILE NOT Eof(Input) DO
	BEGIN
		Read(<буфер чтения>);
		<прочие действия>
	END;

И, сколь мне известно, работу с этими двумя файлами поддерживает любая версия, любой компилятор Pascal.

отлично -- просто у меня не было под рукой учебника, в справочнике такие тонкости видимо считаются общеизвестными и не упоминаются ...

В-третьих, я смотрю уже не первую тему в этом разделе, и постоянно удивляюсь, как можно судить об удобствах языков программирования, если не уметь проектировать (т.е. составлять внятные алгоритмы или модели)?

ну своего рода раш подход - смотришь на то, что можно на языке сделать после 20-50 часового знакомства и забываешь или продолжаешь изучение

В частности, я не понял, зачем для этой задачи использовать какой-либо сторонний парсер?

скорость написания программы, абстракция алгоритма

Также я не понял, почему на Pascal плохо пишутся автоматы? У нас даже студенты легко пишут автоматы в курсе о компиляторах на любых алгоритмических и объектно-ориентированных языках, в частности, на Pascal.

ну не знаю, теорию автоматов не читал, курс компиляторов тоже, с паскалем знаком 38 часов - наверное просто не уловил сути

хм а зачем теории автоматов, объектно-ориентированный язык?
в чем приемущества его использования?

В-чевёртых, при должной тренировке и грамотном разделении труда (в олимпиадной команде 3 участника) такая задача за пару часов решается, и тренер команды нашего университета, посмотрев эту тему, не нашёл в задаче ничего особо сложного.

там 11 задач на 5 часов, я почему то думал что эффективнее раскидать задачи по участникам, что бы они не мешали друг другу, чем заниматься организацией их работы ...

Я бы решал задачу методом конвейерной обработки, определив в качестве интерфейса между частями конвейера:
- передаваемый символ,
- управляющие работой конвейера сигналы.

я поначалу так же пытался, но код стал совершенно не поддерживаемый, алгоритм по ходу менялся тк не мог реализовать некоторые команды из-за слабого знания языка

а чем турбо паскаль так хорош?
он под линуксом есть?

2) На первом шаге работает анализатор блоков входной информации, который представляет собой простейший автомат, последовательно переходящий между состояниями "Ключевые слова", "Первая программа", "Вторая программа" в момент чтения разделительного символа #. Текущее состояние (текущий блок) и входной символ, кроме разделителя блоков, передаются далее по конвейеру для последующей обработки. Также в конвейер транслируется внешний сигнал о завершении работы и генерируется внутренний сигнал о смене режима работы (текущего блока).

когда код превысил 300 строк запутался в сигналах и переписал в императивном стиле 3 циклами : ключевые слова, 1 прога , 2 прога
до трансляции внешнего сигнала о завершении не додумался,
зато хотел сделать наоборот при получении # || eof внутренний блок расположенный за фильтром завершает работу и поднимает исключение, но не осилил работу с исключениями в паскале ...

3) На втором шаге работает фильтр, который анализирует входной поток, очищает его от комментариев, строковых констант и лишних пробельных символов, замещает любые пробельные символы на пробел и подаёт обработанные символы на выход. Для работы фильтра требуется буфер глубиной 2 символа, работающий по схеме FIFO, который принудительно выталкивается при получении сигналов заверешения работы и смены режима (текущего блока). На выход подаётся очередной символ и текущий блок обработки. Транслируются далее по конвейеру сигналы завершения работы и смены режима. Фильтр можно разложить на три последовательных фильтра: в начале комментариев, затем строковых констант и, в конце, пробельных символов. Каждый фильтр представляет собой простейший автомат, который опознаёт начало фильтруемой последовательности, и переходит в активное состояние; в нём он пропускает все символы, пока не будет опознан конец фильтруемой последовательности, после чего подаёт на выход замещающий последовательность символ (если нужно).

до использования буфера не додумался, хотел получить подобную функциональность  regexpr, потом хотел собрать на автоматах единый фильтр, но когда возникли языковые трудности, в итоге все превратилось 3 цикла: коментарии, строки, пробелы ... и есть у меня такое чувство, что это и есть узкое место программы ... чем бы проверить ....

4) На третьем шаге действует анализатор идентификаторов. Для работы анализатора требуется буфер неопределённого размера, в котором посимвольно накапливается очередной идентификатор. По окончании идентификатора, либо по сигналу о смене режима, либо по сигналу о завершении работы выделенный идентификатор помещается в справочник идентификаторов (отдельный для каждого блока).

сигналы не осилил, зато сжульничал вставив пробел в конец программ

В режимах первой и второй программ идентификаторы, не опознанные как ключевые слова, удаляются из буфера, но в соответствующем списке для каждой программы сохраняется, в каком порядке эти идентификаторы следовали. Ключевые слова остаются в буфере. После обработки очередного идентификатора буфер выталкивается далее в конвейер. Символы, не относящиеся к идентификаторам, подаются на выход, минуя буфер. На выход подаётся очередной символ, текущий блок обработки и списки позиций идентификаторов программ. Далее по конвейеру транслируются сигналы смены режима (текущего блока) и завершения работы.

сделал немного проще и опять сжульничал, по условиям \ символа в тексте после прохожнения фильтнов не было, так что опознаные слова и идентификаторы заменял на \порядковый_номер, неопознаные на \последний_номер+1 и вносил после этого в конец списка единого для ключевых слов и идентификаторов, что наверное несколько расходится с теорией компиляции - зато работает быстрее - и не нада сверять потом буфера программ с отдельными списками
при переходе к следующей проге опять таки ничего не удалял, о просто конец списка устанавливал на последнее ключевое слово

5) На четвёртом шаге действует компаратор программ. Он накапливает в буфере неопределённого размера текст первой программы, а при начале получения текста второй программы производит посимвольное сравнение второй программы с текстом первой, выталкивая из буфера первой программы символы по схеме FIFO. Поскольку тексты очищены от специфических идентификаторов, строк и комментариев, сжаты по пробелам, они по условию задачи должны быть идентичны. Если встретится различие в символах, в выходной поток записывается NO, и работа программы завершается. Если поступил сигнал о завершении работы, а различий не встретилось, считается, что тексты программ идентичны и начинается сравнение идентификаторов. Списки идентификаторов проходятся параллельно, и каждый элемент одного списка сохраняется вместе с соответствующим элементом другого списка в справочник соответствия при условии, что элемента первого списка в справочнике ещё нет; если же элемент в справочнике находится, то проверяется, равна ли пара этого элемента справочника элементу из второго списка. Если равенство отсуствует, в выходной поток записывается NO, и работа программы завершается. Если списки порядка идентификаторов программ закончились, в выходной поток записывается YES, и работа программы завершается.

а вот тут немного не понял, помоему
printf ... for +++
и
... print for +++
окажутся идентичными
так что каждый элемент списка должен еще и содержать место ид и ключевого слова в тексте
но тк я сжульничал на 4 этапе, то на 5 требуется только сравнить тексты программ
но в принципе эффективность 4+5 этапов по моим расчетам одинакова

Конвейер в принципе можно реализовать и на едином буфере, но, по-моему, это менее удобно для фильтров.

не то слово, вроде огромные трудности в реализации

В качестве справочников можно использовать любую структуру данных, ориентированную на быстрый поиск, например, сбалансированное бинарное дерево. Можно исключить справочники идентификаторов для программ, сохраняя в списках сами идентификаторы - ограничение по памяти и ограничения входного файла позволяют это сделать, но процесс сравнения строк более долгий, чем сравнение указателей на элемент справочника. Поскольку сбалансированные бинарные деревья в библиотеках языка Pascal не всегда встречаются, а написание их достаточно трудоёмко, можно их заменить на более простые в программировании структуры, но это будет стоить уменьшения производительности программы.

во во второе по вероятности узкое место программы, после фильтров конечно...

зы правильный алгоритм у тебя уже есть, на форуме возникло мнение, что со знанием теории компиляции, при использованиии regexpr можно написать прогу за 30 минут, без регвыражений за 1 час

рискнешь?

зыы сколько времени ушло на разработку алгоритма?

[Dimka]

смотришь на то, что можно на языке сделать после 20-50 часового знакомства

Имхо, прежде, чем что-то делать на новом языке, нужно уметь делать на старом; а если никакие языки ещё не знакомы, то основательно познакомиться хоть с каким-нибудь. Посему подход меня удивляет. Удивляет тем, что никаких объективных результатов он не даёт, тем не менее используется. Если только в порядке развлечения. В таких условия что-либо серьёзно обсуждать становится совершенно бессмыслено, посему и наблюдается тишина в темах.

скорость написания программы, абстракция алгоритма

Какой смысл говорить о скорости, когда ещё не решён вопрос об алгоритме? Чтобы применять абстракции, нужно точно знать, каким образом эти абстракции можно интерпретировать, к чему прикладывать, а каким и к чему нельзя. Т.е. в начале составляется алгоритм, а затем уже принимается специальное решение об использовании парсера, если он в этот алгоритм встраивается. Я же наблюдаю парсер первым пунктом твоего плана действий. Видимо, логика такая: если обработка текста, то сперва нужен парсер, а потом разберёмся с решаемой задачей...

Кроме того, универсальный парсер будет гораздо "тяжелее" на подъём и в работе, нежели специализированный автомат для такой узкой задачи. Обращаю внимание, что ты решаешь не класс задач, а конкретную задачу. В этом, имхо, заключается недостаток международных олимпиад по программированию - качество страдает.

хм а зачем теории автоматов, объектно-ориентированный язык?
в чем приемущества его использования?

Когда автомат один - никакого преимущества. Если же речь идёт о системе взаимодействующих автоматов, то удобство ООП или хотя бы модульного подхода становится очевидным.

там 11 задач на 5 часов, я почему то думал что эффективнее раскидать задачи по участникам, что бы они не мешали друг другу, чем заниматься организацией их работы ...

Некоторые задачи - да, некоторые - нет.

я поначалу так же пытался, но код стал совершенно не поддерживаемый, алгоритм по ходу менялся тк не мог реализовать некоторые команды из-за слабого знания языка

Так это не проблема языка и не проблема незнания языка, а проблема навыков и профессиональной культуры разработчика. Программирование - это ж не "топтание кнопок", это инженерная дисциплина, в рамках которой давно уже выработан ряд мер по управлению сложностью разработки. Проще говоря, когда не знаешь, что искать в языке, тогда и кажется, будто язык плох. Хотя все языки в рамках той или иной парадигмы программирования имеют сходные элементы, обусловленные парадигмой.

а чем турбо паскаль так хорош?
он под линуксом есть?

По сравнению с чем хорош? Эта ветка языка, осуществившая перевод Pascal с сугубо учебного языка в язык, пригодный для промышленной разработки программ. Работает под DOS. У Free Pascal есть режим совместимости и поддержка всех библиотек Turbo Pascal (вплоть до графических под svgalib).

когда код превысил 300 строк запутался в сигналах и переписал в императивном стиле 3 циклами : ключевые слова, 1 прога , 2 прога
до трансляции внешнего сигнала о завершении не додумался,
зато хотел сделать наоборот при получении # || eof внутренний блок расположенный за фильтром завершает работу и поднимает исключение, но не осилил работу с исключениями в паскале ...

Потому что начать надо было с наброска общей схемы работы программы и с графов переходов для автоматов, а не с кодирования.

Исключения же появились лишь в Object Pascal.

сделал немного проще и опять сжульничал, по условиям \ символа в тексте после прохожнения фильтнов не было, так что опознаные слова и идентификаторы заменял на \порядковый_номер, неопознаные на \последний_номер+1 и вносил после этого в конец списка единого для ключевых слов и идентификаторов, что наверное несколько расходится с теорией компиляции - зато работает быстрее - и не нада сверять потом буфера программ с отдельными списками

Какой смысл вставлять в код номера, если их потом опять придётся парсить и анализировать? В чём же здесь простота? Тогда уж выгоднее вместо номера вставить 2-хбайтовый код - он фиксированного размера и более прост в обработке... Хотя в этой конкретной задаче вообще нет смысла оставлять идентификаторы в исходном коде (кроме заведомо одинаковых ключевых слов).

так что каждый элемент списка должен еще и содержать место ид и ключевого слова в тексте

Невозможно. Идентификаторы могут быть различной длины, поэтому абсолютные их позиции в тексте могут различаться (если идентификаторы не удалять). Если так надо, проще оставлять в тексте сигнальные символы о наличии очередного идентификатора.

Хотя, поскольку тексты обрабатываются посимвольно, сравнение одинаковости кода и сопоставление идентификаторов может происходить параллельно по мере поступления новой порции кода или прочтения очередного идентификатора.

Если рассматривать условие задачи с формальной точки зрения (т.е. не считая язык Db языком, поскольку не задана его грамматика, а считая его набором произвольных символов), ты прав. Но в более-менее реальном языке идентификатор не может оказаться в произвольном месте, как ты это в своём примере показал.

на форуме возникло мнение, что со знанием теории компиляции, при использованиии regexpr можно написать прогу за 30 минут, без регвыражений за 1 час

рискнешь?

На каком форуме? Причём тут RegExp? И какое отношение имеет скорость разработки к обсуждаемым алгоритмам (основной тематике раздела)?

[Алексей++]

блин, ничего умного не скажу, но , действительно, чёррррррт побери, при чём тут скорость НАПИСАНИЯ программ ? Причём человек чуть ли не во всех своих многочисленных темах говорит про это. Создалось впечатление, что Mayor1 пишет программы не для реального использования, а только на спор с кем то.

[Mayor]

блин, ничего умного не скажу, но , действительно, чёррррррт побери, при чём тут скорость НАПИСАНИЯ программ ? Причём человек чуть ли не во всех своих многочисленных темах говорит про это. Создалось впечатление, что Mayor1 пишет программы не для реального использования, а только на спор с кем то.

для реального использования были пока только 2: маска телефоного номера - фронтенд для программирования мини-атс, gsm шлюз - для оценки экономической целесобразности его установки - в принципе поставленными задачами справились ...

остальные программы, чисто чтобы потестить незнакомый язык программирования , естественно они берутся из диапазона задачек для первокурсников - всеросийских межвузовских олимпиад, в зависимости от степени освоения языка

оценивать приходится по:
- времени изучения языка
- времени разработки алгоритма
- времени написания программы
- объема исходников
- временной сложности алгорима О лучше О*лнО лучше О**2 и тп
- способности поддерживать код для расширения условий задачи

алгоритмы вынужден разрабатывать в ленивом стиле, тк на этапе разработки алгоритма не уверен, смогу ли реализовать отдельные элементы на текущем знании языка, как следствие того что не смогу является:
- смена всего или части алгоритма
- смена языка программирования

[Алексей++]

а что означает
>>О лучше О*лнО лучше О**2 и тп

[Mayor]

а если никакие языки ещё не знакомы, то основательно познакомиться хоть с каким-нибудь.

не вижу смысла знакомится с вероятно бесперспективным языком, пока не будет доказана на реальных примерах его эффективность

В таких условия что-либо серьёзно обсуждать становится совершенно бессмыслено, посему и наблюдается тишина в темах.

скорее это вопрос целевой аудитории, если язык никому не известен или задача кажется слишком сложной или занудной для реализации

Кроме того, универсальный парсер будет гораздо "тяжелее" на подъём и в работе, нежели специализированный автомат для такой узкой задачи. Обращаю внимание, что ты решаешь не класс задач, а конкретную задачу. В этом, имхо, заключается недостаток международных олимпиад по программированию - качество страдает.

пожалуй в качестве ответа будет цитата:

Незная ничего о теории компиляции врядли кто решит задачу на прасинг сложнее чем парсинг и вычисление простого арифметического выражения...

Все эти соревнования ориентированны скорее на демонстрацию знаний/навыков/умений, а не как не сообразительности, находчевости, умения рещать задачи с которыми никогда не сталкивался. Побеждает тот, кто знает как решать (т.е. знает подходы к решению) большего числа типов задач...

А так, то что вы привели замеры времени - изучал то, пробовал другое...
Читать условие было влом, но судя по входным/выходным данным там лесический разбор с последующим сравнением порядка следования классов лексем...
Хорошо зная регулярные выражения и тот самый юнит вы бы решили эту задачу менее чем за полчаса.
Без регулярных выражений, с помощью конечного автомата - около часа или два - если где-то запутатесь и прийдется отлаживать...

с чем я в принципе согласен

Так это не проблема языка и не проблема незнания языка, а проблема навыков и профессиональной культуры разработчика. Программирование - это ж не "топтание кнопок", это инженерная дисциплина, в рамках которой давно уже выработан ряд мер по управлению сложностью разработки. Проще говоря, когда не знаешь, что искать в языке, тогда и кажется, будто язык плох. Хотя все языки в рамках той или иной парадигмы программирования имеют сходные элементы, обусловленные парадигмой.

для меня тот язык плох, который плохо осваивается...
пока задача интересна и легка, не ограничено время на ее решение, не к чему долбить по ней тяжелой артилерией, можно на ней потестить какой нить новый язык, наверное это просто вопрос переизбытка времени ...

Потому что начать надо было с наброска общей схемы работы программы и с графов переходов для автоматов, а не с кодирования.

да но для этого лушче сначало почитать, что нить по теории автоматов, а то все мои познания в ней сводятся к тому, как  один мегаджедайский программер в аське  полчаса объяснял как на ее базе построен авторизатор, тогда я конечно ничего не понял, но потом тренеруясь на расчете простых символьных выражений ее использовал, что в свою очередь пригодилось для этой задачи ...
универсальный парсер на такой базе мне конечно же не создать

Какой смысл вставлять в код номера, если их потом опять придётся парсить и анализировать?

парсить потом уже ничего не придется, потом только останется побайтово сравнить 2 строки, если есть различия то программы не совпадают, иначе совпадают

В чём же здесь простота? Тогда уж выгоднее вместо номера вставить 2-хбайтовый код - он фиксированного размера и более прост в обработке...

проблемма в том, что я не знал как вписать в сроку байт код из целой переменной, а как вписать символьное значение целой переменной знал, вот так и пришлось реализовать

Хотя в этой конкретной задаче вообще нет смысла оставлять идентификаторы в исходном коде (кроме заведомо одинаковых ключевых слов).

а как тогда привязать место расположение индификатра к тексту программы?

Хотя, поскольку тексты обрабатываются посимвольно, сравнение одинаковости кода и сопоставление идентификаторов может происходить параллельно по мере поступления новой порции кода или прочтения очередного идентификатора.

слишком сложно реализовать, потому что потребуется парсить одновременно обе программы

Если рассматривать условие задачи с формальной точки зрения (т.е. не считая язык Db языком, поскольку не задана его грамматика, а считая его набором произвольных символов), ты прав. Но в более-менее реальном языке идентификатор не может оказаться в произвольном месте, как ты это в своём примере показал.

почему не может?

Код:

if (( a + b )>0) print f

if (a( + b )>0) print f

в первом случае + инфиксная функция над 2мя индефикаторами

во втором случае а префиксная функция высшего порядка над 2мя
индефикаторами ( унарной функцией + и b )

естественно в случае такого языка как хаскель, когда допускается отделять функцию от параметров и параметры пробелами

И какое отношение имеет скорость разработки к обсуждаемым алгоритмам (основной тематике раздела)?

такое что участник форума может потратить полчаса, час выходного времени на реализацию интересного алгоритма, а вот сутки уже врядли

[Mayor]

а что означает
>>О лучше О*лнО лучше О**2 и тп

временая сложность алгоритма, Ахо Ульман  алгоритмы и структуры данных

функция которая выводит гипотетическое время выполнения программы в зависимости от объема входных данных

на практике:

для О:
если на 1000 элементах программа выполнялась 10 секунд, то на 10000 элементов она будет  выполняться 100 секунд

для О**2
если прога на 100 элементах выполнялась 20 секунд, то на 1000 она будет выполняться  2000 секунд

в качестве конкретного примера:
сортировка пузырьками = О**2
поиск в несортированых данных = О
быстрая сортировка = О*lnO
поиск в сортированных данных лнО
поиск данных в словаре = 1 ( не зависит от размера словаря)

[Алексей++]

>>такое что участник форума может потратить полчаса, час выходного
>>времени на реализацию интересного алгоритма, а вот сутки уже врядли

- не правда твоя. Я лично сидел сутками (и неделями) над интересной с моей точки зрения задачей. А твой подход - "аа, не получается за пол часа, ну нафик". В корне неверный подход ИМХО

[Mayor]

- не правда твоя. Я лично сидел сутками (и неделями) над интересной с моей точки зрения задачей. А твой подход - "аа, не получается за пол часа, ну нафик". В корне неверный подход ИМХО

ну по чему же если бы повнимательнее посмотрел сначала то заметил, что для этой задачи я :
более 38 часов изучал и практиковался на паскале
около 10 часов на разработку алгоритмов решения
около 20 часов на их реализацию

потому что эта задача на мой взгляд интересная ... вот только почему при готовом более эффективном чем мой алгоритме ее решения никто не пытается переписать \ улучшить мой вариант?

[Алексей++]

>>более 38 часов изучал и практиковался на паскале
ну, скажем так, это не считается, потому что учить язык можно вечно, а к решению задачи (написать алгоритм) изучение языка мало относится

>>вот только почему при готовом более эффективном чем мой алгоритме ее
>>решения никто не пытается переписать \ улучшить мой вариант?
а кто то должен был это сделать ? И , кроме того, раз (это написано в твоём вопросе) есть "готовый более эффективный алгоритм" - зачем тогда кому то улучшать твой вариант ? как-то загадочно говоришь...

[Dimka]

оценивать приходится по:
- времени изучения языка
- времени разработки алгоритма
- времени написания программы
- объема исходников
- временной сложности алгорима О лучше О*лнО лучше О**2 и тп
- способности поддерживать код для расширения условий задачи

1) Любые языки изучаются одинаковое количество времени, поскольку набор базовых концепций в них примерно одинаков. Разное время может занимать изучение сервисных библиотек для языков. Т.е. пункт либо ничего не характеризует, либо даёт обратную характеристику: чем богаче библиотеки, чем больше времени уходит на их изучение, тем, получается, хуже язык.

2) Время разработки алгоритма никак не характеризует алгоритмический язык программирования, поскольку алгоритмический (операционный, императивный) язык - лишь средство программирования алгоритма. Т.е. пункт никак не характеризует язык программирования.

3) Львиную долю экономии времени обеспечивает не сам язык, а развитость среды разработки на нём. Скажем, MS Visual Studio удобнее при разработке программ, чем обычный текстовый редактор. И разработка программы на C++ на Visual Studio может идти быстрее, чем написание программы на JScript в текстовом редакторе, хотя синтаксис последнего проще, и количество базовых концепций у него меньше. Т.е. пункт ничего не характеризует.

4) Объём исходников не играет роли в развитой среде разработки, поскольку много кода генерируется автоматически.

5) Временная сложность алгоритма также не связана с языком программирования, как и время разработки алгоритма (см пункт 2).

6) Способность поддерживать код для расширения условий задачи зависит от программиста, а не от языка программирования. Грамотное кодирование на любом языке даст легко поддерживаемый код. Неграмотное кодирование даже на самом гибком языке программирования даст нечитаемую программу, которую придётся переписывать "с нуля".

не вижу смысла знакомится с вероятно бесперспективным языком, пока не будет доказана на реальных примерах его эффективность

Во-первых, что такое бесперспективный язык? Языки можно классифицировать по поддерживаемым ими парадигмам программирования, можно классифицировать по "модности" (т.е. количеству их использующих разработчиков и развитости их библиотек). Во-вторых, как можно судить о "вероятности" (бес)перспективности языка, если его не знать?

скорее это вопрос целевой аудитории, если язык никому не известен или задача кажется слишком сложной или занудной для реализации

В том-то и дело, что задачи разработки алгоритма не ставилось. Почему-то ставилась задача кодирования некоего неизвестного решения данной задачи. Т.е. наблюдается провал в части проектирования решения. Поскольку решения могут быть различны, нет смысла сравнивать языки до тех пор, пока не будут сопоставлены решения и выбрано лучшее. Только после этого можно решать задачу сопоставления различных стилей кодирования.

Хорошо зная регулярные выражения и тот самый юнит вы бы решили эту задачу менее чем за полчаса.
Без регулярных выражений, с помощью конечного автомата - около часа или два - если где-то запутатесь и прийдется отлаживать...

Обоснование этого мнения? Если согласен, то, видимо, знаешь обоснование.

Читать условие было влом

Кстати, тоже характеризует. "Не читал, но скажу."

для меня тот язык плох, который плохо осваивается...

Все языки хорошо осваиваются, если понимать основные принципы их устройства.

да но для этого лушче сначало почитать, что нить по теории автоматов, а то все мои познания в ней сводятся к тому, как  один мегаджедайский программер в аське  полчаса объяснял как на ее базе построен авторизатор, тогда я конечно ничего не понял

Но ты выше заявил, что Pascal плохо подходит к написанию автоматов. Как такое можно заявлять, если ты не знаешь, что такое автомат, и как его программировать?

парсить потом уже ничего не придется, потом только останется побайтово сравнить 2 строки, если есть различия то программы не совпадают, иначе совпадают

Если под номерам понимать порядковые номера первого вхождения идентификатора в коде, то согласен. Единственно, требуется сохранение этих номеров, если справочник идентификаторов не представляет собой неотсортированный последовательный список или массив. Но если имеется список идентификаторов в порядке их вхождения в коде, то номера будут избыточны, достаточно своевременно подавать сигнал о необходимости сравнения очередной пары идентификаторов.

проблемма в том, что я не знал как вписать в сроку байт код из целой переменной, а как вписать символьное значение целой переменной знал, вот так и пришлось реализовать

например, так:

Код: (Pascal)

VAR
   X: Word;
   S: STRING;
<...>
S := S + Chr(Hi(X)) + Chr(Lo(X));

Где функция Chr возвращает символ с кодом аргумента, а функции Hi и Lo возвращают старший и младший байты двухбайтового слова (беззнакового 2-хбайтового целого).

а как тогда привязать место расположение индификатра к тексту программы?

А смысл? Если тексты программ одинаковы, и речь идёт о более-менее реальном языке программирования, то в текст программы должен содержать одинаковые синтаксические конструкции, в которых место положения идентификаторов строго определено. Если это разные синтаксические конструкции, то тексты будут разными. Если это одинаковые синтаксические конструкции, то идентификаторы в них будут расположены в одинаковых местах, следовательно, конкретное место положения очередного идентификатора не имеет никакого значения для решения задачи.

слишком сложно реализовать, потому что потребуется парсить одновременно обе программы

Не парсить, а сравнивать. Просто вторая программа сразу поступает со входа, а первая - из накопительного буфера, где она была до того сохранена.

почему не может?

Код:

if (( a + b )>0) print f

if (a( + b )>0) print f

в первом случае + инфиксная функция над 2мя индефикаторами
во втором случае а префиксная функция высшего порядка над 2мя
индефикаторами ( унарной функцией + и b )

Убедил. Тогда достаточно оставлять в тексте первой программы сигнальные символы вроде \ или # о том, что в этом месте находится очередной идентификатор. И к моменту обнаружения во второй программе очередного идентификатора в первой программе должен быть обнаружен сигнальный символ. Если его нет, то программы различны, иначе сравнивается очередная пара идентификаторов.

такое что участник форума может потратить полчаса, час выходного времени на реализацию интересного алгоритма, а вот сутки уже врядли

Ты недооцениваешь участников форума Если требуется разработать (а не реализовать) очень интересный с какой-либо точки зрения алгоритм, времени найдётся, сколько нужно

вот только почему при готовом более эффективном чем мой алгоритме ее решения никто не пытается переписать \ улучшить мой вариант?

А смысл? Интересен алгоритм - принципиальное решение задачи, а не программный код. Программный код многие писать умеют - это совершенно неинтересно.

[Mayor]

А смысл? Интересен алгоритм - принципиальное решение задачи, а не программный код. Программный код многие писать умеют - это совершенно неинтересно.

ну ладно узкие места вроде объяснили, когда будет достаточно свободного времени попробую обойти 100кб по временному ограничению на mawk, или почитаю теорию автоматов и перепишу полностью на автоматах на паскале

[.]

Из условия следуют упрощения, которые можно сделать дополнениями:
1) любые строковые константы идентичны
2) любые комментарии и пробельные идентичны - почти очевидное условие.
3а) (если можно написать эту программу на Си) объём ввода не занимает больше 4 Mib - читаем всё, сначала до конца, там где надо расставляя \0. Тогда новой памяти для расположения строковых названий выделяться не будет. Для С++ смысла не вижу.
3б) единственное, что нужно сохранить в итоге - это названия вызываемых функций, если мы принимаем п. 1. В этом случае можно читать ввод по одному символу/буферу

алгоритмы решения следующие:
Первый вариант:
Этап 1:
идём по одному символу, кладя обе программы в 2 разные древовидные структуры (благо Си, как и остальные языки) легко помещаются. goto - единственный оператор, который может "всё сломать". Насколько я понял, его наличие не предпологается.
Этап 2:
сравнение 2х деревьев с учетом типа переменной. "одинаковые" индексы переменных запоминаем в отдельном буфере.

Второй вариант:
идём по одному символу. кладём первую программу в дерево. Проходя по второй программе _сразу_ сравниваем.

Возможные затруднения в реализации сравнения:
1) перестановка _независимых_ предложений
{a=3; b=1;}  эквивалентно {b=1;a=3;}
{a=3; b=a + 1;}  не может быть переставлено местами эквивалентно {b=1;a=3;}

Описание синтаксического дерева просто, приведенная выше информация является достаточной для того, чтобы приступить к кодированию. На реализацию этого алгоритма у меня ушло ... 10 минут.

[Dimka]

древовидные структуры (благо Си, как и остальные языки) легко помещаются. goto - единственный оператор, который может "всё сломать".

Дерево синтаксического разбора и обход дерева в порядке выполнения операторов - совершенно разные вещи. Goto прекрасно помещается в само дерево, но ломает порядок его обхода. В данной задаче обход (т.е. исполнение программы) не требуется, нужно лишь определить совпадение структуры. Поэтому обозначенной тобою проблемы в данном случае просто нет.