С регулярно наступающим Новым годом вас!

    Наткнувшись на занятную головоломку на тему регулярных выражений, конечно же я не смог пройти мимо:

    regex.alf.nu

    В честь наступающего Нового года я набрал в ней 2014 очков. Кто больше?

    Мои варианты ответов
    Plain strings
    ^(.*oo[^k])|foo$
    

    Anchors
    .+ick$
    

    Ranges
    ^[a-f]{2,}[^m]$
    

    Backrefs
    (\w{3}).*\1.*
    

    Abba
    ^(?!.*?(\w)\1).*$|ef
    

    A man, a plan
    ^(\w)(\w).*\2\1$
    

    Prime
    ^x(xx+?)\1+$
    

    Four
    (\w).*\1.*\1.*\1
    

    Order
    ^[^o].{1,5}$
    

    Triples
    00
    

    Glob
    \*(\w+).+\S\1|(\w+)\*.+\1
    

    Balance
    ((<)\2)\1
    

    Power
    ^((((((((((x)\10?)\9?)\8?)\7?)\6?)\5?)\4?)\3?)\2?)\1?$
    

    Поделиться публикацией

    Комментарии 41

      +1
      Да, фактически я не осилил Balance и не понял Triples.
        +1
        Да и не страшно, Ваш счет очень символичен :) плюс дает повод к состязанию.
        Благодарю за разминку для мозга и С Новым Годом Вас и всех хабражителей!
        +4
        8. Four: (\w).(\w).*\2.\1 — 194 points
        Замысел: повторение 2-х символов (расположенных не рядом а через 1 символ) в прямом и обратном порядке.
        Хорошо видно на примере «unintelligibility»: tel и обратное ему lit, t..l <=> l..t.
          +1
          Четыре символа, через один: (.).\1.\1.\1 = 198, думаю можно еще оптимизировать.
            +2
            (.)(.\1){3}
          +3
          12. Balance: ^(<(<(<(<(<(<(<>)*>)*>)*>)*>)*>)*>)*$ — 283 points
          Замысел: кол-во открывающихся и закрывающихся равно, так что дублируем это условие то момента пока будет покрыта максимально длинная непрерывная последовательность.
            +2
            Что ж за мазохизм парсить регулярными выражениями нерегулярные языки :)
              0
              Регулярные выражения в тесте не поддерживают lookbehind'ы (хотя lookahead'ы прокатывают) и рекурсивные выражения и многое другое.
              Упражнение с балансом должно решаться рекурсивной регуляркой/вызовом процедуры: например <(?R)*> при включенном глобальном матче.
              +3
              Набрал 2683, некоторые из решений брал ваши и пытался их улучшить. В итоге вот мои ответы, отличные от ваших:
              Скрытый текст
              Plain strings
              foo

              Anchors
              ick$

              Ranges
              ^[a-f]+$

              Backrefs
              (.{3}).*\1

              Prime
              ^x(x(x+)?)\1$

              Four
              (\w).\1.\1.\1

              Triples
              00|22|44|55

              Glob
              ^([^*]+) .+ \1$|^\*([^*]+) .+ .+\2$|^([^*]+)\* .+ \3.+$|\*([^*]+)\*.* .+ .+\4.+$

              Balance
              ^(<(<(<(<(<(<(<(<(<(<(<>)*>)*>)*>)*>)*>)*>)*>)*>)*>)*>)*$


              Некоторые — просто более короткая запись ваших выражений. Логику некоторых заданий не понял. В особенности Triple, но мой вариант дает больше очков)
                +1
                Добавлю ещё немного очков для Triples:
                Скрытый текст
                00|22|44|55|7[14]


                Update: после рефреша увидел ниже решение получше.
                  0
                  Anchors можно оптимизировать
                  Скрытый текст
                  k$
                  +1
                  Матчится всё, кроме Triples, Glob и Balance. (2642)

                  Скрытый текст
                  Plain strings (207)
                  foo

                  Anchors (208)
                  k$

                  Ranges (202)
                  ^[a-f]*$

                  Backrefs (201)
                  (...).*\1

                  Abba (193)
                  ^(?!.*(.)(.)\2\1)

                  A man, a plan (176)
                  ^(.)(.).*\2\1$

                  Prime (285)
                  ^(?!(xx+?)\1+$)

                  Four (199)
                  (.)(.\1){3}

                  Order (187)
                  ^[a-fgm](?!.*(a|less$))

                  Triples (229)
                  00|22|44|55

                  Glob (220)
                  (^(.+)(?!.*\*).*\2$|(.+)\*(.+)\s.*\3.+$)

                  Balance (242)
                  ^<<.*>>$

                  Powers (93)
                  ^(?!(x(xx)+)\1*$)
                    +5
                    7. Prime: ^(?!(x{2,})\1+$) — 284 points
                    Замысел: включать линейные числа, исключать плоские числа.
                    Интерактивно поиграться можно тут — www.debuggex.com/r/vDKnAGo_5jWbl_xC (очень помогло при составлении и отладке)

                    Из wiki:
                    Линейные числа — числа, не разлагающиеся на сомножители, то есть их ряд совпадает с рядом простых чисел, дополненным единицей: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, … (последовательность A008578 в OEIS).
                    Плоские числа — числа, представимые в виде произведения двух сомножителей, то есть составные: 4, 6, 8, 9, 10, 12, 14, 15, … (последовательность A002808 в OEIS)

                    Решения Triples и Glob довольно монструозны, так что не публикую. В сумме набрал — 3126.
                      +2
                      Вот так у меня получилось, часть — оптимизация выражений сообщества. Думаю, и здесь можно соптимизировать, но спать хочется :)
                      Все заматчилось. (странно, спойлер и разметка не работает… :( )

                      Plain strings (207)
                      Anchors (206)
                      Ranges (202)
                      Backrefs (201)
                      Abba (193)
                      A man, a plan (176)
                      Prime (286)
                      Four (199)
                      Order (199)
                      Triples (563)
                      Glob (347)
                      Balance (283)
                      Powers (93)

                      Score 3155

                      Plain strings
                      foo

                      Anchors
                      ick$

                      Ranges
                      ^[a-f]+$

                      Backrefs
                      (...).*\1

                      Abba
                      ^(?!.*(.)(.)\2\1)

                      A man, a plan
                      ^(.)(.).*\2\1$

                      Prime
                      ^(?!(xx+)\1+$)

                      Four
                      (.)(.\1){3}

                      Order
                      ^.{5}[^e]?$

                      Triples
                      (00[0369]|12|015|60|50|76|87|9005|78|04|47|31|58|72|02|75|303|824)$

                      Glob
                      ^(([^*]+) .+ \2|\*([^*]+) .+ .+\3|([^*]+)\*.+ \4.+|\*([^*]+)\*.+ .+\5.+)$

                      Balance
                      ^(([^*]+) .+ \2|\*([^*]+) .+ .+\3|([^*]+)\*.+ \4.+|\*([^*]+)\*.+ .+\5.+)$

                      Powers
                      ^(?!(x(xx)+)\1*$)

                        +1
                        foo 207
                        k$ 208
                        [a-f]{4} 202
                        (\w{3}).*\1 199
                        (...).*\1 201
                        ^(?!.*(.)(.)\2\1) 193

                          +1
                          (.)(.)[^r]?\2\1 175

                          кстати: four решил не так, как все
                          ([aoei])[^bcnal]\1 192
                          +1
                          Triples (578) : 00[03]$|06|01[25]$|009|2[34]|32|5[45]|^8[17]|390|472
                          Glob (356) : ^((\w+).+ \2|\*(\w+) .+ .+\3|(\w+)\*.+ \4.+|\*(\w+)\*.+ .+\5.+)$
                          
                            +1
                            Чит:
                            Balance (286) : ^(<(<(<(<(<(<<>>)*>)*>)*>)*>)*>)*$
                            
                              +1
                              Ещё чуть-чуть:
                              Balance (287) : ^(<(<(<(<(<(<.*)*>)*>)*>)*>)*>)*$
                              
                              +2
                              Triples (587) : ^(?!.*(0005|01[034]|08|11|68|84|9[237]))|27
                              
                                +2
                                Ещё чит:
                                Glob (375) : err|fa|lo|pl|bo|co|c$|ep|pr|tl|ur|wr|ob|rb|ta
                                  0
                                  Glob (381) : fa|ta|tl|pl|co|c$|[nue]p|[puw]r|[o re]b
                                  
                                +2
                                С регулярно наступающим Новым годом вас!

                                Регулярное Вам спасибо!
                                  +4
                                  что-то вы перемудрили. Первый  — foo, второй — k$, третий — ^[a-f]+$ и так далее.
                                    +2
                                    Жаль, что в Javascript не поддерживаются рекурсивные подмаски (как в PCRE). А так для Balance можно было бы использовать такое выражение:
                                    ^(([^<>]*<(?1)>)*[^<>]*)$
                                    (можно протестировать, например, в Notepad++)
                                      +1
                                      Спасибо и Вас с регулярно наступающим! :)
                                        +1
                                        Собрал лучшие (3219):
                                        Plain strings (207)
                                        foo
                                        

                                        Anchors (208)
                                        k$
                                        

                                        Ranges (202)
                                        ^[a-f]+$
                                        

                                        Backrefs (201)
                                        (...).*\1
                                        

                                        Abba (195)
                                        ^(?!.*(.)\1)|fu
                                        

                                        A man, a plan (176)
                                        ^(.)(.).*\2\1$
                                        

                                        Prime (286)
                                        ^(?!(xx+)\1+$)
                                        

                                        Four (199)
                                        (.)(.\1){3}
                                        

                                        Order (199)
                                        ^.{5}[^e]?$
                                        

                                        Triples (587)
                                        ^(?!.*(0005|01[034]|08|11|68|84|9[237]))|27
                                        

                                        Glob (379)
                                        err|[tp]l|[cbl]o|ep|[upw]r|[or]b|[ft]a|c$
                                        

                                        Balance (287)
                                        ^(<(<(<(<(<(<.*)*>)*>)*>)*>)*>)*$
                                        

                                        Powers (93)
                                        ^(?!(x(xx)+)\1*$)
                                        
                                          0
                                          A man, a plan (177)
                                          ^(.)[^p].*\1$
                                          +2
                                          Score 3169 в результате. Не сразу понял, что можно упускать .*

                                          Результаты
                                          Plain strings (207)
                                          foo

                                          Anchors (208)
                                          k$

                                          Ranges (202)
                                          ^[a-f]+$

                                          Backrefs (201)
                                          (...).*\1

                                          Abba (193)
                                          ^(?!.*(.)(.)\2\1)

                                          A man, a plan (176)
                                          ^(.)(.).*\2\1$

                                          Prime (286)
                                          ^(?!(xx+)\1+$)

                                          Four (198)
                                          (.).\1.\1.\1

                                          Order (199)
                                          ^.{0,5}[^e]$

                                          Triples (575)
                                          (00[03]$|^8[^5]|06|01[52]$|009|5[45]|2[43]|902|289|^32)

                                          Glob (348)
                                          ^(([^*]+).+ \2|\*([^*]+)\*.+ .+\3.+|([^*]+)\*.+ \4.*|\*([^*]+) .+ .+\5)$

                                          Balance (283)
                                          ^(<(<(<(<(<(<(<>)*>)*>)*>)*>)*>)*>)*$

                                          Powers (93)
                                          ^(?!(.(..)+)\1*$)


                                          Пришлось помучатся с числами (Triples). Совсем не приходило никакого путного решения.

                                          Спасибо, размял мозги.
                                            +6
                                            Всего лишь 720. Было сложно, но я упоротый упорный.

                                            Некоторые ответы
                                            1.^(afoot|catfoot|dogfoot|fanfoot|foody|foolery|foolish|fooster|footage|foothot|footle|footpad|footway|hotfoot|jawfoot|mafoo|nonfood|padfoot|prefool|sfoot|unfool)$
                                            2.^(Mick|Rick|allocochick|backtrick|bestick|candlestick|counterprick|heartsick|lampwick|lick|lungsick|potstick|quick|rampick|rebrick|relick|seasick|slick|tick|unsick|upstick)$
                                            3.^(abac|accede|adead|babe|bead|bebed|bedad|bedded|bedead|bedeaf|caba|caffa|dace|dade|daff|dead|deed|deface|faded|faff|feed)$
                                            6.^(civic|deedeed|degged|hallah|kakkak|kook|level|murdrum|noon|redder|repaper|retter|reviver|rotator|sexes|sooloos|tebbet|tenet|terret)$
                                            9.^(access|accloy|adeem|aflow|aglow|beefin|befist|billot|bossy|certy|chintz|chips|chort|cloop|coost|demos|fitty|flory|flossy|ghost|mopsy)$
                                            10.^(000000000|000000003|000000006|000000009|000000012|000000015|066990060|140091876|173655750|312440187|321769005|368542278|390259104|402223947|443512431|714541758|747289572|819148602|878531775|905586303|953734824)$

                                            За остальные ответы (в том же духе) почему-то дают отрицательное количество очков…
                                              +1
                                              За каждый символ регэкспа отнимают 1 очко, видимо там длина регэкспа была больше получаемых очков
                                              0
                                              Собрал лучшие на данный момент решения.
                                              Результат 3398
                                              Plain strings (207): foo
                                              Anchors (208): k$
                                              Ranges (202): [a-f]{4}
                                              Backrefs (201): (...).*\1
                                              Abba (193): ^(?!.*(.)(.)\2\1)
                                              A man, a plan (177): ^(.)[^p].*\1$
                                              Prime (286): ^(?!(xx+)\1+$)
                                              Four (199): (.)(.\1){3}
                                              Order (199): ^.{5}[^e]?$
                                              Triples (587): ^(?!.*(0005|01[034]|08|11|68|84|9[237]))|27
                                              Glob (381): fa|ta|tl|pl|co|c$|[nue]p|[puw]r|[o re]b
                                              Balance (287): ^(<(<(<(<(<(<.*)*>)*>)*>)*>)*>)*$
                                              Powers (93): ^(?!(x(xx)+)\1*$)
                                              Long count (178): 0+ 0+1 0010 0011 0100 0101 0110 01+ 10+ 1001 1010 1011 1100 1101 1+0 1+$
                                              
                                                +1
                                                Ещё +2 балла для ровного счёта в 3400:
                                                Abba(195): ^(?!.*(.)\1)|fu
                                                
                                                  +1
                                                  Ещё (3418):
                                                  Long count (196): ^0+ 0+1 0010 0011 0100 0101 0110 01+ 10+ 1001 1010 101
                                                  
                                                    0
                                                    А мне за ваш вариант Long count даёт 216. В любом случае можно чуть улучшить:
                                                    ^0+ 00.{8}0011 0100 0101 0110 01+ 10+ 1001 1010 101
                                                    
                                                      +1
                                                      Тогда уж
                                                      ^0+ 00.+0011 0100 0101 0110 01+ 10+ 1001 1010 101
                                                      


                                                      Есть Long count v2, где спойлером к предыдущему заданию указано «suffusion of yellow». Что бы это значило…
                                                0
                                                Для Triples, Glob, Balance
                                                Score 3688
                                                Plain strings (207)
                                                Anchors (208)
                                                Ranges (202)
                                                Backrefs (201)
                                                Abba (193)
                                                A man, a plan (176)
                                                Prime (286)
                                                Four (199)
                                                Order (199)
                                                Triples (561)
                                                Glob (381)
                                                Balance (287)
                                                Powers (93)
                                                Long count (252)
                                                Long count v2 (243)
                                                  +1
                                                  Как вы улучшили Long count`ы? Я вот такие смог придумать только:
                                                  Long count (250):     ^\1(?!.*(\d{4}).*\1)
                                                  Long count v2 (240):  ^\1(?!.*(\d{4}).*\1|.*111 0|s)
                                                  

                                                  Общий результат 3701
                                                    0
                                                    ^(?!.*(\S{4}).*\1)
                                                    ^(?!.*(\S{4}).*\1|.{38}0|s)
                                                    я не додумал только более красивое решение для Triples, Glob, Balance
                                                  0
                                                  Дело было к ночи, пришла в голову идея «решить» головоломку методом перебора. Об оценке времени перебора задумался, только когда скрипт был готов на 3/4, так что, осознав бессмысленность затеи, всё же дописал его, чтобы посчитать точное время выполнения.
                                                  Первые 2 решения нашлись за секунду, но уже на третей задаче потребовалось более 4 часов, чтобы убедиться, что решений короче 6 символов у неё нет. Наверняка можно оптимизировать алгоритм и перебирать 6- или даже 7-символьные решения за то же время, но решить задачу это не поможет.

                                                  Можно спать спокойно, в ближайшие несколько лет нас компьютерами не заменят :)

                                                  Если кому-то интересно, готовый скрипт на C#, реализованный в виде LINQ-выражения, можно посмотреть здесь. Писалось в LINQPad, требует HtmlAgilityPack и Newtonsoft.Json.
                                                    0
                                                    Просто вы не умеете их готовоить (с)
                                                    к слову сделал регулярку для Glob с 392 поинтами

                                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                  Самое читаемое