Comments 26
Круто! Хабр - торт.
Интересно, а можно ли написать автоматический генератор этого удовольствия для разных делителей и систем счисления.
Тут вроде что-то типа линейных уравнений - но можно делать только подстановки и трюк со само-рекуррентностью и надо выразить одну переменную.
Или же есть какой-то алгоритм прямо для перевода конечного детерменированного автомата в регулярное выражение без рекуррентных ссылок.
Или же есть какой-то алгоритм прямо для перевода конечного детерменированного автомата в регулярное выражение без рекуррентных ссылок.
Алгоритм Клини
Интересно, а можно ли написать автоматический генератор этого удовольствия для разных делителей и систем счисления.
На кодоварсе подобная задача есть, для двоичной системы счисления и чисел до 18. Я пока не решал, но там видимо как раз придется такую штуку сделать программно
Ха, вообще алгоритм очень простой получается. Строим автомат, а потом выкидываем по одной вершине, заменяя входящие+исходящие ребра на новые ребра. Главная фишка - теперь на ребрах будем писать регулярные выражения. Если в вершине есть цикл, то он добавляется между входящей и исходящей строкой с *. Если получаются параллельные ребра, то они объединяются через |. Удаляем все вершины, кроме остатка 0. Получившееся в итоге ребро берем в ответ со звездочкой.
Вот регулярка для делимости на 3 для двоичной системы, полученная за 3 минуты на листочке: ^(0|1(01*0)*1)*$
Правда, этой ругулярке будут соответствовать и кривые строки вроде 0011, которые не являются корректным числом, но без ведущих нулей будут длиться на 3. А еще этому соответствует пустая строка. Чтобы этого не было, надо заменить * на + в конце.
Забавно, что обычно для даже очень простого регулярного выражения получается очень большой авотомат, и тот недетерминированный (который можно сделать детерменированным, но он еще больше станет). А тут автомат на самом деле мизерный.
Кстати, задача для проверки делимости на 3 тоже есть на кодоварсе. Да, там всё просто, но некоторые пользователи ухитрились придумать реги, которые зависают на не слишком длинных строках вида "000...01" из-за бэктрекинга. Например, в ответах js видел вот такое:
^(0*(1(01*0)*1)*)*$Тут же проблема во вложенных, ничем не разделенных *? Не уверен, что можно гарантировать что этот алгоритм не сделает чего-то подобного. Конкретно этой ситуации не будет, ибо звездочка добавляется только для циклов при удалении вершины, и она будет обрамлена двумя ребрами из вершины. И так на каждом ребре.
Это еще раз демонстрирует забавный перекос в задаче: регулярка, хоть и эквивалентна автомату - на самом деле соответствует какой-то очень сильно раздутой его версии.
Да получается забавно, что исходной задаче, если ее реализовать в лоб на каком нибудь языке простым автоматом состояний, то ей не нужны никакие ни бектрекинги ни рекурсии, Надо просто идти по графу и определить на какой ноде поток цифр закончится. Но после всех этих преобразований из машины состояний в регулярку и обратно могут рождаться какие то монстры.
забавный перекос в задаче: регулярка, хоть и эквивалентна автомату - на самом деле соответствует какой-то очень сильно раздутой его версии
Да, это любопытный момент. На досуге раскурю, в чем тут философия. Я эти задачки давно видел на cw, но с наскока не взял (кроме делимости на 3, конечно), теперь можно тот 1 kue решить, автоматизировав подход.
Если интересно, вот унивресальное решение для любой базы и делителя.
Проблема только, что ответ она выдает экспоненциально длинный. Пока не смог оценить, но там что-то порядка O(N^B). Хотя в некоторых случаях выдает весьма короткий ответ. Почти половина кода - это разбор случаев, когда там нужно скобки в регекспе ставить.
код
def int_to_base(n, base):
if n == 0:
return "0"
digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
result = ""
while n > 0:
n, remainder = divmod(n, base)
result = digits[remainder] + result
return result
# Checks if parenthesis are needed when chaining two expressions
def NeedPar(s):
depth = 0
for c in s:
if c == '(': depth += 1
elif c == ')': depth -= 1
elif c == '|' and depth == 0: return True
return False
# Checks if parenthesis are not needed when adding *
def Single(s):
if len(s) == 1: return True
if s[0] != '[' or s[-1] != ']': return False
for i in range(1, len(s)-1):
if s[i] < '0' or s[i] > int_to_base(B-1, B): return False
return True
def GenRegEx(N, B):
tr = [['' for j in range(0, N)] for i in range (0, N)]
for i in range(0, N):
for c in range (0, B):
j = (i*B+c) % N
tr[i][j] += int_to_base(c, B)
for i in range(0, N):
for j in range(0, N):
if len(tr[i][j]) > 1:
tr[i][j] = '['+tr[i][j]+']'
for i in range(N-1, 0, -1):
for j in range(0, i):
for k in range (0, i):
if tr[j][i] == '' or tr[i][k] == '':
continue
if NeedPar(tr[j][i]):
cur = '(' + tr[j][i] + ')'
else:
cur = tr[j][i]
if tr[i][i] != '':
if Single(tr[i][i]):
cur += tr[i][i] + '*'
else:
cur += '('+tr[i][i] + ')*'
if NeedPar(tr[i][j]):
cur += '(' + tr[i][k] + ')'
else:
cur += tr[i][k]
if tr[j][k] != '':
tr[j][k] += '|'
tr[j][k] += cur
for j in range (0, i):
tr[j].pop()
tr.pop()
return '^(' + tr[0][0] + ')*$'
Вот варианты вывода:
N=3 Base=10:
len = 107
^([0369]|[258][0369]*[147]|([147]|[258][0369]*[258])([0369]|[147][0369]*[258])*([258]|[147][0369]*[147]))*$
N=5 Base=2:
len = 48
^(0|1(10|(0|11)(01*01)*01*00)*(0|11)(01*01)*1)*$
N=3 Base=16:
len=139
^([0369CF]|[258BE][0369CF]*[147AD]|([147AD]|[258BE][0369CF]*[258BE])([0369CF]|[147AD][0369CF]*[258BE])*([258BE]|[147AD][0369CF]*[147AD]))*$@fori тут получилось даже сильно короче вашего варианта.
Но тут как повезет. Код выше удаляет состояния в порядке убывания. Но если их в другом порядке исключать, то результат может получаться короче или длиннее.
Особо обидно, что этот метод для делимости на 10 в десятичной системе выдает регулярку длиной в 567981 знаков.
Надо что-то с комбинаторным взрывом делать и как-то это безобразие минифицировать.
Особо обидно, что этот метод для делимости на 10 в десятичной системе выдает регулярку длиной в 567981 знаков.
для N == Base получается полный граф, где ребро D ведет в вершину D. И под каким-то соусом тут можно все ненулевые вершины схлопнуть в одну ненулевую. Вопрос, в каких ещё случаях можно провернуть такой трюк хотя бы частично...
Плюс, если N раскладывается на множители, то регу можно составить из нескольких lookahead, например при N=12 будет
^(?=..проверка_для_4..$)(?=..проверка_для_3..$)Хотя для двух разных простых N и Base это всё не сработает, конечно.
Можно в каком-то смысле эквивалентные состояния автомата сжать сначала, да. Но в общем случае это не поможет. Проблема хорошо видна для N=B=3:
^(0 | 22*0 | (1 | 22*1)(1 | 22*1)*(0 | 22*0))*$ Тут, фактически перебираются варинты: в строке может быть только цифра 0, цифры 0 и 2, цифры 0,2 и 1. В последнем случае внутри тоже перебираются варинты: цифира 1, цифра 1 и 2 , 0 или 0 и 2.
И все эти случаи можно посокращать, вынося суффиксы-префиксы за скобки.
Я думаю хорошее решение будет строить регулярки не в виде строк, а ввиде дерева операций и оптимизировать, когда ребро удаляется. Там надо будет из всех вариантов через | выделить общие суффиксы/префиксы и все дико посокращается.
Сделал кучу эвристик, вроде
"abc|adc" -> "a(b|d)c"
"(a|)" -> "a?"
"aa*"->"a+"
"a+?"->"a*"Стало сильно лучше - для N=Base=10 выдало регулярку "всего" в 1538 знаков.
Для N=Base=3 дает теперь сильно более вменяемую регулярку:
^((2*1)*2*0)*$ Как ее преобразовывать к
([12]*0)*я не вижу.
Нужен какой-то принципиально другой подход.
Надо что-то с комбинаторным взрывом делать и как-то это безобразие минифицировать.
В худшем случае (когда n простое) всё равно будет экспоненциальная длина. Регулярка явно прописывает все маршруты из нулевого состояния в нулевое, а их будет много...
Прикол, в этой задаче тупое решение, которое выдает регулярку в 116620 тысяч знаков при N=17 проходит, ибо эвристики, пытающиеся это добро соптимизировать, хоть и выдают регулярку в 83841 знаков, но работают слишком долго.
Если решить исходную задачу деления на 7, то откроется список решений других пользователей и среди них можно найти решение более общей задачи - для любого делителя. Оно оказалось совсем не большое, но код правда на Haskell
Не вполне ясно зачем нужно было избавляться от рекурсии. Рекурсия в регулярках бывает (например, в PCRE есть ?R).
Рекурсия может потребовать стек для хранения переходов, а стек в свою очередь может быть overflow в запущенных случаях. Как минимум от этой проблемы избавимся, так как на выходе получили дерево разбора уложенное в плоскую строку, требующее хранение только текущей позиции в регулярке. Хотя может и ошибаюсь и выполнение простой регулярки без рекурсий тоже хранит стеки
Отличная статья! Интересное применение для регулярных выражения.
В своё время мне было скучно на занятиях по дискретной математике, где мы писали регулярные выражения и строили конечные автоматы для делимости чисел на 5 или 8 (достаточно просто в десятичной системе счисления). Поэтому, потратив минут 5 я построил автомат (который вышел очень простым), а потом за час построил регулярное выражение для делимости числа на 3 в десятичной системе счисления.
([0369]|[147]([0369]|[147][0369]*[258])*([258]|[147]([0369]|[258][0369]*[147])*[147])|[258]([0369]|[258][0369]*[147])*([147]|[258]([0369]|[147][0369]*[258])*[258]))+Вот здесь его можно проверить с тестом на первые 300'000 тысяч чисел: https://regex101.com/r/E9CTvt/1
Проверять его нужно не первыми газиллионами, а property-based тестом, сравнивая с
number
|> Integer.digits()
|> Enum.join()
|> String.to_integer()
|> rem(3) == 0Умные люди придумали QuickCheck почти тридцать лет назад ровно для этой цели.
А сколько тут Integer вернет digits ? А то у to_integer может случится too large or too small for an Int64. Хорошо у Haskell есть теоретически бесконечный Integer (пишут может доходить до 16 ГБ в зависимости от реализации) https://www.reddit.com/r/haskell/comments/1gg3i8/can_haskell_handle_integers_of_any_size_or_is/?rdt=50739
сам натыкался на эту задачу в кодварсе, меня как большого любителя регулярок она растоптала
автор - гений
задача - хтонь
спасибо большое)
Регулярные выражения делимости чисел