INFOMAN брой 17
/*
ЗМС'2000 (задачата е давана и в сп.Computer)
Задача А: Хакер
Задача: Дадени са списък от файлове и номера на тези от тях, които трябва да
се изтрият. Да се напише програма, която прави това с минимален брой команди
DEL <име на файл>
Могат да се използват маските ? (за заместване на един символ) и * (може да
стои само в края на ред и замества много символи)
Пълно условие: Пешо Хакера обича да хаква отдалечени компютри през telnet.
През ръцете му са минали какви ли не сървъри и операционни системи. Веднъж
Пешо успял в обикновена чат-сесия, под съвсем тъп предлог,да получи паролата
на наивен потребител на отдалечена мрежа.Въпросната мрежа била много странна.
Работела под операционна система,силно напомняща ДОС,която не поддържала дър-
вовидна структура на файловата система. Всички файлове (а те не били много -
2-3 хиляди) се намирали в една и съща директория. Имената на файловете се
състояли само от главни латински букви и цифри и имали дължина до 20 символа.
Освен това Пешо открил, че имала много странни права на достъп, позволяващи
изпълнение от промпта на не повече от 100 команди на сесия. Така поне било
за потребителя, от чието име се включвал. Пешо разгледал внимателно мрежата
и скоро открил, че тя е пълно дърво и че процесорът често се претоварва, по-
ради което всички, с изключение на администратора имали право на ограничен
брой команди. Пешо-хакера много се подразнил от това. Проучил още малко мре-
жата и скоро установил кои са жизненоважните й файлове, след което естестве-
но му се поискало да ги изтрие, та да отърве света от това недоносче.
Имало обаче проблем. Пешо ценял труда на обикновените потребители и ни-
кога не повреждал файловете им, като си позволявал да скапва само системните
файлове. Пешо разбрал, че командата за изтриване е DEL <маска> и че опера-
ционната система поддържа стандартните за маската символи ? и *. Първият за-
мествал произволен символ (буква или цифра), а вторият - последователност от
0,1, или повече символа. Символът * можел да се поставя само в края на маска-
та. Пешо бил мързелив човек, не обичал да пише много, бил ограничен от опера-
ционната система по отношение на броя разрешени команди на сесия, пък и си
падал маниак. Решил да покаже на администратора колко е умен и да изтрие сис-
темните файловете с минимален брой команди DEL.
За целта изготвил два отделни списъка. В първия записал имената на всич-
ки файлове по едно на ред и го запазил под името FILES.TXT. Във втория запи-
сал номерата на тези файлове от FILES.TXT, които трябва да бъдат изтрити,
като ги разделил с поне един интервал или знак за нов ред. След това седнал
да пише проста програмка, която да му подготви нужния скрипт (последовател-
ност от команди DEL, по една на ред) и да го запише във файла HACKER.OUT.
Проблемът е, че макар и велик хакер, Пешо е малко скаран с алгоритмите. По-
могнете му да си напише нужната програма!
Пример:
FILES.TXT DELETE.TXT HACKER.OUT
PRESLAV 1 3 4 5 6 9 DEL PROST
PRESLI DEL ?R?S?A*
BRESLAV
BRESLA
PRESLATA
PROST
PARASIT
PARAVAN
PRASKAM
PASCAL
Забележка: Следното решение е алчен алгоритъм,а задачата е NP-пълна. От това
става ясно, че то дава добро приближение до отговора, но решението не е на-
пълно точно. За съжаление не успях да дам контрапример.
Решение:За решаването на задачата ще използваме алчен алгоритъм и ще докажем,
че той е подходящ.
Без ограничение на общността ще наричаме БУКВИ всички символи, които
могат да се срещнат в името на файла.
МАСКА ще наричаме комбинация от букви (позволени за имената символи) и
специални символи ('?' и '*'). Всяка така получена маска може да отговаря на
няколко имена на файлове.В частност и на едно - когато в името няма специал-
ни символи. Възможно е и две маски да съвпадат ('ABC?????' и 'ABC*'.)
Ще обхождаме файловете, генерирайки всички маски (с изключение на повта-
рящите се, за да не губим излишна скорост.) Генерирането ще става като в
името по метода на Грей правим различните комбинации от букви и '?'. След
като опитаме тази маска, правим от нея маската вкючваща '*'.Тя е единствена,
т.к. '*' може да стои само на последно място и то трябва да е след последна-
та буква (ако между последната буква и '*' има '?', тази маска е еквивалент-
на на генерираната от нас). Т.е. видяхме, че по този начин се генерират
всички възможни различни маски.
От всички маски за всички файлове взимаме тази, която покрива най-много
файлове (тя, като рекорд, се повтаря във всички файлове, които покрива),
които трябва да бъдат изтрити, и нито един, който трябва да бъде запазен.
Трием с тази маска и повтаряме операцията наново, докато не изтрием всички
ненужни файлове.
Така показаният алчен алгоритъм работи, т.к. взимайки "най-масовата"
маска, ние си гарантираме, че нито един от изтритите с нея файлове не може
да генерира по-добра маска,т.е. в по-късен момент не може да създаде по-пъл-
ноценна команда.
Предстои кратко описание на използваните процедури:
int match( char* mask, char* name ) - проверява дали маската покрива името.
Връща 1 за да и 0 за не.
int files_left( void ) - проверява дали са останали файлове за триене. Връща
1 за да и 0 за не.
int count( char* mask ) - брои колко файла покрива маската. Ако покрива файл,
който не трябва да се трие, връща 0.
void put_star( char* mask, int ind ) - добавя '*' в края на маската
void put_question( char* name, int ind ) - генерира пермунтациите на букви и
'?' чрез алгоритъма на Грей.
void generate( char* name, int i ) - извиква генерирането на всички комбинации
за поредното име и индекса му.
Решението различава главни от малки букви, но може да се пригоди да не
го прави като просто по време на входа обръща всички в главни.
Мартин Русков
*/
#include <stdio.h>
#include <string.h>
#define MAX_FILES 100
#define FILE_LENGTH 30
char file[][FILE_LENGTH + 1] =
{ "PRESLAV", "PRESLI", "BRESLAV", "BRESLA", "PRESLATA", "PROST", "PARASIT", "PARAVAN", "PRASKAM", "PASCAL" };
char command[MAX_FILES][FILE_LENGTH + 1];
int files = 10;
int need[] = { 1, 0, 1, 1, 1, 1, 0, 0, 1, 0 }; /* files need to be deleted */
int deletes[MAX_FILES]; /* files properly deleted by the best mask of file i */
char del_cmd[MAX_FILES][FILE_LENGTH + 1]; /* command that achieves number in deletes */
int match( char* mask, char* name ) /* compares the mask to the filename */
{
int i = 0;
for(; mask[i] == name[i] || mask[i] == '?'; i++ );
if( i >= strlen( name ) || mask[i] == '*' )
{
for(;i < strlen( mask ) ;i++ )
if( mask[i] != '?' && mask[i] != '*' )
return 0;
return 1;
}
return 0;
}
int files_left( void )
{
int i;
int c = 0;
for( i = 1; i <= files; i++ )
if( need[i] == 1 ) c++;
return c;
}
int count( char* mask )
{
int i, c = 0;
for( i = 1; i <= files; i++ )
if( match( mask, file[i] ) )
if( need[i] == 1 || need[i] == -1 )
c++;
else
return 0;
return c;
}
void put_star( char* mask, int ind )
{
int i;
int del_temp;
i = strlen( mask );
mask[++i] = '*', mask[++i] = 0;
del_temp = count( mask );
if( del_temp > deletes[ind] )
{
deletes[ind] = del_temp;
strcpy( del_cmd[ind], mask );
}
mask[--i] = 0;
return;
}
void put_question( char* name, int ind ) /* gray algorithm */
{
int i = 0, p, j, n, del_temp;
char mask[FILE_LENGTH + 1];
n = strlen( name );
strcpy( mask, name );
do
{
p = 0, j = ++i;
while( !(j % 2) )
j /= 2, p++;
if( p < n )
if( mask[p] == '?' )
mask[p] = name[p];
else
mask[p] = '?';
del_temp = count( mask );
if( del_temp > deletes[ind] )
{
deletes[ind] = del_temp;
strcpy( del_cmd[ind], mask );
}
put_star( mask, ind );
}
while( p < n );
return;
}
void generate( char* name, int i )
{
char mask[FILE_LENGTH + 1];
deletes[i] = 1;
strcpy( del_cmd[i], name );
if( strlen( name ) < FILE_LENGTH )
{
strcpy( mask, name );
put_star( mask, i );
}
put_question( name, i );
return;
}
int main( void )
{
int i, t;
for(; files_left();)
{
memset( deletes, 0, sizeof( int ) * MAX_FILES );
for( i = 1; i <= files; i++ )
if( need[i] == 1)
generate( file[i], i );
for( i = 2, t = 1; i <= files; i++ )
if( deletes[t] < deletes[i] ) t = i;
printf( "DEL %s\n", del_cmd[t] );
for( i = 1; i <= files; i++ )
if( match( del_cmd[t], file[i] ) )
need[i] = -1;
}
return 0;
}