ValiDate ISO 8601 von RX

16

Herausforderung

Finden Sie die kürzeste Regex, die

  1. validiert, dh stimmt mit jedem möglichen Datum im proleptischen Gregorianischen Kalender überein (der auch für alle Daten vor seiner ersten Annahme im Jahr 1582 gilt) und
  2. stimmt mit keinem ungültigen Datum überein.

Ausgabe

Die Ausgabe ist daher wahr oder falsch.

Eingang

Die Eingabe erfolgt in einem der drei erweiterten ISO 8601- Datumsformate - ohne Zeitangabe.

Die ersten beiden sind ±YYYY-MM-DD(Jahr, Monat, Tag) und ±YYYY-DDD(Jahr, Tag). Beide benötigen eine spezielle Hülle für den Schalttag. Sie werden naiv getrennt von diesen erweiterten RXs abgeglichen:

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

Das dritte Eingabeformat ist ±YYYY-wWW-D(Jahr, Woche, Tag). Es ist das komplizierte wegen des komplexen Schaltwochenmusters.

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

Eine grundlegende, aber unzureichende Gültigkeitsprüfung für alle drei zusammen würde ungefähr so ​​aussehen:

[+-]?\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]))

Bedingungen

Ein Schaltjahr im proleptischen Gregorianischen Kalender enthält den Schalttag …-02-29 und ist somit 366 Tage lang, …-366existiert also. Dies geschieht in jedem Jahr, dessen Ordnungszahl durch 4 teilbar ist, jedoch nicht durch 100, es sei denn, es ist auch durch 400 teilbar. Das Jahr Null ist in diesem Kalender vorhanden und es handelt sich um ein Schaltjahr.

Ein langes Jahr im ISO-Wochenkalender enthält eine 53. Woche, die man als Schaltwoche bezeichnen könnte. Dies geschieht in allen Jahren, in denen der 1. Januar ein Donnerstag ist, und zusätzlich in allen Schaltjahren, in denen es ein Mittwoch ist. Es stellt sich heraus, dass es normalerweise alle 5 oder 6 Jahre in einem scheinbar unregelmäßigen Muster auftritt.

Ein Jahr hat mindestens 4 Ziffern. Jahre mit mehr als 10 Ziffern müssen nicht unterstützt werden, da dies dem Alter des Universums (ca. 14 Milliarden Jahre) nahe kommt. Das führende Pluszeichen ist optional, obwohl der tatsächliche Standard vorsieht, dass es für Jahre mit mehr als 4 Stellen erforderlich sein sollte.

Teilweise oder verkürzte Daten, dh mit weniger als Tagesgenauigkeit, dürfen nicht akzeptiert werden.

Die Teile der Datumsnotation, z. B. der Monat, müssen nicht mit einer Gruppe übereinstimmen, auf die verwiesen werden könnte.

Regeln

Das ist Code-Golf. Der kürzeste reguläre Ausdruck ohne ausgeführten Code gewinnt. Update: Sie können Funktionen wie Rekursion und ausgeglichene Gruppen verwenden, werden jedoch mit dem Faktor 10 bestraft, mit dem die Anzahl der Zeichen dann multipliziert wird! Dies unterscheidet sich nun von den Regeln im Hardcode-Golf: Regex für die Teilbarkeit durch 7 . Frühere Antwort gewinnt ein Unentschieden.

Testfälle

Gültige Tests

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 

Das letzte ist optional gültig, dh führende und nachfolgende Leerzeichen in Eingabezeichenfolgen können abgeschnitten werden.

Ungültige Formate

-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

Ungültige Daten

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
quelle
2
Diese Frage ist nicht genau definiert, da die Regex-Sprache nicht angegeben ist.
Orlp
1
@orlp Wenn es nicht angegeben ist, ist die Auswahl nicht beschränkt. Ich habe absichtlich "regex" oder "RX" geschrieben, damit man Dialekte verwenden kann, die eine Rekursion usw. ermöglichen (dh CFG, nicht RG).
Crissov
Ich würde Ihnen dringend empfehlen, die Regex-Sprache einzuschränken, da es für einen Wettbewerber sehr sauer sein wird, stundenlang an einer Lösung zu arbeiten, die von einer Sprache, die von Grund auf mächtiger ist, trivial geschlagen wird. Wenn Sie die Sprache auf die tatsächliche CS-Definition von regulären Ausdrücken (wie DFA) beschränken, wird das Problem zu einer interessanten Optimierungsantwort.
Orlp
Die Validierung von ISO-8601-Daten mit regulären Ausdrücken ist etwas, was ich eigentlich für die Arbeit tun musste. Aber stimme orlp zu, ich denke hier ist eine Sprache notwendig.
Alex A.
1
Regex erbt von Method in Perl 6 und ist selbst eine Form von ausführbarem Code.
Brad Gilbert b2gills

Antworten:

4

PCRE (auch Perl), 778 Bytes

/^([+-]?\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])$/

Ich habe die Begrenzer in die Byteanzahl aufgenommen, um zu zeigen, dass keine Flags erforderlich sind.

Es stimmt nicht mit gültigen Daten in anderen Zeichenfolgen überein, z 1234-56-89 2016-02-29 9876-54-32. Der reguläre Ausdruck ist kürzer, wenn das Jahr nicht auf maximal 10 Stellen überprüft wird.

