задачка (программистское)

[avva]

Отличную задачку прочитал в одном блоге сегодня: написать регулярное выражение (используя только самые стандартные средства регулярных выражений), которое распознает строки, являющиеся двоичной записью чисел, делящихся на 7 (и никакие другие). Пустая строка считается вариантом числа 0 (так что тоже распознается).

Я справился за 104 символа. Если вас заинтересовала задачка и вы ее решили, покажите ваше решение в комментах. Я свое помещу завтра вечером.

P.S. Мое решение в комментах.

Comments

[ex-ex-annut.livejournal.com]

сразу ум приходит прямое решение
степени двойки
2^i = 1 mod 7 iff i = 0 mod 3
2^i = 2 mod 7 iff i = 1 mod 3
2^i = -3 mod 7 iff i = 2 mod 3
то есть бинарное чисо делится на 7 если записав его в виде
***kjikjikjikji
i + 2j - 3k делится на 7 (то есть i это число единиц стоящих на расстоянии - mod 3 от правого края бинарного представления числа)
например 105 равно
1101001
ikjikji
i = 3
j = 0
k = 1
3 - 3 = 0 делится на 7

далее делаем конечный автомат
прямая реализация
b_ij i = 0..2 j = 0..6
при считываемом нуле b_ij -> b i+1 mod 3,j
при считываемой единице
b i,0 -> b i +1 mod 3, j +1 mod 7
b i,1 -> b i + 1 mod 3, j + 2 mod 7
b i, 2 -> b i +1 mod 3, j -3 mod 7


наверное, больше, чем 104
простите нет времени сейчас до конца доделывать и оптимизировать

[ygam.livejournal.com]

Признак деления на 7 в восьмеричной системе подобен признаку деления на 9 в десятеричной, и можно построить Mealy machine с тройками цифр и 8 состояниями - но это будет гораздо больше 104 символов.

[ringm.livejournal.com]

Это решение очевидно, да. В принципе, регэксп получается больше 104 символов, но не очень большой. Для восьмеричной системы это выглядит как все варианты разложения 7 на слагаемые, со вставленными произвольно повторенными нулями: (7|60*1|50*(2|10*1)|...|0)*. В двоичную переносится легко, при этом старшие двоичные цифры можно выносить за скобки.

Только отдельная задница в том, что числа мы записываем в "big-endian" формате, и когда мы видим первую единицу, неизвестно, в какой позиции по модулю 3 она стоит. Чтобы решить эту проблему, нужно отдельно разбирать эти три варианта, что опять же сильно увеличивает размер решения. Видимо, я чего-то не понимаю...

[tobe-determined.livejournal.com]

please don't call RegExp "регулярным выражением" :)))

[netch]

Бат вай?

[ringm.livejournal.com]

Решил вернуться к задачке :) ну я и тупица... зачем же все так сложно...
Автомат просто должен честно считать остаток по модулю 7.
При съедании очередной цифры k m:=(m*2+k)%7. Семь состояний, позицию помнить не надо.

[spamsink]

У меня получилось 9 базовых паттернов, между каждыми двумя цифрами которых вставляется (000|111)*, и потом ((эти 9 паттернов через ИЛИ)0*)*. Неоптимально, видать.

[avva.livejournal.com]

А вы проверили ваше решение? У меня паттерн далеко не столь симметричный вышел,
и я не уверен, что понимаю, как ваш работает.

[ex-ex-annut.livejournal.com]

простая, но с первого взгляда кажется неожиданной

Известно, что для проблемы П существует детерминированная машина Тьюринга М, которая решает ее за полиномиальное время
Дать детерминированную машину которая решает П за полиномиальное время (о машине М ничего не известно)

[spamsink]

Увы, я не все перечислил, и кроме вставных 000 и 111, нужно еще включать 011100 и 001110. Идея в том, что цепочек с 3, 4 или 5 единицами, делящихся на 7, в которых не встречается более чем три нуля или три единицы подряд, конечное число, а все остальные получаются из них и цепочек из любого количества нулей путем конкатенации. Но так явно длиннее, чем 104 символа.

[migmit.livejournal.com]

Не надо спорить со стандартной терминологией.

[averros.livejournal.com]

Мне лень было оптимизировать выражение, но вот это гарантировано работает :)

