Сопоставьте строки, длина которых равна четвертой степени

В рамках этого вопроса, давайте рассмотрим только те строки, которые состоят из символа, xповторенного произвольное количество раз.

Например:

<empty>
x
xx
xxxxxxxxxxxxxxxx

^{(Ну, на самом деле это не обязательно x- любой символ в порядке, если вся строка содержит только 1 тип символа)}

Напишите регулярное выражение в любой разновидности регулярного выражения по вашему выбору, чтобы соответствовать всем строкам, длина которых равна n ^4, для некоторого неотрицательного целого числа n (n> = 0). Например, допустимы строки длиной 0, 1, 16, 81 и т. Д .; остальные недействительны.

^{Из-за технического ограничения, значения n больше 128 сложно проверить. Тем не менее, ваше регулярное выражение должно логически работать правильно, независимо от.}

Обратите внимание, что вы не можете выполнять произвольный код в своем регулярном выражении (для пользователей Perl). Разрешен любой другой синтаксис (осмотр, обратная ссылка и т. Д.).

Пожалуйста, включите краткое объяснение вашего подхода к проблеме.

^{(Пожалуйста, не вставляйте автоматически сгенерированное объяснение синтаксиса регулярных выражений, так как они бесполезны)}

Это (ир) регулярное выражение, кажется, работает.

^((?(1)((?(2)\2((?(3)\3((?(4)\4x{24}|x{60}))|x{50}))|x{15}))|x))*$

Это регулярное выражение совместимо с разновидностями PCRE, Perl, .NET.

Это в основном следует за «деревом различий» (не уверенным, есть ли для него правильное имя), которое сообщает регулярному выражению, сколько еще х должно соответствовать следующей четвертой степени:

1     16    81    256   625   1296  2401 ...
   15    65    175   369   671   1105 ...
      50    110   194   302   434 ...
         60    84    108   132 ...
            24    24    24 ...  # the differences level out to 24 on the 4th iteration

\2, \3, \4Магазины и обновления разница , как показано на 2 - й, 3 - й и 4 - й строки, соответственно.

Эта конструкция может быть легко расширена для более высоких степеней.

Конечно, это не элегантное решение, но оно работает.

Другое решение

Это, на мой взгляд, одна из самых интересных проблем на сайте. Мне нужно поблагодарить deadcode за то, что он поднял его наверх.

^((^|xx)(^|\3\4\4)(^|\4x{12})(^x|\1))*$

39 байтов , без каких-либо условий или утверждений ... вроде. Чередования, поскольку они используются ( ^|), являются условным способом выбора между «первой итерацией» и «не первой итерацией».

Это регулярное выражение можно увидеть здесь: http://regex101.com/r/qA5pK3/1

И PCRE, и Python правильно интерпретируют регулярное выражение, и оно также было протестировано в Perl до n = 128 , включая n ⁴ -1 и n ⁴ +1 .

Определения

Общая методика такая же, как и в других уже опубликованных решениях: определите самоссылающееся выражение, которое на каждой последующей итерации соответствует длине, равной следующему члену прямой разностной функции, D _f , с неограниченным квантификатором ( *). Формальное определение функции прямой разницы:

Кроме того, разностные функции более высокого порядка также могут быть определены:

Или, в более общем плане:

Функция прямой разности имеет много интересных свойств; это для последовательностей то же, что производная для непрерывных функций. Например, D _й Апа п - го порядка многочлен всегда будет п-1 - го порядка многочлена, и для любого I , если D _е ^я = D _е ^{+ 1} , то функция F является экспоненциальным, во многом таким же образом , что производная е ^х равна себе. Простейшая дискретная функция, для которой f = D _f, равна 2 ⁿ .

f (n) = n ²

Прежде чем мы рассмотрим вышеупомянутое решение, давайте начнем с чего-то более простого: регулярное выражение, которое соответствует строкам, длина которых представляет собой идеальный квадрат. Изучение функции прямой разницы:

