ValiDate ISO 8601 от RX

16

Вызов

Найдите кратчайшее регулярное выражение, которое

  1. проверяет, т.е. совпадает, каждую возможную дату в Григорианском календаре Proleptic (которая также применяется ко всем датам до его первого принятия в 1582 году) и
  2. не соответствует ни одной недействительной дате.

Выход

Поэтому вывод правдивый или ложный.

вход

Ввод в любом из 3 расширенных форматов даты ISO 8601 - без раз.

Первые два ±YYYY-MM-DD(год, месяц, день) и ±YYYY-DDD(год, день). Оба нуждаются в специальном корпусе для високосного дня. Они наивно сопоставляются отдельно этими расширенными RX:

(?<year>[+-]?\d{4,})-(?<month>\d\d)-(?<day>\d\d)
(?<year>[+-]?\d{4,})-(?<doy>\d{3})

Третий формат ввода ±YYYY-wWW-D(год, неделя, день). Это сложный из-за сложной модели високосной недели.

(?<year>-?\d{4,})-W(?<week>\d\d)-(?<dow>\d)

Базовая, но недостаточная проверка достоверности для всех трех вместе выглядела бы примерно так:

[+-]?\d{4,}-((0\d|1[0-2])-([0-2]\d|3[01]) ↩
            |([0-2]\d\d|3[0-5]\d|36[0-6]) ↩
            |(W([0-4]\d|5[0-3])-[1-7]))

условия

Високосный год в календаре преждевренного григорианскому содержит високосный день …-02-29 и , таким образом , он долго 366 дней, следовательно , …-366существует. Это происходит в любом году, порядковый номер которого делится на 4, но не на 100, если он также не делится на 400. В этом календаре существует нулевой год, и это високосный год.

Долгий год в недельном календаре ISO содержит 53 - ю неделю, что один может срок на « прыжок неделю ». Это происходит во все годы, когда 1 января - четверг, и дополнительно во все високосные годы, когда это среда. Оказывается, это происходит каждые 5 или 6 лет обычно, по-видимому, нерегулярно.

Год имеет как минимум 4 цифры. Не нужно поддерживать годы с более чем 10 цифрами, потому что это достаточно близко к возрасту вселенной (около 14 миллиардов лет). Знак «плюс» необязателен, хотя действительный стандарт предполагает, что он должен быть обязательным для годов с более чем 4 цифрами.

Частичные или усеченные даты, то есть с точностью менее суток, не должны приниматься.

Части нотации даты, например, месяц, не должны совпадать с группой, на которую можно сослаться.

правила

Это код-гольф. Самое короткое регулярное выражение без выполненного кода выигрывает. Обновление: вы можете использовать такие функции, как рекурсия и сбалансированные группы, но будут оштрафованы с коэффициентом 10, на который затем умножается количество символов! Это теперь отличается от правил в жестком коде гольфа: регулярное выражение для делимости на 7 . Ранее ответ выигрывает ничью.

Контрольные примеры

Действительные тесты

2015-08-10
2015-10-08
12015-08-10
-2015-08-10
+2015-08-10
0015-08-10
1582-10-10
2015-02-28
2016-02-29
2000-02-29
0000-02-29
-2000-02-29
-2016-02-29
200000-02-29
2016-366
2000-366
0000-366
-2016-366
-2000-366
2015-081
2015-W33-1
2015-W53-7
 2015-08-10 

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

Неверные форматы

-0000-08-10     # that's an arbitrary decision
15-08-10        # year is at least 4 digits long
2015-8-10       # month (and day) is exactly two digits long, i.e. leading zero is required
015-08-10       # year is at least 4 digits long
20150810        # though a valid ISO format, we require separators; could also be interpreted as a 8-digit year
2015 08 10      # separator must be hyphen-minus
2015.08.10      # separator must be hyphen-minus
2015–08–10      # separator must be hyphen-minus
2015-0810
201508-10       # could be October in the year 201508
2015 - 08 - 10  # no internal spaces allowed
2015-w33-1      # letter ‘W’ must be uppercase
2015W33-1       # it would be unambiguous to omit the separator in front of a letter, but not in the standard
2015W331        # though a valid ISO format we require separators
2015-W331
2015-W33        # a valid ISO date, but we require day-precision
2015W33

Неверные даты

