5

Есть два набора строк.
Белый список:

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

12
  • @Abyx По условиям задачи такое невозможно
    – Oceinic
    8 янв 2016 в 13:22
  • А что за метка hackerrank.com?
    – VladD
    8 янв 2016 в 13:23
  • 3
    Вам, возможно, покажется интересным это: nbviewer.ipython.org/url/norvig.com/ipython/xkcd1313.ipynb
    – VladD
    8 янв 2016 в 13:27
  • @Abyx, видимо задача на сообразительность.
    – dzhioev
    8 янв 2016 в 13:27
  • @Oceinic "по условиям задачи такое невозможно" - это значит, что достаточно что бы регулярка однозначно определила, что строка в белом списке без возможности пропуска левых строк - я правильно понял ?
    – Mike
    8 янв 2016 в 13:29

2 ответа 2

7

Возможно получение двух решающих паттернов: по попаданию в белый список (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("<span style='$left'>Токенов:</span><span style='$left width:30px;' align='right'>%d</span>", count($tokens));
    printf("<span style='$left'>&emsp;Строк,&emsp;всего:</span><span style='$left width: 24px;' align='right'>%d</span>&emsp;по токену: $sum_max&emsp;", count($list));
    print("Токен: $ppp_max &emsp; Паттерн: $pat<br>");
    $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("Жадные паттерны:<br><br>");
$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("<br><br>white_pattern = $white_pattern<br>black_pattern = $black_pattern<br>");  

$left = 'display: block; float: left; ';
print("<br>Проверка:<br>");
foreach($white_black as $str){
    $in_white = preg_match("/$white_pattern/",$str);
    $in_black = preg_match("/$black_pattern/",$str);
    print("<br><span style='$left width:80px'>$str:</span>$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

Проверка показала, что все паттерны работают. Схема с полным "жадным" перебором дала такие же результаты.

2
  • Да, черный список оказался более сжимабельным)
    – Mi Ke Bu
    9 янв 2016 в 12:23
  • @Mi Ke Bu Он явно меньше. 9 янв 2016 в 15:42
4

Ответ:

/ag|c[de]|dc|fe|g[df]|aa[dj]|ab[cf]|b[aeh]{2}|bjb|cij|a{9}/

Проверка:

var W=['bhdgffhfa','aggjjaaga','hbefebhfi','dbceeabih','ihifdbhhf','djacfjbae','ibjbeigac','jaffigdad','aaaaaaaaj','dgifecchi','dcbhgjaaf','eedfbcedb','aaaaaaabf','beaajbihg','aaaaaaaag','eacccdjeh','aaaaaaaad','hehcijfhc','aaaaaaaaa','aaaaaaabc','jfdhdeice'],
   B=['aaaaaaaai','ehigcbgjd','hgjdeajec','aaaaaaabe','haebgiggc','aaaaaaaba','aaaaaaaaf','bfjhehbcf','diieabefh','jhjcaeead','ifbjdgibf','dddbgcgai','bbcafhcif','hfjciccbi','fdbgidjdj','aaaaaaabb','jhdibgbfj','cfjbaijad','bhgjfacgi','ehhieihhh','abijjabda'];

var text="ag|c[de]|dc|fe|g[df]|aa[dj]|ab[cf]|b[aeh]{2}|bjb|cij|a{9}",
   reg=new RegExp(text);
document.write('<b>Длина выражения</b><br>С границами - '+reg.toString().length)
document.write('<br>Только символы - '+text.length)
document.write('<br><b>Тесты</b><br>Из белого '+W.filter(e=>reg.test(e)).length+'/'+W.length)
document.write('<br>Из черного '+B.filter(e=>reg.test(e)).length+'/'+B.length)

Решение по шагам

  • Первым делом определим алфавит: в задаче используются символы abcdefghij

  • Регулярное выражение будет определять принадлежность по уникальным для списка кускам (токен). Списка два - белый W и черный B, я выбрал белый список, просто он первый. Попробуйте с черным, возможно там есть более короткое решение?).

  • Токены сначала нужно найти. Сгенерируем 2, 3, 4-символьные множества:

    function set(lev,str){
        //set(2) - "aa,ab, ... ,jh,ji,jj", строкой пока компактнее
        lev--; str=str||"";
        return "abcdefghij".split('').map(function(e){
            return lev>0 ? set(lev,str+e) : str+e;
        }).join();
    }
    //"aa","ab",...,"jjji","jjjj" - массив
    sets=[].concat(set(2),set(3),set(4)).join().split(',')
    
  • Для каждого токена определим, сколько раз он встречается в списках W и B.

    var freqs=sets.map(function(token){return {
       t:token,
       w:W.filter(function(e){return ~e.indexOf(token);}).length,
       b:B.filter(function(e){return ~e.indexOf(token);}).length
    };});
    
  • Определим список токенов, уникальных для W и не содержащих в себе меньших токенов

    uniq=freqs.filter(function(e){//берем уникальные для W
       return e.w>0 && e.b==0;
    }).filter(function(big,i,arr){//выкидываем избыточные - содержащие других
       return undefined==arr.find(function(small){//содержу ли другой, меньше и лаконичнее?
          return big.t.length>small.t.length && ~big.t.indexOf(small.t);
       });
    });
    //выводим списком с частотами - что одним выстрелом многих зайцев бьет?
    uniq.map(x=>x.t+'\t'+x.w).join('\n')
    //выводим через | для тестов в regex101.com и им подобных сервисах
    uniq.map(x=>x.t).join('|')
    
  • Минимизация количества токенов. Берем http://regex101.com, белый и черный списки, полученную регулярку x|y|...|z и по одному пробуем убирать токены из регулярного выражения, следя за тем, чтобы в белом списке в каждом элементе был найден хотя бы один токен. Для особых случаев вписываем токен руками (пример - a{9})

  • Оптимизация символов. Имеем регулярное выражение, покрывающее белый список, но:

    • Некоторые токены отличаются символами в одной позиции.
      • XX: cd|сe можно превратить в c[de].
        Польза = -1|-1c+2[] = 0 (полезна при похожести больше чем 2 токенов)
      • XXX: aad|aaj превращаем в aa[dj].
        Польза = -1|-2a+2[] = -1 символ
    • Некоторые токены отличаются символами в двух позициях.
      • XXX: bae|bea|bhh - b[aeh]{2}. Тут мы разширяем список токенов и это опасно. Но нам повезло и токены baa|bee|bah|beh|bha|bhe отсутствуют в черном списке, и эта расширяющая не сломает результат.
        Польза = -2|-2b-3eah+2[]+3{2} = -2 символа

P.S: Теоретически, поиск похожих, формирование замен и проверку списка-антогониста можно бы автоматизировать с помощью алгоритма Левинштейна (как в Word - похожие слова) и кластеризации, но мне было влом и количество токенов не такое уж большое для ручного, творческого процесса

3
  • А откуда взялся вариант a{9}? 9 янв 2016 в 15:37
  • Он как раз особый случай -> вписан руками. Мой код не ищет готовый ответ, в отличие от вашего кода, он просто помогает перелопатить тонны данных и откинуть заведомо бесполезные сочетания.
    – Mi Ke Bu
    10 янв 2016 в 18:15
  • Если код решает задачу - значит, он отлажен. 10 янв 2016 в 22:45

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.