16
\$\begingroup\$

In the game Terraria, one of the game mechanics involves building houses so that an NPC can move in. There is a strict set of rules for what counts as a valid house or not. Here is the list of rules:

  1. The total area in the house must be at least 60 square tiles, but less than 750. Also, the size of the house including the outer frame must be at least one of these:

    5x12
    6x10
    7x9
    8x8
    9x7
    10x6
    12x5
    15x4
    

    for simplicity's sake, you can safely assume that: a) All input houses will be rectangles, and b) no solid tile # will be inside of the house. Here is our 12x6 frame (drawn in beautiful ASCII):

    ############
    #          #
    #          #
    #          #
    #          #
    ############
    
  2. The house must be covered in background walls. These are not solid tiles, but rather a wall behind the house in the third dimension. Holes are allowed, but no holes can be larger than 4x4. If there is a row or column of 5 or more space characters in a row, this is a hole larger than 4x4, and the house is invalid. Multiple holes are also allowed, but there must be at least a single wall apart.

    ############
    #**********#
    #**********#
    #**********#
    #**********#
    ############
    
    ############
    #*    *    #
    #*    *    #
    #*    *    #
    #******    #
    ############  (Still acceptable since neither hole is larger than 4x4 and there is a separator)
    
    ############
    #    ******#
    #***    ***#
    #    ******#
    #***    ***#
    ############  (Also still valid. No row or column of blank spaces is longer or taller than 4.)
    
  3. There must be an entrance. This can be a door | on the sides or a platform - on the floor or ceiling. If the only entrance is on a corner, the NPC is unable to enter. Also, if you have a platform as the floor, you must have at least a single solid block for the NPC to stand on. This solid block cannot be directly adjacent to the side walls on the left or the right. These are all valid houses with entrances:

    ############
    #**********#
    |**********#
    #**********#
    #**********|
    ############  (Multiple doors, or doors up high are okay)
    
    ############
    #**********#
    #**********#
    #**********#
    #**********#
    #######----#
    
    #----#######
    #**********#
    #**********#
    #**********#
    #**********#
    ############
    
  4. There must be at least one light source $, table T and chair C, although more is allowed. The light source can be in the air or on the ground, but the table and chair both must be on the ground, e.g on the lowest row.

    ############
    #**********#
    #**********#
    #***$******|
    #****TC****|
    ############
    

    Also, you can assume that there is a wall behind any furniture, so a torch, chair or table can count as a separator between two holes.

    ############
    #*    *    #
    #*    *    #
    #*    $    #
    #**TC******|
    ############
    

The challenge

You must write the shortest function that takes a house as an ASCII string, and returns true/false whether or not it is valid housing. You can take this as a newline delimited string, a list of strings, or any other way as long as it is reasonable. For my sake, please include a short program so I can test if it works right or not.

For reference, these are all invalid inputs:

############
-**********#
-****$*****#
-**********#
-******TC**#
############  (You can't have platforms on the sidewalls)

###########-
#**********#
#**********#
#****$*****#
#**T***C***#
###########|  (NPC can't enter because the only entrances are on the corner)

############
#**********#
#******$***#
#**********#
#T****C****#
##--------##  (NPC has nowhere to stand)

############
#**********#
#**********#
#**********#
#**$**TC***#
##########|#  (Door cannot be in the floor or ceiling)

############
#**********#
#**********#
#**********#
|**   T C  #
############  (Since table and chair do not count as a background wall, the hole in background is too wide)

####### ####
#**********#
#**********#
#****$*****#
#**T***C***|
############  (There's a hole in the frame.)


###########################################################################
#                                                                         #
#                                                                         #
#                                                                         #
#                                                                         #
#                                                                         #
#                                                                         #
#                                                                         #
#                                                                         #
#                                                                         #
###########################################################################  (House is 75x11, which is too big.)

Leaderboard

var QUESTION_ID=68237,OVERRIDE_USER=31716;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