2015        # a valid ISO format, but we require day-precision
2015-08     # a valid ISO format, but we require day-precision
2015-00-10  # month range is 1–12
2015-13-10  # month range is 1–12
2015-08-00  # day range is 1–28 through 31
2015-08-32  # max. day range is 1–31
2015-04-31  # day range for April is 1–30
2015-02-30  # day range for February is 1–28 or 29
2015-02-29  # day range for common February is 1–28
2100-02-29  # most century years are non-leap
-2100-02-29 # most century years are non-leap
2015-000    # day range is 1–365 or 366
2015-366    # day range is 1–365 in common years
2016-367    # day range is 1–366 in leap years
2100-366    # most century years are non-leap
-2100-366   # most century years are non-leap
2015-W00-1  # week range is 1–52 or 53
2015-W54-1  # week range is 1–53 in long years
2016-W53-1  # week range is 1–52 in short years
2015-W33-0  # day range is 1–7
2015-W33-8  # day range is 1–7
Crissov
источник
2
Этот вопрос не является четко определенным, поскольку язык регулярных выражений не указан.
orlp
1
@orlp Если не указано иное, выбор не ограничен. Я специально написал «regex» или «RX», чтобы можно было использовать диалекты, которые допускают рекурсию и т. Д. (Т. Е. CFG, а не RG).
Crissov
Я настоятельно рекомендую вам ограничить язык регулярных выражений, потому что участнику будет очень трудно часами работать над решением, которое будет тривиально побеждено языком, который является существенно более мощным. Если вы ограничите язык фактическим CS-определением регулярных выражений (например, DFA), тогда проблема станет интересным ответом на оптимизацию.
orlp
Проверка дат ISO-8601 с использованием регулярных выражений - это то, что я должен был сделать для работы. Но согласитесь с orlp, я думаю, что здесь необходим язык.
Алекс А.
1
Regex наследует от Method в Perl 6, поэтому сам является формой исполняемого кода.
Брэд Гилберт b2gills

Ответы:

4

PCRE (также Perl), 778 байт

/^([+-]?\d*((([02468][048]|[13579][26]|\d\d(?!00))([02468][048]|[13579][26]))|\d{4}(?!-02-29|-366))-((?!02-3|(0[469]|11)-31|000)((0[1-9]|1[012])-(0[1-9]|[12]\d|30|31)|([012]\d\d|3([0-5]\d|6[0-6])))|(W(?!00)([0-4]\d|51|52)-[1-7]))|((\+?\d*([02468][048]|[13579][26])|-\d*([02468][159]|[13579][37]))(04|09|15|20|26|32|37|43|48|54|60|65|71|76|82|88|93|99)|(\+?\d*([02468][159]|[13579][37])|-\d*([02468][26]|[13579][048]))(05|11|16|22|28|33|39|44|50|56|61|67|72|78|84|89|95)|(\+?\d*([02468][26]|[13579][048])|-\d*([02468][37]|[13579][159]))(01|07|12|18|24|29|35|40|46|52|57|63|68|74|80|85|91|96)|\+?\d*(([02468][37]|[13579][159])(03|14|20|25|31|36|42|53|59|64|70|76|81|87|92|[049]8))|-\d*(([02468][048]|[13579][26])([059]2|08|13|19|24|30|36|41|47|58|64|69|75|80|86|97)))-W53-[1-7])$/

Я включил разделители в число байтов, чтобы показать, что он не зависит от каких-либо флагов.

Он не соответствует действительным датам в других строках, таких как 1234-56-89 2016-02-29 9876-54-32. Регулярное выражение короче, не проверяя не более 10 цифр за год.

Расширено с комментариями:

