Wykrywanie portalu Nether

53

Gra wideo Minecraft polega na umieszczaniu i usuwaniu różnego rodzaju bloków w siatce liczb całkowitych 3D, która tworzy świat wirtualny. Każdy punkt sieci może zawierać dokładnie jeden blok lub być pusty ( oficjalnie blok „ powietrzny ”). W tym wyzwaniu zajmiemy się tylko jedną pionową płaszczyzną 2D świata 3D i jednym rodzajem bloku: obsydianem .

Gdy obsydian tworzy obrys pustego prostokąta w płaszczyźnie pionowej, można utworzyć portal w dolnej części . Pusty prostokąt może mieć dowolny rozmiar, od 2 jednostek szerokości przez 3 jednostki wysokości do 22 jednostek szerokości i 22 jednostki wysokości. Narożniki prostokąta nie muszą być otoczone obsydianem, tylko boki.

Załóżmy na przykład, że Xjest obsydianem i .pustką: (Liczby służą wyłącznie do celów identyfikacyjnych i są również puste).

...................................
..XXXX....XXXX....XXXXXXXXX........
..X..X...X....X..X.........X..XXXX.
..X.1X...X.2..X..X...3...X.X..X....
..X..X...X....XXXX.........X..X.6X.
..XXXX....XXXX...XXXXXXXXXXX..X..X.
.............X.4.X....X.5.X...XXXX.
.............X...X....X...X........
..............XXX......XXX.........
...................................

Ta siatka zawiera 3 prawidłowe portale:

  • Portal 1 ma 2 na 3 jednostki, jest całkowicie pusty i graniczy z obsydianem. Dlatego jest ważny.
  • Portal 2 ma wymiary 4 na 3, jest całkowicie pusty i graniczy z obsydianem. Dlatego jest ważny.
  • Portal 3 nie jest całkowicie pusty. Dlatego jest nieważny.
  • Portal 4 ma wymiary 3 na 3, jest całkowicie pusty i graniczy z obsydianem. Dlatego jest ważny.
  • Portal 5 to 3 na 2 jednostki, co jest zbyt małe. Dlatego jest nieważny.
  • Portal 6 nie ma części granicy. Dlatego jest nieważny.

Wyzwanie

Napisz program lub funkcję, która pobiera te ciągi reprezentujące siatki obsydianu i pustki oraz wypisuje lub zwraca liczbę obecnych portali sieciowych.

  • Dane wejściowe mogą pochodzić z argumentu stdin lub pliku lub funkcji.
  • Możesz założyć, że dane wejściowe są zawsze dobrze uformowane - tzn. Idealnie prostokątna siatka tekstu, o szerokości i wysokości co najmniej 1 znaku, zawierająca tylko Xi .. Opcjonalnie możesz założyć, że po ostatnim wierszu jest końcowy znak nowej linii.

  • W razie potrzeby możesz użyć dowolnych dwóch różnych drukowalnych znaków ASCII zamiast Xi ..

  • Obsidian może znajdować się na granicy siatki. Wszystko poza granicami jest uważane za puste.

Przykładowe dane wejściowe - dane wyjściowe powinny być 4:

................................................................
...................................XXXXXXXXXXXXXXXXXXXXXXXXX....
..XXXX....XXXX....XXXXXXXXX........X.......................X....
..X..X...X....X..X.........X..XXXX.X.......................X....
..X..X...X....X..X.......X.X..X....X.......................X....
..X..X...X....XXXX.........X..X..X..XXXXXXXXXXXXXXXXXXXXXXXX....
..XXXX....XXXX...XXXXXXXXXXX..X..X.X......................X..XXX
.............X...X....X...X...XXXX.X......................X..X..
.............X...X....X...X........X......................X..X..
..............XXX......XXX........XXXXXXXXXXXXXXXXXXXXXXXX...X..
..................................XX.........................XXX

Punktacja

Zgłoszenie z najmniejszą liczbą bajtów wygrywa.

Hobby Calvina
źródło
Czy mogę użyć innego znaku ASCII zamiast nowego wiersza?
Zgarb
@Zgarb Nie, nadal chcę, aby dane wejściowe wyglądały jak siatka.
Hobby Calvina
4
Kiedy rozmiar portali Nether zmienił się ze statycznego 2x3 na opcjonalne większe rozmiary?
Sparr
5
@Sparr SInce 1.7.2 (zobacz historię aktualizacji ). Nie jestem pewien, czy mogą to zrobić w wersjach konsolowych.
Calvin's Hobbies
4
Zdecydowanie +1, ponieważ Minecraft.
Alex A.,

