Есть два набора строк.
Белый список:
bhdgffhfa
aggjjaaga
hbefebhfi
dbceeabih
ihifdbhhf
djacfjbae
ibjbeigac
jaffigdad
aaaaaaaaj
dgifecchi
dcbhgjaaf
eedfbcedb
aaaaaaabf
beaajbihg
aaaaaaaag
eacccdjeh
aaaaaaaad
hehcijfhc
aaaaaaaaa
aaaaaaabc
jfdhdeice
И черный список:
aaaaaaaai
ehigcbgjd
hgjdeajec
aaaaaaabe
haebgiggc
aaaaaaaba
aaaaaaaaf
bfjhehbcf
diieabefh
jhjcaeead
ifbjdgibf
dddbgcgai
bbcafhcif
hfjciccbi
fdbgidjdj
aaaaaaabb
jhdibgbfj
cfjbaijad
bhgjfacgi
ehhieihhh
abijjabda
Нужно написать регулярное выражение, не длинее 60 символов, способное различать из какого набора взята строка.
Например, если на входе программе дано aaaaaaaaa, программа должна решить, что это строка из белого списка.
UPDATE: https://www.hackerrank.com/contests/regular-expresso/challenges/match-maker
Ответ
Возможно получение двух решающих паттернов: по попаданию в белый список (whitelist) и в чёрный список (blacklist).
Паттерн белого списка: /ce|ag|fe|ff|aaj|cd|dc|aad|abc|abf|acf|bei|bhh|cij|aaaaaaaaa/
Паттерн чёрного списка: /bg|ai|bb|ie|jc|jd|bd|cg|jh|aba|abe|aaaaaaaaf/
Паттерн чёрного списка короче и допускает сжатие до 37 символов:
/ai|b[bdg]|cg|ie|j[cdh]|ab[ae]|a{8}f/
Но использование двух паттернов позволяет провести диагностику.
Решающие паттерны набираются из уникальных для соответствующего списка токенов по оптимизированному "жадному" алгоритму.
К рассмотрению приняты двух- и трёхсимвольные токены, а также 9-символьные токены, начинающиеся с "aaaaaaa".
Программа на языке PHP:
$whitelist = "
bhdgffhfa
aggjjaaga
hbefebhfi
dbceeabih
ihifdbhhf
djacfjbae
ibjbeigac
jaffigdad
aaaaaaaaj
dgifecchi
dcbhgjaaf
eedfbcedb
aaaaaaabf
beaajbihg
aaaaaaaag
eacccdjeh
aaaaaaaad
hehcijfhc
aaaaaaaaa
aaaaaaabc
jfdhdeice
";
$blacklist = "
aaaaaaaai
ehigcbgjd
hgjdeajec
aaaaaaabe
haebgiggc
aaaaaaaba
aaaaaaaaf
bfjhehbcf
diieabefh
jhjcaeead
ifbjdgibf
dddbgcgai
bbcafhcif
hfjciccbi
fdbgidjdj
aaaaaaabb
jhdibgbfj
cfjbaijad
bhgjfacgi
ehhieihhh
abijjabda
";
//Генератор решающих токенов
function tokens_gen($whitelist, $blacklist){
$white_tokens = [];
$black_tokens = [];
for($i=-1; $i< 12; $i++){
$c = ($i<0) ? "" : chr(ord("a")+$i); // сначала двухсимвольные токены
$c = ($i==10) ? "aaaaaaa" : $c; // последними - токены c "aaaaaaa"
for($ord2=ord("a"); $ord2 <= ord("j"); $ord2++){
for($ord3=ord("a"); $ord3 <= ord("j"); $ord3++){
$ccc = $c.chr($ord2).chr($ord3);
$pm_white = preg_match("/$ccc/", $whitelist);
$pm_black = preg_match("/$ccc/", $blacklist);
if(($pm_white==1) && ($pm_black==0)) array_push($white_tokens, $ccc);
if(($pm_black==1) && ($pm_white==0)) array_push($black_tokens, $ccc);
}
}
}
return [$white_tokens, $black_tokens];
}
// "Жадный" рекурсивный отбор токенов
function greedy($tokens, $list, $pat=""){
$tokens_new = [];
$ppp_max = "";
foreach($tokens as $ppp){
$p = ($pat=="")? $ppp: "$pat|$ppp";
$sum = 0;
foreach($list as $str) $sum += preg_match("/$p/", $str);
if($sum > $sum_max){
$ppp_max = $ppp;
$sum_max = $sum;
}
if($sum > 0) array_push($tokens_new, $ppp);
}
if($ppp_max == "") return $pat;
$pat = ($pat=="")? $ppp_max: "$pat|$ppp_max";
$left = 'display: block; float: left; ';
printf("Токенов:%d", count($tokens));
printf(" Строк, всего:%d по токену: $sum_max ", count($list));
print("Токен: $ppp_max Паттерн: $pat
");
$list = preg_grep("/$ppp_max/", $list, PREG_GREP_INVERT);
$pat = greedy($tokens_new, $list, $pat);
return $pat;
}
// Перевод контрольных строк в массивы
$white = explode(chr(10), trim($whitelist));
foreach($white as &$w) $w=trim($w);
$black = explode(chr(10), trim($blacklist));
foreach($black as &$b) $b=trim($b);
$white_black = array_merge($white, $black);
// Получение решающих токенов
list($white_tokens, $black_tokens) = tokens_gen($whitelist, $blacklist);
// Получение жадных паттернов
print("Жадные паттерны:
");
$white_pattern = greedy($white_tokens, $white);
$black_pattern = greedy($black_tokens, $black);
//$black_pattern = 'ai|b[bdg]|cg|ie|j[cdh]|ab[ae]|a{8}f';
print("
white_pattern = $white_pattern
black_pattern = $black_pattern
");
$left = 'display: block; float: left; ';
print("
Проверка:
");
foreach($white_black as $str){
$in_white = preg_match("/$white_pattern/",$str);
$in_black = preg_match("/$black_pattern/",$str);
print("
$str:$in_white $in_black");
}
Результаты:
Жадные паттерны:
Токенов:108 Строк, всего:21 по токену: 3 Токен: ce Паттерн: ce
Токенов:108 Строк, всего:18 по токену: 2 Токен: ag Паттерн: ce|ag
Токенов:88 Строк, всего:16 по токену: 2 Токен: fe Паттерн: ce|ag|fe
Токенов:81 Строк, всего:14 по токену: 2 Токен: ff Паттерн: ce|ag|fe|ff
Токенов:67 Строк, всего:12 по токену: 2 Токен: aaj Паттерн: ce|ag|fe|ff|aaj
Токенов:49 Строк, всего:10 по токену: 1 Токен: cd Паттерн: ce|ag|fe|ff|aaj|cd
Токенов:41 Строк, всего:9 по токену: 1 Токен: dc Паттерн: ce|ag|fe|ff|aaj|cd|dc
Токенов:33 Строк, всего:8 по токену: 1 Токен: aad Паттерн: ce|ag|fe|ff|aaj|cd|dc|aad
Токенов:28 Строк, всего:7 по токену: 1 Токен: abc Паттерн: ce|ag|fe|ff|aaj|cd|dc|aad|abc
Токенов:26 Строк, всего:6 по токену: 1 Токен: abf Паттерн: ce|ag|fe|ff|aaj|cd|dc|aad|abc|abf
Токенов:24 Строк, всего:5 по токену: 1 Токен: acf Паттерн: ce|ag|fe|ff|aaj|cd|dc|aad|abc|abf|acf
Токенов:22 Строк, всего:4 по токену: 1 Токен: bei Паттерн: ce|ag|fe|ff|aaj|cd|dc|aad|abc|abf|acf|bei
Токенов:18 Строк, всего:3 по токену: 1 Токен: bhh Паттерн: ce|ag|fe|ff|aaj|cd|dc|aad|abc|abf|acf|bei|bhh
Токенов:11 Строк, всего:2 по токену: 1 Токен: cij Паттерн: ce|ag|fe|ff|aaj|cd|dc|aad|abc|abf|acf|bei|bhh|cij
Токенов:5 Строк, всего:1 по токену: 1 Токен: aaaaaaaaa Паттерн: ce|ag|fe|ff|aaj|cd|dc|aad|abc|abf|acf|bei|bhh|cij|aaaaaaaaa
Токенов:118 Строк, всего:21 по токену: 5 Токен: bg Паттерн: bg
Токенов:118 Строк, всего:16 по токену: 2 Токен: ai Паттерн: bg|ai
Токенов:82 Строк, всего:14 по токену: 2 Токен: bb Паттерн: bg|ai|bb
Токенов:75 Строк, всего:12 по токену: 2 Токен: ie Паттерн: bg|ai|bb|ie
Токенов:67 Строк, всего:10 по токену: 2 Токен: jc Паттерн: bg|ai|bb|ie|jc
Токенов:53 Строк, всего:8 по токену: 2 Токен: jd Паттерн: bg|ai|bb|ie|jc|jd
Токенов:37 Строк, всего:6 по токену: 1 Токен: bd Паттерн: bg|ai|bb|ie|jc|jd|bd
Токенов:24 Строк, всего:5 по токену: 1 Токен: cg Паттерн: bg|ai|bb|ie|jc|jd|bd|cg
Токенов:18 Строк, всего:4 по токену: 1 Токен: jh Паттерн: bg|ai|bb|ie|jc|jd|bd|cg|jh
Токенов:12 Строк, всего:3 по токену: 1 Токен: aba Паттерн: bg|ai|bb|ie|jc|jd|bd|cg|jh|aba
Токенов:5 Строк, всего:2 по токену: 1 Токен: abe Паттерн: bg|ai|bb|ie|jc|jd|bd|cg|jh|aba|abe
Токенов:3 Строк, всего:1 по токену: 1 Токен: aaaaaaaaf Паттерн: bg|ai|bb|ie|jc|jd|bd|cg|jh|aba|abe|aaaaaaaaf
white_pattern = ce|ag|fe|ff|aaj|cd|dc|aad|abc|abf|acf|bei|bhh|cij|aaaaaaaaa
black_pattern = bg|ai|bb|ie|jc|jd|bd|cg|jh|aba|abe|aaaaaaaaf
Проверка:
bhdgffhfa:1 0
aggjjaaga:1 0
hbefebhfi:1 0
dbceeabih:1 0
ihifdbhhf:1 0
djacfjbae:1 0
ibjbeigac:1 0
jaffigdad:1 0
aaaaaaaaj:1 0
dgifecchi:1 0
dcbhgjaaf:1 0
eedfbcedb:1 0
aaaaaaabf:1 0
beaajbihg:1 0
aaaaaaaag:1 0
eacccdjeh:1 0
aaaaaaaad:1 0
hehcijfhc:1 0
aaaaaaaaa:1 0
aaaaaaabc:1 0
jfdhdeice:1 0
aaaaaaaai:0 1
ehigcbgjd:0 1
hgjdeajec:0 1
aaaaaaabe:0 1
haebgiggc:0 1
aaaaaaaba:0 1
aaaaaaaaf:0 1
bfjhehbcf:0 1
diieabefh:0 1
jhjcaeead:0 1
ifbjdgibf:0 1
dddbgcgai:0 1
bbcafhcif:0 1
hfjciccbi:0 1
fdbgidjdj:0 1
aaaaaaabb:0 1
jhdibgbfj:0 1
cfjbaijad:0 1
bhgjfacgi:0 1
ehhieihhh:0 1
abijjabda:0 1
Проверка показала, что все паттерны работают.
Схема с полным "жадным" перебором дала такие же результаты.
Комментариев нет:
Отправить комментарий