Mit Kommentaren erweitert:

/^  # 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 Dennis
quelle
Ich habe noch nicht alles überprüft, aber es scheint, dass Sie durch (?!…)Ausdrücke im Vergleich zu meiner Lösung die meisten Bytes gewinnen .
Crissov
1
@Crissov Die (?!…)Ausdrücke speichern jeweils nur wenige Bytes. Ich habe viele Bytes reduziert, indem ich drei der positiven / negativen Wochen- / Wochentags-Jahresmuster zu je einem kombiniert habe. Die letzten entsprechen sich nicht. Also ich 8 bekam auch lange Untermuster bis 5. Da |20|25|ist die gleiche Länge wie |2[05]|ich für die lesbare Option ging.
CJ Dennis
Dieser Ausdruck stimmt mit dem Testfall -0000-08-10 überein und stimmt nicht ␠2015-08-10␠mit führenden und nachfolgenden Leerzeichen überein .
Crissov
Ich denke, diese Lösung hat einen Fehler für Daten innerhalb von W50.
Crissov
W(?!00)([0-4]\d|51|52)-[1-7]muss etwas äquivalent zu sein W(?!00)([0-4]\d|5[0-2])-[1-7]. Dies fügt der Länge ein Zeichen hinzu. 779
Crissov
9

PCRE: 603 940 947 949 956 Bytes

^\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*$

Hinweis: Einige Klammerpaare können möglicherweise weggelassen werden.

Teilbarkeit durch 4

Die Vielfachen von 4 wiederholen sich in einem einfachen Muster:

  • 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, …

Dies oder das Gegenteil könnte durch einen ebenfalls einfachen regulären Ausdruck für alle zweistelligen Zahlen mit führender Null übereinstimmen:

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

Es könnte einige Bytes einsparen, wenn es Zeichenklassen für gerade und ungerade Ziffern gäbe (wie \ound \e), aber soweit ich weiß, gibt es keine.

Jahre

Dieser Ausdruck würde für den Julianischen Kalender ausreichen, aber die Gregorianische Schaltjahrerkennung muss in Sonderfällen 00mit einer Teilbarkeit des Jahrhunderts durch 4 nachgestellt werden:

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

Dies würde einige Änderungen am Gesetzwidrigen -0000-…(zusammen mit -00000-…usw.) oder der Durchsetzung des Pluszeichens für positive Jahreszahlen mit mehr als vier Ziffern erfordern . Letzteres wäre eher einfach, wird aber nicht benötigt:

(?<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}))

Tag des Jahres

Dreistellige Ordnungsdaten sind recht einfach, wir müssen uns nur -366auf Schaltjahre beschränken (und nicht zulassen -000).

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

Tag des Monats des Jahres

Die sieben Monate mit 31 Tagen sind 01Januar, 03März, 05Mai, 07Juli, 08August, 10Oktober und 12Dezember. Nur vier Monate haben genau 30 Tage, 04April, 06Juni, 09September und 11November. Schließlich hat der 02Februar 28 Tage in gemeinsamen Jahren und 29 in Schaltjahren. Wir können zuerst einen regulären Ausdruck für die immer gültigen Tage bis 01erstellen 28und dann Sonderfälle hinzufügen.

(?<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)

Es darf weder ein Monat noch ein Tag sein, 00die in einer früheren Version nicht berücksichtigt wurden .

Wochentag des Jahres

Alle Jahre umfassen 52 Wochen

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

Lange Jahre, die-W53 Wiederholungen in einem 400-Jahres-Zyklus enthalten, z. B. 2000 für den aktuellen Zyklus hinzufügen und das aktuelle Jahr im dritten Eintrag suchen:

  • 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.

Jedes der vier Jahrhunderte hat ein einzigartiges Muster. Es gibt wahrscheinlich nicht viel Raum für Optimierungen.

  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

Wir können nach jeder Ziffer gruppieren, um herauszufinden, dass wir zwei Bytes oder so sparen können:

  • Gruppiert nach 1. Ziffer.
    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]
  • Gruppiert nach 2. Ziffer.
    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

Die Jahrhundertzahl wird durch eine Variation des Teilbarkeitsausdrucks leicht wieder angeglichen.

  • 1. Jahrhundert: [02468][048]|[13579][26]
  • 2. Jahrhundert: [02468][159]|[13579][37]
  • 3. Jahrhundert: [02468][26]|[13579][048]
  • 4. Jahrhundert: [02468][37]|[13579][159]

Bisher funktioniert dies nur für positive Jahre, einschließlich Jahr Null. Für negative Jahre müssen wir die Werte von der obigen Liste von 400 subtrahieren und den Rest wiederholen, da das Muster nicht symmetrisch ist.

  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

oder

  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]

Alles zusammen

Jedes Jahr

[+-]?\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])

Schaltjahreszuschläge

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

Schaltwochenjahr-Ergänzungen

+?\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
quelle
Ihr Muster ist nicht am Anfang und Ende verankert, sodass es mit gültigen Daten in einer ansonsten ungültigen Zeichenfolge übereinstimmt.
CJ Dennis
@CJDennis Das stimmt, ich werde jetzt die beiden Zeichen hinzufügen.
Crissov
Ich habe auch optionale führende und nachfolgende Leerzeichen hinzugefügt \s*.
Crissov