Odpowiedzi:

24

Perl, 81 86

Używanie więcej niż jednego wyrażenia regularnego.

#!perl -p0
$_=map{/.
/;$n="@-"-++$.;/(?=X{$.}..{$n}(X\.{$.}X.{$n}){3,22}.X{$.})/gs}($_)x21

Wyrażenie regularne dla określonej szerokości portalu jest znacznie prostsze niż ogólne: X{$m}..{$n}(X\.{$m}X.{$n}){3,22}.X{$m}gdzie mjest szerokość portalu i njest total width - 1 - m. Wyrażenie regularne musi być wprowadzone w przód w twierdzeniu o zerowej szerokości, (?=...)ponieważ dopasowania mogą się nakładać. Następnie powtarzam 21 razy to ustawienie wyrażenia regularnego $ni $.. "@-"ocenia pozycję początkową ostatniego dopasowania ( /.\n/), która ma całkowitą szerokość - 1. $.jest używana jako druga zmienna, ponieważ jest inicjalizowana, 1gdy jest używana z -p0.

nutki
źródło
2
Możesz zapisać bajt, jeśli używasz innego znaku niż .dla pustych komórek (więc nie musisz przed nim uciekać).
Martin Ender,
62

Regex (smak .NET), 182 181 145 132 126 114 104 100 98 97 96 bajtów

Rozpoznawanie wzorów 2D ASCII? Brzmi jak praca dla wyrażeń regularnych! (Nie ma.)

Wiem, że to znów spowoduje niekończące się dyskusje na temat tego, czy wysyłanie wyrażeń regularnych jest poprawnymi programami, ale wątpię, czy i tak pokona APL lub CJam, więc nie widzę żadnej szkody. (Powiedział, że oni zrobić przekazać nasz test zagorzałych dla „Czym jest język programowania?” ).

Pobiera to dane wejściowe jako ciąg znaków do dopasowania, a wynikiem jest liczba znalezionych dopasowań. Używa _zamiast ., bo musiałbym uciec przed tym drugim. Wymaga również końca nowej linii.

(X(X){1,21})(?=\D+((?>(?<-2>_)+)_))(?=.((?!\7)(.)*
.*(X\3X|()\1.)(?=(?<-5>.)*(?(5)!)
)){4,23}\7)

Możesz to przetestować na żywo w RegexHero lub RegexStorm ). Mecze będą górnymi obsydianowymi rzędami portali. Jeśli znajdziesz przypadek testowy, w którym się nie powiedzie, daj mi znać!

Co to za czary?

Poniższe objaśnienie zakłada podstawowe zrozumienie grup bilansujących .NET . Istotą jest to, że przechwytywania są stosami w wyrażeniu regularnym .NET - każde nowe przechwytywanie dla tej samej nazwy jest wypychane na stos, ale istnieje również składnia do przechwytywania przechwytywania z tych stosów, a także składnia przechwytywania przechwytywania z jednego stosu i przechwytywania przechwytywania na inny w tym samym czasie. Aby uzyskać pełniejszy obraz, możesz rzucić okiem na moją odpowiedź na temat Przepełnienia stosu, która powinna obejmować wszystkie szczegóły.

Podstawową ideą jest dopasowanie wzoru, takiego jak:

 X{n}..{m}
X_{n}X.{m} |
X_{n}X.{m} |  3 to 22 times
X_{n}X.{m} |
 X{n}..{m} 

Gdzie njest między 2 a 22 (włącznie). Najtrudniejszą rzeczą jest uzyskanie wszystkich ns i wszystkie ms być takie same. Ponieważ rzeczywiste postacie nie będą takie same, nie możemy po prostu użyć odwołania wstecznego.

Zauważ, że regex musi osadzić nowe wiersze, które napiszę jak \nponiżej.