(((((0|00*0)|(1|00*1)1(10*11)*(1|10*0))|((1|00*1)00|(1|00*1)1(10*11)*10*100)(((1|00)0|01(10*11)*10*100))*01(10*11)*(1|10*0))|(((1|00*1)01|(1|00*1)1(10*11)*10*101)|((1|00*1)00|(1|00*1)1(10*11)*10*100)(((1|00)0|01(10*11)*10*100))*((1|00)1|01(10*11)*10*101))((0(10*11)*10*101|(1|0(10*11)*10*100)(((1|00)0|01(10*11)*10*100))*((1|00)1|01(10*11)*10*101)))*(0(10*11)*(1|10*0)|(1|0(10*11)*10*100)(((1|00)0|01(10*11)*10*100))*01(10*11)*(1|10*0)))|(((1|00*1)1(10*11)*0|((1|00*1)00|(1|00*1)1(10*11)*10*100)(((1|00)0|01(10*11)*10*100))*01(10*11)*0)|(((1|00*1)01|(1|00*1)1(10*11)*10*101)|((1|00*1)00|(1|00*1)1(10*11)*10*100)(((1|00)0|01(10*11)*10*100))*((1|00)1|01(10*11)*10*101))((0(10*11)*10*101|(1|0(10*11)*10*100)(((1|00)0|01(10*11)*10*100))*((1|00)1|01(10*11)*10*101)))*(0(10*11)*0|(1|0(10*11)*10*100)(((1|00)0|01(10*11)*10*100))*01(10*11)*0))((1|0((0(10*11)*10*101|(1|0(10*11)*10*100)(((1|00)0|01(10*11)*10*100))*((1|00)1|01(10*11)*10*101)))*(0(10*11)*0|(1|0(10*11)*10*100)(((1|00)0|01(10*11)*10*100))*01(10*11)*0)))*0((0(10*11)*10*101|(1|0(10*11)*10*100)(((1|00)0|01(10*11)*10*100))*((1|00)1|01(10*11)*10*101)))*(0(10*11)*(1|10*0)|(1|0(10*11)*10*100)(((1|00)0|01(10*11)*10*100))*01(10*11)*(1|10*0)))

На самом деле, есть универсальный способ решать эту задачу для любой системы счисления и для любого делителя.

Если интересно, могу рассказать как, и вывесить программку на JavaScript (аж 70 строчек), которую я использовал для генерации этого регулярного выражения.

[avva.livejournal.com]

Конечно есть, например, построить автомат и перевести его в regexp через теорему Клини :)

[averros.livejournal.com]

Ну так оно это и делает :)

[tobe-determined.livejournal.com]

режет слух

[nchaly.livejournal.com]

Немного преобразуя признак делимости на 7 (http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B8%D0%B7%D0%BD%D0%B0%D0%BA_%D0%9F%D0%B0%D1%81%D0%BA%D0%B0%D0%BB%D1%8F#.D0.9F.D1.80.D0.B8.D0.B7.D0.BD.D0.B0.D0.BA_.D0.B4.D0.B5.D0.BB.D0.B8.D0.BC.D0.BE.D1.81.D1.82.D0.B8_.D0.BD.D0.B0_7), для двоичных чисел получаем формулу:
a₀ + a₁ * 2 + a₂ * 4 ...
В общем, долго объяснять, к делу. Возьмем число "111" и будем добавлять нули после последней единицы, пытаясь найти закономерность.

Итерация 0: 111 делится на 7, причем число нулей справа не влияет на делимость.
1: 1X101 делится на 7, если вместо X будет стоять (0(0{3}*))
2: 1X1001 - случай более сложный. Один из экстремальных под-случаев: ((001){7})+
Методом подбора получаем два варианта:
11011001 и 01101001. Обобщая:
2a: "1(0{3}*)10(0{3}*)1(0{3}*)100(0{3}*)1" и
2b: "01(0{3}*)10(0{3}*)100(0{3}*)1"
3: (Обобщение 1) Также делится на 7 "1X1X1", где X = "(0{3})*",
4: (Обобщение 2) Также делится на 7 "1X1X1", где X = "(0(0{3})*)",
5: 1X1000001 - частный случай 2.
6: 1X10000001 - частный случай 3.
7: 1X100000001 - частный случай 4.
8: 1X1000000001 - частный случай 2.
9: частный случай 3 и мы зациклились на 3х случаях - 2, 3, 4. Теперь пробуем записать все вместе.

Самая общая запись: (A | B | C | D)+,
где A - (1(0{3}*)10(0{3}*)1(0{3}*)100(0{3}*)1(0)* | 01(0{3}*)10(0{3}*)100(0{3}*)1(0)*) (случай 2);
B - (1(0{3})*1(0{3})*1(0)*) (случай 3);
C - (1(0(0{3})*)1(0(0{3})*)1(0)*) (случай 4).
D - ((001){7}(0)*) (экстремальный случай 2)

В итоге: ((1(0{3}*)10(0{3}*)1(0{3}*)100(0{3}*)1(0)* | 01(0{3}*)10(0{3}*)100(0{3}*)1(0)*) | (1(0{3})*1(0{3})*1(0)*) | (1(0(0{3})*)1(0(0{3})*)1(0)*) | ((001){7}(0)*))+

156 символов, но я не совсем уверен, а проверять времени нет. Может что-то упустил?

(Сокращенная форма:
((1X10X1X100X1(0)* | 01X10X100X1(0)*) | (1X1X1(0)*) | (10X10X1(0)*) ((001){7}(0)*))+,
где X - тройки нулей - (0{3})*)

[nchaly.livejournal.com]

Опечатка:
3: (Обобщение 1) Также делится на 7 "1X1X1", где X = "(0{3})*",
4: (Обобщение 2) Также делится на 7 "1X1X1", где X = "(0(0{3})*)",

Следует читать:
3: (Обобщение 0) Также делится на 7 "1X1X1", где X = "(0{3})*",
4: (Обобщение 1) Также делится на 7 "1X1X1", где X = "(0(0{3})*)",

[avva.livejournal.com]

Выглядит убедительно, но проверять у меня сейчас тоже времени нет :)

