Реґулярний вираз для двійкових числів подільних на N

P.Y. написав:

leofun01 написав:
Ото вибрав собі задачу про regex'и, ..
Там, де перевірка подільності двійкового числа на 5?

Там, де перевірка подільності двійкового числа на N. На вхід функція приймає одне число N, на вихід функія дає стрічку, яка містить RegEx (вона може бути статична або динамічно побудована).

1 <= N <= 18;
Довжина RegEx: до 400000; (це підказка до швидкого рішеня, бо це > 3*2^(18-1))
RegEx може містити тільки такі символи: 01?:*+^$()[]|;
Код треба вмістити в 5000 символів;

P.Y. написав:

задача вимагає ввіпхнути всю логіку в єдиний регекс?

І так і ні. Це залежить від вашого алґоритму. Вся лоґіка має бути в коді, regex не мусить бути єдиним на всю програму. Є [як мінімум] 2 шляхи: { важкий, легкий }; легкий мож робити: { ітеративно, рекурсивно }.

Легкий шлях я знаю як робити, але після цього

hufftheweevil (автор kata) написав:

No funny business! There should be no need for prototyping, so don't even think about it.

я буду лупити важкий, буде "funny business", шо би це не значило.

upd: Бачу, до задачі є інтерес .. ну то можете накидувати свої версії тут, а я десь в кінці тиждня підтягнуся. І щоб вам не було сумно, починайте з задач про подільність на 5 і на 7.

Подякували: P.Y.1

Важкий шлях (не рекомендовано користувати, але для розуміня дискретних автоматів може бути користно) :
Послідовно будуїмо реґулярні вирази для не парних N і відповідних (N * 2^p). Початковий і кінцевий стан для автоматів буде 0.

3

від  #     : 0 1 2
до 2*# + 0 : 0 2 1  mod 3
до 2*# + 1 : 1 0 2  mod 3
         |   ^-^-^- вершини
       ребри

Ґраф для дискретний автомат :

RegEx (14) для [не порожної] двійкової послідовності, яку можна ділити на 3 :

(0|1(01*0)*1)+

RegEx для [не порожної] двійкової послідовності, яку можна ділити на (3 * 2^p) :

^(0+|(0*1(01*0)*1)+0*)$    : ділити на  3
^(0+|(0*1(01*0)*1)+00*)$   : ділити на  6
^(0+|(0*1(01*0)*1)+000*)$  : ділити на 12
^(0+|(0*1(01*0)*1)+0{3,})$ : ділити на 24
^(0+|(0*1(01*0)*1)+0{4,})$ : ділити на 48, і так далі ...

5

від  #     : 0 1 2 3 4
до 2*# + 0 : 0 2 4 1 3  mod 5
до 2*# + 1 : 1 3 0 2 4  mod 5
         |   ^-^-^-^-^- вершини
       ребри

 (0| 1(10)*(0|11) \
(01* 0(01)*(1|00) )*1)+
     ^-^^---^-^^-       xor 1

RegEx (36) для [не порожної] двійкової послідовності, яку можна ділити на 5 :

(0|1(10)*(0|11)(01*0(01)*(1|00))*1)+

RegEx для [не порожної] двійкової послідовності, яку можна ділити на (5 * 2^p) :

^(0+|(0*1(10)*(0|11)(01*0(01)*(1|00))*1)+0*)$    : ділити на  5
^(0+|(0*1(10)*(0|11)(01*0(01)*(1|00))*1)+00*)$   : ділити на 10
^(0+|(0*1(10)*(0|11)(01*0(01)*(1|00))*1)+000*)$  : ділити на 20
^(0+|(0*1(10)*(0|11)(01*0(01)*(1|00))*1)+0{3,})$ : ділити на 40
^(0+|(0*1(10)*(0|11)(01*0(01)*(1|00))*1)+0{4,})$ : ділити на 80, і так далі ...

7

від  #     : 0 1 2 3 4 5 6
до 2*# + 0 : 0 2 4 6 1 3 5  mod 7
до 2*# + 1 : 1 3 5 0 2 4 6  mod 7
         |   ^-^-^-^-^-^-^- вершини
       ребри

 (0| 1(1|0 ((0|11)(1|00))* ((0|11)01|10)) \
(01* 0(0|1 ((1|00)(0|11))* ((1|00)10|01)) )*1)+
     ^-^-^ --^-^^--^-^^--- --^-^^-^^-^^--       xor 1