/^  # Start of pattern (no leading space)
  (
    # YEAR
    # Optional sign and digits if more than 4 in year
    [+-]?\d*(
      # Years 00??, 04??, 08?? ... 92??, 96?? OR dd not followed by 00
      # followed by 00, 04, 08 ... 92, 96 OR
      (([02468][048]|[13579][26]|\d\d(?!00))([02468][048]|[13579][26])) |
      # any year not followed by 29 February or day 366
      \d{4}(?!-02-29|-366)
    # dash
    ) -
    # MONTH AND DAY, or DAY OF YEAR, or WEEK OF YEAR AND DAY if less than 53 weeks
    (
      # Not (30 or 31 February OR 31 April, June, September or December OR day 0)
      (?!02-3|(0[469]|11)-31|000)
      (
        # Month         dash         day         OR
        (0[1-9]|1[012]) - (0[1-9]|[12]\d|30|31) |
        # 001-299 OR 300-359 OR 360-366
        ([012]\d\d | 3([0-5]\d | 6[0-6]))
      # OR
      ) |
      (
        # W    01-52    dash    1-7
        W(?!00)([0-4]\d|51|52)-[1-7]
      )
    # OR
    ) |
    # WEEK OF YEAR AND DAY only if week is 53
    (
      # Optional plus and extra year digits
      \+?\d*(
        # Years +0303 - +9998
        ([02468][37]|[13579][159])(03|14|20|25|31|36|42|53|59|64|70|76|81|87|92|[049]8)
      ) |
      # Minus and extra year digits
      -\d*(
        # Years -0002 - -9697
        ([02468][048]|[13579][26])([059]2|08|13|19|24|30|36|41|47|58|64|69|75|80|86|97)
      ) |
      # Years +0004 - +9699, -0104 - -9799
      (\+?\d*([02468][048]|[13579][26])|-\d*([02468][159]|[13579][37]))
          (04|09|15|20|26|32|37|43|48|54|60|65|71|76|82|88|93|99) |
      # Years +0105 - +9795, -0205 - -9895
      (\+?\d*([02468][159]|[13579][37])|-\d*([02468][26]|[13579][048]))
          (05|11|16|22|28|33|39|44|50|56|61|67|72|78|84|89|95) |
      # Years +0201 - +9896, -0301 - -9996
      (\+?\d*([02468][26]|[13579][048])|-\d*([02468][37]|[13579][159]))
          (01|07|12|18|24|29|35|40|46|52|57|63|68|74|80|85|91|96)
    # dash W 53 dash 1-7
    )-W53-[1-7]
  # End of pattern (no trailing space)
  )$/x
CJ Деннис
источник
Я еще не все проверил, но, похоже, вы получаете больше байтов по (?!…)выражениям по сравнению с моим решением.
Crissov
1
@Crissov (?!…)Выражения сохраняют только несколько байтов каждое. Я сократил количество байтов, объединив три положительных / отрицательных шаблона «неделя года / день недели» в один. Последние не соответствуют друг другу. Таким образом, я получил 8 длинных подшаблонов до 5. Кроме того, поскольку |20|25|это та же длина, что и |2[05]|для более удобочитаемой опции.
CJ Dennis
Это выражение соответствует тестовому сценарию -0000-08-10 и не совпадает ␠2015-08-10␠с пробелами в начале и в конце, но так как оба были произвольными решениями или дополнительными функциями, я позволю этому скользить.
Крисов
Я думаю, что это решение имеет ошибку для дат в пределах W50.
Крисов
W(?!00)([0-4]\d|51|52)-[1-7]должно быть что-то эквивалентное W(?!00)([0-4]\d|5[0-2])-[1-7]. Это добавляет один символ к длине. 779
Crissov
9

PCRE: 603 940 +947 949 956 байт

^\s*[+-]?(\d{4,10}-((00[1-9]|0[1-9]\d|[12]\d\d|3[0-5]\d|36[0-5])|(0[1-9]|1[0-2])-(0[1-9]|1\d|2[0-8])|(0[13-9]|1[0-2])-(29|30)|(0[13578]|1[02])-31|W(0[1-9]|[1-4]\d|5[0-2])-[1-7]))|((\d{2,8}([13579][26]|[2468][048]|0[48])|(\d{0,6}([13579][26]|[02468][048])00))-(366|02-29))|(\+?\d{0,6}(([02468][048]|[13579][26])([26]0|71|[38]2|[49]3|[05]4|15|[27]6|37|[48]8|[09]9)|([02468][159]|[13579][37])(50|[16]1|[27]2|33|[48]4|[09]5|[15]6|67|[27]8|[38]9)|([02468][26]|[13579][048])([48]0|[09]1|[15]2|63|[27]4|[38]5|[49]6|[05]7|[16]8|29)|([02468][37]|[13579][159])([27]0|[38]1|[49]2|[05]3|[16]4|25|[37]6|87|[049]8|[5]9))|-\d{0,6}(([02468][048]|[13579][26])(0[28]|1[39]|24|3[06]|4[17]|5[28]|6[49]|75|8[06]|9[27])|([02468][159]|[13579][37])(0[49]|15|2[06]|3[27]|4[38]|54|6[05]|7[16]|8[28]|9[39])|([02468][26]|[13579][048])(0[51]|16|2[28]|3[39]|44|5[06]|6[17]|7[28]|8[49]|95)|([02468][37]|[13579][159])(0[17]|1[28]|2[49]|35|4[06]|5[27]|6[38]|74|8[05]|9[16])))-W53-[1-7]\s*$