[avva.livejournal.com]

Мой вариант:

^(0|1((0(01|111)*(00|110))*(1|0(01|111)*10))(01*0(1(10|000)*(11|0(000)
*01))*(0|1(10|000)*0(000)*1))*1)*$

Кстати, о ^ и $ в начале и конце нельзя забывать, без них неправильно работает по понятным причинам, если задуматься.

Как сделал: сначала немного тормозил :) потом спросил себя, откуда я собственно знаю, что это регулярный язык. Сам себе ответил: потому что легко написать автомат, который проверяет путем просто деления в столбик на 7. Во время деления в столбик на 7 в уме всегда надо помнить не более чем текущий остаток, т.е. у автомата не должно быть более 6 состояний, +-1. Написал автомат. Он очень простой. Состояния обозначаются остатками в скобках, например (010), а переходы в зависимости от следующего символа --0--> или --1-->. Тогда автомат выглядит так (картинку лень рисовать):

(0) --0--> (0)
(0) --1--> (1)

(1) --0--> (10)
(1) --1--> (11)

(10) --0--> (100)
(10) --1--> (101)

ну и так далее. Переходя из трехсимвольных состояний, приписываем цифру, вычитаем 7 и смотрим, куда пришли. Единственный способ вернуться обратно в состояние (0), раз из него выйдя - через (11) --1--> (0).

Дальше из автомата делается регэкс. Это можно сделать автоматически через теорему Клини, но тогда он выходит огромный. Если руками, то можно сделать несколько наблюдений. Нам надо закончить обработку ввода, находясь в состоянии (0) - начальном и конечном. Значит, все выражение будет выглядеть как (0|back-to-zero)* где back-to-zero ловит все возможные способы выйти из 0 и вернуться обратно. Поскольку по дороге обратно мы обязаны пройти через состояние (11) и сделать из него шаг --1-->, можно записать:

back-to-zero = 1(X)(Y)*1

где X ловит все способы добраться от (1) до (11), не проходя уже по дороге через (11), т.е. первый проход до (11); а Y ловит все способы сделать цикл, начинающийся и кончающийся в (11), но не возвращающийся еще в (0). После того, как мы доходим до (1) первой единичкой, оттуда до (11) с помощью X, и крутимся в (11) сколько угодно раз с помощью Y*, мы делаем последний шаг единичкой и возвращаемся в (0).

Ну и дальше X и Y выписываются отдельно похожим образом. В каждом из них мы смотрим на все возможные маршруты, отдельно отмечая циклы (которых всего несколько, так что это просто) и выделяя их в *-ные подстроки. Каждый из них мы по сути дела в уме делим на отдельные случаи и расписываем их так же, как back-to-zero. Это тот же подход, что и в доказательстве теоремы Клини, но из-за того, что мы это делаем на детерминистском автомате и вручную, можно избежать большого количества ненужных *-блоков и повторений. В конце концов выходит

X = (0(01|111)*(00|110))*(1|0(01|111)*10)

Y = 01*0(1(10|000)*(11|0(000)*01))*(0|1(10|000)*0(000)*1)

и из них компонуется ответ.

[nchaly.livejournal.com]

Parsing Techniques подействовали? :)

[avva.livejournal.com]

Там этого нет, кстати (перехода от автомата к регэкспу), это обычно не нужно на практике... они помогли в том смысле, что я мозги немного прочистил на всю эту тему, так что быстрее двигались :)

Parsing Techniques

[nchaly.livejournal.com]

Я пока не дошел до места, где этого нет :) "Прошел" классификацию грамматик, шетопом поругивая университетских аспирантов, которые преподавали нам это сами не особо разбираясь. Оказывается, я многие вещи делал автоматически. Только теперь вник в суть. Спасибо за линк, хорошая книга. Даже на английском ее нетрудно читать.

[ex-ex-annut.livejournal.com]

более простой признак делимости на 7
который легко доказывается
http://avva.livejournal.com/1727810.html?replyto=40659010

[avva.livejournal.com]

Всегда пожалуйста :)

[ivan-gandhi.livejournal.com]

It is kind of obvious how this is accomplished; and yes, one can strip out starting and trailing sequences, and optimize it.

But JavaScript! That's good. I thought I was the only one that uses JavaScript for casual calculation. :)

[averros.livejournal.com]

Heh. One of the things I did in recent years is implementing a Distributed JavaScript compiler & bytecode interpreter. (This is a flavor of security-hardened JavaScript augmented with strong types and remote method execution, used as Inteface Definition Language and scripting language of Secure Object Request Broker).

[ex-ex-annut.livejournal.com]

есть универсальный способ решать эту задачу для любой системы счисления и для любого делителя.

Эта задачка сейчас достаточно стандартная для начальных курсов по теории автоматов.языков.

еще одна ошибка

[nchaly.livejournal.com]

((001){7}(0)*) следует заменить на (1(001){6}(0)*)