RegEx (80) для [не порожної] двійкової послідовності, яку можна ділити на 7 :

(0|1(1|0((0|11)(1|00))*((0|11)01|10))(01*0(0|1((1|00)(0|11))*((1|00)10|01)))*1)+

RegEx для [не порожної] двійкової послідовності, яку можна ділити на (7 * 2^p) :

# можна ділити на 14
^(0+|(0*1(1|0((0|11)(1|00))*((0|11)01|10))(01*0(0|1((1|00)(0|11))*((1|00)10|01)))*1)+0+)$

# можна ділити на 28
^(0+|(0*1(1|0((0|11)(1|00))*((0|11)01|10))(01*0(0|1((1|00)(0|11))*((1|00)10|01)))*1)+0{2,})$

# можна ділити на 56
^(0+|(0*1(1|0((0|11)(1|00))*((0|11)01|10))(01*0(0|1((1|00)(0|11))*((1|00)10|01)))*1)+0{3,})$

9

від  #     : 0 1 2 3 4 5 6 7 8
до 2*# + 0 : 0 2 4 6 8 1 3 5 7  mod 9
до 2*# + 1 : 1 3 5 7 0 2 4 6 8  mod 9
         |   ^-^-^-^-^-^-^-^-^- вершини
       ребри

 (0| 1((01|1(00|110)*10)(11)*0)* (0(11)*0|1(00|110)*(01|111|101(11)*0)) \
(01* 0((10|0(11|001)*01)(00)*1)* (1(00)*1|0(11|001)*(10|000|010(00)*1)) )*1)+
     ^--^^-^-^^-^^^--^^--^^--^-- -^-^^--^-^-^^-^^^---^^-^^^-^^^-^^--^--       xor 1

RegEx (142) для [не порожної] двійкової послідовності, яку можна ділити на 9 :

(0|1((01|1(00|110)*10)(11)*0)*(0(11)*0|1(00|110)*(01|111|101(11)*0))(01*0((10|0(11|001)*01)(00)*1)*(1(00)*1|0(11|001)*(10|000|010(00)*1)))*1)+

RegEx для [не порожної] двійкової послідовності, яку можна ділити на (9 * 2^p) :

# можна ділити на 18
^(0+|(0*1(1|0((0|11)(1|00))*((0|11)01|10))(01*0(0|1((1|00)(0|11))*((1|00)10|01)))*1)+0+)$

# можна ділити на 36
^(0+|(0*1(1|0((0|11)(1|00))*((0|11)01|10))(01*0(0|1((1|00)(0|11))*((1|00)10|01)))*1)+0{2,})$

# можна ділити на 72
^(0+|(0*1(1|0((0|11)(1|00))*((0|11)01|10))(01*0(0|1((1|00)(0|11))*((1|00)10|01)))*1)+0{3,})$

RegEx з повторно використаними фраґментами [для 9] :

 (0|1(01(11)*0|1(00|110)*(        10  (11)*0))*\
     (0 (11)*0|1(00|110)*( 01|111|101 (11)*0)) \
(01*0(10(00)*1|0(11|001)*(        01  (00)*1))*\
     (1 (00)*1|0(11|001)*( 10|000|010 (00)*1)) \
)*1)+

Видаляємо { пробіли, слеші, розриви рядків } і буде RegEx (154) :

(0|1(01(11)*0|1(00|110)*(10(11)*0))*(0(11)*0|1(00|110)*(01|111|101(11)*0))(01*0(10(00)*1|0(11|001)*(01(00)*1))*(1(00)*1|0(11|001)*(10|000|010(00)*1)))*1)+

11

від  #     : 0  1  2  3  4  5  6  7  8  9 10
до 2*# + 0 : 0  2  4  6  8 10  1  3  5  7  9  mod 11
до 2*# + 1 : 1  3  5  7  9  0  2  4  6  8 10  mod 11

