Wykryj awarie zamków

40

Jednym z interesujących aspektów grawitacji jest to, że o ile mi wiadomo, nie można po prostu unosić rzeczy w powietrzu.

Wydaje się jednak, że nie wszyscy w Association of Random Castle Builders są tego świadomi, co prowadzi do takich zamków jak ten:

                      #
                      #
    #  #      #  #   ###
    ####      ####   # #
    #### #  # ####   ###
    ##############   ###
    ######  ######   ###
    #####    #####   ###
                     ###
``````````````````````````````

i ten:

                                       # # #    # # #   
                                       ##############
                                       ###  ####  ###
    #  #      #  #      #  #      #  # ###  ####  ### #  #      #  #      #  #      #  #
    ####      ####      ####      #### ############## ####      ####      ####      ####
    #### #  # #### #  # #### #  # #### ## ######## ## #### #  # #### #  # #### #  # ####
    ####################################################################################
    ######  ########  ########  ########  ########  ########  ########  ########  ######
    ###################################    ######    ###################################
    ###################################    ######    ###################################
                                       ##
                                         ##
                                           ##
                                             ##
                                               ##
````````````````````````````````````````````````````````````````````````````````````````````

a nawet ten:

       ##########
   ####   #      ###
#######################
            #
              #
                #
                  #
                    #  # # #
                  #   #  ###
                   #   # ###
                # # #  #  ##
                # # ##   ###
                 #  #  #####
                   #   #####
                  # #  #####
                       #####
                       ## ##
                       #####
                       #####
                       ## ##
                       ## ##
````````````````````````````````````````````

Wyzwanie

W przypadku ważnego zamku wszystkie bloki zostaną połączone z ziemią bezpośrednio lub pośrednio. Twój program lub funkcja otrzyma zamek taki jak te powyżej jako dane wejściowe, a twój program musi zwrócić wartość prawdy lub fałszu odzwierciedlającą, czy zamek jest ważny, czy nie.

