W duchu tego xkcd
Napisz program, który gra w wyrażenie regularne z dowolnymi parami list. Program powinien przynajmniej starać się, aby wyrażenie regularne było krótkie, program, który po prostu wyświetla dane wyjściowe /^(item1|item2|item3|item4)$/
lub podobny, jest niedozwolony.
Punktacja opiera się na zdolności do generowania najkrótszego wyrażenia regularnego. Listy testowe to listy odnoszących sukcesy i nieudanych kandydatów na prezydenta USA, które można znaleźć tutaj (dzięki @Peter). Oczywiście program musi działać na wszystkich rozłącznych listach, więc zwyczajne zwrócenie odpowiedzi prezydentowi nie jest brane pod uwagę.
regular-expression
metagolf
Manishearth
źródło
źródło
/^item1|atem2|item3|item4$/
prawdopodobnie ma niezamierzone pierwszeństwo (ciąg musi zaczynać sięitem1
, zawieraćatem2
, zawieraćitem3
lub kończyćitem4
).Odpowiedzi:
Perl (
111110122 znaków)Wykorzystuje moduł CPAN wywoływany
Regexp::Assemble
w celu optymalizacji wyrażeń regularnych. Ponieważ jaki jest lepszy język dla wyrażeń regularnych niż Perl.Również wersja do odczytu, dla zabawy (wykonana za pomocą
-MO=Deparse
).Przykładowe dane wyjściowe (zrobiłem CTRL-D później
item4
).Jako bonus piszę wyrażenie regularne dla każdego słowa w pytaniu.
Ponadto lista prezydentów (262 bajtów).
źródło
Nie moje rozwiązanie (oczywiście nie jestem Peter Norvig!), Ale oto rozwiązanie (nieznacznie zmodyfikowanego) pytania, które dzięki niemu: http://nbviewer.ipython.org/url/norvig.com/ipython/xkcd1313.ipynb
program, który daje, jest następujący (jego praca, nie moja):
gdzie zwycięzcami i przegranymi są odpowiednio listy zwycięzców i przegranych (lub dowolne 2 listy, oczywiście) zobacz artykuł w celu uzyskania szczegółowych wyjaśnień.
źródło
Moje rozwiązanie napisane w Factor :
Jest to ten sam algorytm, co algorytm Norviga. Jeśli celem jest poprawienie czytelności, prawdopodobnie możesz odegrać w golfa wiele innych postaci.
źródło
Mój kod nie jest bardzo golfowy i skondensowany, ale możesz to sprawdzić na https://github.com/amitayd/regexp-golf-coffeescript/ (a konkretnie algorytm w src / regexpGolf.coffee).
Opiera się na algorytmie Petera Norviga, z dwiema ulepszeniami:
(A także wrzucił opcjonalną losowość)
Dla zestawów zwycięzców / przegranych w tym quizie znalazłem 76 wyrażeń regularnych, używając go:
Więcej szczegółów w moim blogu na temat przenoszenia solvera do coffeescript .
źródło