13
\$\begingroup\$

The challenge

Given a 2d string representing the bottom of a boat as an input, you must determine whether or not the boat will float. This 2D string can be in whatever format is most convenient. (String with newlines, list of string, list of list of chars, etc.) Print a truthy value if it will float, and a falsey value if it will sink.

A boat will tip over if the bottom has an inconsistent density, so every character of must be the same. Also, if a boat has large holes in it, represented by spaces, it will sink, so your boat must have no holes with an area greater than 4. Here is an example:

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

This boat is valid because the largest hole in it has an area of 4. This boat:

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

is invalid because it has a hole with an area of 7. You can safely assume that the outside of every input will be a solid rectangle with no holes. Here are some more tests:

$$$$$$$$
***$$$$$
***$$$$$
***$$$$$
$$$$$$$$
Invalid density. Sink.

%%%%%%%%
%    % %
%%%%%  %
%    % %
%%%%%%%%
None of the holes are larger than 4. Float.

OOOOOOOO
OOOOOOO 
OOOOOOOO
OOOOOOOO
OOOOOOOO
The outside border is not solid. Undefined.

&&&&&&&&&&&&&
& & & & & & &
&& & & & & &&
& & & & & & &
&& & & & & &&
& & & & & & &
&&&&&&&&&&&&&
Although I would not be comfortable riding in this boat myself, 
none of the holes are larger than 4. It floats.

@@@@@
@   @
@   @
@   @
@@@@@
It sinks.

Rules

  • IO can be in any reasonable format.
  • Standard loopholes apply.
  • Shortest answer in bytes wins.
  • The given string will entirely consist of printable ASCII.
\$\endgroup\$
6
  • \$\begingroup\$ What is the bottom? What is the frame? \$\endgroup\$
    – flawr
    Apr 30, 2016 at 20:10
  • \$\begingroup\$ @flawr The bottom is the string you take as input. The frame is a poor choice of wording that I will edit out. \$\endgroup\$
    – DJMcMayhem
    Apr 30, 2016 at 20:12
  • \$\begingroup\$ A "2d string"? You mean a list of strings? \$\endgroup\$
    – anon
    Apr 30, 2016 at 20:14
  • 1
    \$\begingroup\$ I think the & boat exists \$\endgroup\$
    – l4m2
    Jun 16, 2018 at 4:52
  • \$\begingroup\$ "A boat will tip over if the bottom has an inconsistent density, so every character of must be the same." If the outside border was one character and the interior were a different character it would be inconsistent density but it wouldn't tip over would it? \$\endgroup\$ Jun 18, 2018 at 3:18

2 Answers 2

3
\$\begingroup\$

Matlab, 106 bytes

s=input('');im=~(s-32);c=bwconncomp(im,4);disp(~nnz(cellfun(@nnz,c.PixelIdxList)>3)&nnz(unique(s(~im)))<2)

The input is a matrix of characters, e.g. for the first test case:

`['$$$$$$$$';'***$$$$$';'***$$$$$';'***$$$$$';'$$$$$$$$']`

Explanation:

s=input('');           %read input
im=~(s-32);            %convert input to bw image (space = black)
c=bwconncomp(im,4);    %calculate the connected components (4 connectivity)

disp(
     ~nnz(cellfun(@nnz,c.PixelIdxList)>3) %find out whether we have components that have more at least 4 pixels
     &nnz(unique(s(~im)))<2)              %find out if we have more than 1 non-space character
\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Unicode), 76 bytes

{(1=≢∪' '~⍨∊⍵)∧×/5>a/⍨×a←∊g↓⍉↑(g←{⊃,/{×⊃⍵:+/⍵⋄⍵}¨⍵⊂⍨1,2{≠/0=⊃¨⍺⍵}/⍵}¨)' '=⍵}

Try it online!

Accepts input as a list of strings.

1 for floating, and 0 for sinking.

Explanation

{(1=≢∪' '~⍨∊⍵)∧×/5>a/⍨×a←∊g↓⍉↑(g←{⊃,/{×⊃⍵:+/⍵⋄⍵}¨⍵⊂⍨1,2{≠/0=⊃¨⍺⍵}/⍵}¨)' '=⍵}
                                                                      ' '=⍵ boolean array for spaces
                              (g←{⊃,/{×⊃⍵:+/⍵⋄⍵}¨⍵⊂⍨1,2{≠/0=⊃¨⍺⍵}/⍵}¨)       apply the following function g to each row:
                                                    1,2{≠/0=⊃¨⍺⍵}/⍵         get the start of each group of zeroes/nonzero values
                                                 ⍵⊂⍨                        cut the list according to that
                                     {×⊃⍵:+/⍵⋄⍵}¨                           sum each nonzero array
                                  ⊃,/                                       join all of that together
                         g↓⍉↑                                               apply g again on the transpose
                  a/⍨×a←∊                                                   flatten and remove zeroes
              ×/5>                                                          are all sums ≤ 4?
             ∧                                                              and
     ' '~⍨∊⍵                                                                the boat with spaces removed
    ∪                                                                       uniquified 
 1=≢                                                                        has only 1 element?
                
\$\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.