\$\endgroup\$
  • 6
    \$\begingroup\$ Cool challenge, fellow Terraria lover. \$\endgroup\$ – Rɪᴋᴇʀ Dec 30 '15 at 23:38
  • \$\begingroup\$ Can we assume that holes will be rectangular? Otherwise this could use a test case where the whole does not fit in 4x4 but which never contains more than 4 spaces in a row. \$\endgroup\$ – Martin Ender Dec 31 '15 at 9:30
  • \$\begingroup\$ There are many points which I find unclear. 1. Does the frame have to be rectangular? "all houses will be rectangles" suggests that they do, but doesn't clearly rule out frames which are non-rectangular but go into all four corners of their axis-aligned bounding box. And possibly holes can be surrounded by #. 2. As Martin asked, what exactly does "no holes can be larger than 4x4" mean? (Note also that it wasn't until my third read-through that I was certain of understanding what the hole was. You should write the spec for people who haven't played the game). \$\endgroup\$ – Peter Taylor Dec 31 '15 at 10:40
  • 1
    \$\begingroup\$ 3. "This solid block cannot be directly adjacent to the walls" - what is a wall? From point 2 it seems to be *, but that would exclude the given examples of valid doors. 4. Does "on the ground" mean "in the penultimate row" or "above a #"? 5. "This does not apply to table and chairs." So does that mean that a 4x4 hole with a T or C directly below it is too big? 6. "NPC can't enter because the only entrances are on the corner" I don't think the spec said anything about the corners. May they be - or | if there are other doors? \$\endgroup\$ – Peter Taylor Dec 31 '15 at 10:47
  • \$\begingroup\$ 7. If entrances on a corner are a problem because they don't admit access, does that mean that each * must be reachable from an entrance? Or are isolated * in the middle of holes allowed, holes which cut the entire room in two with only one side having an entrance allowed, and entrances which go directly into a hole allowed? \$\endgroup\$ – Peter Taylor Dec 31 '15 at 10:48
2
\$\begingroup\$

Python 2, 503 439 bytes

Not super short, but it's a solution. Let me know if you see something to golf. I'd recommend looking at my ungolfed version as well, since it's actually readable.

Edit: All the ifs outside a loop have been combined at the bottom.

def f(s):
 s=s.split("\n");e=l=0;h=len(s);w=len(s[0])
 for c in s[0][1:-1]+s[-1][1:-1]:
    if(c in"#-")<1:return 0
    if"-"==c:e=1
 for r in s[1:-1]:
    if(r[0]in"#|")*(r[-1]in"#|")<1or" "*5in r:return 0
    if"$"in r:l=1
 for r in zip(*s):
    if" "*5in`r`[2::5]:return 0
 if(h*w<60)+(h*w>749)+(w<5)+(h<4)or" "in s[0][0]+s[0][-1]+s[-1][0]+s[-1][-1]or("T"in s[-2])*("C"in s[-2])*l<1or("#"in s[-1][2:-2])<1or"|"in"".join(s[1:-1])<1>e:return 0
 return 1

Try it online

Ungolfed:

Also outputs the reason the result is False, for debugging purposes.

def f(s):
    
    # check dimensions
    s=s.split("\n")
    h=len(s)
    w=len(s[0])
    if h*w < 60 or h*w > 749 or w<5 or h<4: return False,"Size"
    
    # top / bottom
    e=0
    for c in s[0][1:-1]+s[-1][1:-1]:
        if(c in"#-")<1:return False,"T/B"
        
        # entrance
        if"-"==c:e=1
    
    # no spaces in corners -_-
    if" "in s[0][0]+s[0][-1]+s[-1][0]+s[-1][-1]: return False,"Corner"
    
    # light, table, chair
    l=t=c=0
    
    # left / right
    for r in s[1:-1]:
        if(r[0]in"#|")*(r[-1]in"#|")<1: return False,"L/R"
        
        # walls, put above
        if" "*5in r: return False,"Walls"
        
        # light
        if"$"in r:l=1
    
    # table, chair
    if"T"in s[-2]:t=1
    if"C"in s[-2]:c=1
    
    if l*t*c<1: return False,"L/T/C"
    
    # wall columns
    for r in zip(*s): # Transpose
        if" "*5in`r`[2::5]: # Tuple to string
            return False,"Walls"
    
    # entrance
    if"|"in"".join(s[1:-1])<1>e: return False,"Entrance"
    
    # place to stand
    if("#"in s[-1][2:-2])<1: return False,"Stand"
    
    return True

Ungolfed version online

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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