RegEx з повторно використаними фраґментами [для 11] :

 (0|1(1(10)*0   0 |(1(10)*(11|010)|00)(10(01)*(0010|1)|(0|11)110)*((10(01)*00|01|111)        0))*\
     (1(10)*011|01|(1(10)*(11|010)|00)(10(01)*(0010|1)|(0|11)110)*((10(01)*00|01|111)11|110|00)) \
(01*0(0(01)*1   1 |(0(01)*(00|101)|11)(01(10)*(1101|0)|(1|00)001)*((01(10)*11|10|000)        1))*\
     (0(01)*100|10|(0(01)*(00|101)|11)(01(10)*(1101|0)|(1|00)001)*((01(10)*11|10|000)00|001|11)) \
)*1)+
    ^-^-^^--^   ^ --^-^^---^^-^^^--^^--^^-^^---^^^^-^---^-^^-^^^----^^-^^--^^-^^-^^^-        ^---\
     -^-^^--^^^-^^--^-^^---^^-^^^--^^--^^-^^---^^^^-^---^-^^-^^^----^^-^^--^^-^^-^^^-^^-^^^-^^-- \
    xor 1

Видаляїмо { пробіли, слеші, \n, xor } і маємо RegEx (356) для [не порожної] двійкової послідовності, яку можна ділити на 11 :

(0|1(1(10)*00|(1(10)*(11|010)|00)(10(01)*(0010|1)|(0|11)110)*((10(01)*00|01|111)0))*(1(10)*011|01|(1(10)*(11|010)|00)(10(01)*(0010|1)|(0|11)110)*((10(01)*00|01|111)11|110|00))(01*0(0(01)*11|(0(01)*(00|101)|11)(01(10)*(1101|0)|(1|00)001)*((01(10)*11|10|000)1))*(0(01)*100|10|(0(01)*(00|101)|11)(01(10)*(1101|0)|(1|00)001)*((01(10)*11|10|000)00|001|11)))*1)+

Той RegEx можна трохи потиснути [для 11] :

 (0|1(1(10)*0   0 |(1(10)*(11|010)|00)(10(01)*(0010|1)|(0|11)110)*(10(01)*00  | 0  1   |111 )0)*\
     (1(10)*011|01|(1(10)*(11|010)|00)(10(01)*(0010|1)|(0|11)110)*(10(01)*0011|(0|11)(0|111)) ) \
(01*0(0(01)*1   1 |(0(01)*(00|101)|11)(01(10)*(1101|0)|(1|00)001)*(01(10)*11  | 1  0   |000 )1)*\
     (0(01)*100|10|(0(01)*(00|101)|11)(01(10)*(1101|0)|(1|00)001)*(01(10)*1100|(1|00)(1|000)) ) \
)*1)+

Видаляїмо { пробіли, слеші, \n } і буде RegEx (348) :

(0|1(1(10)*00|(1(10)*(11|010)|00)(10(01)*(0010|1)|(0|11)110)*(10(01)*00|01|111)0)*(1(10)*011|01|(1(10)*(11|010)|00)(10(01)*(0010|1)|(0|11)110)*(10(01)*0011|(0|11)(0|111)))(01*0(0(01)*11|(0(01)*(00|101)|11)(01(10)*(1101|0)|(1|00)001)*(01(10)*11|10|000)1)*(0(01)*100|10|(0(01)*(00|101)|11)(01(10)*(1101|0)|(1|00)001)*(01(10)*1100|(1|00)(1|000))))*1)+

Але користувати я буду 356, бо з ним код буде короткий.

▼заплановано на наступні місяці, триває пошук ..

▼не заплановано, але може комусь буде користно

Подякували: P.Y.1

Ласкаво просимо!

Повідомлення: 3

1 Тема від leofun01 09.10.2024 15:10:44 Востаннє редагувалося leofun01 (09.10.2024 15:58:38)

Тема: Реґулярний вираз для двійкових числів подільних на N

2 Відповідь від P.Y. 09.10.2024 20:28:59

Re: Реґулярний вираз для двійкових числів подільних на N

3 Відповідь від leofun01 13.10.2024 22:05:19

Re: Реґулярний вираз для двійкових числів подільних на N

3

5

7

9

11

13

15

Повідомлення: 3

Переглядають тему: 1 гість, 0 користувачів