Вырожденный случай:

main(){}

критерий серьёзной заявки - софтинка должна давать лучший результат чем grep -v pattern и sed s/pattern// (то есть лучше тупой инверсии условия/удаление подстрок)

Вот это не понял. По условию ведь оно самое и есть?

Не, он хочет более хитрого, так исказить строку, что она не пройдёт через grep, но чтобы потом undegrep её восстановил.

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

Ну тогда алгоритм такой:

Строим дерево для регекса, и проходим его допустим в глубину, находим все верхние узлы, для которых множество FIRST не равно любому символу или пустой строке, соединяем эти множества, получаем FIRST-множество букв всех первых непустых и не ".*" верхних узлов, сортируем его, вычисляем букву X, которая имеет код скажем +1 от последней. Добавляем в строку после каждой буквы из этого множества букву X, все grep обосрется.

Обратный алгоритм думаю понятен.

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

Добавляем в строку после каждой буквы из этого множества букву X, все grep обосрется.

на «a.» какой получится X и куда его добавить в классический «abracadabra» ?

хм, ну да... логичнее тогда не добавлять после, а наоборот, заменять на X а саму X заменять на X+1 X+1 на X+2 и т.д.

на X+код заменять

Короче суть в том, чтобы grep обосрался на FIRST-множестве

Лучше сразитесь в https://helloworldopen.com/, время на регистрацию еще есть.

Языки: C, C# / Mono, Clojure, CoffeeScript, Haskell, Java, JavaScript, Lua, Python, Ruby, Scala, Go

там же небось умным надо быть

на X+код заменять

и следить чтобы X+N не попал в FIRST, а X+256 заменить обратно на X :) и полностью перелопатить весь файл до байта. Критерий минимальных правок xdiff не выдержан

Короче суть в том, чтобы grep обосрался на FIRST-множестве

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

ps. я теги lisp,haskell,prolog поставил потому как считаю в итоге упрётся в поиск оптимума, а они это вроде как умеют :)

Вроде на участие таких критериев нет, и взноса нет. Команды макс. три человека. Естественно если ты «не умный», то будешь в хвосте. Но можно ведь написать бота (на Хаскелле) который доедет до финиша, а потом смеятся над лоравскими Сишниками (у которых переполнился буфер, или какая-другая низкоуровневая каракатица) и Яваскриптерами (у которых вылез рантайм еррор, вызваный бага которого бы нашел компилятор).

для каждого отдельного regex может быть построен более оптимальный вариант

Минимизированный DFA - как раз и есть оптимум для конкретного регекса

X+256 заменить обратно на X

Да не, просто по модулю

Критерий минимальных правок xdiff не выдержан

Ну так а с чего ты взял что есть еще что-то более минимальное?

То есть изменения внесённые degrep каким-то образом обратимы.

Очевидно же, что это невозможно.

Минимизированный DFA - как раз и есть оптимум для конкретного регекса

дык то понятно :-) вопрос в том чтобы внести минимальные правки во входящий поток чтоб DFA представляющий регекс сфейлился (и очевидно лучше в последний момент).

То есть правки в первую очередь минимальны, а во вторую уже обратимы. а то всё очень просто - выбрать пару символов, в любых сочетаниях не проходящих регекс и перекодить файл в «такой-вот-бинарный-вид» :-)

То есть правки в первую очередь минимальны, а во вторую уже обратимы.

Это взаимопротиворечивые условия. Минимальные правки не будут обратимы. Если хочется обратимости - придется разрешить неминимальные правки.

В теории это возможно

Хотелось бы увидеть формальное доказательство

Тривиальное

bash+sed+enc, строк в 30 можно уложиться. Критерий минимальности отличий игнорируется.

1. находим экспериментальным путём строку, не соответствующую шаблону(например, перебираем длинные хеши шаблона с последоватльной затравкой), используем в качестве маркера и/или ключа. 2. строки, соответствующие шаблону прогоняем через «openssl enc», и оборачиваем маркерами, повторяем до тех пор, пока результат шифрования соответствует шаблону.

В обратную сторону очевидно.

degrep и undegrep одна и та-же программа. В теории это возможно.

Нет, невозможно. Потому что по условию

чтоугодно | degrep $pattern | grep $pattern

cat $file | degrep $pattern | degrep $pattern | grep $pattern

cat $file | grep $pattern

Есть, конечно, объездной путь — сделать undegrep ссылкой на degrep и анализировать argv[0]. Но это суксь.

undegrep ссылкой на degrep и анализировать argv[0]

degrep -v же

Это сначала нужно определить, что вобще есть строки, не соответствующие шаблону. Ведь можно написать ″.″, а можно ″[1]|[^1]″.

Есть, конечно, объездной путь — сделать undegrep ссылкой на degrep и анализировать argv[0].

Наверное, ТС это и подразумевал, как раньше был gzip/gunzip. Теперь, правда, gunzip стал bash-скриптом, непонятно зачем. Или это только в RHEL так?

определить, что вобще есть строки, не соответствующие шаблону

Есть(не всегда) «решение» а есть «грязный хак». Второе, часто, сильно дешевлее и вполне удовлетворяет житейские потребности, но подходит далеко не для каждого соревнования и совсем не годится для математики. Из ТЗ не очень понятно, что задача из последних.