(                     # Open capturing group 1. This will contain the top of a portal, which
                      # I can reuse later to match the bottom (being of the same length).
  X                   # Match a single X.
  (X){1,21}           # Match 1 to 21 X's, and push each separately on the <2> stack. Let's
                      # Call the number of X's captured N-1 (so N is the inner width of the
                      # portal).
)                     # End of group 1. This now contains N X's.
(?=                   # Start a lookahead. The purpose of this lookahead is to capture a 
                      # string of N underscores in group 2, so I can easily use this to match 
                      # the inside rows of the portal later on. I can be sure that such a 
                      # string can always be found for a valid portal (since it cannot have 0 
                      # inner height).
  \D+                 # Skip past a bunch of non-digits - i.e. *any* of the vaild characters
                      # of the input (_, X, \n). This to make sure I search for my N 
                      # underscores anywhere in the remainder of the input.
  (                   # Open capturing group 3. This will contain a portal row.
    (?>               # This is an atomic group. Once the engine hass successfully matched the
                      # contents of this group, it will not go back into the group and try to
                      # backtrack other possible matches for the subpattern.
      (?<-2>_)+       # Match underscores while popping from the <2> stack. This will match as
                      # many underscores as possible (but not more than N-1).
    )                 # End of the atomic group. There are two possible reasons for the
                      # subpattern stopping to match: either the <2> stack is empty, and we've
                      # matched N-1 underscores; or we've run out of underscores, in which 
                      # case we don't know how many underscores we matched (which is not 
                      # good).
    _                 # We simply try to match one more underscore. This ensures that we 
                      # stopped because the <2> stack was empty and that group 3 will contain
                      # exactly N underscores.
  )                   # End of group 3.
)                     # End of the lookahead. We've got what we want in group 2 now, but the
                      # regex engine's "cursor" is still at the end of the portal's top.
(?=                   # Start another lookahead. This ensures that there's actually a valid
                      # portal beneath the top. In theory, this doesn't need to be a 
                      # lookahead - I could just match the entire portal (including the lines
                      # it covers). But matches cannot overlap, so if there were multiple
                      # portals next to each other, this wouldn't return all of them. By 
                      # putting the remainder of the check in a lookahead the actual matches
                      # won't overlap (because the top cannot be shared by two portals).
  .                   # Match either _ or X. This is the character above the portal side.

  (                   # This group (4) is where the real magic happens. It's purpose is to to
                      # count the length of the rest of the current line. Then find a portal
                      # row in the next line, and ensure that it's the same distance from the
                      # end of the line. Rinse and repeat. The tricky thing is that this is a
                      # single loop which matches both inner portal rows, as well as the 
                      # bottom, while making sure that the bottom pattern comes last.

    (?!\7)            # We didn't have a group 7 yet... group 7 is further down the pattern.
                      # It will capture an empty string once the bottom row has been matched.
                      # While the bottom row has not been matched, and nothing has been
                      # captured, the backreference will fail, so the negative lookahead will
                      # pass. But once we have found the bottom row, the backreference will
                      # always match (since it's just an empty string) and so the lookahead
                      # will fail. This means, we cannot repeat group 4 any more after the
                      # bottom has been matched.
    (.)*              # Match all characters until the end of the line, and push each onto
                      # stack <5>.
    \n                # Match a newline to go to the next line.
    .*                # Match as many characters as necessary to search for the next portal
                      # row. This conditions afterwards will ensure that this backtracks to
                      # the right position (if one exists).
    (                 # This group (6) will match either an inner portal row, or the bottom
                      # of the portal.
      X\3X            # Match X, then N underscores, then X - a valid inner portal row.
    |                 # OR
      ()              # Capture an empty string into group 7 to prevent matching further rows.
      \1.             # Use the captured top to match the bottom and another character.
    )
    (?=               # This lookahead makes sure that the row was found at the same 
                      # horizontal position as the top, by checking that the remaining line
                      # is the same length.
      (?<-5>.)*       # Match characters while popping from the <5> stack.
      (?(5)!)\n       # Make sure we've hit end of the line, *and* the <5> stack is empty.
    )
  ){4,23}             # Repeat this 4 to 23 times, to ensure an admissible portal height.
                      # Note that this is one more than the allowed inner height, to account
                      # for the bottom row.
  \7                  # Now in the above repetition there is nothing requiring that we have
                      # actually matched any bottom row - it just ensured we didn't continue
                      # if we had found one. This backreference takes care of that. If no
                      # bottom row was found, nothing was captured into group 7 and this
                      # backreference fails. Otherwise, this backreference contains an empty
                      # string which always matches.
)

C #, 185 bajtów

Oto pełna funkcja C #, aby ten wpis był prawidłowy. Czas napisać „interpretera” wiersza poleceń dla wyrażeń regularnych .NET ...

