Na potrzeby tego wyzwania mówimy, że wzór wyrażenia regularnego pasuje do łańcucha, jeśli cały łańcuch jest dopasowany przez wzorzec, a nie tylko podłańcuch.
Biorąc pod uwagę dwa wzorce wyrażeń regularnych A i B , mówimy, że A jest bardziej wyspecjalizowany niż B, jeśli każdy ciąg pasujący do A jest również dopasowany przez B, ale nie na odwrót. Mówimy, że jest równoważny do B , jeśli oba wzory pasują dokładnie ten sam zestaw strun. Jeśli żaden wzorzec nie jest bardziej wyspecjalizowany niż drugi i nie są one równoważne, mówimy, że A i B są nieporównywalne .
Na przykład wzorzec Hello, .*!jest bardziej wyspecjalizowany niż .*, .*!; wzory (Hello|Goodbye), World!i Hello, World!|Goodbye, World!są równoważne; i wzory Hello, .*!i .*, World!są nieporównywalne.
Relacja „bardziej wyspecjalizowana niż” określa ścisłe częściowe uporządkowanie zbioru wzorców wyrażeń regularnych. W szczególności, dla wszystkich wzorów A i B , dokładnie jedna z następujących czynności:
- A jest bardziej wyspecjalizowany niż B ( A < B ).
- B jest bardziej wyspecjalizowany niż A ( A > B ).
- A i B są równoważne ( A = B ).
- A i B są nieporównywalne ( A ∥ B ).
Gdy A i B są nieporównywalne, możemy dalej rozróżnić dwa przypadki:
- A i B są rozłączne ( A ∥ B ), co oznacza, że żaden łańcuch nie pasuje do nich obu.
- I B są przecinające się ( A ≬ B ), co oznacza, że niektóre ciągi są dopasowane zarówno.
Wyzwanie
Napisz program lub funkcję, która bierze parę wzorców wyrażeń regularnych i porównuje je w powyższej kolejności. Oznacza to, że jeśli dwa wzory są i B , program powinien ustalić, czy A < B , A > B , A = B lub A ∥ B .
× 92% Premia Dodatkowa premia jest przyznawana, jeśli gdy wzorce są nieporównywalne, program określa, czy się przecinają, czy rozłączają.
Wejście i wyjście
Program powinien zaakceptować dwa wzorce wyrażeń regularnych, jako ciągi znaków, w smaku zdefiniowanym poniżej. Możesz odczytać dane wejściowe poprzez STDIN , wiersz poleceń , jako argumenty funkcji lub równoważną metodę . Możesz założyć, że wzorce są prawidłowe.
Program powinien wygenerować jeden z dokładnie czterech różnych wyników (lub pięć różnych wyników, jeśli wybierasz powyższą premię), w zależności od wyniku porównania (dokładne wyniki zależą od Ciebie.) Możesz zapisać wynik w STDOUT , zwróć jako wynik funkcji lub użyj równoważnej metody .
Smak Regex
Możesz obsługiwać dowolne funkcje wyrażenia regularnego, które lubisz, ale musisz obsługiwać następujące:
- Alternacja z
|. - Kwantyfikacja za pomocą
*. - Grupowanie za pomocą
(i). - Dopasowywanie dowolnego znaku (ewentualnie z wyłączeniem nowych linii) z
.. - (Opcjonalnie: × 80% Premia) Dopasowywanie prostych i negowanych klas postaci odpowiednio z
[…]i[^…]. Nie musisz obsługiwać żadnych predefiniowanych klas znaków (np.[:digit:]), Ale powinieneś obsługiwać zakresy znaków. - Postać ucieka z
\. Powinno być możliwe przynajmniej zaszyfrowanie znaków specjalnych (tj.|*().[^-]\), A najlepiej także zwykłych znaków specjalnych w innych smakach (np.{}), Ale zachowanie podczas ucieczki znaków niespecyficznych nie jest określone. W szczególności nie musisz obsługiwać specjalnych sekwencji specjalnych, takich jak\nznak nowej linii i tym podobne. Możliwą implementacją jest po prostu wzięcie znaku\za literał.
Możesz założyć, że istnieje znak wejściowy, który nie może być dopasowany żadną literałem (tzn. Może być dopasowany tylko przez .negowane klasy znaków).
Dodatkowe zasady
- Możesz używać bibliotek wyrażeń regularnych lub wbudowanej funkcji wyrażeń regularnych tylko w celu dopasowywania i zastępowania ciągów.
- Możesz zignorować wszelkie problemy związane z ustawieniami regionalnymi, takie jak reguły sortowania.
- Aby stwierdzić oczywiste: twój program musi się zakończyć. Powinien wykonać się w rozsądnym czasie, biorąc pod uwagę typowe wzorce (zdecydowanie nie więcej niż godzinę, najlepiej znacznie krócej).
Punktacja
To jest golf golfowy. Twój wynik jest produkt o wielkości kodu w bajtach, a każda z premii . Na najniższym wynikiem wygrywa.
Przypadki testowe
Format przypadków testowych jest następujący:
<Test ID>
<Pattern A>
<Ordering>
<Pattern B>
<Test ID>
<Pattern A>
<Ordering>
<Pattern B>
...
Gdzie <Test ID>jest identyfikatorem przypadku testowego <Pattern A>i <Pattern B>jest wzorcami wyrażeń regularnych oraz <Ordering>jest kolejnością między nimi i jest jednym z:
<:<Pattern A>jest bardziej wyspecjalizowany niż<Pattern B>.>:<Pattern B>jest bardziej wyspecjalizowany niż<Pattern A>.=: Wzory są równoważne.|: Wzory są nieporównywalne i rozłączne.X: Wzory są nieporównywalne i przecinają się.
Specjalna wartość <empty pattern>oznacza pusty wzór.
A. Podstawowe wzorce
B. Złożone wzorce
C. Podstawowe wzorce z klasami postaci
D. Złożone wzorce z klasami postaci
Program testowy
Do porównania wzorców wyrażeń regularnych można użyć następującego fragmentu kodu:
<style>#main {display: none;}#main[loaded] {display: inline;}.pattern_container {position: relative;}.pattern_underlay, .pattern {font: 12pt courier, monospace;overflow: hidden;white-space: pre;padding: 7px;box-sizing: border-box;}.pattern_underlay {background-color: #dddddd;color: #707070;border-radius: 4px;box-shadow: 0.5px 0.5px 2.5px #aaaaaa;}.pattern_underlay[error] {background-color: #ffccbb;}.pattern {position: absolute;left: 0px;top: 0px;background: none;border: none;width: 100%;height: 100%;resize: none;white-space: normal;}#ordering {min-width: 28pt;text-align: center;font-size: 16pt;}#status {padding: 5px;background-color: #fffdce;box-shadow: 1.5px 1.5px 3.5px #aaaaaa;font-size: 10pt;white-space: pre;display: none;}#status[error] {display: inline;background-color: #ffe8df;}#status[loading] {display: inline;}.inline_code {background-color: #dddddd;font: 12pt courier, monospace;padding: 2px;}.placeholder {visibility: hidden;}.error_text {background-color: #fffcb7};</style><span id="main"><table><tr><td><div class="pattern_container"><div class="pattern_underlay" id="pattern1_underlay"></div><textarea class="pattern" id="pattern1" oninput="compare()">Hello, .*!</textarea></div></td><td id="ordering"></td><td><div class="pattern_container"><div class="pattern_underlay" id="pattern2_underlay"></div><textarea class="pattern" id="pattern2" oninput="compare()">.*, .*!</textarea></div></td></tr></table><br></span><span id="status" loading>Loading...</span><script type='text/javascript'>var Module = {setStatus: function (status) {document.getElementById("status").innerHTML = status;if (status == "") {compare();document.getElementById("status").removeAttribute("loading");document.getElementById("main").setAttribute("loaded", 1);}}};function underlay_chars(str) {if (/^\n*$/.exec(str))return str.split("\n").map(function () { return '<span class="placeholder"> \n</span>'; });if (str.indexOf("\n") >= 0)str = str.replace(/\s*$/gm, function (m) { return m.replace(/[^\n]/g, "\0"); });return (str + "\n").split("").map(function (c) {if (c == "\0") return "·";else return '<span class="placeholder">' + c + '</span>';});}function underlay_str(str) {return underlay_chars(str).join("");}function str_to_array32(str) {a = [];for (c of str) {n = c.charCodeAt(0);a.push(n & 0xff, (n >> 8) & 0xff, (n >> 16) & 0xff, n >> 24);}a.push(0, 0, 0, 0);return a;}function compare() {try {for (e of ["pattern1_underlay", "pattern2_underlay", "status"])document.getElementById(e).removeAttribute("error");for (e of ["pattern1", "pattern2"])document.getElementById(e + "_underlay").innerHTML = underlay_str(document.getElementById(e).value);c = Module.ccall("regex_compare", "number", ["array", "array"], [str_to_array32(document.getElementById("pattern1").value),str_to_array32(document.getElementById("pattern2").value)]);if (c >= 0)document.getElementById("ordering").innerHTML = "∥≬<>="[c];else {i = Module.ccall("regex_error_index", "number", [], []);l = Module.ccall("regex_error_length", "number", [], []);e = document.getElementById("pattern" + -c + "_underlay");t = underlay_chars(document.getElementById("pattern" + -c).value);e.setAttribute("error", 1);e.innerHTML =t.slice(0, i).join("") +'<span class="error_text">' + t.slice(i, i + l).join("") + "</span>" +t.slice(i + l).join("");e.setAttribute("error", 1);throw "Pattern error: " + Module.ccall("regex_error", "string", [], []).replace(/`(.*?)'/g, '<span class="inline_code">$1</span>');}} catch (e) {document.getElementById("ordering").innerHTML = "??";document.getElementById("status").innerHTML = e;document.getElementById("status").setAttribute("error", 1);}}</script><script async type="text/javascript" src="https://gist.githack.com/anonymous/91f27d6746566c7b4e4c/raw/c563bf84a01c3a1c6e5f021369a3e730a2e74a1a/rpo.js"></script>