One of the interesting aspects of gravity is that, as far as I'm aware, you can't just have stuff floating in midair.

However, it seems not everyone at the Association of Random Castle Builders is aware of this fact, leading to castles such as this one:

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

and this one:

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

and even this one:

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

Challenge

For a valid castle, all blocks will be connected to the ground either directly or indirectly. Your program or function will be given a castle such as the ones above as input, and your program must return a truthy or falsy value reflecting whether the castle is valid or not.

Rules

Input is given as a string.
All valid castles rest on a surface, ````````. (If the input string does not contain a surface, the castle is invalid.)
You can assume all input will satisfy these criteria:
- The surface will always be flat.
- The surface will always be at least as wide as the castle, so there will be no blocks to the left or right of the ground.
- The input will never have # below the surface.
- Input will only contain characters given in this challenge. (#, `, space or newline.)
- You may assume the input will always contain at least one character.
Blocks are connected if they are either horizontally or vertically adjacent. Diagonal does not count!
- Connected:
```
#	or	##
#
```
- Not connected:
```
#      or	# #	or	 #
                  		#
#
```
Castles must exist to be valid. (In other words, inputs without any # must give a falsy value.)
Input will only contain characters given in this challenge. (#, `, space or newline.)
You may assume the input will always contain at least one character.
Standard I/O and loophole rules apply.

Test cases

Falsy

All the examples given above.

#  #      #  #
####      ####
#### #  # ####
##############
######  ######
#####    #####

(No ground.)

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

(Topmost block is not connected either horizontally or vertically.)

```
   
```
```
(No castle.)



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

(Central tower isn't connected to the rest of the castle because there are no horizontally or vertically adjacent blocks connecting it.)

```
   
```
(No castle.)
(No castle, just a single newline character.)
```
# #
#
```````
```
(Rightmost block is not connected either horizontally or vertically.)
```
   
```
```
(No castle.)

Truthy

```
#
`
```

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

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

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

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

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

Good luck!

user2428118

Posted 2017-02-03T12:27:00.943

Reputation: 2 000

Can we assume all lines of the input will be the same length (i.e. filled up with spaces)? – smls – 2017-02-03T13:03:55.410

@smls No, you cannot assume input will be padded. – user2428118 – 2017-02-03T13:08:23.943

Some more test-cases that might be good to add: 1) Non-flat surface. 2) Too short surface. 3) Castle not connected to the surface. 4) Block connected to nothing but a surface. – smls – 2017-02-03T13:35:43.447

1@smls Re #1 and #2: I actually meant to specify that submissions don't have to handle that, but I now see that's not how I wrote it down. Since there are no solutions posted yet that handle these things, I'll update the question so that it's clear you don't have to handle these. Re #3: I can't really think of a situation where code would correctly handle Falsy test case 2, 4 and 6 and yet fail to detect a situation where there are no blocks at all connected to the ground. Re #4: I'm not sure what you mean by that. Isn't that already handled by Truthy test case number 1? – user2428118 – 2017-02-03T13:46:19.917

1Related. – Zgarb – 2017-02-03T14:10:56.577

@user2428118: You're right, they're already implicitly handled. – smls – 2017-02-03T14:43:23.260

How about an input where the castle is connected to the ground from the bottom (falsy I assume). – feersum – 2017-02-03T15:35:06.117

@feersum I hadn't thought of that yet... I don't want to render the existing answers invalid, so I'll specify that case doesn't have to be handled. – user2428118 – 2017-02-03T16:09:42.343

@user2428118 When you say input cannot be padded, do you mean right-padded, or on both sides? It seems like the string would have to be left-padd to align properly, but maybe I don't understand the input format. – Brian J – 2017-02-03T20:30:41.463

@Brian You've misread my comment. I said "you cannot assume input will be padded", in other words: input may or may not have padding and your code should work regardless of whether the input is padded or not. – user2428118 – 2017-02-03T21:03:57.650

@user2428118 So in the banana example, what would the input string look like? How do we know that the stem is on the right side of the banana? – Brian J – 2017-02-03T21:09:58.977