Это означает, что первая итерация должна соответствовать строке длиной 1 , вторая - строке длины 3 , третья - строке длины 5 и т. Д., И, в общем, каждая итерация должна соответствовать строке на два длиннее предыдущей. Соответствующее регулярное выражение следует почти непосредственно из этого утверждения:

^(^x|\1xx)*$

Можно видеть, что первая итерация будет соответствовать только одной x, а каждая последующая итерация будет соответствовать строке на два длиннее предыдущей, в точности так, как указано. Это также подразумевает удивительно короткий идеальный квадратный тест в Perl:

(1x$_)=~/^(^1|11\1)*$/

Это регулярное выражение может быть дополнительно обобщено, чтобы соответствовать любой n -угольной длине:

Треугольные числа:
^(^x|\1x{1})*$

Квадратные числа:
^(^x|\1x{2})*$

Пятиугольные числа:
^(^x|\1x{3})*$

Шестиугольные числа:
^(^x|\1x{4})*$

и т.п.

f (n) = n ³

Переходя к n ³ , еще раз исследуем функцию прямой разницы:

Как это реализовать, может быть не сразу понятно, поэтому мы также рассмотрим вторую функцию разности:

Таким образом, прямая разность не увеличивается на постоянную, а на линейную величину. Приятно, что начальное (' -1- е') значение D _f ² равно нулю, что сохраняет инициализацию на второй итерации. Полученное регулярное выражение выглядит следующим образом:

^((^|\2x{6})(^x|\1))*$

Первая итерация будет соответствовать 1 , как и раньше, вторая будет соответствовать строке на 6 длиннее ( 7 ), третья будет соответствовать строке 12 длиннее ( 19 ) и т. Д.

f (n) = n ⁴

Функция прямой разности для n ⁴ :

Вторая прямая разностная функция:

Третья функция прямой разности:

Теперь это безобразно. Начальные значения для D _f ² и D _f ³ являются ненулевыми, 2 и 12 соответственно, что необходимо учитывать. Вы, наверное, уже поняли, что регулярное выражение будет следовать этой схеме:

^((^|\2\3{b})(^|\3x{a})(^x|\1))*$

Поскольку D _f ³ должен соответствовать длине 12 на второй итерации, a обязательно равно 12 . Но поскольку он увеличивается на 24 каждого слагаемого, следующее более глубокое вложение должно использовать свое предыдущее значение дважды, подразумевая, что b = 2 . Последнее, что нужно сделать, это инициализировать D _f ² . Поскольку D _f ² напрямую влияет на D _f , что в конечном итоге и соответствует, его значение можно инициализировать, вставив соответствующий атом непосредственно в регулярное выражение, в этом случае (^|xx). Окончательное регулярное выражение становится:

^((^|xx)(^|\3\4{2})(^|\4x{12})(^x|\1))*$

Высшие заказы

Полином пятого порядка можно сопоставить с помощью следующего регулярного выражения:
^((^|\2\3{c})(^|\3\4{b})(^|\4x{a})(^x|\1))*$

f (n) = n ⁵ является довольно простым упражнением, поскольку начальные значения для второй и четвертой прямых разностных функций равны нулю:

^((^|\2\3)(^|\3\4{4})(^|\4x{30})(^x|\1))*$

Для полиномов шести порядков:
^((^|\2\3{d})(^|\3\4{c})(^|\4\5{b})(^|\5x{a})(^x|\1))*$

Для полиномов седьмого порядка:
^((^|\2\3{e})(^|\3\4{d})(^|\4\5{c})(^|\5\6{b})(^|\6x{a})(^x|\1))*$

и т.п.

Обратите внимание, что не все полиномы могут быть сопоставлены именно таким образом, если любой из необходимых коэффициентов не является целым числом. Например, n ⁶ требует, чтобы a = 60 , b = 8 и c = 3/2 . Это можно обойти, в этом случае:

^((^|xx)(^|\3\6\7{2})(^|\4\5)(^|\5\6{2})(^|\6\7{6})(^|\7x{60})(^x|\1))*$

