Matthias Goergens имеет регулярное выражение в 25 604 символа (по сравнению с исходным 63 993 символами), чтобы соответствовать числам, кратным 7, но это включает в себя множество ошибок: избыточные скобки, распределение ( xx|xy|yx|yyа не [xy]{2}) и другие проблемы, хотя я уверен, что новый старт будет полезен в экономии места. Насколько маленький это может быть сделано?
Допускается любое разумное разнообразие регулярных выражений, но в регулярном выражении нет исполняемого кода.
Регулярное выражение должно соответствовать всем строкам, содержащим десятичное представление числа, делимого на 7, и никаких других. Дополнительный кредит за регулярное выражение, которое не допускает начальные 0.
code-golf
math
regular-expression
Чарльз
источник
источник
Ответы:
10791 символов, допускаются начальные нули
10795 символов, ведущие нули запрещены
0|((foo)0*)+, Где указанное регулярное выражение(0|foo)+.объяснение
Числа, кратные 7, сопоставляются очевидным конечным автоматом с 7 состояниями Q = {0,…, 6}, начальным и конечным состоянием 0 и переходами d: i ↦ (10i + d) mod 7. Я преобразовал этот конечный автомат в регулярное выражение, использующее рекурсию на множестве разрешенных промежуточных состояний:
Для i, j ∈ Q и S ⊆ Q пусть f (i, S, j) - регулярное выражение, которое соответствует всем автоматным путям из i в j, используя только промежуточные состояния в S. Тогда
f (i, ∅, j) = (j - 10i) mod 7,
f (i, S ∪ {k}, j) = f (i, S, j) ∣ f (i, S, k) f (k, S, k) * f (k, S, j).
Я использовал динамическое программирование, чтобы выбрать k, чтобы минимизировать длину полученного выражения.
источник
0|((foo)0*)+13,7551269912731 ПерсонажиЭто регулярное выражение не отклоняет ведущий ноль.
Это проверено с Regex Coach .
Как мы туда попали
Вышеуказанное регулярное выражение сначала создается DFA, который будет принимать желаемый ввод (десятичные дроби, делимые на 7), а затем конвертируется в регулярное выражение и фиксирует нотацию.
Чтобы понять это, сначала необходимо создать DFA, который принимает следующий язык:
То есть он будет «совпадать» с двоичными числами, которые делятся на 7.
DFA выглядит так:
Как это устроено
Вы сохраняете текущее значение
A, представляющее значение битов, прочитанных DFA. Когда вы читаете0тогдаA = 2*Aи когда вы читаете1A = 2*A + 1. На каждом шаге вы рассчитываете,A mod 7затем вы переходите в состояние, которое представляет ответ.Итак, тестовый прогон:
Мы читаем, в
10101котором это двоичное представление для 21 в десятичном виде.q0, в настоящее времяA=01, из «правила» вышеA = 2*A + 1такA = 1.A mod 7 = 1поэтому мы переходим к состояниюq10,A = 2*A = 2,A mod 7 = 2поэтому мы переходим кq21,A = 2*A + 1 = 5,A mod 7 = 5, перейти кq50,A = 2*A = 10,A mod 7 = 3, перейти кq31,A = 2*A + 1 = 21,A mod 7 = 0, перейти кq010101делится на 7!Преобразование DFA в регулярное выражение - сложная задача, поэтому я заставил JFLAP сделать это для меня, выполнив следующее:
Для десятичных чисел
Процесс почти такой же:
Я создал DFA, который принимает язык:
Вот DFA:
Логика аналогична, такое же количество состояний, просто еще много переходов для обработки всех дополнительных цифр, которые приносят десятичные числа.
Теперь правило менять
Aна каждом шаге: когда вы читаете десятичную цифруn:A = 10*A + n. Затем снова вы простоmodAна 7 и переходите к следующему состоянию.Ревизии
Редакция 5
Вышеупомянутое регулярное выражение теперь отклоняет числа, начинающие нули - конечно, кроме нуля.
Это немного отличает DFA, в основном вы отходите от исходного узла, когда читаете первый ноль. Чтение другого нуля ставит вас в бесконечный цикл в разветвленном состоянии. Я не исправил диаграмму, чтобы показать это.
Редакция 7
Сделал некоторый "metaregex" и сократил мое регулярное выражение, заменив некоторые союзы на классы персонажей.
Редакция 10 и 11 (от nhahtdh)
Модификация автора отклонять ведущий ноль неверна. Это приводит к тому, что регулярные выражения не соответствуют действительным числам, таким как 1110 (десятичное = 14) в случае двоичного регулярного выражения и 70 в случае десятичного регулярного выражения. Эта ревизия отменяет модификацию и, следовательно, позволяет сопоставлять произвольные начальные нули и пустую строку.
Эта ревизия увеличивает размер десятичного регулярного выражения, поскольку исправляет ошибку в исходном регулярном выражении, вызванную отсутствием ребра (9) из состояния 5 в состояние 3 в исходном DFA.
источник
1110, а десятичный не соответствует70. Это было проверено как в Python, так и в Perl. (Python требует преобразования каждого(в(?:первый).NET регулярное выражение,
119118105 байт111 символов, запрещающих начальные 0:
113 символов, запрещающие начальные 0 и поддерживающие отрицательные числа:
Попробуй это здесь.
Пояснение (предыдущей версии)
Он использует приемы, использованные в ответах на этот вопрос: « Копы и грабители: Reverse Regex Golf» . Регулярное выражение .NET имеет функцию, называемую балансирующая группа, которая может использоваться для выполнения арифметики.
(?<a>)толкает группуa.(?<-a>)выскакивает и не совпадает, если ранее не былоaподходящей группы .(?>...)Подходим и не возвращаемся позже. Таким образом, он всегда будет соответствовать только первой подходящей альтернативе.((?<-t>)(){3}|){6}Умножьте номер группы t на 3. Сохраните результат в номере группы 2.(?=[1468](?<2>)|)(?=[2569](?<2>){2}|)([3-6](?<2>){3}|\d)Совпадение с номером и номером группы 2.((?<-2>){7}|){3}Удалить группу 2, кратную 7 раз.((?<t-2>)|){6}Удалить группу 2 и сопоставить с тем же номером группы t.$(?(t)a)Если группа все еще соответствует, сопоставьтеaпосле конца строки, что невозможно.Я думал, что эта 103-байтовая версия также должна работать, но не нашел обходного пути для ошибки в компиляторе.
источник
468 персонажей
Аромат регулярных выражений в Ruby допускает рекурсию (хотя это своего рода обман), поэтому легко реализовать DFA, который распознает числа, делимые на 7, используя это. Каждая именованная группа соответствует состоянию, и каждая ветвь в чередованиях использует одну цифру, а затем переходит в соответствующее состояние. Если достигнут конец числа, регулярное выражение совпадает только в том случае, если двигатель находится в группе «А», в противном случае происходит сбой.
Он распознает ведущие нули.
источник
{a*b*|a and b an equal amount of times})Я был действительно впечатлен ответом Гриффина, и мне нужно было понять, как это работает! Результатом является следующий JavaScript. (Это 3,5 тыс. Символов, что в некотором смысле короче!)
genФункция принимает делитель и основание и генерирует регулярное выражение, которое соответствует числам в указанном основании, которые делятся на этот делитель.Я обобщил NFA Гриффина для любой базы:
nfaфункция берет делитель и базу и возвращает двумерный массив переходов. Например, для перехода из состояния 0 в состояние 2 требуетсяstates[0][2] == "1".reduceФункция принимает вstatesмассив и запускает его через этот алгоритм , чтобы перевести НКА в регулярное выражение. Сгенерированные регулярные выражения огромны и выглядят так, как будто имеют много избыточных предложений, несмотря на мои попытки оптимизации. Регулярное выражение для 7 base 10 составляет около ~ 67k символов; Firefox выдает «InternalError» для n> 5, пытаясь проанализировать регулярное выражение; запуск регулярного выражения в Chrome начинает замедляться при n> 6.Также есть
testфункция, которая принимает регулярное выражение и основание и запускает его для чисел от 0 до 100, так чтоtest(gen(5)) == [0, 5, 10, 15, ...].Несмотря на неоптимальный результат, это была фантастическая возможность обучения, и я надеюсь, что часть этого кода будет полезна в будущем!
источник
Perl / PCRE, 370 символов
Отклоняет пустую строку, а также строки с начальными 0 (кроме «0»).
источник