Meta regex golf

29

В духе этого xkcd

введите описание ссылки здесь

Напишите программу, которая играет в рег-гольф с произвольными парами списков. Программа должна по крайней мере попытаться сделать регулярное выражение коротким, программа, которая только выводит /^(item1|item2|item3|item4)$/или подобное, не допускается.

Оценка основана на способности генерировать кратчайшее регулярное выражение. Тестовые списки - это списки успешных и неудачных кандидатов в президенты США, найденные здесь (спасибо @Peter). Конечно, программа должна работать для всех непересекающихся списков, поэтому простое возвращение ответа президенту не считается.

Manishearth
источник
3
/^item1|atem2|item3|item4$/вероятно, имеет непреднамеренный приоритет (строка должна начинаться с item1, содержать atem2, содержать item3или заканчиваться item4).
Конрад Боровски
7
Это было бы более интересной задачей, если бы она имела систему оценки, основанную, главным образом, на размере сгенерированных регулярных выражений.
Питер Тейлор
1
В духе текста заголовка XKCD, успешных и неудачных кандидатов в президенты США . (Примечание: я сделал этот список вручную, следуя Википедии , так что могут быть небольшие ошибки; я удалил из списка проигравших все фамилии, соответствующие победителю, потому что иначе отличить списки невозможно, но я намеренно не дедуплицировал иным образом) ,
Питер Тейлор,
4
Интересно, является ли Рэндалл Манро лучшим автором задач по коду-гольфу, чем мы ...
Йоханнес Кун
6
Интересно, собирается ли Рэндалл Манро отказаться от этого вопроса?
Boothby

Ответы:

8

Perl (111 110 122 персонажа)