Здесь я изменил б до 6 и c на 2 , которые имеют тот же продукт, что и указанные выше значения. Важно, чтобы произведение не менялось, так как a · b · c ·… контролирует функцию постоянной разности, которая для полинома шестого порядка равна D _f ⁶ . Присутствуют два атома инициализации: один для инициализации D _f до 2 , как при n ⁴ , а другой для инициализации пятой разностной функции до 360 , одновременно добавляя недостающие два из b .

Вот решение, в котором не используются условные, объявленные вперед или вложенные обратные ссылки, просмотр назад, балансировка групп или рекурсия регулярного выражения. Он использует только упреждающие и стандартные обратные ссылки, которые очень широко поддерживаются. Я был вдохновлен работать в соответствии с этими ограничениями благодаря Regex Golf , который использует движок регулярных выражений ECMAScript.

Принцип работы этого 50-байтового регулярного выражения довольно прост и совершенно отличается от всех других представленных решений этой головоломки. Удивительно было обнаружить, что такая математическая логика выражается в регулярном выражении.

      \2                     \4  \5
^((?=(xx+?)\2+$)((?=\2+$)(?=(x+)(\4+)$)\5){4})*x?$

(Группы захвата помечены над регулярным выражением)

Регулярное выражение можно обобщить на любую степень, просто заменив 4in {4}на требуемую степень.

Попробуйте онлайн!

Он работает путем многократного деления наименьшей четвертой степени простого числа, на которое делится текущее значение. Таким образом, частное на каждом шаге всегда является четвертой степенью, если исходное значение было четвертой степенью. Окончательный коэффициент 1 указывает, что исходное значение действительно было четвертой степенью; это завершает матч. Ноль также соответствует.

Сначала он использует ленивую группу захвата \2для захвата наименьшего фактора числа больше 1. Таким образом, этот фактор гарантированно будет простым. Например, с 1296 (6 ^ 4) он первоначально захватит \2= 2.

Затем, в начале цикла, который повторяется 4 раза, он проверяет, делится ли текущее число на \2, с (?=\2+$). Первый раз в этом цикле этот тест бесполезен, но его цель станет очевидной позже.

Затем внутри этого внутреннего контура, он использует жадную группу захвата , \4чтобы захватить крупнейший фактор этого числа меньше , чем он сам: (?=(x+)(\4+)$). Фактически это делит число на наименьший простой множитель,\2 ; например, 1296 первоначально будет \4записано как = 1296/2 = 648. Обратите внимание, что деление текущего числа на \2неявное. Хотя можно явно разделить текущее число на число, содержащееся в группе захвата (которую я обнаружил только через четыре дня после публикации этого ответа), выполнение этого приведет к более медленному и трудному для понимания регулярному выражению, и это не необходимо, поскольку наименьший коэффициент числа больше 1 всегда будет совпадать с его наименьшим фактором, меньшим, чем он сам (так что их произведение равно самому числу).

Так как этот вид регулярных выражений может «съесть» только строку (уменьшив ее), оставив результат в конце строки, нам нужно «переместить» результат деления в конец строки. Это делается путем захвата результата вычитания (текущий номер минус \4) в группу захвата \5, а затем, вне предвидения, сопоставляя часть начала текущего номера, соответствующую \5. Это оставляет оставшуюся необработанную строку в конце совпадающей \4по длине.

Теперь он возвращается к началу внутреннего цикла, где становится очевидным, почему существует критерий делимости на главный фактор. Мы только что поделили на наименьшее простое число числа; если число все еще делится на этот коэффициент, это означает, что исходное число может делиться на четвертую степень этого фактора. Первый раз, когда этот тест выполняется, он бесполезен, но следующие 3 раза он определяет, является ли результат неявного деления на \2еще делимым на \2. Если он еще делится \2на в начале каждой итерации цикла, то это доказывает, что каждая итерация делит число на \2.

В нашем примере с вводом 1296 это будет проходить следующим образом:

\2= 2
\4= 1296/2 = 648
\4= 648/2 = 324
\4= 324/2 = 162
\4 = 162/2 = 81

Теперь регулярное выражение может вернуться к первому шагу; это то, что *делает финал . В этом примере 81 станет новым номером; следующий цикл будет выглядеть следующим образом:

