14
\$\begingroup\$

This challenge is not code golf. Please read the scoring before you attempt to submit an answer.

You will be given a multi-line string as input. You should output the size of the largest contiguous chunk of non-space characters. Contiguous just means that the chunk is a single piece rather than multiple disconnected pieces.

Characters are adjacent to characters directly before and after then in the same row or column. So this means that chunks cannot be connected via diagonals only.

alskdm
askl  so
mmsu  89s
    ks2mks
   3klsl

These two chunks are disconnected the bigger one has 16 characters.

You must support all printable ASCII plus space and newline. If your program includes any characters outside of this range you must support those characters too. Nothing else needs to be supported. The input will contain at least 1 non-space character and may have trailing spaces on lines.

Scoring

Answers will be scored first on the size of their own largest chunk with lower score being better. As a tie breaker they will be scored simply in their total length with lower score being better.

Test cases

If you want to copy and paste them you can view the source here.

a  
=> 1
a a
=> 1
a
a
=> 2
5a $
a  @ 
=> 3
yus
8  2
   3
=> 4
323
  
ke
=> 3
alskdm  
askl  so  
mmsu  89s
    ks2mks
   3klsl
=> 16
\$\endgroup\$
7
  • \$\begingroup\$ "newline"? I suppose not if input is taken as list of strings or other array-based thingy. \$\endgroup\$
    – Adám
    Jan 30, 2022 at 12:07
  • \$\begingroup\$ Are tabs considered whitespace, or are they treated just like any other non-whitespace character (for scoring). What about other non-printable bytes? \$\endgroup\$
    – AnttiP
    Jan 30, 2022 at 12:11
  • 1
    \$\begingroup\$ @AnttiP The challenge does not mention whitespace so it does not matter whether they are considered whitespace. They are not spaces though since they are a different character. \$\endgroup\$
    – Wheat Wizard
    Jan 30, 2022 at 12:13
  • 1
    \$\begingroup\$ So how to score Whitespace submissions? \$\endgroup\$
    – l4m2
    Jan 30, 2022 at 17:12
  • 1
    \$\begingroup\$ Can the input be an array of lines? A rectangular char array with right padding? \$\endgroup\$
    – Luis Mendo
    Jan 30, 2022 at 17:15

10 Answers 10

6
\$\begingroup\$