use Regexp::Assemble;@ARGV=shift;my$r=new Regexp::Assemble;chomp,add$r "^\Q$_\E\$"while<>;$_=as_string$r;s/\(\?:/(/g;print

При этом используется модуль CPAN, вызываемый Regexp::Assembleдля оптимизации регулярных выражений. Потому что какой язык для регулярных выражений лучше, чем Perl.

Также читаемая версия, просто для удовольствия (сделана с помощью -MO=Deparse).

use Regexp::Assemble;
my $r = Regexp::Assemble->new;
while (<>) {
    chomp($_);
    $r->add("^\Q$_\E\$");
}
$_ = $r->as_string;
# Replace wasteful (?:, even if it's technically correct.
s/\(\?:/(/g;
print $_;

Пример вывода (я сделал CTRL-D после item4).

$ perl assemble.pl
item1
atem2
item3
item4
^(item[134]|atem2)$

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

^(a((ttemp)?t|llowed\.|rbitrary)?|\/\^item1\|atem2\|item3\|item4\$\/|s(ho(rt,|uld)|imilar)|p((air|lay)s|rogram)|(Writ|mak|Th)e|l(ists\.|east)|o([fr]|utputs)|t(h(at|e)|o)|(jus|no)t|regex|golf|with|is)$

Также список президентов (262 байта).

^(((J(effer|ack|ohn)s|W(ashingt|ils)|Nix)o|Van Bure|Lincol)n|C(l(eveland|inton)|oolidge|arter)|H(a(r(rison|ding)|yes)|oover)|M(cKinley|adison|onroe)|T(a(ylor|ft)|ruman)|R(oosevelt|eagan)|G(arfield|rant)|Bu(chanan|sh)|P(ierce|olk)|Eisenhower|Kennedy|Adams|Obama)$
Конрад Боровски
источник
Похоже, это читает stdin для одного списка и заставляет другой быть пустым. Конечно, это не то, о чем вопрос?
Питер Тейлор
1
@PeterTaylor: Ну, дело не в том, что второй список имеет какое-либо значение. Если во втором списке нет дубликатов первого списка, регулярное выражение является действительным. Было бы неплохо иметь более короткое регулярное выражение, но я вроде как ленивый.
Конрад Боровски
ИМО, по крайней мере, у вас должен быть способ принять это как входные данные, даже если вы затем откажетесь от него.
Питер Тейлор
@PeterTaylor: Если вы так говорите. Моя программа теперь принимает два аргумента, один из которых является первым списком.
Конрад Боровски
4
Это здорово; но он создает ненужные длинные выражения, поскольку создает исключение (для любого другого списка) путем сопоставления всех возможных полных слов. Что не совсем в духе оригинального гольфа.
Николь
4

Не мое решение (очевидно, я не Питер Норвиг!), Но вот решение (слегка измененного) вопроса любезно предоставлено им: http://nbviewer.ipython.org/url/norvig.com/ipython/xkcd1313.ipynb

программа, которую он дает, выглядит следующим образом (его работа, а не моя):

def findregex(winners, losers):
    "Find a regex that matches all winners but no losers (sets of strings)."
    # Make a pool of candidate components, then pick from them to cover winners.
    # On each iteration, add the best component to 'cover'; finally disjoin them together.
    pool = candidate_components(winners, losers)
    cover = []
    while winners:
        best = max(pool, key=lambda c: 3*len(matches(c, winners)) - len(c))
        cover.append(best)
        pool.remove(best)
        winners = winners - matches(best, winners)
    return '|'.join(cover)

def candidate_components(winners, losers):
    "Return components, c, that match at least one winner, w, but no loser."
    parts = set(mappend(dotify, mappend(subparts, winners)))
    wholes = {'^'+winner+'$' for winner in winners}
    return wholes | {p for p in parts if not matches(p, losers)}

def mappend(function, *sequences):
    """Map the function over the arguments.  Each result should be a sequence. 
    Append all the results together into one big list."""
    results = map(function, *sequences)
    return [item for result in results for item in result]

def subparts(word):
    "Return a set of subparts of word, consecutive characters up to length 4, plus the whole word."
    return set(word[i:i+n] for i in range(len(word)) for n in (1, 2, 3, 4)) 

def dotify(part):
    "Return all ways to replace a subset of chars in part with '.'."
    if part == '':
        return {''}  
    else:
        return {c+rest for rest in dotify(part[1:]) for c in ('.', part[0]) }

def matches(regex, strings):
    "Return a set of all the strings that are matched by regex."
    return {s for s in strings if re.search(regex, s)}

answer = findregex(winners, losers)
answer
# 'a.a|i..n|j|li|a.t|a..i|bu|oo|n.e|ay.|tr|rc|po|ls|oe|e.a'

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

Майк ХР
источник
8
Хотя связанная статья интересна, и я с удовольствием ее прочитал, ее лучше было бы разместить в виде комментария к вопросу, а не в качестве ответа, поскольку она не отвечает на поставленный вопрос.
Гарет
1
Вы правы, это могло бы быть лучше в качестве комментария, я разместил его как ответ просто потому, что он отлично отвечает на вопрос. Я не копировал решение, так как думал, что это было бы неискренне и пытался отдать должное за кого-то, кто еще работает, помимо программы, которая играет в рег-гольф с 2 парами списков, она также предоставляет функцию фитнеса и подробный код объяснение наряду с параллелью к задаче покрытия множества, которую я не рассматривал. Если вы все еще думаете, что это не актуально, дайте мне знать, я удалю и опубликую как комментарий.
Майк HR
1
Если вы беспокоитесь о том, чтобы взять кредит на чужую работу, отметьте и попросите мод, чтобы вы ответили «Сообщество вики».
Питер Тейлор
1
@PeterTaylor круто, я не знал, что это был протокол, готово.
Майк HR
2

Мое решение написано в Факторе :

USING:
    formatting fry
    grouping
    kernel
    math math.combinatorics math.ranges
    pcre
    sequences sets ;
IN: xkcd1313

: name-set ( str -- set )
    "\\s" split members ;

: winners ( -- set )
    "washington adams jefferson jefferson madison madison monroe
monroe adams jackson jackson vanburen harrison polk taylor pierce buchanan
lincoln lincoln grant grant hayes garfield cleveland harrison cleveland     mckinley
 mckinley roosevelt taft wilson wilson harding coolidge hoover roosevelt
roosevelt roosevelt roosevelt truman eisenhower eisenhower kennedy johnson     nixon
nixon carter reagan reagan bush clinton clinton bush bush obama obama" name-set ;

: losers ( -- set )
    "clinton jefferson adams pinckney pinckney clinton king adams
jackson adams clay vanburen vanburen clay cass scott fremont breckinridge
mcclellan seymour greeley tilden hancock blaine cleveland harrison bryan bryan
parker bryan roosevelt hughes cox davis smith hoover landon wilkie dewey dewey
stevenson stevenson nixon goldwater humphrey mcgovern ford carter mondale
dukakis bush dole gore kerry mccain romney" name-set winners diff
    { "fremont" } diff "fillmore" suffix ;

: matches ( seq regex -- seq' )
    '[ _ findall empty? not ] filter ;

: mconcat ( seq quot -- set )
    map concat members ; inline

: dotify ( str -- seq )
    { t f } over length selections [ [ CHAR: . rot ? ] "" 2map-as ] with map ;

: subparts ( str -- seq )
    1 4 [a,b] [ clump ] with mconcat ;

: candidate-components ( winners losers -- seq )
    [
        [ [ "^%s$" sprintf ] map ]
        [ [ subparts ] mconcat [ dotify ] mconcat ] bi append
    ] dip swap [ matches empty? ] with filter ;

: find-cover ( winners candidates -- cover )
    swap [ drop { } ] [
        2dup '[ _ over matches length 3 * swap length - ] supremum-by [
            [ dupd matches diff ] [ rot remove ] bi find-cover
        ] keep prefix
    ] if-empty ;

: find-regex ( winners losers -- regex )
    dupd candidate-components find-cover "|" join ;

: verify ( winners losers regex -- ? )
    swap over [
        dupd matches diff "Error: should match but did not: %s\n"
    ] [
        matches "Error: should not match but did: %s\n"
    ] 2bi* [
        dupd '[ ", " join _ printf ] unless-empty empty?
    ] 2bi@ and ;

: print-stats ( legend winners regex -- )
    dup length rot "|" join length over /
    "separating %s: '%s' (%d chars %.1f ratio)\n" printf ;

: (find-both) ( winners losers legend -- )
    -rot 2dup find-regex [ verify t assert= ] 3keep nip print-stats ;

: find-both ( winners losers -- )
    [ "1 from 2" (find-both) ] [ swap "2 from 1" (find-both) ] 2bi ;



IN: scratchpad winners losers find-both 
separating 1 from 2: 'a.a|a..i|j|li|a.t|i..n|bu|oo|ay.|n.e|ma|oe|po|rc|ls|l.v' (55 chars 4.8 ratio)
separating 2 from 1: 'go|e..y|br|cc|hu|do|k.e|.mo|o.d|s..t|ss|ti|oc|bl|pa|ox|av|st|du|om|cla|k..g' (75 chars 3.3 ratio)

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

Бьорн Линдквист
источник
1
К вашему сведению, вы пропустили кучу неудачников из официального списка (Burr, Jay, Badnarik, вероятно, другие, которых я не вижу). Итак, ваши результаты неверны; например, первое регулярное выражение не работает, потому что оно соответствует Burr и Jay.
Эликсинид
1

Мой код написан не в полном объёме , но вы можете проверить его на https://github.com/amitayd/regexp-golf-coffeescript/ (или, в частности, алгоритм на src / regexpGolf.coffee).

Он основан на алгоритме Питера Норвига с двумя улучшениями:

  1. Создайте части для использования с наборами символов (то есть используйте [ab] z, [ac] z и [bc] z, если допустимые части - это az, bz и cz).
  2. Позволяют строить «верхние оптимальные пути» обложек, а не только обложки, сделанные из лучших кандидатов на каждой итерации.

(А также кидали в произвольную случайность)

Для наборов победителей / проигравших в этом тесте я нашел регулярное выражение 76 символов, используя его:

[Jisn]e..|[dcih]..o|[AaG].a|[sro].i|T[ar]|[PHx]o|V|[oy]e|lev|sh$|u.e|rte|nle

Еще несколько подробностей в моем блоге о переносе решателя на coffeescript .

Амитай Добо
источник
2
Не могли бы вы указать свой код в своем ответе? В противном случае мы не сможем увидеть код без нажатия на ссылку!
wizzwizz4