7
\$\begingroup\$

Inspired by this stack of little statues that are currently on my desk at work, given to me by my colleagues from Sri Lanka when they visited The Netherlands:

enter image description here

This is split into two different challenges due to popular demand:
Part 1) Determine the amount of statues
Part 2) Can the statues be stacked? (this challenge)

Challenge 2:

Input:

\$statues\$: a list of multi-line strings (or character matrices), containing only the characters \n|-# (where the # can be another character of your own choice). You're also allowed to take it as a single multi-line string input and parse it into a list yourself.

       ####
       ## #
       ## ##
####   #  ##
# ##  ## ###  ##      #
#  #  ## ###  ##  #   #
----  ------  --  -  --

Output:

Two distinct values of your own choice indicating truthy/falsey; so yes, 1/0 is allowed as output in languages like Java/C# .NET and such (relevant forbidden loophole). The output will be truthy if the statues can be stacked.

How can the statues be stacked?

When stacking statues, we can only stack statues with a width of the base that is \$\leq\$ the width of the top of the statue beneath it. So with the statues above, these are all possible pairs of how we could stack two statues on top of each other:

####
# ##    ##
#  #    ##      #        #
----    --      -       --
####    ####    ####    ####    ##
## #    ## #    ## #    ## #    ##    #      #
## ##   ## ##   ## ##   ## ##   --    -     --    #    #
#  ##   #  ##   #  ##   #  ##   ####  ####  ####  -   --   #
## ###  ## ###  ## ###  ## ###  # ##  # ##  # ##  ##  ##   -
## ###  ## ###  ## ###  ## ###  #  #  #  #  #  #  ##  ##   #
------  ------  ------  ------  ----  ----  ----  --  --  --

One possible complete stack keeping that in mind could therefore be:

 #
 -
 #
--
##
##
--
####
# ##
#  #
----
####
## #
## ##
#  ##
## ###
## ###
------

So in this case the result is truthy, since the statues can be stacked.

Challenge rules:

  • You can use a different consistent character other than # for the statue border if you want (other than - \n). Please state which one you've used in your answer if it's different than #.
  • You can use any two distinct output values to indicate truthy/falsey respectively.
  • You are allowed to take the \$statues\$ input in any reasonable format. Can be a single multi-line string, a list/array/stream of multi-line strings, a list of character matrices, etc.
  • You are allowed to pad the statues input with trailing spaces so it's a rectangle.
  • You can assume statues are always separated by at least one space/newline from one-another, so something like #|#| won't be in the input.
  • You can assume the statues will only have a base at the bottom side, so a statue like this won't be in the input:
--
##
##
--
  • You can assume all statues will only be placed on top of each other, and never next to each other if the top of a statue is large enough to hold two adjacent statues with small bases, or if it could fit on a smaller ledge. For example, these towers of statues aren't allowed when verifying if the statues can be stacked:
                        #
  #                     # #
#--                     - -
####                    ###
----                    ---
Statue on lower ledge   Two statues next to each other on top of single statue
  • You can assume the top and base parts of a statue are always a single piece, without any gaps. So a statue like this won't be in the input:
#  #
----

But a statue like this is possible:

#
#  #
----
  • You can assume the base determines the width of a statue. So you won't have statues like these in the input:
#######
 #####
 ####     ###
  ---     --

General rules:

  • This is , so shortest answer in bytes wins.
    Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
  • Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
  • Default Loopholes are forbidden.
  • If possible, please add a link with a test for your code (i.e. TIO).
  • Also, adding an explanation for your answer is highly recommended.

Test cases:

Truthy test cases:

       ####
       ## #
       ## ##
####   #  ##
# ##  ## ###  ##      #
#  #  ## ###  ##  #   #
----  ------  --  -  --
__________________________________________________

  ##
  ##
  ##
####
# #  #
---- -
__________________________________________________

  # #
### #
# # #
--- -
__________________________________________________

###
###
### ## #
--- -- -
__________________________________________________

      #
####  #
# ##  #
###   #         #
##### # ###### ###
----- - ------ ---
__________________________________________________

              #
# # # # # # # #
- - - - - - - -

Falsey test cases:

#
# # ##
--- --
__________________________________________________

     #
     #  #
 ### ## # #
## # ## ### #####
---- -- --- -----
__________________________________________________

     # #
## ### # #
-- --- - -
__________________________________________________

#
####  #
---- --
\$\endgroup\$
8
  • 7
    \$\begingroup\$ Identifying the statues all by themselves could be a separate challenge. \$\endgroup\$
    – Razetime
    Dec 15, 2020 at 9:06
  • 2
    \$\begingroup\$ @Razetime yeah looks like a challenge easier said than done.. reminds me of that story of a programming teacher, I think it was in the 70s that asked his students to write a program that could detect rectangles in an image as a simple homework, that proved much harder than expected, as image recognition only began to be solved decades later.. \$\endgroup\$
    – Kaddath
    Dec 15, 2020 at 10:27
  • \$\begingroup\$ @Razetime Hmm.. given that your comment has more upvotes than my challenge, I'll delete and split it into two parts. \$\endgroup\$ Dec 15, 2020 at 12:23
  • \$\begingroup\$ @Razetime I've split it into two challenges. With this you'll get a list of the statues (with the base at the bottom) and determine whether they can be stacked. With the other challenge the input is as before, and you determine the amount of statues. \$\endgroup\$ Dec 15, 2020 at 13:02
  • 1
    \$\begingroup\$ @vrintle Yes, it's already in the Challenge rules (third bullet point). :) \$\endgroup\$ Dec 15, 2020 at 13:05

2 Answers 2

2
\$\begingroup\$

Ruby 2.7, 83 77 bytes

->a{a.map{[_1[/-+/].size,_1[/#+/].size]}.sort.each_cons(2).any?{_2[1]<_1[0]}}

Try it online!

Takes an array of string (statues), and outputs the swapped boolean values. TIO uses an older version of Ruby, whereas in Ruby 2.7, we've numbered parameters, which saves four bytes.

\$\endgroup\$
2
\$\begingroup\$

Python 3.8, 98 bytes

lambda x,Q=sorted:[*sum(Q(s:=[(-len(b),-len(a))for a,*_,b in map(str.split,x)]),())]==Q(sum(s,()))

Try it online! The footer converts from the format of testcases in the challenge to a list of multiline statues.

This sorts the pairs (base_width, top_width) in descending order and verifies that top_width and base_width of adjacent pairs are descending by comparing the flattened list with the sorted list of all widths.
The same logic can be found in my 494-byter for the original challenge, which had to deal with rotated and somewhat overlapping statues:

Q=sorted
E=enumerate
def f(G):
 s=[];B,S=[{(x,y)for y,r in E(G)for x,v in E(r)if v in e}for e in('-|','#')]
 while B:
  u,U=l,L=x,y=d=min(B);b={d};R=G[y];exec("l-='-'[:l]==R[l-1];u+=R[u+1:]>[]!=R[u+1]=='-';L-='|'[:L]==G[L-1][x];U+=G[U+1:]>[]!=G[U+1][x]>'-';b|={(l,y),(u,y),(x,L),(x,U)};"*len(G+R));B-=b;z=-len(b);h=[]
  while b:b={h.append(abs([x-a,y-p][R[x]<'|']))or(a,p)for a,p in S if any(abs(c-a)+abs(d-p)<2for c,d in b)};S-=b
  s+=(z,-h.count(max(h))),
 return[*sum(Q(s),())]==Q(sum(s,()))

Try it online! and an ungolfed version.

\$\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.