Projekt języka: Dopasowywanie wzorów 2-D

49

To dwutygodniowe wyzwanie nr 6 . Temat: Projektowanie języka

Jest grupę czatu na to wyzwanie. Dołącz do nas, jeśli chcesz omówić pomysły!

A teraz coś z zupełnie innej beczki...

Co dwa tygodnie chcemy eksperymentować z nowym rodzajem wyzwania. W tym wyzwaniu będziesz projektować język! Dopasowywanie wzorców jest bardzo częstym problemem w programowaniu i często bardzo przydatne w golfie kodowym. Na przykład wyrażenia regularne mogą być użyte do wykrycia wzorca w linii tekstu. Nie ma jednak żadnych ustalonych metod opisywania i wykrywania wzorów dwuwymiarowych.

Wyzwanie

Musisz zaprojektować język dopasowywania wzorców, który pozwala na opisywanie wzorców dwuwymiarowych w blokach tekstu. Tryb pracy w języku polskim będą podobne do wyrażeń regularnych (choć język nie musi mieć nic wspólnego z regex inaczej):

  • Jako dane wejściowe otrzymasz prostokątny blok tekstu. Możesz założyć, że tekst składa się tylko z drukowalnych znaków ASCII (0x20 do 0x7E), a także nowych linii (0x0A) do oddzielenia wierszy siatki.
  • Jeśli dopasowanie, zgodnie z opisem wzoru, można znaleźć jako dowolny podzbiór tego bloku tekstu, to dopasowanie powinno zostać zwrócone lub wydrukowane. Jeśli dopasowanie może być inne niż prostokątne, należy je dopełnić do prostokątnego obszaru z pewnym zastrzeżonym znakiem. Jeśli istnieje kilka prawidłowych dopasowań, możesz zdecydować, w jaki sposób wybierane będzie zwrócone dopasowanie (największe, najmniejsze, pierwsze itd.).

W przypadku niektórych aplikacji może być przydatne, jeśli twoja implementacja może zwrócić pozycję dopasowania zamiast samego dopasowania, ale nie jest to wymagane.

Przynajmniej twój język powinien być w stanie dopasować wzorzec jako ciągły, prostokątny podregion jego danych wejściowych.

Twoja odpowiedź powinna zawierać:

  • Opis języka.
  • Realizacja pracy . Może to być program lub zestaw funkcji / klas w wybranym języku.
  • Powinieneś zademonstrować swój język, pokazując, jak można go użyć do rozwiązania poniższych przykładów . Twój język nie musi być w stanie dopasować wszystkich, ale musisz być w stanie dopasować co najmniej 8 z nich. Jeśli twój język może zrobić coś wymyślnego, o czym nie pomyśleliśmy, możesz go również dołączyć.

Jeśli twoja odpowiedź opiera się na istniejących pomysłach, to dobrze, ale proszę przyznać kredyt tam, gdzie jest to należne.

Rozszerzenia

Powyżej opisano minimum, które musi spełnić prawidłowe zgłoszenie. Jednak kilka uogólnień może uczynić taki język dopasowywania wzorców jeszcze bardziej przydatnym, w tym między innymi:

  • Możliwość zakotwiczenia wzoru do jednej lub więcej krawędzi, dzięki czemu można sprawdzić, czy cały obszar wejściowy ma określony wzór.
  • Wytwarzanie wszystkich dopasowań zamiast tylko jednego. Możesz wybrać semantykę nakładających się dopasowań.
  • Przyjmowanie tekstu nieprostokątnego jako danych wejściowych.
  • Umożliwianie wzorom określania dopasowań nieprostokątnych. W takim przypadku dane wyjściowe należy uzupełnić do prostokąta z pewnym zastrzeżonym znakiem.
  • Umożliwianie wzorom określania dopasowań z otworami.
  • Zezwalanie na niesąsiadujące dopasowania, takie jak dwa znaki występujące z pewnym przesunięciem.
  • Łatwa specyfikacja obrotów i odbić.
  • Opcjonalnie potraktuj dane wejściowe cyklicznie jak cylinder lub torus, tak aby przeciwległe krawędzie były uważane za sąsiadujące.

Punktacja

Głównym celem tego wyzwania jest stworzenie skutecznego języka dopasowywania wzorców 2D, który mógłby potencjalnie zostać wykorzystany w przyszłości. Jako taki, system punktacji, taki jak „najkrótsza łączona długość do rozwiązania przykładów”, doprowadziłby do zakodowania na stałe niektórych funkcji kosztem ogólnej użyteczności. Dlatego zdecydowaliśmy, że to wyzwanie najlepiej jest przeprowadzić jako konkurs popularności. Zgłoszenie z największą liczbą głosów wygrywa. Chociaż nie możemy wymuszać sposobu głosowania przez ludzi, oto kilka wskazówek, na co wyborcy powinni szukać:

  • Wyrazistość. Czy język może rozwiązać wiele problemów, nawet poza przykładami przedstawionymi w tym pytaniu? Czy obsługuje którekolwiek z sugerowanych rozszerzeń?
  • Czytelność. Jak intuicyjna jest notacja (przynajmniej dla osób znających podstawową składnię)?
  • Golfitude. To wciąż CodeGolf.SE. Na potrzeby tej strony byłoby oczywiście dobrze mieć pasujący język, który wymaga bardzo małego kodu do opisania wzorca.

Przykładowe problemy

Poniższy fragment kodu pokazuje 16 przykładowych problemów, z którymi mógł się uporać język dopasowywania wzorców 2D. Każdy przykład zawiera krótki opis problemu, a następnie zwykle następuje jeden przykład wprowadzania, w którym można znaleźć dopasowanie, i jeden przykład, w którym nie można znaleźć dopasowania (jeśli dotyczy).

Jak wspomniano powyżej, Twój język musi być w stanie rozwiązać tylko 8 z tych problemów. Wszystko to jest opcjonalne, ale powinno oczywiście zwiększyć liczbę głosów.

Pokaż fragment kodu

(Nie, nie musisz czytać tego kodu HTML. Naciśnij przycisk „Uruchom fragment kodu”, aby dobrze go renderować w przeglądarce, którą możesz następnie wyświetlić na pełnym ekranie).

popularity-contest string grid language-design PhiNotPi
źródło
Czy istnieje ogólny limit czasowy na te problemy? Jestem bardzo zainteresowany rozwiązaniem tego problemu, ale jestem bardzo zajęty, może to zająć mi 2 tygodnie.
Devon Parsons,
7
@DevonParsons Nie ma terminu wejścia.
PhiNotPi
Wygląda interesująco, zwłaszcza że stworzyłeś dla tego nowy tag. Myślę, że powinny być za to punkty bonusowe za stworzenie języka 2D.
mbomb007
1
@ mbomb007 Istnieją punkty bonusowe za stworzenie języka 2D. Jestem prawie pewien, że uzyskałby przyzwoitą liczbę głosów pozytywnych. ;)
Martin Ender
@ MartinBüttner Nawet nie wiem, jak stworzyć język. Czy może to być coś tak (prostego?) Jak tworzenie programu w języku Python, który pobiera plik kodu nowego języka (i interpretuje go / wykonuje w oparciu o zdefiniowaną składnię) i generuje dane wyjściowe?
mbomb007

Odpowiedzi:

32

SnakeEx

Rozwiązuje problemy 15/16 do tej pory!

Tłumacz online ! - Pełna specyfikacja językowa - Źródło Javascript

zrzut ekranu tłumacza

Ideą tego języka jest zdefiniowanie „węży”, które poruszają się po znakach sprawdzających tekst przy użyciu składni przypominającej wyrażenia regularne.

Program w SnakeEx składa się z listy definicji węży wykorzystujących różne sekwencje poleceń. Węże mogą odradzać inne węże za pomocą tych definicji, i tam SnakeEx uzyskuje większość swojej mocy - możemy dopasowywać struktury rozgałęziające, a nawet rekurencję (patrz przykład Paren Matching).

Każdy program będzie zasadniczo wyglądał jak zbiór wyrażeń regularnych, ale z dodatkiem poleceń kierunkowych formy, <dir>które zmieniają kierunek węża, oraz wywoływania poleceń postaci, {label<dir>params}które spawnują więcej węży.

Jako punkt wejścia tłumacz interpretuje jednego węża, używając pierwszej definicji, przesuwając się w prawo.