BQN, score 1, 125 112 108 bytesSBCS

 { ⌈ ´ + ˝ ∨ ˝ ∘ × ⎉ 1 ‿ ∞ ˜ ⍟ ≠ 2 > + ´ ∘ | ∘ - ⌜ ˜ '
' ( + ´ ∘ = ∾ ⊐ ˜ ) ¨ ( ' ' < ⊑ ) ¨ ⊸ / ⌽ ¨ 1 ↓ ↑ 𝕩 }

Run online!

1↓↑𝕩 Non-empty prefixes of the input.
⌽¨ Reverse each prefix.
(' '<⊑)¨⊸/ Keep the prefixes that don't start with whitespace.
'␤'(+´∘=∾⊐˜)¨ For each prefix, get ⟨number of newlines, index of newline⟩. These are the 1-based coordinates of non-space characters.
2>+´∘|∘-⌜˜ Convert the coordinate list to an adjacency matrix.
∨˝∘×⎉1‿∞˜⍟≠ OR matrix power to 2^length.
⌈´+˝ Maximum number of 1s in a single row.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ This is where J would be screwed by its digraphs \$\endgroup\$
    – Jonah
    Jan 30, 2022 at 14:26
  • \$\begingroup\$ Assuming you're just using individual BQN glyphs separated by spaces, surely you should have an odd number of bytes, unless you've accidentally left a useless leading or trailing space...? \$\endgroup\$ Jan 30, 2022 at 23:04
  • 1
    \$\begingroup\$ @DominicvanEssen Notice the leading space, to avoid vertical chunks \$\endgroup\$
    – isaacg
    Jan 31, 2022 at 0:46
4
\$\begingroup\$

JavaScript (Node.js), score 3, 628 518 bytes

(n, S= 'm' + 'a' + 'p' , T= 'f' + 'l' + 'a' + 't' + 'M' + 'a' + 'p' , L= 'l' + 'e' + 'n' + 'g' + 't' + 'h' , R=n [ 's' + 'p' + 'l' + 'i' + 't' ](' \n '[ 's' + 'l' + 'i' + 'c' + 'e' ]( 1,2 ))[ S ](e =>[ ... e]) )=> R[ S ](( e,i ) => e[S ](( E,I ) =>k =( G= (F= l=> ( M=R [ T ](( a,b ) => a[ T ](( A,B ) => l [ 's' + 'o' + 'm' + 'e' ](j => (j[ 0]- b<0 ?b- j[ 0]: j[ 0]- b)+ (j[ 1]- B<0 ?B- j[ 1]: j[ 1]- B)< 2) &&A !=' '? [[b , B]] : [ ])) )[ L ]== l[ L ]?M [ L ] :F( M)) ([[ i,I ]]) ) > k&& E !=' '?G :k ) , k = 0 ) | k

Try it online!

Assuming I've interpreted the rules correctly, this has a score of 3 (the longest contiguous non-space chunk has 3 characters, and there are a lot of 3-char chunks). Pretty long, however, and if it were code-golf the length would be more like 400.

Explanation: we have a counter k which holds the max size. It is initially set at 0. We loop through each non-space character and in each case, we capture the chunk that contains that character. If its size is bigger than k, we set k to its size. Eventually k will hold the biggest one and we just return that.

To capture the chunk containing some character, start with the character in question, then we get the adjacent ones and add them to the list. We then get the adjacent ones to the characters in this bigger list, and add them to the list, etc etc, until no more characters are added. The list now represents the chunk which contains the character in question.

\$\endgroup\$
6
  • 3
    \$\begingroup\$ It'd be score 1 if you use jsfuck and add space between each char \$\endgroup\$
    – l4m2
    Jan 30, 2022 at 17:11
  • \$\begingroup\$ @l4m2 Indeed, didn't think of that \$\endgroup\$
    – ophact
    Jan 30, 2022 at 17:37
  • 1
    \$\begingroup\$ You could reduce your byte count by merging smaller chunks together e.g. , with T=. \$\endgroup\$
    – Neil
    Jan 30, 2022 at 22:09
  • \$\begingroup\$ @l4m2 A naive port of my answer to JSFuck with prompt and alert is ~32K. But this can most certainly be significantly shortened. I wonder how short it could be if JSFuck is mixed with the standard JS parts that can be written with 1-char chunks. (But I'm not going to try...) \$\endgroup\$
    – Arnauld
    Jan 31, 2022 at 0:53
  • \$\begingroup\$ @Arnauld Maybe I will \$\endgroup\$
    – l4m2
    Jan 31, 2022 at 5:14
4
\$\begingroup\$

Python 3, score=3, 320 bytes

def f(L ,m= 0,i =-1 ):

 for l in L:
  
  i+= 1;j =0

  for _ in l:

   V=[ 0]; g(L ,i, j,V );m = max (m, V[0 ]); j+= 1

 L [:] =m,

def g(L ,i, j,V ):

 if len (L) >i> -1 <j< len (L[ i]) !=( i,j ) not in V!= ' ' <L[ i][ j]:

  V[0 ]+= 1;V +=( i,j ),

  for x,y in [(0 ,1) ,(0 ,-1 ),( 1,0 ),( -1, 0)] :g( L,i +x, j+y ,V)

Try it online!

The function f takes in a list of strings L as input. Outputs by modifying L to becomes [answer] (a list containing the answer as the only element).

Big idea

This is a straightforward DFS implementation. g(L,i,j,V) is the recursive DFS part, taking in the lines L, the coordinates i, j and the list of visited coordinates V.

To get a score of 3, the following features become unavailable:

  • eval and exec: we cannot do any string manipulation of the source code
  • import: no library outside of built in functions and operators
  • input: we cannot get input from STDIN. Thus we cannot write a full program, and instead must answer with a function
  • lambda: cannot create lambda function, so we must relies on def. Luckily def is usable.
  • print, return and exit: this leaves modifying function arguments as the only output method.

Fortunately, for and if are available for flow control.

More details

V is originally the list of visited coordinates, however for convenience I reserve V[0] to store the current size of the chunk. Thus g returns by incrementing V[0] by 1 every time it finds a new valid coordinate.

\$\endgroup\$
3
\$\begingroup\$

Jelly, score 1, 51 bytes

Ỵ n ⁶ T € ṭ € " J $ Ẏ W ạ § Ị Ẹ ʋ Ƈ @ Ƭ Ẉ ɗ € ` F Ṁ

A monadic Link accepting a list of characters that yields the size of the biggest chunk.

Try it online! Or see the test-suite (cases split with =).

How?

We can place spaces between instructions in Jelly without affecting the code (literals being single instructions). Unfortunately, many useful instructions for this challenge are two bytes long - for example: getting truthy multidimensional indices; forming powersets; matrix multiplication, determinants or powers. So, we just have to use the basics here.

Ỵn⁶T€ṭ€"J$ẎWạ§ỊẸʋƇ@ƬẈɗ€`FṀ - Link: list of characters, X
Ỵ                          - split X at newline characters
 n⁶                        - not equal space character? (vectorises)
   T€                      - truthy indices of each
         $                 - last two links as a monad:
        J                  -   range of length -> row_numbers
       "                   -   zip with:
     ṭ€                    -     tack each -> coordinates
          Ẏ                - tighten -> list of coordinates
                       `   - use as both arguments of:
                     ɗ€    -   for each, last three links as a dyad:
           W               -     wrap -> our initial list of collected coordinates
                   Ƭ       -     collect inputs up while they're distinct:
                  @        -       with swapped arguments:
                 Ƈ         -         keep those (of all coordinates) for which:
                ʋ          -           last four links as a dyad
            ạ              -             absolute difference
                                           (vectorises across collected coordinates)
             §             -             sums -> Manhatten distances
              Ị            -             -1 <= x <= 1? (vectorises)
               Ẹ           -             any?
                    Ẉ      -     length of each
                        F  - flatten
                         Ṁ - maximum
\$\endgroup\$
2
\$\begingroup\$

Charcoal -v, score 6, 305 bytes

while Input Push u i Assign []q for Map u Map i[k, m, l] for i if Less " " Pop k Push q k Assign 0 h while q{ Assign [Pop q]z while Filter Minus q z Filter 4 Count z Map l Plus p And Equals r Modulo n 2 Minus Minus n r 1 for k Push z l Assign Minus q z q if Less h Length z Assign Length z h} Print Cast h

Try it online! Takes input as a list of newline-terminated strings. Readable version:

while (Input()) Push(u, i);
Assign([], q);
for (Map(u, Map(i, [k, m, l]))) for (i) if (Less(" ", Pop(k))) Push(q, k);
Assign(0, h);
while (q) {
    Assign([Pop(q)], z);
    while (Filter(Minus(q, z), Filter(4, Count(z, Map(l, Plus(p, And(Equals(r, Modulo(n, 2)), Minus(Minus(n, r), 1))))))))
        for (k) Push(z, l);
    Assign(Minus(q, z), q);
    if (Less(h, Length(z))) Assign(Length(z), h);
}
Print(Cast(h));

Try it online! Explanation:

while (Input()) Push(u, i);

Input the multiline string as a list of strings.

for (Map(u, Map(i, [k, m, l]))) for (i) if (Less(" ", Pop(k))) Push(q, k);

Create a list of coordinates of all of the non-blank characters.

Assign(0, h);

Start tracking the maximum chunk size.

while (q) {

Loop until all of the coordinates have been assigned to a chunk.

    Assign([Pop(q)], z);

Start a new chunk.

    while (Filter(Minus(q, z), Filter(4, Count(z, Map(l, Plus(p, And(Equals(r, Modulo(n, 2)), Minus(Minus(n, r), 1))))))))

While there are coordinates not in the chunk that are adjacent to at least one coordinate in the chunk, ...

        for (k) Push(z, l);

... add all of the discovered coordinates to the chunk.

    Assign(Minus(q, z), q);

Remove the chunk from the coordinates.

    if (Less(h, Length(z))) Assign(Length(z), h);

Update the maximum chunk size if necessary.

}
Print(Cast(h));

Output the maximum chunk size.

\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES7), score 3, 211 bytes

s =>( o=g =(X ,Y) =>m . map ((r ,y) =>r . map ((c ,x) =>c ==' '|| (1/ Y?( X-x )** 2+( Y-y )** 2-1 :k= 0) || g(x ,y, o=o >++ k?o :k, r[x ]=' ')) ))( m=s [ 's' + 'p' + 'l' + 'i' + 't' ]`
`
. map (s =>[ ... s]) )|o

Try it online!

Commented

In the final code, we use [ 's' + 'p' + 'l' + 'i' + 't' ] instead of split and a literal line feed instead of \n. Everything else is just extra spaces all over the place.

s => (                   // s = input string
  o =                    // initialize o to a zero'ish value
  g =                    // g is a recursive function taking
  (X, Y) =>              // the current position (X, Y)
  m.map((r, y) =>        // for each row r[] at position y in m[]:
    r.map((c, x) =>      //   for each character c at position x in r[]:
      c == ' ' || (      //     do nothing if c is a space
        1 / Y ?          //     otherwise, if Y is defined:
          (X - x) ** 2 + //       make sure that the quadrance between
          (Y - y) ** 2   //       (X, Y) and (x, y)
          - 1            //       is equal to 1
        :                //     else:
          k = 0          //       reset k to 0
      ) ||               //     if the above is falsy:
      g(                 //       do a recursive call:
        x, y,            //         pass the new position (x, y)
        o =              //         update o to ...
        o > ++k ? o : k, //         max(o, k) where k is pre-incremented
        r[x] = ' '       //         put a space at the new position
      )                  //       end of recursive call
    )                    //   end of inner map()
  )                      // end of outer map()
)(                       // initial call to g:
  m =                    //   initialize m[] to
  s.split`\n`            //   the input string split by new lines
  .map(s => [...s])      //   and each row turned into a list of chars.
) | o                    // end of call: return o
\$\endgroup\$
1
  • \$\begingroup\$ Use ' s ' [ 1 ] instead of 's' and I'll compare with something like jsfuck \$\endgroup\$
    – l4m2
    Jan 31, 2022 at 7:22
1
\$\begingroup\$

JavaScript (Node.js), score 1, 626 613 bytes

 [ L = `
` , s = ' s ' [ 1 ] , l = ' l ' [ 1 ] , c = ' c ' [ 1 ] , o = ' o ' [ 1 ] , t = ' t ' [ 1 ] , r = ' r ' [ 1 ] , n = ' n ' [ 1 ] , i = ' i ' [ 1 ] ] [ ' f ' [ 1 ] + i + l + l ] [ c + o + n + ' s ' [ 1 ] + t + r + ' u ' [ 1 ] + c + t + o + r ] ( W = ' o ' , ` g = ( X , Y ) = > s . m a p ( ( r , y ) = > r . m a p ( ( c , x ) = > c > W ? ( x - X ) * * 2 + ( Y - y ) * * 2 - 1 | | g ( x , y , k = 1 / Y ? k + 1 : 1 , r [ x ] = o = o > k ? o : k ) : 0 ) )
 g ( s = o . s p l i t ( L ) . m a p ( t = > [ . . . t ] ) )
r e t u r n + o ` [ s + ' p ' [ 1 ] + l + i + t ] ` ` [ ' j ' [ 1 ] + o + i + n ] ( [ ] ) )

Try it online!

That's what I meant "something like jsfuck". Can only define function using "constructor". Other code quite like Arnauld's besides that I forgot that => is 2 char

\$\endgroup\$
0
\$\begingroup\$

Python SciPy, score 8, 167 bytes

lambda x:max( bincount (label( ((a:= array([x .split( "\n")]). T.view( "U1"))!= " ")&(a !="\x00" ))[0]. ravel()) [1:])

from scipy. ndimage import*

from numpy import*

Attempt This Online!

Leaves the chunking to scipy.ndimage.label. The chunk sizes are extracted by numpy.bincount which is also the longest function name used at 8 characters

\$\endgroup\$
5
  • 2
    \$\begingroup\$ With python the optimal score is 4, achievable like this: Try it online!. I don't have time to golf today, so I'm not gonna submit an answer. \$\endgroup\$
    – AnttiP
    Jan 30, 2022 at 17:37
  • \$\begingroup\$ Thanks, @AnttiP! In the end i decided this answer was not worth any further investment. Out of curiosity. How do you do stuff like importing in that scheme? \$\endgroup\$
    – loopy walt
    Jan 31, 2022 at 18:13
  • 1
    \$\begingroup\$ You can use exec instead of eval \$\endgroup\$
    – AnttiP
    Jan 31, 2022 at 18:16
  • \$\begingroup\$ @AnttiP I see. I wasn't sure exec would get the namespace subtleties right, but I suppose as you put everything under exec it's alright. \$\endgroup\$
    – loopy walt
    Jan 31, 2022 at 18:48
  • \$\begingroup\$ @loopywalt exec and eval have no differences in terms of namespacing. P.S.: you can also import with __import__("math") \$\endgroup\$
    – pxeger
    Feb 2, 2022 at 13:15
0
\$\begingroup\$

Pip -r, score 1, 181 bytes

g M : 1 - { _ Q s M a } + $ + : ^ 0 X # _ M g W J % : g { i : # : K 0 ~ J g ( g i / Y # @ g i % y ) : 2 L y + # g g : Z ( J * g ) R K 1 . 2 . K 1 2 X # _ Y 2 N J g I y > x x : y } x

Takes input from stdin. Attempt This Online! (Runs all of the test cases easily, but times out if passed its own source code.)

Explanation

Several operators that would have been useful are two characters (ZD, MM, MX, @?), so we have to work around them.

gM:1-{_QsMa}+$+:^0X#_Mg
g                        List of lines of stdin (due to -r flag)
 M:                      Map this function to each line in-place:
     {   Ma}              Map this function to each character of the line:
      _Qs                  Is it equal to space? (1 if so, 0 if not)
   1-                     Subtract each result from 1, swapping 1s with 0s
            +             Pad each line to the same length by adding the following:
                     Mg    Map this function to each line of the input:
                   #_       Length of the line
                 0X         String of that many zeros
                ^           Split into a list of digits
             $+:           Sum down the columns of the resulting list of lists

Here's a demonstration of how the padding logic works:

         g  ["ab"; "cde"; ""; "f"]
      #_M   [2; 3; 0; 1]
    0X      [00; 000; ""; 0]
   ^        [[0; 0]; [0; 0; 0]; []; [0]]
$+:         [0; 0; 0]

When two lists of different lengths are added, the part of the longer one that sticks out past the end of the shorter one is included in the result unchanged. Thus, summing the list of lists gives us the longest list-of-zeros in it, and adding that list to each processed row from the input essentially right-pads it with zeros to match the length of the longest row.

W J%:g{...}x
W             Loop while
     g         g, which is now a list of lists of integers
   %:          Take each of those numbers mod 2 in-place
  J            Join them together into a single string
              is truthy (i.e. not all 0s):
      {...}    (see below)
           x  After the loop, x holds the max chunk size; output it

The initial value of x is "", which is equivalent to 0 in numeric contexts. Since the maximum chunk is of size at least 1, the value of x will always be updated, so we don't have to worry about the possibility of outputting its initial value.

Our flood-fill algorithm finds a chunk of 1s and turns them into 2s. The mod-2 operation at the beginning of the loop then turns these 2s into 0s. Once all chunks have been found, g is entirely 0s, at which point the loop halts.

Inside the loop, the first thing we do is find a 1 and change it to 2:

i:#:K0~Jg (gi/Y#@gi%y):2
       Jg                 Join g into a single string
      ~                   Find the first regex match of
    K0                    0, zero or more times (equivalent to `0*`)
  #:                      Length of that match
                          This is the row-major flat index of the first nonzero entry in g
i:                        Store it in i
                @g        First row in g
               #          Length
              Y           Yank that value into y
          (g         )    Index into g at
            i/             Row: i/y
                  i%y      Column: i mod y
                      :2  Set the element at that location to 2

Then we flood-fill by changing every run of 1s adjacent to a 2 to a run of 2s, swapping rows for columns, and repeating several times:

Ly+#g g:Z(J*g)R K1 .2.K1 2X#_
L                              Loop
 y                              Length of first row in g (width of grid)
  +                             Plus
   #g                           Length of g (height of grid)
                               times:
          J*g                   Join each row in g into a single string
         (   )R                 Replace each match of this regex:
                K1               1, zero or more times
                   .2            Followed by 2
                     .K1         Followed by 1, zero or more times
                                with this callback function:
                           #_    Length of match
                         2X      String of that many 2s
        Z                       Zip (transpose) the resulting list of strings
                                (note: it becomes a list of lists of digits again)
      g:                        Assign back to g

Finally, we get the size of the chunk we just found and update x if the chunk size is bigger:

Y2N Jg Iy>xx:y
    Jg          Join g into a single string
 2N             Count the number of 2s
Y               Yank that value into y
       I        If
        y>x     y (chunk size) is greater than x (previous max chunk size):
           x:y   Set x to y
\$\endgroup\$
0
\$\begingroup\$

05AB1E, score 1, 107 101 bytes

S ¶ ¡ ζ ζ ð Ê Ð U ˜ ƶ s g ä Δ ε 0 š Ć } ¬ 0 * š Ć 2 F ø € ü 3 } X * ε ε 1 è y ø 1 è « à ] ˜ 0 K D ¢ à

Try it online or verify all test cases.

Explanation:

Most of it is similar as my 05AB1E answer for the Is there a stable way to stack these? challenge, except that 0δ.ø is ε0šĆ} and Ås is , since the 2-byte builtins and Ås cannot be separated to minimize the score. (Also, S¶¡ζζ could have been .B€S, but .B is a 2-byte builtin as well.)

Step 1. Convert the input to a matrix of characters:

S       # Convert the (implicit) input-string to a list of characters
 ¶¡     # Split it on newlines to a character-matrix

Step 2. Right-pad this input-matrix with spaces:

ζ       # Zip/transpose the input-matrix; swapping rows/columns,
        # using a space as filler if the rows are of unequal length
 ζ      # Zip/transpose back

Step 3. Transform all spaces to 0 and all other characters to 1:

ðÊ      # Check for each character whether it's NOT a space
        # (0 if a space; 1 otherwise)
  Ð     # Triplicate the matrix
   U    # Pop and store a copy in variable `X`

Step 4. Create a matrix of the same size with unique positive integers:

˜       # Flatten the matrix
 ƶ      # Multiply every 1 by its 1-based index
  s     # Swap so the matrix is at the top
   g    # Pop and push its length (amount of rows)
    ä   # Split the list into that many equal-sized parts

Step 5. Flood-fill this matrix based on the matrix of 0s/1s we stored in variable X:

Δ       # Loop until the matrix no longer changes:

Step 5.1: Add a border of 0s around the matrix:

 ε      #  Map over each row:
  0š    #   Prepend a 0
    Ć   #   Enclose; append its own head
 }      #  Close the map
  ¬     #  Push the first row (without popping the matrix)
   0*   #  Transform all 0s/1s to 0s by multiplying by 0
     šĆ #  Prepend and enclose this row as well

Step 5.2: Create overlapping 3x3 blocks of this matrix:

 2F     #  Loop 2 times:
   ø    #   Zip/transpose; swapping rows/columns
    €   #   Map over each row:
     ü3 #    Pop and push its overlapping triplets
  }     #  Close the loop

Step 5.3: Transform the 0s back, based on the matrix of variable X:

   X*   #  Multiply the values at the same positions by matrix `X`

Step 5.4: For each 3x3 block, get the maximum of its center and its horizontal/vertical neighbors:

 εε     #  Nested map over the 3x3 blocks:
   1è   #   Get the middle row
   yø1è #   As well as the middle column
   «    #   Merge these triplets together
   à    #   Pop and push the maximum of this list
]       #  Close the nested maps and until_no_changes loop

Step 6: Check which island is the largest:

˜       # Flatten the matrix to a list
 0K     # Remove all 0s
   D    # Duplicate this list
    ¢   # Count each value
     à  # Pop and push the maximum
        # (after which it is output implicitly as result)
\$\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.