Как стать автором
Поиск
Написать публикацию
Обновить

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

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


Update: после рефреша увидел ниже решение получше.
Всего голосов 1: ↑1 и ↓0+1
Anchors можно оптимизировать
Скрытый текст
k$
Комментарий пока не оценивали0
Матчится всё, кроме 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*$)
Всего голосов 1: ↑1 и ↓0+1
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.
Всего голосов 5: ↑5 и ↓0+5
Вот так у меня получилось, часть — оптимизация выражений сообщества. Думаю, и здесь можно соптимизировать, но спать хочется :)
Все заматчилось. (странно, спойлер и разметка не работает… :( )

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*$)

Всего голосов 2: ↑2 и ↓0+2
foo 207
k$ 208
[a-f]{4} 202
(\w{3}).*\1 199
(...).*\1 201
^(?!.*(.)(.)\2\1) 193

Всего голосов 1: ↑1 и ↓0+1
(.)(.)[^r]?\2\1 175

кстати: four решил не так, как все
([aoei])[^bcnal]\1 192
Всего голосов 1: ↑1 и ↓0+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: ↑1 и ↓0+1
Чит: 
Balance (286) : ^(<(<(<(<(<(<<>>)*>)*>)*>)*>)*>)*$
Всего голосов 1: ↑1 и ↓0+1
Ещё чуть-чуть:
Balance (287) : ^(<(<(<(<(<(<.*)*>)*>)*>)*>)*>)*$
Всего голосов 1: ↑1 и ↓0+1
Triples (587) : ^(?!.*(0005|01[034]|08|11|68|84|9[237]))|27
Всего голосов 2: ↑2 и ↓0+2
Glob (381) : fa|ta|tl|pl|co|c$|[nue]p|[puw]r|[o re]b
Комментарий пока не оценивали0
С регулярно наступающим Новым годом вас!

Регулярное Вам спасибо!
Всего голосов 2: ↑2 и ↓0+2
что-то вы перемудрили. Первый  — foo, второй — k$, третий — ^[a-f]+$ и так далее.
Всего голосов 8: ↑6 и ↓2+4
Жаль, что в Javascript не поддерживаются рекурсивные подмаски (как в PCRE). А так для Balance можно было бы использовать такое выражение:
^(([^<>]*<(?1)>)*[^<>]*)$
(можно протестировать, например, в Notepad++)
Всего голосов 2: ↑2 и ↓0+2
Спасибо и Вас с регулярно наступающим! :)
Всего голосов 1: ↑1 и ↓0+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*$)
Всего голосов 1: ↑1 и ↓0+1
A man, a plan (177)
^(.)[^p].*\1$
Комментарий пока не оценивали0
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). Совсем не приходило никакого путного решения.

Спасибо, размял мозги.
Всего голосов 2: ↑2 и ↓0+2
Всего лишь 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)$

За остальные ответы (в том же духе) почему-то дают отрицательное количество очков…
Всего голосов 8: ↑7 и ↓1+6
За каждый символ регэкспа отнимают 1 очко, видимо там длина регэкспа была больше получаемых очков
Всего голосов 1: ↑1 и ↓0+1
Собрал лучшие на данный момент решения.
Результат 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+$
Комментарий пока не оценивали0
Ещё +2 балла для ровного счёта в 3400:
Abba(195): ^(?!.*(.)\1)|fu
Всего голосов 1: ↑1 и ↓0+1
Ещё (3418):
Long count (196): ^0+ 0+1 0010 0011 0100 0101 0110 01+ 10+ 1001 1010 101
Всего голосов 1: ↑1 и ↓0+1
А мне за ваш вариант Long count даёт 216. В любом случае можно чуть улучшить:
^0+ 00.{8}0011 0100 0101 0110 01+ 10+ 1001 1010 101
Комментарий пока не оценивали0
Тогда уж
^0+ 00.+0011 0100 0101 0110 01+ 10+ 1001 1010 101


Есть Long count v2, где спойлером к предыдущему заданию указано «suffusion of yellow». Что бы это значило…
Всего голосов 1: ↑1 и ↓0+1
Для 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)
Комментарий пока не оценивали0
Как вы улучшили Long count`ы? Я вот такие смог придумать только:
Long count (250):     ^\1(?!.*(\d{4}).*\1)
Long count v2 (240):  ^\1(?!.*(\d{4}).*\1|.*111 0|s)

Общий результат 3701
Всего голосов 1: ↑1 и ↓0+1
^(?!.*(\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.
Всего голосов 2: ↑1 и ↓10
Просто вы не умеете их готовоить (с)
к слову сделал регулярку для Glob с 392 поинтами
Комментарий пока не оценивали0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Показать лучшие за всё время

Истории

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2024, Habr