Nie jest zbyt zwięzłe, ale jest bardzo potężne i (myślę) dość czytelne.

Aktualizacje

  • Zmieniono! logiczne nie i ~ nie oznaczać dopasowań
  • Dodano, <!>aby rozwiązać kolinear
  • Rozwiązane pasujące krzyże
  • Rozwiązane szachownice w mniej okropny sposób
  • Dodano ograniczoną składnię zamknięcia %{min,max}
  • Dodano przykład rekurencji

Rozwiązania

15 rozwiązanych, 1 w toku

Możesz łatwo wypróbować te programy, korzystając z linku internetowego tłumaczonego powyżej!

Problem 1 - Znalezienie szachownicy

m:{v<R>2}{h<>1}
v:{c<L>A1}+
h:{c<R>A2}+
c:_?(#_)+#?

Aby uzyskać szczegółowe wprowadzenie, zacznij od problemu 3.

Problem 2 - Weryfikacja szachownic

m:{v<R>2}{h<>1}
v:${c<L>A1}+$
h:${c<R>A2}+$
c:$_?(#_)+#?$

Zakończenie węży odpowiednimi wężami za pomocą symbolu poza zakresem $jest jednym ze sposobów dopasowania programu do całego wejścia.

Problem 3 - Wykryj prostokąt cyfr

m:{c<R>A1}%{2,}
c:[0-9]%{2,}

Te mruchy wąż porządku tarła o co najmniej 2 węży ( %{2,}to zamknięcie, czyli „2 do nieskończoności”) przy użyciu HD (c c), i w ruchu w prawo (w <R>), czy też w tym przypadku, ponieważ we wszystkich kierunkach są w stosunku do obecnego węża. AParam jest cukier, który określa, że tylko wąż tarło powinien poruszać się po zakończeniu rozmowy. 1Parametrem jest jak ograniczyć wyniki do prostokątów - parametry numeryczne umieścić węży w „grupach”. Mecz się nie liczy, chyba że wszystkie węże w tej samej grupie przemierzą dokładnie tę samą odległość.

Problem 4 - Znalezienie słowa w wyszukiwaniu słów

m:<*>GOLF

Polecenie kierunku <*>określa, że ​​wąż powinien obracać się w dowolnym kierunku ukośnym lub ortogonalnym. Następnie szuka prostego wyrażenia regularnego.

Problem 5 - Wykryj kwadratowe wejścia

m:{v<R>1}{h<>1}
v:${c<L>A1}+$
h:${c<R>A1}+$
c:$.+$

Kluczem jest tutaj znak specjalny $, który pasuje tylko wtedy, gdy wąż jest poza boiskiem. Odradzamy węża poziomego i pionowego; każdy z nich spawnuje więcej węży, które biegną wzdłuż krawędzi, i wszystkie są w tej samej grupie i muszą być tej samej długości.

Problem 6 - Znajdź szybowce w grze życia

m:<+>[({l1<R>A}{l2<R>A}{l3<R>})({l1<L>A}{l2<L>A}{l3<L>})]
l1:##\.
l2:[(#\.)(\.#)]#
l3:#\.\.

mrozpoczyna się w dowolnym z czterech ortogonalnych kierunków ( <+>), osiągając obrót. Następnie wygląda na lewo lub prawo na trzy rzędy w kolejności, osiągając odbicie.

(Zauważ, że zastąpiłem spacje kropkami tylko dlatego, że pola tekstowe HTML użyte w moim tłumaczu wydają się robić głupie rzeczy, jeśli mają wiele spacji w rzędzie)

Problem 7 - Dopasuj portale Nether

m:{e<R>A1}{d<R>A1}%{2,22}{e<R>1}
e:~.X%{3,22}~.
d:X\.+X

Te mruchy prawy wąż, tarła węża sprawdzić lewą krawędź, 2-22 węże sprawdzić środkowe kolumny, a na końcu węża, by sprawdzić prawą krawędź. ~Operator wskazuje, że cokolwiek następująco powinny być sprawdzane, ale nie powinny być oznakowane jako część rozwiązania.

Ograniczone zamknięcia pozwalają nam teraz w pełni i poprawnie rozwiązać ten problem!

Problem 8 - Umieszczenie skrzyni Minecraft

m:~{s<>}~!{d<+>}\.
s:<+>.<BR>([$\.]<R>)%{3}
d:.<+>CC

Używamy tutaj logicznej not ( !), która pasuje wtedy i tylko wtedy, gdy następujący token nie pasuje do niczego. Deklaracja dwykrywa podwójną skrzynię w określonym kierunku, więc !{d<+>}upewnij się, że nie ma podwójnych skrzyń w żadnym prostopadłym kierunku. sprzesuwa się małym diamentem wokół aktualnego kwadratu, sprawdzając, czy co najmniej 3 z tych pól są puste lub poza planszą. Trailing w \.końcu pasuje do kwadratu, zakładając, że wszystkie poprzednie warunki się powiodły.

Problem 9 - Wyrównanie w poziomie i pionie

m:<R>?#~.*#

Wąż mopcjonalnie skręca w prawo ( <R>?) przed dopasowaniem sekwencji. .jest symbolem wieloznacznym, podobnie jak w wyrażeniu regularnym.

Problem 10 - Punkty kolinearne

m:<!>#~.*#~.*#

Dzięki dodaniu <!>kierunku możemy rozwiązać to teraz! <!>jest jak, <+>ale zamiast rozgałęziać się w czterech kierunkach, rozgałęzia się we wszystkich możliwych kierunkach.

Problem 12 - Unikaj litery Q

m:{h<R>A}%{4}
h:[^Qq]%{4}

Po prostu spawnuje 4 węże, z których każdy szuka czterech znaków, które nie są literą Q.

Problem 13 - Wydobycie diamentów

m:{tl<RB>1}{tr<RF>1}
tl:X/*{bl<L>1}X
tr:X\\*{br<R>1}X
bl:X\\*X
br:X/*X

Ten jest całkiem schludny. mspawnuje dwa węże, jeden w prawo, a drugi w prawo. Każdy z nich podąża za ciosami do X, a następnie spawnuje kolejnego węża pod kątem prostym do bieżącego kierunku, który podąża za ciosami do dolnego X.

Problem 14 - Dopasowywanie krzyży

m:{a<R>A}+{b<R>A}+{a<R>A}+
a:{e<>P1}{c<>P2}{e<>P3}
b:{c<>P1}{c<>P2}{c<>P3}
e:\.+
c:#+

Oto pierwszy raz, kiedy Pużyłem parametru iggyback. Zwykle węże są niezależne, ale jeśli wykonasz połączenie z tym parametrem, wąż wywołujący zostanie przeniesiony wraz z odbiorcą. Więc e2możemy sprawdzić sekwencję „.”, Następnie sekwencję „#”, a następnie kolejną sekwencję „.” I sprawić, by wszystkie były osobnymi wywołaniami, abyśmy mogli pogrupować je za pomocą „1,” 2 ”i„ 3 ” , zmuszając ich długości do dopasowania.

Problem 15 - Dopasuj słowo na tablicy Boggle

m{I}:<*>p<*>a<*>n<*>a<*>m<*>a

Proste, jeśli trudne. Iparametr określa rozróżnianie wielkości liter (możemy określić parametry zarówno w definicjach, jak i w wywołaniach). Wąż obraca się w dowolnym kierunku, pasuje do postaci, obraca się ponownie i tak dalej.

m{EI}:<*>p<*>a<*>n<*>a<*>m<*>a

To jest wersja znaków, których nie można ponownie użyć. EParametr xclusive zabrania węża od dopasowania dowolnego znaku, który został już oznakowane, podobnie jak ślady śluzu feersum użytkownika.

Problem 16 - Owinięcie krawędzi

m{W}:{c<R>WA}%{3}
c:###

Ten Wparametr pozwala wężowi na zawijanie, gdy kończy się poza granicami. Mamy również Hi Vpozwalamy tylko na owijanie poziome lub pionowe.

Extra - Solver Maze

m{E}:$(<P>\.)+$

Rozwiązuje labirynt ASCII, w którym podłoga jest pieszą. <P>Kierunku oznacza przodu, w lewo lub w prawo (na cukier [<F><L><R>]).

Extra - Paren Matching

m:\(~{r<>P}\)
r:[^\(\)]*(\({r<>P}\))?[^\(\)]*

Nie wiem jeszcze, jak zrobić Preludium, ale oto pierwszy krok! Tutaj używam rwęża rekurencyjnie, aby dopasować odpowiedni nawias, sprawdzając, czy nie ma między nimi niepasującego nawiasu.

Extra - Topologia ASCII: liczenie pętli

BMac
źródło
Czy rozważysz dodanie składni, aby ten język mógł zastępować, a nie tylko dopasowywać? Chcę użyć jakiegoś rozwiązania tego wyzwania, aby napisać wpis dla codegolf.stackexchange.com/questions/51231/…, ale żadne rozwiązanie tutaj nie znajdzie i zamieni . (Wiem, że moja odpowiedź nie byłaby ważna ze względu na reguły dotyczące specyfikacji języka)
Sparr
@Sparr. Niezły pomysł, z pewnością przydałby się do golfa kodowego. Nie jestem pewien, kiedy będę miał czas na zrobienie tego sam, ale będę o tym pamiętać.
BMac
3
osobno: składnia zmian kierunku jest myląca. ponieważ wąż rozwija się po dopasowaniu postaci, wydaje mi się, że muszę zmienić kierunek o jedną postać przed tym, co ma dla mnie sens. przykład: ciąg „ABC \ nDEF” i chcę dopasować tetris w kształcie litery L zdefiniowany przez ABCF, chcę napisać mojego węża jako „m: ABC <R> F”, ale muszę napisać „m: AB <R> CF ”. Rozumiem, że to pasuje do specyfikacji, ale uważam, że jest to bardzo sprzeczne z intuicją.
Sparr
Mam częściowe rozwiązanie dla składni preludium. Jedyny problem polega na tym, że nie mogę dopasować go, jeśli nie pasuje do całego wejścia: m:{a<>} a:[({n<R>A})({n<R>A}*{l<R>A}{a<>P}{r<R>A})]*{n<R>A}* l:$[^\(\)]*\([^\(\)]*$ r:$[^\(\)]*\)[^\(\)]*$ n:$[^\(\)]+$
TheNumberOne
21

Slip, Python 3.4 ( Github wiki , tłumacz online )

Podobnie jak poddanie się feersum, opiera się ono również na przemierzaniu siatki, ale podobnie jak poddanie się CarpetPython, opiera się na wyrażeniu regularnym. Jakoś wygląda na to, że udało mi się zdobyć środek.

Istnieje wiele niezaimplementowanych funkcji, które chcę dodać, więc w stosownych przypadkach zanotowałem, co zamierzam zrobić, kiedy będę miał czas.

Aktualizacje

(Szczegółowe informacje na stronie Github)

  • 5 kwietnia 2015 : Slip ma teraz tłumacza online ! Wciąż jest na wczesnym etapie, więc może być kilka błędów.

  • 5 kwietnia 2015 : Aktualizacja wydajności! Teraz Nether znacznie szybciej portuje duże dane wejściowe (2 s). Wprowadzono także szereg zmian składniowych, więc sprawdź wiki. Naprawiono również numerację grup.

Poślizg ma wskaźnik dopasowania, który zaczyna się od określonego kwadratu i początkowo jest skierowany w prawo. Po dopasowaniu znaku wskaźnik przesuwa się do przodu w bieżącym kierunku (chociaż implementacja nie robi rzeczy dokładnie w tej kolejności).

Kierunek meczu wskazówka może być ustawiony na określonym kierunku z ^<digit>, gdzie ^0, ^1, ^2, ..., ^7ustawiania wskaźnika N, NE, E, ..., NW odpowiednio (idąc do ruchu wskazówek zegara).

Dostępne są również następujące skróty:

  • ^* sprawdza wszystkie 8 kierunków ortogonalnych lub ukośnych,
  • ^+ sprawdza wszystkie 4 kierunki ortogonalne.

(Plan na przyszłość: Zezwól na ustalanie dowolnych kierunków, np. (1, 2)Na ruch rycerza)

Na przykład ( Problem 4 - Znalezienie słowa podczas wyszukiwania słowa ),

^*GOLF

wypróbowuje wszystkie 8 kierunków ortogonalnych lub ukośnych, szukając słowa „GOLF”. Domyślnie Slip wypróbowuje wszystkie możliwe kwadraty początkowe i zwraca jeden wynik z każdego z nich, odfiltrowując duplikaty, więc siatka taka jak

GOLF
O
L
FLOG

zwraca tylko górny i dolny wiersz jako pasujące (ponieważ górny i lewa kolumna „GOLF” zaczynają się od tego samego kwadratu). Aby uzyskać wszystkie dopasowania, omożna użyć nakładającego się trybu dopasowania.

Podobnie ( Problem 15 - Dopasuj słowo na tablicy Boggle ),

p^*a^*n^*a^*m^*a

dopasowuje panama, próbując za każdym razem innego kierunku. Użyj iflagi, aby rozróżnić wielkość liter. Slip domyślnie używa znaków, ale można to przełączać za pomocą rflagi no-repeat.

(Plan na przyszłość: modyfikator trybu wyszukiwania, który automatycznie sprawdza zestawy wskazówek po każdym ruchu, dzięki czemu powtarzanie nie ^*jest konieczne)

Kierunek wskaźnika dopasowania można również obrócić o 90 stopni w lewo lub w prawo za pomocą <lub >. Na przykład,

 `#`#< `#<  <`#<`#

szuka wzoru

  #
## 
 ##

patrząc w następującej kolejności:

765
894
123

To pozwala nam rozwiązać Problem 6 - Znalezienie szybowce z

^+(`#`# >`# > `#>`#> |`#`# <`# < `#<`#< | `#`#> `#>  >`#>`#| `#`#< `#<  <`#<`#)

gdzie części 1 i 2 kodują kształty szybowca, a części 3 i 4 kodują ich odbite odpowiedniki.

Zauważ, że Slip używa backsticka `do ucieczki. Wynika to z tego, że Slip ma inną formę ruchu, która nadaje nazwie język - polecenie slip. /przesuwa wskaźnik dopasowania prostopadle w lewo, natomiast \przesuwa wskaźnik dopasowania prostopadle w prawo.

Na przykład,

abc   ghi
   def

może być dopasowany przez abc\def/ghi.

Chociaż nie jest szczególnie użyteczne samo w sobie, poślizg staje się ważniejszy w połączeniu z (?| <regex> )grupą stacjonarną, która działa jak pasujący wzrok. Wyrażenie regularne wewnątrz jest dopasowywane, a następnie na jego końcu pozycja i kierunek wskaźnika dopasowania są resetowane do stanu przed grupą stacjonarną.

Na przykład,

abc
def
ghi

można dopasować do (?|abc)\(?|def)\(?|ghi).

Podobnie problem 12 - Unikaj litery Q można rozwiązać

%(\(?|[^qQ]{4})){4}

gdzie %jest polecenie antypoślizgowe, aby zatrzymać \aktywację pierwszego .

Slip ma również asercję długości (?_(<group num>) <regex> ), która pasuje do wyrażenia regularnego w środku tylko wtedy, gdy jego długość dopasowania jest taka sama jak długość danej grupy num.

Na przykład problem 13 - Wydobycie diamentów można łatwo rozwiązać

^1X(`/*)X>(?_(1)`\*)X>(?_(1)`/*)X>(?_(1)`\*)

który najpierw próbuje dopasować górną lewą stronę diamentu, a następnie zapewnia, że ​​pozostałe trzy boki mają tę samą długość.

(Uruchom z vflagą dla pełnego wyjścia)

Match found in rectangle: (8, 0), (12, 4)
  X
 / \
X   X
 \ /
  X

Match found in rectangle: (0, 0), (6, 6)
   X
  / \
 /   \
X     X
 \   /
  \ /
   X

Match found in rectangle: (2, 2), (4, 4)
 X
X X
 X

Match found in rectangle: (10, 2), (14, 6)
  X
 / \
X   X
 \ /
  X

Match found in rectangle: (5, 3), (9, 7)
  X
 / \
X   X
 \ /
  X

Match found in rectangle: (0, 6), (2, 8)
 X
X X
 X

Alternatywą dla golfistów jest

^1X(`/*)(X>(?_(1)`\*)X>(?_(1)`/*)){2}

która dwukrotnie pasuje do pierwszej strony.

Wiele innych problemów można rozwiązać za pomocą poślizgu, grup stacjonarnych i stwierdzeń długości:

Problem 14 - Dopasowywanie krzyżyków:

(?|(`.+)(`#+)(`.+))(\(?|(?_(2)`.+)(?_(3)`#+)(?_(4)`.+)))*(\(?|(?_(2)`#+)(?_(3)`#+)(?_(4)`#+)))+(\(?|(?_(2)`.+)(?_(3)`#+)(?_(4)`.+)))+

Po uchwycić Szerokości .s i #s w pierwszym rzędzie, to jest po prostu poślizgnięcia całą drogę w dół.

Wynik:

Match found in rectangle: (0, 1), (5, 5)
.###..
######
######
.###..
.###..

Match found in rectangle: (4, 6), (6, 8)
.#.
###
.#.

Ten można prawdopodobnie zagrać w golfa z odrobiną rekurencji, gdy tylko rozwiążę kilka błędów.

Problem 3 - Wykryj prostokąt cyfr:

(?|`d`d+)(\(?|(?_(1)`d+)))+

Dopasuj górny wiersz składający się z dwóch lub więcej cyfr, a następnie upewnij się, że każdy wiersz poniżej ma taką samą długość. `djest predefiniowaną klasą znaków równoważną do [0-9].

Zauważ, że znajdzie to wszystkie dopasowania .

Problem 7 - Dopasuj portale sieciowe:

(?|.X{2,22}.)\((?|(?_(1)X`.+X))\){3,22}(?_(1).X+.)

które generuje, na przykład w oryginalnym wątku :

Match found in rectangle: (2, 1), (5, 5)
XXXX
X..X
X..X
X..X
XXXX

Match found in rectangle: (9, 1), (14, 5)
.XXXX.
X....X
X....X
X....X
.XXXX.

Match found in rectangle: (13, 4), (17, 8)
.XXXX
X...X
X...X
X...X
.XXX.

Wreszcie, niektóre inne funkcje Slip obejmują:

  • $0, $1, $2, ..., $7zakotwicz krawędź północną, północno-wschodni narożnik, wschodnią krawędź itp. $+zakotwicza dowolną krawędź i $*zakotwicza dowolny narożnik.
  • $po którym następuje mała litera, ustawia kotwicę w bieżącej pozycji, którą później można dopasować, $a następnie odpowiednią literą , np . $ai $A.
  • # przełącza flagę no-move, która zatrzymuje przesuwanie wskaźnika dopasowania do przodu po następnym meczu.
  • ,dopasowuje znak podobny do znaku ., ale nie dodaje go do wyniku, pozwalając na niesąsiadujące dopasowania, jednocześnie będąc rozpoznawalnym przez (?_()).

... i więcej. Na tej stronie jest naprawdę zbyt wiele do wypisania.

Inne problemy

Problem 1 - Znalezienie szachownicy:

(?|`#?(`_`#)+`_?)(?_(1)(?|...+))(\(?_(1)(?|`#?(`_`#)+`_?$a)))+<(?|`#?(`_`#)+`_?)(?_(9)(?|...+))(\(?_(9)(?|`#?(`_`#)+`_?)))+$A

Dwa problemy z szachownicą z pewnością nie są mocną stroną Slipa. Pasuje górny rząd następnie upewnić się, że przynajmniej długość 3 i zastępców między #i _, następnie wsunąć i dopasować kolejne wiersze. Do końca $akotwica powinna znajdować się w prawym dolnym rogu szachownicy.

Następnie skręcamy w lewo i powtarzamy dla kolumn, upewniając się, że pasujemy $Ana końcu.

Problem 2 - Weryfikacja szachownic:

$7%(\(?|`_?(`#`_)*`#?$2))+$5<%(\(?|`_?(`#`_)*`#?$0))+$3

Podobnie jak w poprzednim problemie, sprawdzamy, czy każdy wiersz jest poprawny, a następnie obracamy w lewo i robimy to samo dla kolumn. Kotwy służą do zapewnienia, że ​​dopasowana jest tylko cała deska.

Problem 9 - Wyrównanie w poziomie i pionie:

>?`#,*`#

Stosujemy opcjonalne? kwantyfikator do >polecenia obrotu, abyśmy mogli dopasować w prawo lub w dół. Znajdujemy wszystkie 5 w przykładzie z otrybem nakładania się, ale tylko 4 bez niego odtąd #.,##i #.,#zaczynamy od tej samej pozycji.

Problem 10 - Punkty współliniowe

^+`#(?|(,*)<(,*))(((?_(2),*)<(?_(3),*),>)+#`#){2}

Dopasuj #następnie niektóre znaki poziome i niektóre znaki pionowe, następnie powtarzaj do drugiego #i powtarzaj do trzeciego #.

Problem 5 - Wykrywanie kwadratowych danych wejściowych:

$7.(.*)>(?_(1).*)$3>((?|.*)\)*

Zakotwicz lewy górny róg i sprawdź, czy górna krawędź ma taką samą długość jak prawa krawędź, zanim zakotwicz prawy dolny róg. Jeśli dane wejściowe przejdą, przejdziemy w górę, aby dopasować całość danych wejściowych.

Problem 8 - Umieszczenie skrzyni Minecraft:

`.^+(($^|(?|`.))>){3}($^|`.|C<(($^|(?|`.))>){3})

Biegnij z pflagą, aby uzyskać pozycje dla każdego meczu. $^jest kotwicą, która pasuje, jeśli następny ruch wyrzuci wskaźnik dopasowania poza granice.

Najpierw dopasowywania ., a następnie sprawdzić, że jesteśmy otoczeni przez trzy .s / granice, to zapewnia, że czwarty otaczających plac jest także ./ lub granica to pojedyncza klatka piersiowa (sprawdzając jego okoliczne kwadraty).

Problem 11 - Sprawdź składnię Preludium :

$7>%(/(?|[^()]+$4)(?1)?|/(?|[^()]*`([^()]*$4)(?1)?/(?|[^()]*`)[^()]*$4)(?1)?)$1

Podjąłem kilka prób, ale myślę, że to prawda. Tutaj używamy rekurencji, która ma taką samą składnię jak PCRE.

To podejście wymaga, aby dane wejściowe były prostokątne, ale gdy już zrobię dopasowanie nieprostokątne, założenie to nie będzie konieczne.

Oto to samo podejście, gra w golfa z większą rekurencją:

$7>%((/(?|([^()]*)$4)|/(?|(?4)`((?3))(?1)?/(?|(?4)`)(?3)))*)$1

Problem 16 - Owiń wokół krawędzi:

%(\(?|`#{3})){3}

(Uwaga: opakowanie nie zostało jeszcze przekazane tłumaczowi online)

Wymaga to flagi zawijania w. Technicznie rzecz %biorąc, początkowy brak poślizgu nie jest konieczny, ale wtedy mecz byłby liczony jako rozpoczynający się o jedno pole wyżej.

Problem EX 1 - Rozwiązanie labiryntu:

S(^+`.)*^+E

Problem z komentarza BMac na czacie . Użyj rflagi dla trybu bez powtarzania, aby wskaźnik dopasowania nie zaciął się w przód iw tył.

Problem EX 2 - Rozpoznawanie twarzy :

(?|O(,*),(?_(2),*)O)(?_(2)(\(?|,))*)\(?|,(?_(2),*)O)(?_(2)(\(?|,))*)\`\(?_(2)`_*)`_(?_(2)`_*)`/

Pamiętaj, że dopasowuję tylko twarze, nie usuwając. Pamiętaj, że pytanie zawiera symbole euro, które będą musiały zostać zastąpione niektórymi drukowanymi kodami ASCII, aby działały.

Sp3000
źródło
Ten wzór skrótu jest szybowcem Conwaya
Heimdall
17

PMA / Snails (C ++)

Widzę język jako ślimaki poruszające się po siatce i wykonujące polecenia. Ślimaki pozostawiają ślad śluzu na każdym kwadracie, na który się poruszają, co domyślnie powoduje, że kwadrat jest następnie niemożliwy do dopasowania. Dopasowanie zakończy się pomyślnie, jeśli osiągnięty zostanie koniec listy poleceń.

Teraz jest wystarczająco dużo operatorów, że będziemy potrzebować listy priorytetów, aby ich śledzić. Operacje są rozwiązywane w następującej kolejności:

  1. Wewnątrz grup ( ) [ ]
  2. Podziel wzdłuż znaku naprzemiennego |
  3. Oceń wszystko po lewej stronie `jako jako grupa
  4. Kwantyfikatory [m],[n]in
  5. Asercje = !
  6. Powiązanie

Tłumacz jest napisany w C ++. Abysmal kod źródłowy można znaleźć tutaj .

Problem 4: Wyszukiwanie słów

Program

z\G\O\L\F

wystarcza, aby uzyskać prawdziwą lub falsey wartość dla tego, czy słowo zostanie znalezione. z(jedno z 15 bezwzględnych lub względnych poleceń kierunkowych) odpowiada dowolnemu ośmioliniowemu kierunkowi. Wiele kolejnych poleceń kierunkowych jest ORedowanych razem. Na przykład ruldybyłoby prawie równoważne z, ponieważ są to polecenia dla prawej, w górę, w lewo, w dół i w dowolnym kierunku po przekątnej. Jednak kierunki będą testowane w innej kolejności. Pierwszy dopasowany znak to zawsze ten, od którego zaczyna się ślimak, niezależnie od kierunku. \<znak> pasuje do jednego literału.

Domyślną strategią jest wypróbowanie wzorca na każdym kwadracie w obwiedni wyrównanego do lewej wejścia i wyprowadzenie liczby dopasowań. Jeśli wartość logiczna 1lub 0jest wymagana, można użyć następującego programu:

?
z\G\O\L\F

Jeśli w pliku źródłowym znajduje się co najmniej jedna nowa linia, pierwszy wiersz jest traktowany jako opcja wstępnej konwersji danych wejściowych na formę prostokątną. Te ?odciski opcja 0 lub 1 w zależności od tego, czy istnieje dopasowanie wszędzie.

Problem 15: Boggle

Po zaimplementowaniu przemiany można teraz rozwiązać Boggle. Lepiej byłoby użyć dopasowywania bez rozróżniania wielkości liter dla tego, ale implementacja nie jest moim najwyższym priorytetem.

\p|\P)z(\a|\A)z{\n|\N)z{\a|\A}z(\m|\M)z(\a|\A

|działa dokładnie tak samo jak regex jednowymiarowy. Istnieją dwie pasujące pary ograniczników do grupowania, a mianowicie ()i {}. Nawias zamykający zamyka wszystkie otwarte grupy przeciwnego typu, które stoją między nim a najbliższym tego samego typu. Na przykład następujące {({{): tylko grupa z lewej strony pozostaje otwarta. Jak widać, niedopasowane symbole grupujące na krawędziach są domyślnie zamknięte. Jest jeszcze jedno polecenie grupowania, do `którego teraz nie wejdę.

Problem 8: Skrzynie Minecraft

Program drukuje liczbę prawidłowych miejsc w klatce piersiowej. To była pierwsza gra w golfa i kilka razy zmniejszyłem liczbę bajtów (17).

\.!(o\C)2o(!\Cw)3
  • \. dopasowuje kropkę dosłownie w punkcie początkowym meczu.
  • !(o\C)2jest równoważne, !((o\C)2)ponieważ kwantyfikacja ma wyższy priorytet niż twierdzenie. <atom> <number>oznacza powtarzanie <atom>dokładnie <number>razy. oobraca ślimaka w dowolnym prostopadłym kierunku. !jest twierdzeniem negatywnym. Dlatego ta część sprawdza brak sąsiedniej podwójnej skrzyni.
  • o obraca się w jakimś ortogonalnym kierunku.
    • (!\Cw)3zapewnia, że Cślimaka nie ma, a następnie 3 razy obraca się w lewo.

Problem 2: Weryfikacja szachownic

&
\#!(o^_)|\_!(o^#

&Opcja ustawia wyjście programu a 1jeśli uda mecz na wszystkich pozycjach, a 0inaczej. ^cdopasowuje znak, który nie jest, podobnie cjak [^c]w wyrażeniu regularnym. Jako całość program oznacza: Wydrukuj 1, jeśli na każdej pozycji w ograniczającym prostokącie wejścia znajduje się albo taki, #który nie jest ortogonalnie sąsiadujący ze znakiem, który nie jest _, albo taki, _który nie jest ortogonalnie sąsiadujący ze znakiem, który jest nie #; w przeciwnym razie 0.

feersum
źródło
Pomysł na śluzowce jest dobry na radzenie sobie z boggle, miałem z tym pewne problemy
BMac
To dobre rozwiązanie problemu Boggle. Nie mogę tego rozwiązać moim podejściem.
Logic Knight
14

Klasa Re2d, Python 2

Aktualizacja: dodano problem „9. Wyrównanie”.

Moje podejście polega na użyciu modułu ponownie Python do wyszukiwania i dopasowywania. Klasa Re2d przygotowuje tekst do przetworzenia, wykonuje funkcje re i formatuje wyniki do wydruku.

Pamiętaj, że nie jest to zupełnie nowy język - jest to standardowy język wyrażeń regularnych rzutowany na 2 wymiary z dodanymi flagami dla dodatkowych trybów 2D.

Klasa ma następujące zastosowanie:

re2dobject = Re2d(<horizontal pattern>, [<vertical pattern>], [<flags>])

Oba wzorce są standardowymi liniowymi wzorcami RE tekstu. Jeśli nie zostanie dostarczony wzór pionowy, klasa użyje wzoru poziomego do dopasowania również w pionie. Flagi są standardowymi flagami RE z niektórymi rozszerzeniami 2D.

Testowanie

1. Finding chessboards
Chessboard pattern at (2, 1, 4, 3)

print '\n1. Finding chessboards'
reob1 = Re2d('#(_#)+_?|_(#_)+#?')
found = reob1.search('~______~\n~##_#_#~\n~#_#_##~\n~##_#_#~\n~______~')
print 'Chessboard pattern at', found
assert not reob1.search('#_##\n_#_#\n__#_\n#_#_\n#_#_')

Metoda wyszukiwania znalazła wzór szachownicy i zwraca pozycję 4-krotną. Krotka ma x,ypozycję pierwszego znaku dopasowania i width, heightdopasowanego obszaru. Podany jest tylko jeden wzór, więc będzie on używany do dopasowania poziomego i pionowego.

2. Verifying chessboards
Is chess? True

print '\n2. Verifying chessboards'
reob2 = Re2d('^#(_#)*_?|_(#_)*#?$')
print 'Is chess?', reob2.match('_#_#_#_#\n#_#_#_#_\n_#_#_#_#')
assert not reob2.match('_#_#_#__\n__#_#_#_\n_#_#_#__')

Szachownica została zweryfikowana za pomocą metody dopasowania, która zwraca wartość logiczną. Należy pamiętać, że ^i $rozpocząć i znaki końcowe są wymagane, aby dopasować cały tekst.

3. Rectangle of digits
Found: [(0, 1, 5, 3), (1, 1, 4, 3), (2, 1, 3, 3), (3, 1, 2, 3), (0, 2, 5, 2), (1, 2, 4, 2), (2, 2, 3, 2), (3, 2, 2, 2), (6, 3, 2, 2)]
Not found: None

print '\n3. Rectangle of digits'
reob3 = Re2d(r'\d\d+', flags=MULTIFIND)
print 'Found:', reob3.search('hbrewvgr\n18774gwe\n84502vgv\n19844f22\ncrfegc77')
print 'Not found:', reob3.search('uv88wn000\nvgr88vg0w\nv888wrvg7\nvvg88wv77')

Teraz używamy MULTIFINDflagi, aby zwrócić wszystkie możliwe dopasowania dla bloku ponad 2-cyfrowego. Metoda znajduje 9 możliwych dopasowań. Pamiętaj, że mogą się one nakładać.

4. Word search (orthogonal only)
Words: [(0, 0, 4, 1), (0, 3, 4, 1), (3, 3, -4, -1), (3, 2, -4, -1), (3, 0, -4, -1)] [(0, 0, 1, 4), (3, 0, 1, 4), (3, 3, -1, -4), (0, 3, -1, -4)]
Words: ['SNUG', 'WOLF', 'FLOW', 'LORE', 'GUNS'] ['S\nT\nE\nW', 'G\nO\nL\nF', 'F\nL\nO\nG', 'W\nE\nT\nS']
No words: [] []

print '\n4. Word search (orthogonal only)'
words = 'GOLF|GUNS|WOLF|FLOW|LORE|WETS|STEW|FLOG|SNUG'
flags = HORFLIP | VERFLIP | MULTIFIND
reob4a, reob4b = Re2d(words, '.', flags), Re2d('.', words, flags)
matching = 'SNUG\nTEQO\nEROL\nWOLF'
nomatch = 'ABCD\nEFGH\nIJKL\nMNOP'
print 'Words:', reob4a.search(matching), reob4b.search(matching)
print 'Words:', reob4a.findall(matching), reob4b.findall(matching)
print 'No words:', reob4a.findall(nomatch), reob4b.findall(nomatch)

Ten test pokazuje użycie przewracania w pionie i poziomie. Pozwala to na dopasowanie odwróconych słów. Przekątne słowa nie są obsługiwane. MULTIFINDFlaga pozwala wielu nakładających się mecze we wszystkich 4 kierunkach. Metoda findall używa funkcji wyszukiwania, aby znaleźć pasujące pola, a następnie wyodrębnia pasujące bloki tekstu. Zwróć uwagę, w jaki sposób wyszukiwanie używa ujemnej szerokości i / lub wysokości dla dopasowań w odwrotnym kierunku. Słowa w kierunku pionowym mają nowe znaki linii - jest to zgodne z koncepcją bloków znaków 2D.

7. Calvins portals
Portals found: [(3, 1, 5, 6)]
Portal not found None

print '\n7. Calvins portals'
reob7 = Re2d(r'X\.{2,22}X|.X{2,22}.', r'X\.{3,22}X|.X{3,22}.', MULTIFIND)
yes = '....X......\n.XXXXXX.XX.\n...X...X...\n.X.X...XXX.\n...X...X.X.\n.XXX...X.X.\nX..XXXXX.X.'
no = 'XX..XXXX\nXX..X..X\nXX..X..X\n..X.X..X\n.X..X.XX'
print 'Portals found:', reob7.search(yes)
print 'Portal not found', reob7.search(no)

To wyszukiwanie wymagało osobnych wzorów dla każdego wymiaru, ponieważ minimalny rozmiar jest inny dla każdego wymiaru.

9. Alignment
Found: ['#.,##', '##'] ['#\n.\n,\n.\n#', '#\n,\n.\n#']
Found: [(3, 4, 5, 1), (6, 4, 2, 1)] [(7, 0, 1, 5), (3, 1, 1, 4)]
Not found: None None

print '\n9. Alignment'
reob9a = Re2d(r'#.*#', r'.', MULTIFIND)
reob9b = Re2d(r'.', r'#.*#', MULTIFIND)
matching = '.,.,.,.#.,\n,.,#,.,.,.\n.,.,.,.,.,\n,.,.,.,.,.\n.,.#.,##.,\n,.,.,.,.,.'
nomatch = '.,.#.,.,\n,.,.,.#.\n.,#,.,.,\n,.,.,.,#\n.#.,.,.,\n,.,.#.,.\n#,.,.,.,\n,.,.,#,.'
print 'Found:', reob9a.findall(matching), reob9b.findall(matching)
print 'Found:', reob9a.search(matching), reob9b.search(matching)
print 'Not found:', reob9a.search(nomatch), reob9b.search(nomatch)

Ten zestaw 2 wyszukiwań znajduje 2 dopasowania pionowe i 2 poziome, ale nie może znaleźć osadzonego #.,#ciągu.

10. Collinear Points (orthogonal only)
Found: [(0, 1, 7, 1)] [(3, 1, 1, 4)]
Not found: None None

print '\n10. Collinear Points (orthogonal only)'
matching = '........\n#..#..#.\n...#....\n#.......\n...#....'
nomatch = '.#..#\n#..#.\n#....\n..#.#'
reob10h = Re2d(r'#.*#.*#', '.')
reob10v = Re2d('.', r'#.*#.*#')
flags = MULTIFIND
print 'Found:', reob10h.search(matching, flags), reob10v.search(matching, flags)
print 'Not found:', reob10h.search(nomatch, flags), reob10v.search(nomatch, flags)

Tutaj używamy 2 wyszukiwań, aby znaleźć dopasowania w obu kierunkach. Jest w stanie znaleźć wiele dopasowań ortogonalnych, ale to podejście nie obsługuje dopasowań po przekątnej.

12. Avoid qQ
Found: (2, 2, 4, 4)
Not found: None

print '\n12. Avoid qQ'
reob12 = Re2d('[^qQ]{4,4}')
print 'Found:', reob12.search('bhtklkwt\nqlwQklqw\nvtvlwktv\nkQtwkvkl\nvtwlkvQk\nvnvevwvx')
print 'Not found:', reob12.search('zxvcmn\nxcvncn\nmnQxcv\nxcvmnx\nazvmne')

To wyszukiwanie znajdzie pierwsze dopasowanie.

13. Diamond Mining
.X.
X.X
.X.

.X.
X.X
.X.

..X..
./.\.
X...X
.\./.
\.X..

..X..
./.\.
X...X
.\./.
..X..

.XX.\
//.\.
X...X
.\./.
..X..

...X...
../.\..
./.X.\.
X.X.X.X
.\.X.//
..\./X.
.X.X..\

Diamonds: [(2, 2, 3, 3), (0, 6, 3, 3)] [(8, 0, 5, 5), (10, 2, 5, 5), (5, 3, 5, 5)] [(0, 0, 7, 7)]
Not found: None None None

print '\n13. Diamond Mining'
reob13a = Re2d(r'.X.|X.X', flags=MULTIFIND)
reob13b = Re2d(r'..X..|./.\\.|X...X|.\\./.', flags=MULTIFIND)
reob13c = Re2d(r'...X...|../.\\..|./...\\.|X.....X|.\\.../.|..\\./..', flags=MULTIFIND)
match = '''
...X......X....
../.\..../.\...
./.X.\..X...X..
X.X.X.XX.\./.\.
.\.X.//.\.X...X
..\./X...X.\./.
.X.X..\./...X..
X.X....X.......
.X.............
'''.strip().replace(' ', '')
nomatch = '''
.X......./....
.\....X.......
...X.\.\...X..
..X.\...\.X.\.
...X.X...X.\.X
../X\...\...X.
.X...\.\..X...
..\./.X....X..
...X..../.....
'''.strip().replace(' ', '')
for diamond in reob13a.findall(match)+reob13b.findall(match)+reob13c.findall(match):
    print diamond+'\n'
print 'Diamonds:', reob13a.search(match), reob13b.search(match), reob13c.search(match)
print 'Not found:', reob13a.search(nomatch), reob13b.search(nomatch), reob13c.search(nomatch)

Problem z diamentami jest trudniejszy. Potrzebne są trzy obiekty wyszukiwania dla trzech rozmiarów. Może znaleźć sześć diamentów w zestawie testowym, ale nie skaluje się do diamentów o zmiennej wielkości. To tylko częściowe rozwiązanie problemu diamentów.

Kod Python 2

import sys
import re

DEBUG = re.DEBUG
IGNORECASE = re.IGNORECASE
LOCALE = re.LOCALE
UNICODE = re.UNICODE
VERBOSE = re.VERBOSE
MULTIFIND = 1<<11
ROTATED = 1<<12     # not implemented
HORFLIP = 1<<13
VERFLIP = 1<<14
WRAPAROUND = 1<<15  # not implemented

class Re2d(object):
    def __init__(self, horpattern, verpattern=None, flags=0):
        self.horpattern = horpattern
        self.verpattern = verpattern if verpattern != None else horpattern
        self.flags = flags

    def checkblock(self, block, flags):
        'Return a position if block matches H and V patterns'
        length = []
        for y in range(len(block)):
            match = re.match(self.horpattern, block[y], flags)
            if match:
                length.append(len(match.group(0)))
            else:
                break
        if not length:
            return None
        width = min(length)
        height = len(length)
        length = []
        for x in range(width):
            column = ''.join(row[x] for row in block[:height])
            match = re.match(self.verpattern, column, flags)
            if match:
                matchlen = len(match.group(0))
                length.append(matchlen)
            else:
                break
        if not length:
            return None
        height = min(length)
        width = len(length)
        # if smaller, verify with RECURSIVE checkblock call:
        if height != len(block) or width != len(block[0]):
            newblock = [row[:width] for row in block[:height]]
            newsize = self.checkblock(newblock, flags)
            return newsize
        return width, height

    def mkviews(self, text, flags):
        'Return views of text block from flip/rotate flags, inc inverse f()'
        # TODO add ROTATED to generate more views
        width = len(text[0])
        height = len(text)
        views = [(text, lambda x,y,w,h: (x,y,w,h))]
        if flags & HORFLIP and flags & VERFLIP:
            flip2text = [row[::-1] for row in text[::-1]]
            flip2func = lambda x,y,w,h: (width-1-x, height-1-y, -w, -h)
            views.append( (flip2text, flip2func) )
        elif flags & HORFLIP:
            hortext = [row[::-1] for row in text]
            horfunc = lambda x,y,w,h: (width-1-x, y, -w, h)
            views.append( (hortext, horfunc) )
        elif flags & VERFLIP:
            vertext = text[::-1]
            verfunc = lambda x,y,w,h: (x, height-1-y, w, -h)
            views.append( (vertext, verfunc) )
        return views

    def searchview(self, textview, flags=0):
        'Return matching textview positions or None'
        result = []
        for y in range(len(textview)):
            testtext = textview[y:]
            for x in range(len(testtext[0])):
                size = self.checkblock([row[x:] for row in testtext], flags)
                if size:
                    found = (x, y, size[0], size[1])
                    if flags & MULTIFIND:
                        result.append(found)
                    else:
                        return found
        return result if result else None

    def search(self, text, flags=0):
        'Return matching text positions or None'
        flags = self.flags | flags
        text = text.split('\n') if type(text) == str else text
        result = []
        for textview, invview in self.mkviews(text, flags):
            found = self.searchview(textview, flags)
            if found:
                if flags & MULTIFIND:
                    result.extend(invview(*f) for f in found)
                else:
                    return invview(*found)
        return result if result else None

    def findall(self, text, flags=0):
        'Return matching text blocks or None'
        flags = self.flags | flags
        strmode = (type(text) == str)
        text = text.split('\n') if type(text) == str else text
        result = []
        positions = self.search(text, flags)
        if not positions:
            return [] if flags & MULTIFIND else None
        if not flags & MULTIFIND:
            positions = [positions]
        for x0,y0,w,h in positions:
            if y0+h >= 0:
                lines = text[y0 : y0+h : cmp(h,0)]
            else:
                lines = text[y0 : : cmp(h,0)]
            if x0+w >= 0:
                block = [row[x0 : x0+w : cmp(w,0)] for row in lines]
            else:
                block = [row[x0 : : cmp(w,0)] for row in lines]
            result.append(block)
        if strmode:
            result = ['\n'.join(rows) for rows in result]
        if flags & MULTIFIND:
            return result
        else:
            return result[0]

    def match(self, text, flags=0):
        'Return True if whole text matches the patterns'
        flags = self.flags | flags
        text = text.split('\n') if type(text) == str else text
        for textview, invview in self.mkviews(text, flags):
            size = self.checkblock(textview, flags)
            if size:
                return True
        return False
Logic Knight
źródło
Jeśli problem z diamentem nie był jasny, diamenty mogą mieć dowolny rozmiar, a nie tylko 0, 1 lub 2. Edycja: Zredagowałem specyfikację, aby to wyjaśnić.
PhiNotPi
Rozumiem. W odpowiedzi zanotuję, że Re2d ma tylko częściowe rozwiązanie tego problemu. Nie można go skalować do zmiennych rozmiarów. Czy to w porządku?
Logic Knight
Tak, w porządku.
PhiNotPi
14

Grime , Haskell

Wprowadzenie

Grime opiera się na gramatyce boolowskiej . Podstawową ideą jest konstruowanie prostokątnych wzorów z mniejszych komponentów i sprawdzanie, czy znajdują się one w macierzy wejściowej. Do tej pory Grime obsługuje tylko dopasowania prostokątne i rozwiązuje co najmniej 11 problemów mniej lub bardziej elegancko.

EDYCJA: Naprawiono krzyże (dzięki DLosc za wykrycie błędu) i dodano wydobycie diamentów.

EDYCJA 2: Dodano klasy postaci, inspirowane klasami Slipa . Zmieniono również składnię flag opcji, poprawiono parser wyrażeń i dodano problem braku Q.

EDYCJA 3: Zaimplementowano ograniczenia rozmiaru i dodano problem z portalami Nether.

Stosowanie

Program Grime nazywa się gramatyką , a poprawnym rozszerzeniem pliku dla gramatyki jest .gr, chociaż nie jest to wymuszone. Gramatyka jest oceniana jako

runhaskell grime.hs [options] grammarfile matrixfile

gdzie matrixfilejest plik zawierający matrycę znaków. Na przykład gramatyka cyfr byłaby oceniana jako

runhaskell grime.hs digits.gr digit-matrix

Dla dodatkowej prędkości polecam kompilację pliku z optymalizacjami:

ghc -O2 grime.hs
./grime digits.gr digit-matrix

Domyślnie interpreter drukuje pierwsze znalezione dopasowanie, ale można to kontrolować za pomocą flag opcji:

  • -e: dopasuj tylko całą matrycę, drukuj 1dla dopasowania i 0dla braku dopasowania.
  • -n: wydrukuj liczbę dopasowań lub całą macierz, jeśli -ejest również podana.
  • -a: wydrukuj wszystkie dopasowania.
  • -p: wydrukuj także pozycje dopasowań, w formacie (x,y,w,h).
  • -s: nie drukuj samych dopasowań.
  • -d: wydrukuj informacje debugowania.

Opcje można również określić w gramatyce, wstawiając je przed dowolnym wierszem i dodając przecinek ,(przykłady poniżej).

Składnia i semantyka

Gramatyka Grime składa się z jednej lub więcej definicji , każda w osobnej linii. Każdy z nich określa wartość nieterminala , a jeden z nich musi określać anonimowy nieterminal najwyższego poziomu . Składnia definicji to albo N=Ealbo E, gdzie Njest wielką literą i Ejest wyrażeniem .

Wyrażenia są zbudowane w następujący sposób.

  • Dowolny znak, który uciekł, \pasuje do dowolnego 1x1prostokąta zawierającego ten znak.
  • . pasuje do dowolnego pojedynczego znaku.
  • $dopasowuje 1x1prostokąt poza matrycą znaków.
  • _ dopasowuje dowolny prostokąt o zerowej szerokości lub wysokości.
  • Wstępnie zdefiniowane grupy znaków to digit, uppercase, lowercase, alphabetic, alpha numeric i symbol.
  • Nowe klasy znaków można zdefiniować za pomocą składni [a-prt-w,d-gu]. Litery po lewej są uwzględnione, a te po prawej są wykluczone, więc pasuje dokładnie do liter abchijklmnoprtvw. Jeśli lewa strona jest pusta, przyjmuje się, że zawiera wszystkie znaki. Przecinek można pominąć, jeśli prawa strona jest pusta. Postacie [],-\muszą być oznaczone znakiem ucieczki \.
  • Nieskalowana wielka litera jest nieterminalem i odpowiada wyrażeniu, które zostało przypisane.
  • Jeśli Pi Qsą wyrażeniami, to PQjest to po prostu ich konkatenacja pozioma i P/Qich konkatenacja pionowa z Pgórą.
  • P+jest jedną lub więcej Ps wyrównane w poziomie, i P/+jest takie samo wyrównane w pionie.
  • Operacji logicznych oznaczono P|Q, P&Qi P!.
  • P?jest skrótem dla P|_, P*dla P+|_i P/*dla P/+|_.
  • P#pasuje do dowolnego prostokąta zawierającego dopasowanie P.
  • P{a-b,c-d}, Gdzie abcdsą nieujemnymi liczbami całkowitymi, to ograniczenie wielkości na P. Jeśli Pjest klasą znaków, to wyrażenie pasuje do dowolnego mxnprostokąta zawierającego tylko te znaki, pod warunkiem, że mjest między ai bwłącznie, i njest pomiędzy ci dwłącznie. W innych przypadkach wyrażenie pasuje do każdego prostokąta, który ma prawidłowy rozmiar i który Prównież pasuje. Jeśli alub czostaną pominięte, uważa się je za 0, a jeśli blub dzostaną pominięte, są nieskończone. Jeśli łącznik między ai bzostanie pominięty, wówczas użyjemy tej samej liczby dla obu końców przedziału. Jeśli całośćc-dczęść jest pominięta, obie osie są ograniczone. Wyjaśnienie, {-b}jest równoważne {0-b,0-b}i {a-,c}jest równoważne z {a-infinity,c-c}.

Notatki

Brud dopuszcza paradoksalne definicje, takie jak A=A!niezdefiniowane zachowanie. Nie powodują jednak awarii ani nieskończonych pętli.

Brud obsługuje dane nieprostokątne; rzędy są po prostu wyrównane do lewej, a luki można dopasować za pomocą $.

W przyszłości chciałbym wdrożyć następujące elementy:

  • Szybsze dopasowanie. Obecnie interpreter nie bierze pod uwagę faktu, że na przykład .można dopasować tylko 1x1prostokąty. Dopóki nie znajdzie dopasowania, wypróbowuje wszystkie prostokąty wszystkich rozmiarów w kolejności, natychmiast zawodząc dla każdego z nich.
  • Operacje rotacji i refleksji w wyszukiwaniu słów i wyzwaniach szybowców.

  • Nieprostokątne mecze z wykorzystaniem kontekstów , które byłyby pomocne w wyzwaniu na tablicy Boggle. Na przykład Pv(Q>R)oznacza Pz dolnym kontekstem ( Qz prawym kontekstem R). Pasowałoby do wzorów w kształcie litery L.

    PPP
PPP
QQQRRRR
QQQRRRR
QQQRRRR

Zadania

Podane z grubsza w kolejności złożoności.

Prostokąt cyfr

d{2-}

To proste: przynajmniej prostokąt cyfr co najmniej wielkości 2x2.

Brak q lub Q

[,qQ]{4}

Jest to prawie tak proste jak pierwsze; teraz mamy bardziej ograniczony rozmiar i niestandardową klasę postaci.

Poziome i pionowe wyrównanie

\#.*\#|\#/./*/\#

Teraz mamy kilka znaków ucieczki. Zasadniczo odpowiada to jednemu #, a następnie dowolnej liczbie dowolnych znaków, a następnie #poziomo lub pionowo.

Wykryj kwadratowe wejścia

S=.|S./+/.+
e,S

Ta gramatyka jest bardzo prosta, w zasadzie definiuje, że kwadrat jest albo 1x1prostokątem, albo mniejszym kwadratem z jedną kolumną przyczepioną do prawej krawędzi, a jeden wiersz przyczepioną do dolnej krawędzi. Zwróć także uwagę na eopcję przed nieterminalem najwyższego poziomu, która przełącza weryfikację całego wejścia.

Znajdowanie słowa w wyszukiwaniu słowa

G=\G
O=\O
L=\L
F=\F
GOLF|FLOG|G/O/L/F|F/L/O/G|G.../.O../..L./...F|...G/..O./.L../F...|F.../.L../..O./...G|...F/..L./.O../G...

To jest okropne, ponieważ Grime nie ma operacji rotacji ani refleksji. Jest również bardzo powolny, ponieważ Grime nie wie, że mecze mogą mieć tylko rozmiar 4x1, 1x4lub 4x4.

Problem szybowców można rozwiązać podobnie, ale jestem zbyt leniwy, żeby to zapisać.

Portale Nether

.\X+./\X/+\.{2-22,3-22}\X/+/.\X+.

Z operatorem ograniczenia rozmiaru nie jest to takie trudne. Środkowa część \.{2-22,3-22}pasuje do dowolnego prostokąta o .prawidłowych rozmiarach, a następnie dodajemy kolumny Xs po obu stronach i sczepiamy rzędy Xs z ignorowanymi końcami na górze i na dole tego.

Pasujące krzyże

E=\.+/+
F=\#+/+
EFE/F/EFE&(E/F/E)F(E/F/E)

To, co tu mamy, to połączenie (logiczne AND) dwóch wyrażeń. Nieterminalny Epasuje do niepustego prostokąta .s i Fniepustego prostokąta #s. Lewa strona koniunkcji odpowiada prostokątom tego typu

...####..
...####..
...####..
#########
#########
.....##..
.....##..

gdzie mamy EFEna górze F, a potem EFEznowu. Prawa strona pasuje do ich transpozycji, więc otrzymujemy dokładnie krzyżyki.

Wydobycie diamentów

C=./+
T=\X|CTC/\/.+\\
B=\X|\\.+\//CBC
CTC/\X.+\X/CBC

Nieterminal Cjest skrótem dla każdej 1xnkolumny. Górnej połowie diamentu odpowiada T: jest to albo pojedynczy X, albo inny Totoczony kolumną po obu stronach i rzędem /[something]\poniżej. Bdopasowuje spód diamentu w ten sam sposób, a nieterminal X[something]Xnajwyższego poziomu jest po prostu rzędem formy między górną połową a dolną połową.

Znajdowanie szachownic

(\#\#|\#/\#|\_\_|\_/\_)#!&[#_]{3-}

Bok prawy [#_]{3-}pasuje dowolny 3x3lub większy prostokąt #S i _S, natomiast gwarancje lewostronnej że nie zawiera dwóch sąsiednich #s lub _s.

Weryfikacja szachownic

e,(\#\#|\#/\#|\_\_|\_/\_)#!&[#_]+/+

Jest to w zasadzie to samo co powyżej, z tym wyjątkiem, że możemy dopasować dowolny niepusty prostokąt, ale musimy użyć eflagi do całej weryfikacji danych wejściowych.

Sprawdź składnię Preludium

A=[,()]/*
P=A*|P(A/\(/A)P(A/\)/A)P
e,P

To chyba najciekawsza jak dotąd gramatyka. Nieterminalny Apasuje do dowolnej kolumny niezawierającej (lub ), i Ppasuje do pewnej liczby As lub dwóch dopasowanych nawiasów, pomiędzy i poza którymi jest więcej Ps.

Zgarb
źródło
@DLosc Naprawiono, dziękuję za znalezienie błędu!
Zgarb
Czy \#(.*|./*)\#zadziała?
patrz
@Sieg Dla wyrównania? Niestety nie, ponieważ byłoby to parsowane jako „jeden #po lewej, następnie wiersz lub kolumna czegokolwiek, a następnie jeden #po prawej”. Muszę określić, że litery #s są pionowo połączone z kolumną za pomocą ukośników /.
Zgarb,
10

TMARL

Język dopasowywania i rozpoznawania szablonów

Opis

Mój tłumacz zajmuje 24 000 znaków ( fragmenty kodu zajmują znaki? ), Więc pełny opis można znaleźć tutaj .

Najlepsze jest to, że tłumacz jest w JavaScript, co oznacza, że ​​możesz wypróbować go tutaj!

Pokaż fragment kodu

A dla problemów:

# 1 - Znajdowanie szachownic

$#_#
a
$_#_
bvacvbS5&(avcS5)G0G2P

&dołącza wyszukiwania. G2 na końcu dostaje trzeci element w elemencie dopasowania, czyli rzeczywiste dopasowanie. Pierwsze 2 elementy to współrzędne xiy (oparte na 1, a nie 0).

# 3 - Wykryj prostokąt cyfr

$DD
$DD
S1G2P

Myślę, że ten jest dość prosty.

# 4 - Znajdowanie słowa w wyszukiwaniu słów

$GO\LF
a
$G
$*O
$**\L
$***F
S6&(aS6)G0G2P

SArgument jest nawet tak, że będzie szukać wszystkich obrotów. Jest większy niż 4, ponieważ można go następnie dołączyć do następnego wyszukiwania (pojedynczych dopasowań nie można dołączyć).

# 5 - Wykryj kwadratowe wejścia

IL-(IG0L)!P

Nie jestem pewien, czy jest to całkowicie legalne, ponieważ poprawnie określa prostokątność tylko wtedy, gdy wejście jest prostokątem. Porównuje długość danych wejściowych ILz długością pierwszego wiersza IG0Li odwraca go.

# 6 - Znajdź szybowce w grze życia

$## 
$# #
$# 
a
$ ##
$## 
$  #
bS6&(bMS6)&(aS6)&(aMS6)G0G2P

Wreszcie zastosowanie lustra!

# 12 - Unikaj litery Q

$[^Qq]
~4*4S1G2P

S1, ponieważ potrzebny jest tylko 1 mecz.

Zrobię kilka trudniejszych później.

Stretch Maniac
źródło