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!

code-golf ascii-art decision-problem 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

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

Wykryj awarie zamków