41
\$\begingroup\$

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!

Improve this question
\$\endgroup\$
16
  • \$\begingroup\$ Can we assume all lines of the input will be the same length (i.e. filled up with spaces)? \$\endgroup\$
    – smls
    Feb 3, 2017 at 13:03
  • \$\begingroup\$ @smls No, you cannot assume input will be padded. \$\endgroup\$
    – user2428118
    Feb 3, 2017 at 13:08
  • 1
    \$\begingroup\$ @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? \$\endgroup\$
    – user2428118
    Feb 3, 2017 at 13:46
  • 1
    \$\begingroup\$ Related. \$\endgroup\$
    – Zgarb
    Feb 3, 2017 at 14:10
  • 2
    \$\begingroup\$ A banana castle? BEST CASTLE EVER \$\endgroup\$
    – Matthew Roh
    Feb 4, 2017 at 16:32

6 Answers 6

Reset to default
12
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – Martin Ender
    Feb 3, 2017 at 16:27
  • \$\begingroup\$ @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. \$\endgroup\$
    – feersum
    Feb 3, 2017 at 17:14
9
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
7
\$\begingroup\$

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 #.
Improve this answer
\$\endgroup\$
0
6
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

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
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.