\2= 3
\4= 81/3 = 27
\4= 27/3 = 9
\4= 9/3 = 3
\4= 3/3 = 1

Теперь он снова вернется к первому шагу с 1 в качестве нового номера.

Число 1 не может быть разделено ни на одно простое число, что делает его несоответствующим (?=(xx+?)\2+$), поэтому оно выходит из цикла верхнего уровня (с *последним в конце). Теперь оно достигает x?$. Это может соответствовать только нулю или единице. Текущее число в этой точке будет 0 или 1, если и только если исходное число было совершенной четвертой степенью; если в этот момент он равен 0, это означает, что цикл верхнего уровня никогда не соответствовал чему-либо, а если он равен 1, это означает, что цикл верхнего уровня делил идеальную четвертую степень вниз до тех пор, пока он больше не делился ничем (или во-первых, это был 1, то есть цикл верхнего уровня никогда не совпадал).

Это также можно решить в 49 байтах, выполнив повторное явное деление (которое также обобщается для всех степеней - замените желаемую мощность минус единицу на {3}), но этот метод намного, намного медленнее, и объяснение алгоритма, который он использует выходит за рамки этого ответа:

^((x+)((\2(x+))(?=(\4*)\2*$)\4*(?=\5$\6)){3})?x?$

Попробуйте онлайн!

Решение

^(?:(?=(^|(?<=^x)x|xx\1))(?=(^|\1\2))(^x|\3\2{12}xx))*$

Это регулярное выражение совместимо с версиями Java, Perl, PCRE и .NET. Это регулярное выражение использует целый ряд функций: просмотр вперед, просмотр назад и обратная ссылка, объявленная в будущем. Предварительно объявленные обратные ссылки ограничивают совместимость этого регулярного выражения с несколькими двигателями.

объяснение

Это решение использует следующий вывод.

Полностью расширяя суммирование, мы можем доказать следующее равенство:

Давайте скомбинируем суммирование в левой части:

Вычтите 2 уравнения (верхнее уравнение минус нижнее уравнение), затем сложите суммы в левой части, а затем упростите это:

Мы получаем разницу между последовательными четвертыми степенями в виде суммы степеней:

Это означает, что разница между последовательными четвертыми степенями увеличится на (12n ² + 2).

Чтобы было легче думать, обращаясь к дереву различий в ответе Волатильности :

• Правая часть окончательного уравнения - это вторая строка в разностном дереве.
• Приращение (12n ² + 2) - это третья строка в дереве разностей.

Достаточно математики. Вернуться к решению выше:

• 1-я группа захвата поддерживает серию нечетных чисел для вычисления i ^2, как видно из уравнения.

  Точнее говоря, длина 1-й группы захвата будет 0 (не используется), 1, 3, 5, 7, ..., поскольку цикл повторяется.

  (?<=^x)xустанавливает начальное значение для ряда нечетных чисел. Это ^просто для того, чтобы упустить прогноз на первой итерации.

  xx\1 добавляет 2 и перейти к следующему нечетному числу.

• 2-я группа захвата поддерживает квадратный ряд чисел для i ² .

  Точнее говоря, длина 2-й группы захвата будет 0, 1, 4, 9, ..., поскольку цикл повторяется.

  ^in (^|\1\2)устанавливает начальное значение для квадрата числового ряда. И \1\2добавляет нечетное число к текущему квадратному числу, чтобы продвинуть его к следующему квадратному числу.

• 3-я группа захвата (вне предвидения и фактически потребляет текст) соответствует всей правой части уравнения, которое мы вывели выше.

  ^xin (^x|\3\2{12}xx)устанавливает начальное значение, которое является + 1правой частью уравнения.

  \3\2{12}xxдобавляет увеличение разности (12n ² + 2), используя n ² из группы захвата 2, и сопоставляет разницу одновременно.

Такое расположение возможно из-за того, что количество текста, совпадающего на каждой итерации, больше или равно количеству текста, необходимому для выполнения предварительного просмотра для построения n ² .