Zaimplementuj funkcję wzorca i łańcucha do dopasowania, zwróć true, jeśli wzorzec pasuje do CAŁEGO łańcucha, w przeciwnym razie false.
Nasza składnia wzorca globalnego to:
?
pasuje do jednej postaci+
dopasowuje jeden lub więcej znaków*
dopasowuje zero lub więcej znaków\
ucieka
Zasady:
- Bez ewaluacji, bez konwersji na wyrażenie regularne, bez wywoływania systemowej funkcji glob.
- I / O nie są wymagane: możesz po prostu napisać funkcję
- Najkrótsze wygrane
Przykłady:
glob('abc', 'abc') => true
glob('abc', 'abcdef') => false IMPORTANT!
glob('a??', 'aww') => true
glob('a*b', 'ab') => true
glob('a*b', 'agwijgwbgioeb') => true
glob('a*?', 'a') => false
glob('?*', 'def') => true
glob('5+', '5ggggg') => true
glob('+', '') => false
glob('a\*b', 'a*b') => true
Oto wskazówka na początek: http://en.wikipedia.org/wiki/Backtracking
code-golf
interpreter
regular-expression
Ming-Tang
źródło
źródło
Odpowiedzi:
Golfscript - 82 znaki
Zakłada, że w ciągach nie ma żadnych znaków nowej linii. Zwraca pustą tablicę dla wartości false i niepustą tablicę dla wartości true (zgodnie z definicją true / false w golfscript).
Jest to rozwiązanie nierekurencyjne (z wyjątkiem kolejnych
*
s), które utrzymuje listę pozycji w łańcuchu wzorcai
, którepattern[0..i]
pasująstring[0..cur]
.Może to działać bardzo długo. Możesz dodać
.&
po,:C%
aby temu zapobiec.źródło
Haskell, 141 znaków
Działa dla wszystkich danych wejściowych, zarówno wzorców, jak i ciągów znaków, z którymi należy się dopasować. Obsługuje końcowe ukośniki odwrotne we wzorcu jako dosłowne dopasowanie (zachowanie nie zostało określone).
Można to uruchomić za pomocą następującego sterownika testowego:
Aktualizacja: Napisałem post na blogu o tej konkretnej odpowiedzi, ponieważ myślę, że dobrze pokazuje, jak Haskell tak łatwo koduje problem.
d
im
z operatoramir
doc
+
sprawie%
, którą obsłużył&
źródło
PHP -
275243 znakówNie golfowany:
źródło
Zbyt szczegółowy Python (
384367 znaków)Nie jest najkrótszy, ale jest miły i funkcjonalny. Środek dyktowania wysyłki w środku można przypuszczalnie przepisać jako rozbieżność w stosunku do
(h(p) == '?') and (? lambda body)
rzeczy typowych . Zdefiniowanie tego operatora h kosztuje mnie kilka znaków bez korzyści, ale miło jest mieć słowo kluczowe na głowę.Chciałbym mieć crack do gry w golfa później, jeśli pozwoli na to czas.
edycja: usunięto niepotrzebną trzecią gałąź w przypadku „*” po przeczytaniu rubinowej odpowiedzi user300
źródło
Krótszy Snappier Python 2.6 (272 znaki)
grał w golfa:
bez golfa:
z udziałem:
podziękowania dla odpowiedzi użytkownika 300 za zilustrowanie, jak upraszcza się sprawy, jeśli można uzyskać jakąś wartość terminatora podczas wyskakiwania z pustego łańcucha.
Chciałbym, aby rozpakowanie głowy / ogona mogło odbywać się w linii podczas deklaracji argumentów m. wtedy m może być lambda, tak jak jego przyjaciele n i glob. python2 nie może tego zrobić, a po krótkiej lekturze wygląda na to, że python3 też nie może. Biada.
testowanie:
źródło
Ruby -
199171Nie golfowany:
Testy:
Zainspirowany odpowiedzią roobs
źródło
lambda s : list(s)+[None]
??
są to dosłowne znaki,=>
są separatorami klucz / wartość w Ruby Hashes i->
uruchamiają lambda :-) ({ ?? => ->{...} }
to hash z kluczem"?"
i lambda jako wartością.) Ale tak, sposób, w jaki jest używany razem wygląda jak dopasowanie wzoru do pojedynczych znaków :-)Funkcja C - 178 niezbędnych znaków
Skompilowany z GCC, nie generuje żadnych ostrzeżeń.
Pierwszy i ostatni wiersz nie są uwzględniane w liczbie znaków. Są one dostarczane wyłącznie dla wygody.
Wysadzony:
źródło
JavaScript - 259 znaków
Moja implementacja jest bardzo rekurencyjna, więc stos zostanie przepełniony, jeśli zostanie użyty wyjątkowo długi wzorzec. Ignorując znak plus (który mogłem zoptymalizować, ale nie dla uproszczenia), dla każdego tokena stosowany jest jeden poziom rekurencji.
Funkcja czasami zwraca liczbę zamiast wartości logicznej. Jeśli to jest problem, możesz użyć go jako
!!glob(pattern, str)
.Niegolfowany (raczej nieupoważniony), który ma służyć jako użyteczny zasób:
Zauważ, że indeksowanie do znaków ciągu znaków jak dla elementów tablicy nie jest częścią starszego standardu językowego (ECMAScript 3), więc może nie działać w starszych przeglądarkach.
źródło
Python (454 znaki)
źródło
D: 363 znaków
Bardziej czytelnie:
źródło
golfscript
jest zbudowany z funkcji, które zużywają dwa argumenty ze stosu, sip, i generują pojedynczą wartość logiczną. jest trochę cholerstwa, aby dostosować to do leniwych i leniwych lub operatorów. Naprawdę wątpię, aby takie podejście było prawie optymalne lub nawet we właściwym kierunku.
jest też kilka zabawnie głupich momentów, takich jak wyskakiwanie
'*'
ze wzoru, pochłanianie'*'
porównania, tylko po to, aby zdać sobie sprawę, że kolejna gałąź nie pasuje. aby zejść w dół drugiej gałęzi, potrzebujemy wzoru z'*'
przodu, ale zużyliśmy ten oryginalny wzór, kiedy go otworzyliśmy'*'
, i zużyliśmy'*'
, więc aby ponownie uzyskać wzór, ładujemy nowy błyszczący łańcuch stały'*'
i dodaj go na miejsce. robi się jeszcze bardziej brzydszy, ponieważ z jakiegoś powodu dopasowywanie znaków musi odbywać się za pomocą wartości ascii, ale powrót do łańcucha wymaga ciągów.mniej golfa
testy
źródło
C # (251 znaków)
Nieco bardziej czytelny:
† Wiem, wiem ... z wyjątkiem globusów zawierających odwrotny ukośnik. Co jest naprawdę niefortunne. W przeciwnym razie byłoby naprawdę sprytnie. :(
źródło