Zasady

  • Dane wejściowe są podawane jako ciąg.
  • Wszystkie ważne zamki spoczywać na powierzchni ````````. (Jeśli łańcuch wejściowy nie zawiera powierzchni, zamek jest nieprawidłowy.)
  • Możesz założyć, że wszystkie dane wejściowe spełnią następujące kryteria:
    • Powierzchnia zawsze będzie płaska.
    • Powierzchnia zawsze będzie co najmniej tak szeroka jak zamek, więc po lewej lub prawej stronie ziemi nie będzie żadnych bloków.
    • Wejście nigdy nie będzie #pod powierzchnią.
    • Dane wejściowe będą zawierać tylko znaki podane w tym wyzwaniu. ( #, `spacja lub nowa linia).
    • Możesz założyć, że dane wejściowe zawsze będą zawierać co najmniej jeden znak.
  • Bloki są połączone, jeśli sąsiadują poziomo lub pionowo. Przekątna się nie liczy!
    • Połączony:
      #	or	##
      #
    • Nie połączony:
      #      or	# #	or	 #
      #
      #
  • Zamki muszą istnieć, aby były ważne. (Innymi słowy, dane wejściowe bez żadnej #muszą dawać wartość fałszowania.)
  • Dane wejściowe będą zawierać tylko znaki podane w tym wyzwaniu. ( #, `spacja lub nowa linia).
  • Możesz założyć, że dane wejściowe zawsze będą zawierać co najmniej jeden znak.
  • Obowiązują standardowe zasady we / wy i luki .

Przypadki testowe

Falsy

  • Wszystkie przykłady podane powyżej.
  • # # # # 
    #### ####
    #### # ####
    ##############
    ###### ###### ######
    ## ### #####
    (Bez ziemi.)
  • # 
    ### ####
    #### # # ####
    ##############
    ###### ###### ######
    ##### # ####
    `` `` `` `` `` `` `
    (Górny blok nie jest połączony ani poziomo, ani pionowo).
  •    
    ``
    (Bez zamku.)


  • # # # # # #
    ##############
    ##### ## #####
    # # # # # # # ##### # #### # # # # # # # #
    #### #### #### #### ## #### ## #### #### #### ####
    ## ## # # #### # #### # # #### # # #### # #### # # #### # # #### # ####
    ######################################################################## ########################################
    ###### ######## ## ###### ######## ######## ######## ######## ######## #### ##
    ########################################## ###### ###### ####### ############################
    ################################################ ######### ##########################
    `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `
    (Centralna wieża nie jest połączona z resztą zamku, ponieważ nie ma łączących go bloków poziomo lub pionowo).
  •    
    (Bez zamku.)

  • (Bez zamku, tylko jeden znak nowej linii.)
  • # # 
    #
    `` `` ``
    (Blok najbardziej po prawej stronie nie jest podłączony poziomo ani pionowo).
  •    
    ``
    (Bez zamku.)

Prawda

  • # 
    `
  • # # # # 
    #### ####
    #### # ####
    ##############
    ###### ###### ######
    ## ### #####
    `` `` `` `` `` ``
  •                       # 
    #
    # # # # ###
    #### #### #
    #### # #######
    ############## ###
    # ##### ###### ###
    ##### ##### ###
    ##### ##### ###
    `` `` `` ` `` `` `` `` `` `` `` `` ``
  •                                        # # # # # #    
    ##############
    ### #### ###
    # # # # # # # ### #### ### # # # # # # # #
    #### #### #### #### ############## #### #### #### ## ##
    #### # # #### # # #### # # #### ## ######## ## #### # # #### # ### ## # # ####
    ################################################################ ########################################################
    ###### ## ###### ######## ######## ######## ######## ######## #### #### ######
    ############################################################## # ###################################
    ################################################ ######### ##########################
    `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` ``
  •                       #### ### 
    # #### ###
    # ###
    # ##
    #
    ###
    #####
    ####### #######
    #########
    ### ## #####
    ##### #####
    ###### ######
    ###################
    ### ########## #
    #############
    #############
    ############# #############
    ###### ######
    ###### ######
    #############
    #############
    #############
    #############
    ###### ###### ##### #
    ###### ######
    #############
    #############
    ########### ##
    #############
    ###### ######
    ###### ######
    ########### ##
    #############
    #############
    #############
    ######### ####
    ##### #####
    ##### #####
    ##### #####
    `` `` `` `` `` `` ` `` ``
  •                                                 
    ####
    #####
    ######
    ####
    ####
    #####
    ########
    ##########
    #### ######
    ###########
    ############
    #####################
    ##### ## ##############
    ########### #################
    ###########################################
    ####### #################################
    ############################### ####################
    #################################################### ####
    ############################
    ######################### #
    `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` ` `

Powodzenia!

użytkownik2428118
źródło
Czy możemy założyć, że wszystkie wiersze wejścia będą tej samej długości (tj. Wypełnione spacjami)?
smls
@smls Nie, nie możesz zakładać, że dane wejściowe zostaną uzupełnione.
user2428118
1
@smls Re # 1 i # 2: Właściwie chciałem sprecyzować, że zgłoszenia nie muszą sobie z tym poradzić, ale teraz widzę, że nie tak to zapisałem. Ponieważ nie opublikowano jeszcze żadnych rozwiązań, które radzą sobie z tymi rzeczami, zaktualizuję pytanie, aby było jasne, że nie musisz sobie z tym poradzić. Re # 3: Naprawdę nie mogę wymyślić sytuacji, w której kod poprawnie obsługiwałby przypadek testowy Falsy 2, 4 i 6, a mimo to nie wykrył sytuacji, w której nie ma żadnych bloków w ogóle podłączonych do ziemi. Re # 4: Nie jestem pewien, co przez to rozumiesz. Czy to nie jest już obsługiwane przez przypadek testowy nr 1 Truthy ?
user2428118
1
Związane z.
Zgarb
2
Zamek bananowy? NAJLEPSZY ZAMEK WKRÓTCE
Matthew Roh

Odpowiedzi:

11

Ślimaki , 21 18 bajtów

-3 bajty z powodu dodatkowych ograniczeń wejściowych edytowanych jako wyzwanie.

!{t=\#!(\#o`+\`}\#

Niestety złożoność czasu jest silna, więc większości danych wejściowych nie można uruchomić.

Wyprowadza 0 dla przypadków fałszowania i liczbę #dla przypadków prawdziwych.

                 ,,
!{ t             ,, Assert that nowhere in the grid,
    =\#          ,, there is a '#'
    !(           ,, such that there does not exist
        (\# o)+  ,, an orthogonally connected path of '#'
        \`       ,, ending at a '`'
    )            ,,
}                ,,
\#               ,, Match '#' at starting position
feersum
źródło
To nie rozpoznaje przykładu zamieszczonego w odpowiedzi Zgarba jako zamku. Nie widzę nic w regułach, które mówią, że nie należy ich wykrywać jako zamków? Reguły mówią tylko, że jest to zamek, jeśli każdy #jest podłączony do ziemi.
Martin Ender
@Zgarb Nie, w wyjaśnieniu +jest błąd - w rzeczywistości jest 1 lub więcej razy, a nie 0. I tak będzie wyglądać inaczej po zezwoleniu na rozłączenie zamków.
feersum
9

Oktawa, 53 51 bajtów

@(s)([~,n]=bwlabel(s>32,4))|n==1&&nnz(diff(+s)==61)

Wypróbuj online!

* Ponieważ op usunął wymóg sprawdzania pustej odpowiedzi wejściowej przywrócono do mojej pierwszej edycji.

Wyjaśnienie:

nnz(s)                       check for empty input
([~,n]=bwlabel(s~=' ',4))    label nonempty regions and count number of labels

n==1                         check if number of labels is 1.

nnz(diff(+s)==61)            check if blocks connected to the surface
rahnema1
źródło
6

Brud , 29 bajtów

C=\`|\#&<0C>oX
e`\#&C!v#!&\##

Wypróbuj online! Większość przypadków testowych kończy się w TIO. Wymień <0C>się <0CoF>zrobić to trochę szybciej.

Wyjaśnienie

Sprawdzam, czy z każdego #istnieje ścieżka do `i czy istnieje przynajmniej jedna #. Niedawno dodałem polecenia obrotu do Grime, które znacznie ułatwiają to wyzwanie.

C=\`|\#&<0C>oX  First line:
C=               Define nonterminal C as
  \`             the literal `
    |            or
     \#          the literal #
       &<  >     which is contained in a larger rectangle
         0C      containing said literal adjacent to a match of C
            oX   rotated by any multiple of 90 degrees.
e`\#&C!v#!&\##  Second line:
e`               Match entire input against this pattern:
         !       does not
       v#        contain
  \#             the literal #
    &C!          which is not a match of C,
          &      and
             #   contains
           \#    the literal #.
Zgarb
źródło
6

JavaScript (ES6), 197 196 bajtów

f=(s,l=Math.max(...s.split`\n`.map(t=>t.length)),t=s.replace(/^.*/g,t=>t+' '.repeat(l-t.length)),u=t.replace(eval('/(#|`)([^]{'+l+'})?(?!\\1)[#`]/g'),'`$2`'))=>t==u?/#/.test(s)>/#/.test(t):f(s,l,u)

Gdzie \nreprezentuje dosłowny znak nowej linii. Próbuje usunąć wszystkie z #nich pojedynczo, znajdując sąsiadujący z a `i zmieniając go na a `. Zwraca, truejeśli #pierwotnie był co najmniej jeden, ale wszystkie zostały usunięte. Wersja wymagająca wypełnienia dla 118 117 bajtów:

f=(s,t=s,u=t.replace(eval('/(#|`)([^]{'+s.search`\n`+'})?(?!\\1)[#`]/'),'`$2`'))=>t==u?/#/.test(s)>/#/.test(t):f(s,u)
Neil
źródło
5

Perl 6 , 180 bajtów

{?/\#/&&?all map ->\c{my \b=[map {[$^a.comb]},.lines];sub f(\y,\x){with b[y;x] ->$_ {b[y;x]=0;/\#/??f(y+(1|-1),x)|f(y,x+(1|-1))!!/\`/??1!!|()}}(|c)},map {|($++X ^$^a.comb)},.lines}

Sprawdza, czy dane wejściowe zawierają co najmniej jeden #i czy każdy #może znaleźć ścieżkę do `.

Raczej nieefektywny, ponieważ szukanie ścieżki jest brutalnie wymuszone przy użyciu funkcji rekurencyjnej, która zawsze odwiedza wszystkie inne #z tego samego połączonego regionu (tj. Nie zwiera).

Używa jakiejś bezbożnej interakcji między operatorami Junction i poślizgnięcia , aby upewnić się, że test ścieżki jest pomijany dla znaków spacji bez konieczności osobnego sprawdzania tego poza funkcją wyszukiwania ścieżki.

smls
źródło
5

Python 3 , 214 206 bajtów

def f(s):
 C=s.split('\n');n=max(map(len,C));o=[''];C=[*''.join(t.ljust(n)for t in C+o)]
 while C>o:o=C;C=['`'if z>' 'and'`'in{C[i+y]for y in(1,-1,n,-n)}else z for i,z in enumerate(C)]
 return'#'in{*s}-{*C}

Wypróbuj online!

Pierwsza linia tutaj jest poświęcona dopełnianiu wszystkich linii do tej samej długości: dzielimy ciąg ( s.split('\n')jest o jeden znak krótszy niż s.splitlines()), znajdujemy maksymalną długość linii i przypisujemy do C spłaszczoną listę wszystkich znaków po wypełnieniu każdego linia. (Nowe linie zniknęły.)

Potem zrób listę, gdzie każda postać nie-przestrzeni w sąsiedztwie co najmniej jednej lewy apostrof jest zastąpiony przez lewy apostrof, i dalej, aż żadna zmiana się (gdy stara lista ojest równa C. Możemy porównać C>ozamiast C!=oponieważ zastępując # (ASCII 35 ) za pomocą `(ASCII 96) może jedynie zwiększyć porządek leksykograficzny listy.)

Jeśli nie ma #, a przynajmniej jeden był obecny na początku, zamek jest ważny.

  • Zapisano osiem bajtów zamiast # sprawdzając różnicę w zestawie '#'in s and'#'not in C
Nick Matteo
źródło