current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 23 down vote favorite
1

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!

share|improve this question
    
Can we assume all lines of the input will be the same length (i.e. filled up with spaces)? – smls 21 hours ago
    
@smls No, you cannot assume input will be padded. – user2428118 21 hours ago
    
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 21 hours ago
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 21 hours ago
1  
Related. – Zgarb 20 hours ago
up vote 6 down vote

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
share|improve this answer
up vote 5 down vote

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 #.
share|improve this answer
up vote 5 down vote

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
share|improve this answer
    
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♦ 18 hours ago
    
@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 17 hours ago
up vote 3 down vote

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.

share|improve this answer
up vote 2 down vote

JavaScript (ES6), 197 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 bytes:

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

Python 3, 214 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 and'#'not in 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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