LINUX.ORG.RU

лиха беда начало

 , , , ,


1

2

очевидно тема contest востребована по весне, но не стоит ограничивать её С, пусть уж будут все :) Пусть будет задача требующая либо глубокой теор.подготовки либо опыта копания си-шных недр, а лучше и того и другого. Либо неординарного мышления, итого:

предполагаемая задача:

создать утилиту degrep которая делает вывод следующего за ней grep в тем-же аргументом пустым. 

  • критерии успеха: `cat $file | degrep $pattern | grep $pattern` всегда пуст вне зависимости от pattern и для любых файлов. pattern соответсвует POSIX и не эквивалентна .*
  • критерий сравнения: разница(например xdelta) между `cat $file` и `cat $file | degrep $pattern` минимальна.
  • критерий серьёзной заявки - софтинка должна давать лучший результат чем grep -v pattern и sed s/pattern// (то есть лучше тупой инверсии условия/удаление подстрок)
  • критерий победы близкой к абсолюту: утилита `undegrep $pattern` восстанавливающая исходный текст файла после degrep. То есть изменения внесённые degrep каким-то образом обратимы.
  • требований по скорости не предъявляется - программа должна завершаться за разумное время. Скажем не больше 20 мин на текст не более 10К
  • абсолютный абсолют - degrep и undegrep одна и та-же программа. В теории это возможно.

PS. у меня готовых решений нет :( буду на общих условиях

PPS. приветствуются даже подходы к её решению, без приложения кодов :) очень лихая вводная получилась

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

main(){}
PolarFox ★★★★★ ()

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

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

lovesan ()
Ответ на: комментарий от lovesan

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

mky ★★★★★ ()
Ответ на: комментарий от lovesan

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

mix_mix ★★★★★ ()
Ответ на: комментарий от mky

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

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

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

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

lovesan ()
Ответ на: комментарий от lovesan

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

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

MKuznetsov ★★★★★ ()
Ответ на: комментарий от MKuznetsov

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

lovesan ()
Ответ на: комментарий от MKuznetsov

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

lovesan ()

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

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

zinfandel ★★ ()
Ответ на: комментарий от lovesan

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

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

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

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

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

MKuznetsov ★★★★★ ()
Ответ на: комментарий от qnikst

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

zinfandel ★★ ()
Ответ на: комментарий от MKuznetsov

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

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

lovesan ()
Ответ на: комментарий от MKuznetsov

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

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

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

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

lovesan ()

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

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

anonymous ()
Ответ на: комментарий от lovesan

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

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

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

MKuznetsov ★★★★★ ()
Ответ на: комментарий от MKuznetsov

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

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

anonymous ()

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

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

buddhist ★★★★★ ()

Тривиальное

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

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

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

DonkeyHot ★★★★★ ()

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

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

чтоугодно | degrep $pattern | grep $pattern
должно выдавать пустой результат, и, в частности,
cat $file | degrep $pattern | degrep $pattern | grep $pattern
должно быть пустым. Если бы undegrep и degrep были одной программой, то последнее было бы эквивалентно
cat $file | grep $pattern

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

Miguel ★★★★★ ()
Ответ на: Тривиальное от DonkeyHot

Re: Тривиальное

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

mky ★★★★★ ()
Ответ на: комментарий от Miguel

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

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

mky ★★★★★ ()
Ответ на: Re: Тривиальное от mky

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

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

DonkeyHot ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.