static int f(string p){return System.Text.RegularExpressions.Regex.Matches(p,@"(X(X){1,21})(?=\D+((?>(?<-2>_)+)_))(?=.((?!\7)(.)*
.*(X\3X|()\1.)(?=(?<-5>.)*(?(5)!)
)){4,23}\7)").Count;}
Martin Ender
źródło
5
Hmm, nie jestem pewien, co sądzę o odpowiedzi typu regex. Dopasowywanie blatów to nie to samo, co wydrukowanie numeru. Oczywiście dobrze byłoby użyć wyrażenia regularnego w programie i wydrukować liczbę dopasowań. Jednak, jak mówisz, prawdopodobnie zostanie pobity, więc też jestem zbyt zaniepokojony.
Calvin's Hobbies
1
Możesz użyć ^(lub dowolnej nieużywanej postaci) dla (?!).
jimmy23013
@ user23013 Och, dobra uwaga, dziękuję.
Martin Ender,
118 bajtów .
jimmy23013
@ user23013 Mam 114, używając tylko nienazwanej grupy, ale nie łącząc kontroli linii w jedną.
Martin Ender,
11

Python, 219 bajtów

def f(s):s=s.split();L=len;R=range;return L([r for r in R(L(s))for a in R(L(s[0]))for w in R(2,23)for h in R(3,min(L(s)+~r,23))if(s[r][a:a+w]==s[r-~h][a:a+w]==w*"X")*all(s[r-~k][a-1:a+w+1]=="X"+"."*w+"X"for k in R(h))])

Lepsze niż Java, ale chłopiec bolało pięciokrotnie zagnieżdżone pętle. for/inMoże być nieznacznie ściśliwy stosując %spodstawienie, ale nie byłoby zaoszczędzić dużo.

Rozszerzony:

def f(s):
  s=s.split()
  L=len
  R=range
  return L([r for r in R(L(s))
              for a in R(L(s[0]))
              for w in R(2,23)
              for h in R(3,min(L(s)+~r,23))
              if(s[r][a:a+w]==s[r-~h][a:a+w]==w*"X")* 
                 all(s[r-~k][a-1:a+w+1]=="X"+"."*w+"X"for k in R(h))])
Sp3000
źródło
1
Moim instynktem jest wypróbowanie magii generacji zagnieżdżonej pętli itertools.
imallett,
7

Java, 304 bajty

To znacznie dłużej niż wyrażenie regularne. Po prostu iteruje każdy możliwy kwadrat na wejściu. Jeśli jest to prawidłowy portal, zwiększa licznik o 1. Następnie zwraca licznik. Można to prawdopodobnie znacznie pograć w golfa. Wszelkie sugestie są mile widziane.

int a(String...a){a=a[0].split("\n");int b=0,c=0,d,e,f,g,h,i=a.length,j=a[0].length();for(;c<j;c++)for(d=0;d<i;d++)for(e=c+2;++e<j&e<c+24;)a:for(f=d+3;++f<i&f<d+24;){for(g=c;g<=e;g++)for(h=d;h<=f;h++){if(g==c|g==e&&h==d|h==f)continue;if((g==c|g==e|h==d|h==f)^a[h].charAt(g)>60)continue a;}b++;}return b;}

Zębaty:

int a(String...a){
    a=a[0].split("\n");
    int b=0,c=0,d,e,f,g,h,i=a.length,j=a[0].length();
    for(;c<j;c++)
        for(d=0;d<i;d++)
            for(e=c+2;++e<j&e<c+24;)
                a:for(f=d+3;++f<i&f<d+24;){
                    for(g=c;g<=e;g++)
                        for(h=d;h<=f;h++){
                            if(g==c|g==e&&h==d|h==f)
                                continue;
                            if((g==c|g==e|h==d|h==f)^a[h].charAt(g)>60)
                                continue a;
                        }
                    b++;
                }
    return b;
}

Pełny program:

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;

public class B {

    public static void main(String[] args) throws FileNotFoundException {
        String blocks = new BufferedReader(new FileReader(args[0])).lines().reduce((a,b)->a+"\n"+b).get();
        System.out.println(new B().a(blocks));
    }

    int a(String...a){
        a=a[0].split("\n");
        int b=0,c=0,d,e,f,g,h,i=a.length,j=a[0].length();
        for(;c<j;c++)
            for(d=0;d<i;d++)
                for(e=c+2;++e<j&e<c+24;)
                    a:for(f=d+3;++f<i&f<d+24;){
                        for(g=c;g<=e;g++)
                            for(h=d;h<=f;h++){
                                if(g==c|g==e&&h==d|h==f)
                                    continue;
                                if((g==c|g==e|h==d|h==f)^a[h].charAt(g)>60)
                                    continue a;
                            }
                        b++;
                    }
        return b;
    }

}
Numer jeden
źródło