Примечание: некоторые пары скобок могут быть удалены.

Делимость на 4

Кратные 4 повторяются в простой схеме:

  • 00, 04, 08, 12, 16,
    20, 24, 28, 32, 36,
    40, 44, 48, 52, 56,
    60, 64, 68, 72, 76,
    80, 84, 88, 92, 96, ...

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

(?<divisible-by-four>[13579][26]|[02468][048])
(?<not-divisible-by-four>[13579][048]|[02468][26]|\d[13579])

Можно было бы сохранить несколько байтов, если бы существовали классы символов для нечетных и четных цифр (например, \oи \e), но, насколько я знаю, это не так.

лет

Этого выражения было бы достаточно для юлианского календаря, но для определения григорианского високосного года требуется особый случай 00с делением на столетие на 4:

(?<leap-year>[+-]?(\d{2,8}([13579][26]|[2468][048]|0[48])|(\d{0,6}([13579][26]|[02468][048])00))
(?<year>[+-]?\d{4,10})

Для этого потребуются некоторые изменения, чтобы запретить -0000-…(наряду -00000-…с другими) или ввести знак плюс для положительных чисел года с более чем 4 цифрами. Последнее было бы довольно просто, но не обязательно:

(?<leap-year>([+-]?(\d\d([13579][26]|[2468][048]|0[48])|(([13579][26]|[02468][048])00)))|([+-](\d{3,8}([13579][26]|[2468][048]|0[48])|(\d{1,6}([13579][26]|[02468][048])00))))
(?<year>([+-]?\d{4})|([+-]\d{5,10}))

День года

Трехзначные порядковые даты довольно просты, мы просто должны ограничить -366их високосными годами (и запретить -000).

(?<ordinal-day>-(00[1-9]|0[1-9]\d|[12]\d\d|3[0-5]\d|36[0-5]))
(?<ordinal-leap-day>-366)

День месяца года

Семь месяцев с 31 днем: 01январь, 03март, 05май, 07июль, 08август, 10октябрь и 12декабрь. Всего четыре месяца имеют ровно 30 дней, 04апрель, 06июнь, 09сентябрь и 11ноябрь. Наконец, в 02феврале 28 обычных дней и 29 високосных. Мы можем сначала построить регулярное выражение для всегда уважительных дней 01через , 28а затем добавлять специальные случаи.

(?<month-day>-(0[1-9]|1[0-2])-(0[1-9]|1\d|2[0-8]))
(?<short-month-day>-(0[13-9]|1[0-2])-(29|30))
(?<long-month-day>-(0[13578]|1[02])-31)
(?<month-leap-day>-02-29)

Не должно быть ни месяца, ни дня, 00которые не были включены в более раннюю версию.

День недели года

Все годы включают 52 недели

(?<week-day>-W(0[1-9]|[1-4]\d|5[0-2])-[1-7])

Длинные годы, которые включают-W53 повторение в 400-летнем цикле, например, добавьте 2000 для текущего цикла и найдите текущий год в третьей записи:

  • 004, 009, 015, 020, 026, 032, 037, 043, 048, 054, 060, 065, 071, 076, 082, 088, 093, 099,
  • 105, 111, 116, 122, 128, 133, 139, 144, 150, 156, 161, 167, 172, 178, 184, 189, 195,
  • 201, 207, 212, 218, 224, 229, 235, 240, 246, 252, 257, 263, 268, 274, 280, 285, 291, 296,
  • 303, 308, 314, 320, 325, 331, 336, 342, 348, 353, 359, 364, 370, 376, 381, 387, 392, 398.

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

  1. 04|09|15|20|26|32|37|43|48|54|60|65|71|76|82|88|93|99
  2. 05|11|16|22|28|33|39|44|50|56|61|67|72|78|84|89|95
  3. 01|07|12|18|24|29|35|40|46|52|57|63|68|74|80|85|91|96
  4. 03|08|14|20|25|31|36|42|48|53|59|64|70|76|81|87|92|98

Мы можем сгруппировать по любой цифре, чтобы узнать, что мы можем сохранить два байта или около того:

  • Сгруппированы по 1-й цифре.
    1. 0[49]|15|2[06]|3[27]|4[38]|54|6[05]|7[16]|8[28]|9[39]
    2. 05|1[16]|2[28]|3[39]|44|5[06]|6[17]|7[28]|8[49]|95
    3. 0[17]|1[28]|2[49]|35|4[06]|5[27]|6[38]|74|8[05]|9[16]
    4. 0[38]|14|2[05]|3[16]|4[28]|5[39]|64|7[06]|8[17]|9[28]
  • Сгруппированы по 2 цифре.
    1. [26]0|71|[38]2|[49]3|[05]4|15|[27]6|37|[48]8|[09]9
    2. 50|[16]1|[27]2|33|[48]4|[09]5|[15]6|67|[27]8|[38]9
    3. [48]0|[09]1|[15]2|63|[27]4|[38]5|[49]6|[05]7|[16]8|29
    4. [27]0|[38]1|[49]2|[05]3|[16]4|25|[37]6|87|[049]8|[5]9

Число столетий легко сопоставимо с вариацией выражения делимости.

  • 1 век: [02468][048]|[13579][26]
  • 2-й век: [02468][159]|[13579][37]
  • 3-й век: [02468][26]|[13579][048]
  • 4 век: [02468][37]|[13579][159]

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

  1. 02|08|13|19|24|30|36|41|47|52|58|64|69|75|80|86|92|97
  2. 04|09|15|20|26|32|37|43|48|54|60|65|71|76|82|88|93|99
  3. 05|11|16|22|28|33|39|44|50|56|61|67|72|78|84|89|95
  4. 01|07|12|18|24|29|35|40|46|52|57|63|68|74|80|85|91|96

или

  1. 0[28]|1[39]|24|3[06]|4[17]|5[28]|6[49]|75|8[06]|9[27]
  2. 0[49]|15|2[06]|3[27]|4[38]|54|6[05]|7[16]|8[28]|9[39]
  3. 0[51]|16|2[28]|3[39]|44|5[06]|6[17]|7[28]|8[49]|95
  4. 0[17]|1[28]|2[49]|35|4[06]|5[27]|6[38]|74|8[05]|9[16]

Собираем все вместе

Любой год

[+-]?\d{4,10}-((00[1-9]|0[1-9]\d|[12]\d\d|3[0-5]\d|36[0-5])|(0[1-9]|1[0-2])-(0[1-9]|1\d|2[0-8])|(0[13-9]|1[0-2])-(29|30)|(0[13578]|1[02])-31|W(0[1-9]|[1-4]\d|5[0-2])-[1-7])

Дополнения високосного года

[+-]?(\d{2,8}([13579][26]|[2468][048]|0[48])|(\d{0,6}([13579][26]|[02468][048])00))-(366|02-29)

Дополнения високосного года

+?\d{0,6}(([02468][048]|[13579][26])([26]0|71|[38]2|[49]3|[05]4|15|[27]6|37|[48]8|[09]9)|([02468][159]|[13579][37])(50|[16]1|[27]2|33|[48]4|[09]5|[15]6|67|[27]8|[38]9)|([02468][26]|[13579][048])([48]0|[09]1|[15]2|63|[27]4|[38]5|[49]6|[05]7|[16]8|29)|([02468][37]|[13579][159])([27]0|[38]1|[49]2|[05]3|[16]4|25|[37]6|87|[049]8|[5]9))-W53-[1-7]
-\d{0,6}(([02468][048]|[13579][26])(0[28]|1[39]|24|3[06]|4[17]|5[28]|6[49]|75|8[06]|9[27])|([02468][159]|[13579][37])(0[49]|15|2[06]|3[27]|4[38]|54|6[05]|7[16]|8[28]|9[39])|([02468][26]|[13579][048])(0[51]|16|2[28]|3[39]|44|5[06]|6[17]|7[28]|8[49]|95)|([02468][37]|[13579][159])(0[17]|1[28]|2[49]|35|4[06]|5[27]|6[38]|74|8[05]|9[16]))-W53-[1-7]
Crissov
источник
Ваш шаблон не привязан в начале и в конце, поэтому он будет соответствовать действительным датам внутри недопустимой строки.
CJ Dennis
@CJDennis Это правда, сейчас я добавлю два символа.
Crissov
Я также добавил дополнительные начальные и конечные пробелы \s*.
Крисов