@BrianJ The original comment by smls asked if submissions can assume that all lines are of equal length, so by adding extra spaces to the right to make sure no line is shorter or longer than the others. Which I choose not to allow. Anyway, here is the banana with newlines replaced by \n. I hope it's clear now?

– user2428118 – 2017-02-03T21:25:54.687

@user2428118 That pastebin makes it very clear to me. I was trying to ask if it would look like that when I said left-padding. Sorry for choosing confusing terminology. – Brian J – 2017-02-03T21:33:24.620

2A banana castle? BEST CASTLE EVER – Matthew Roh – 2017-02-04T16:32:03.270

Now I need to write an AHK script that opens MSPaint and uses the Paintcan tool. – corsiKa – 2017-02-05T04:29:08.853

As usual, left-pad causes trouble. – David Conrad – 2017-02-06T18:54:18.933

Answers

Snails, 21 18 bytes

-3 bytes due to additional input constraints edited into challenge.

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

Unfortunately the time complexity is factorial, so most of the inputs aren't runnable.

Outputs 0 for falsy cases, and the number of # for truthy cases.

                 ,,
!{ 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

Posted 2017-02-03T12:27:00.943

Reputation: 29 566

This doesn't recognise the example you posted on Zgarb's answer as a castle. I don't see anything in the rules that says these shouldn't be detected as castles? The rules only say that it's a castle if each # is connected to the ground. – Martin Ender – 2017-02-03T16:27:47.077

@Zgarb No, there's a bug in the explanation -- + is actually 1 or more times, not 0. it's going to look different anyway after allowing disconnected castles. – feersum – 2017-02-03T17:14:32.520

Octave, 53 51 bytes

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

Try It Online!

*Since op dropped requirement to check for empty input answer reverted to my first edit.

Explanation:

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

Posted 2017-02-03T12:27:00.943

Reputation: 5 435

Grime, 29 bytes

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

Try it online! Most test cases time out on TIO. Replace the <0C> with <0CoF> to make it a little faster.

Explanation

I'm checking that from every # there exists a path to a `, and that there exists at least one #. I recently added rotation commands to Grime, which make this challenge much easier.

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

Posted 2017-02-03T12:27:00.943

Reputation: 39 083

JavaScript (ES6), 197 196 bytes

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)

Where \n represents the literal newline character. Tries to remove all #s one at a time by finding one adjacent to a ` and changing it to a `. Returns true if there was at least one # originally but there were all removed. Version that requires padded input for ~~118~~ 117 bytes:

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

Neil

Posted 2017-02-03T12:27:00.943

Reputation: 95 035

Perl 6, 180 bytes

{?/\#/&&?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}

Checks if the input contains at least one #, and if every # can find a path to a `.

Rather inefficient, because the pathfinding is brute-forced using a recursive function that always visits all other # of the same connected region (i.e. doesn't short-circuit).

Uses some unholy interaction between Junction operators and slipping, to ensure that the path test is skipped for space characters without requiring a separate check for that outside of the pathfinding function.

smls

Posted 2017-02-03T12:27:00.943

Reputation: 4 352

Python 3, 214 206 bytes

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}

Try it online!

The first line here is devoted to padding all the lines to the same length: we split the string (s.split('\n') is one char shorter than s.splitlines()), find the maximum length of a line, and assign to C a flattened list of all the characters after padding each line. (The newlines are gone.)

Then we make a list where each non-space character adjacent to at least one backtick is replaced by a backtick, and continue until no change happened (when the old list o is equal to C. We can compare with C>o instead of C!=o because replacing # (ASCII 35) with ` (ASCII 96) can only increase the list's lexicographical ordering.)

If no # remains, and at least one was present initially, the castle is valid.

Saved eight bytes checking for # in the set difference, rather than '#'in s and'#'not in C

Nick Matteo

Posted 2017-02-03T12:27:00.943

Reputation: 591

Detect Failing Castles

Challenge

Rules

Test cases

Falsy

Truthy

Answers

Snails, 21 18 bytes

Octave, 53 51 bytes

Grime, 29 bytes

Explanation

JavaScript (ES6), 197 196 bytes

Perl 6, 180 bytes

Python 3, 214 206 bytes