22
\$\begingroup\$

Given a string containing only the characters -, |, + and newline determine the longest straight line contained in it. A straight line is either an uninterupted run of -s and +s in a single row or an uninterupted run of |s and +s in a single column.

So for example:

    |      
    |  ----
    |      
  --+--    
    |      
    |      

There are 3 lines here one vertical, two horizontal, with the vertical line being the longest since it is 6 characters.

Your challenge is to write a program or function which takes a string as input and gives the length of the longest line.

You may assume that the input is perfectly rectangular. That is that every row has the same number of characters. You may also assume that the input contains at least 1 of the non-whitespace characters (-, |, and +).

This is , answers will be scored in bytes with fewer bytes being the goal.

Test cases

    |      
    |  ----
    |      
  --+--    
    |      
    |      

6

           
    +      
           
           

1

 ---|---
    |
    |
    |

4

-     
-|||||
-     

1

   |  
   |  
      
+----+

6

 |+-
-+| 

2

   |    
   |    
   |    
   |  + 
      | 
   |  | 
   |    
   |  | 
        
+-+     

4

\$\endgroup\$
5
  • \$\begingroup\$ Can we take input as a 2d array/matrix of characters? \$\endgroup\$ Sep 28 at 11:11
  • \$\begingroup\$ @cairdcoinheringaahing Sure I thought that was a default for ascii-art but it seems that quite strangely ascii-art may have more restrictive rules about input. \$\endgroup\$
    – Wheat Witch
    Sep 28 at 11:14
  • \$\begingroup\$ Suggested test case: two lines, ` |+-` followed by -+| => 2 (tests that solutions don't allow lines to wrap from one row/column to the next). \$\endgroup\$
    – DLosc
    Sep 28 at 15:22
  • \$\begingroup\$ @DLosc Not entirely sure how it does that in a way not already done by the case before it, but I added it. \$\endgroup\$
    – Wheat Witch
    Sep 28 at 15:53
  • 2
    \$\begingroup\$ Can we take input a matrix (or even a list) of character ordinals (e.g. 124 instead of |)? At least 3 existing answers appear to do so \$\endgroup\$ Sep 28 at 21:05

19 Answers 19

10
\$\begingroup\$

Jelly, 19 13 12 bytes

OZ%3;ƲḂŒgẎ§Ṁ

Try it online!

Takes input as a list of lines/a character matrix

First attempt, can probably be improved by a lot. Ports wasif's Vyxal answer for the conversion to 1/0 matrices, so make sure you drop them an upvote as well.

-1 byte thanks to Jonathan Allan!

How it works

OZ%3;ƲḂŒgẎ§Ṁ - Main link. Takes a matrix M on the left
O            - Convert each character to an ordinal
     Ʋ       - Last 4 links as a monad f(ord(M)):
 Z           -   Transpose
  %3         -   Mod by 3 (|,+ -> 1, space -> 2, - -> 0)
    ;        -   Concatenate to ord(M)
      Ḃ      - Mod each 2 (1 -> 1, 45, 43 -> 1, 32, 124, 2, 0 -> 0) 
       Œg    - Over each list, group adjacent equal elements
         Ẏ   - Drop into a list of lists
          §  - Sums of each (lists of 0 -> 0, lists of 1 -> length)
           Ṁ - Maximum
\$\endgroup\$
2
  • \$\begingroup\$ Z%3;ƲḂ saves one (EDIT: if we must take characters I suppose) \$\endgroup\$ Sep 28 at 22:06
  • \$\begingroup\$ @JonathanAllan Nice one, thanks! \$\endgroup\$ Sep 28 at 22:12
8
\$\begingroup\$

05AB1E, 9 bytes

ø3%«É€γOZ

Try it online!

-2 thanks to @ovs

Takes charcode matrix

This takes inspiration from Arnauld answer:

  • Modulo input matrix by 2 (Or is odd number) to get horizontal lines. (Run of 1)

  • Take the input matrix again and transpose (to get the columns) then Modulo by 3 are odd numbers? (Vertical runs)

  • Pair them, for each

  • Group consecutive equals

  • Sum them up

  • Take the maximum

And that's the result

\$\endgroup\$
2
  • 2
    \$\begingroup\$ You can save 2 bytes by checking for oddness after pairing the matrices: ø3%‚É€γOZ \$\endgroup\$
    – ovs
    Sep 28 at 21:06
  • 2
    \$\begingroup\$ But in any case I think you want to use « (concat) instead of (pair), otherwise you would have one nesting level too much and would need €€γ \$\endgroup\$
    – ovs
    Sep 28 at 21:08
8
\$\begingroup\$

JavaScript (ES10), 88 bytes

Expects a matrix of ASCII codes.

m=>Math.max(...m.map(r=>r.map(H=(v,x)=>[m.map(V=r=>V=r[x]%3%2*-~V),H=v%2*-~H])).flat(3))

Try it online!

How?

Given an ASCII code \$v\$, we use \$v\bmod 2\$ and \$(v\bmod 3)\bmod 2\$ to identify horizontal and vertical characters respectively.

 char. | code | % 2 | % 3 % 2
-------+------+-----+---------
  ' '  |  32  |  0  |    0
  '+'  |  43  |  1  |    1
  '-'  |  45  |  1  |    0
  '|'  | 124  |  0  |    1

Commented

m =>                       // m[] = input matrix
Math.max(...               // return the maximum of all values
  m.map(r =>               //   for each row r[] in m[]:
    r.map(H =              //     initialize H to a non-numeric value
    (v, x) =>              //     for each value v at position x in r[]:
      [ m.map(V =          //       initialize V to a non-numeric value
        r =>               //       for each row r[] in m[]:
          V = r[x] % 3 % 2 //         increment V if r[x] is '|' or '+'
              * -~V        //         otherwise, clear V
        ),                 //       end of map()
        H = v % 2          //       increment H if v is '-' or '+'
            * -~H          //       otherwise, clear H
      ]                    //
    )                      //     end of map()
  )                        //   end of map()
  .flat(3)                 //   deep flatten
)                          // end of Math.max()
\$\endgroup\$
7
\$\begingroup\$

Dyalog APL, 31 27 bytes

{≢⍉↑↑⊆⍨¨(↓⍵∊'-+'),↓⍉⍵∊'|+'}

-4 thanks to ovs.

Try it online!

Expects a matrix of characters.

          ⍵∊'-+'            Turn - and + into 1s and other characters into 0s
         ↓                  and split the matrix into individual rows.
                    ⍵∊'|+'  Take the original matrix, turn | and + into 1s,
                   ⍉        transpose it,
                  ↓         and again split it into rows.
                 ,          Join the rows together.
     ⊆⍨¨                    Extract streaks of 1s for each row.
   ↑↑                       Reduce the level of nesting twice to obtain a
                            3-dimensional array where the 1-streaks, padded
                            with 0s at the end, lie along the last dimension.
 ≢⍉                         Finally, get the length of this dimension,
                            i.e., the length of the longest 1-streak.
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Welcome to Code Golf, and nice first answer! \$\endgroup\$ Sep 30 at 13:07
  • \$\begingroup\$ The inner dfn can be replaced by ≢¨¨⊆⍨¨ \$\endgroup\$
    – ovs
    Sep 30 at 13:50
  • \$\begingroup\$ And {≢⍉↑↑⊆⍨¨(↓⍵∊'-+'),↓⍉⍵∊'|+'} seems to work. (Instead of getting the length of each 1-streak and taking the maximum mix all 1-streaks into a single array, and take the length of the last dimension) \$\endgroup\$
    – ovs
    Sep 30 at 14:00
  • \$\begingroup\$ @ovs Thanks! I've updated my answer. \$\endgroup\$ Sep 30 at 15:06
5
\$\begingroup\$

05AB1E, 17 16 bytes

…-+|ü2Iδå`ø«€γOà

Input as a matrix of characters.

Port of @cairdCoinheringaahing's Jelly answer, so make sure to upvote him as well.

Try it online or verify all test cases.

Explanation:

…-+|              # Push string "-+|"
    ü2            # Create overlapping pairs of this string: ["-+","+|"]
       δ          # Map over this pair of strings:
      I å         #  Check for each character in the input-matrix if it's in this string
         `        # After the map: pop and push both matrices separated to the stack
          ø       # Zip/transpose the top one; swapping rows/columns
           «      # Merge the lists together
            €γ    # Split each inner list into groups of the same digits
              O   # Sum each inner-most list
               à  # And take the flattened maximum of these sums
                  # (after which it is output implicitly as result)
\$\endgroup\$
4
\$\begingroup\$

Java (JDK), 192 175 169 167 bytes

n->{int i,r,l=0,b,h[]=new int[n[0].length];for(var a:n)for(r=i=0;i<a.length;i++){l=(r=(b=a[i])==45|b==43?r+1:0)>l?r:l;l=(h[i]=b>45|b==43?h[i]+1:0)>l?h[i]:l;}return l;}

Try it online!

-6 thanks to Kevin Cruijssen; -2 thanks to Celingcat!

\$\endgroup\$
3
  • 2
    \$\begingroup\$ 169 bytes \$\endgroup\$ Sep 28 at 14:47
  • 3
    \$\begingroup\$ Soon I'll finally be able to spell your name without alt-tabbing if you continue to improve my answers almost instantly ;) \$\endgroup\$
    – Jadefalke
    Sep 28 at 14:51
  • 1
    \$\begingroup\$ Haha. I just saw there were new answers for this challenge and got curious, when I saw your Java answer and some minor things to golf. :) \$\endgroup\$ Sep 29 at 7:41
4
\$\begingroup\$

R, 87 86 bytes

Or R>=4.1, 72 bytes by replacing two function appearances with \s.

-1 byte thanks to @Dominic van Essen.

function(s,b=function(x,r=rle(x))max(r$l[r$v==1]))max(apply(s%%2,1,b),apply(s%%3,2,b))

Try it online!

That turned out shorter than I expected.

Takes input as matrix of character codes.

Explanation

function(s,     # function takes s as input
 b=function(x,  # helper function for rows/columns
  r=rle(x))     # compute run length encoding
   max(         # get maximum
    r$l[r$v==1] # of run lengths where value is one
   ))
max(            # maximum of
 apply(         # apply to
  s%%2,         # the matrix with ones for | and +
  1,b),         # the helper function along columns
 apply(         # apply to
  s%%3,         # the matrix with ones for - and +
  2,b)          # the helper function along rows
)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 86 bytes \$\endgroup\$ Sep 29 at 15:39
  • \$\begingroup\$ @DominicvanEssen, nice one, thanks! \$\endgroup\$
    – pajonk
    Sep 30 at 12:52
4
\$\begingroup\$

GolfScript, 52 bytes

n/.zip]"-":a;{{{.a"+"+\?-1>*}%"ø"%{,}/}/"|":a;}%$-1=

Try it online!

Explanation:

n/.             split input on newline
  .zip          duplicate and zip(transpose rows and columns) the copy
      ]         put them in an array
"-":a; has "-"  for first copy and "|" for the zipped copy
{               map over the copies of input
 {              for each line
  {             map over each char
   .a"+"+\?-1>* returns char if == a ("-" or "|") or "+", otherwise 0
  }%
  "ø"%          splits on ø(null char, "\x00") to get array of lines
  {,}/          for each, get length
 }/
 "|":a;         sets a to "|" for the next copy
}%
                left with array of line lengths
$-1=            sort and get last element, aka get max

                implicit print

There is probably some completely different approach that is smaller, but I am pretty happy with how small I got this.

The difference between {...}~(map) and {...}/(for each) is that map returns an array, while for each dumps them on the stack, essentially {...}~~. Rearranging and using / allowed me to save a few chars I didn't think I could, so that's pretty cool.

The code has a literal null char that stackoverflow isn't liking, so I replaced it with ø. The tio.run link should work.

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

Python 3, 114 109 bytes

-5 bytes thanx to Alex Waygood

lambda i,j=''.join:max(map(len,g('[-+]+',i)+g('[|+]+',j(map(j,zip(*i.split('\n')))))))
import re
g=re.findall

Try it online!

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

Pip, 26 bytes

MX#*:(J*ZgR'-sALgR'|s)Jn^w

Try it online! (Uses the -r flag to take input as lines of stdin, but would also work without the flag if input lines were given as command-line arguments.)

Explanation

MX#*:(J*ZgR'-sALgR'|s)Jn^w
                            g is lines of input; s is space; n is newline; w is
                            regex matching runs of whitespace (implicit)
         gR'-s              In g, replace all hyphens with spaces
        Z                   Zip (transpose rows for columns)
      J*                    Join each column into a string
              AL            To the list of columns, append this list:
                gR'|s       In g, replace all pipes with spaces
     (               )Jn    Join the resulting list on newlines
                        ^w  Split on runs of whitespace
  #*:                       Get the length of each run of non-whitespace characters
MX                          Take the maximum
\$\endgroup\$
2
\$\begingroup\$

C++ (gcc), 124 bytes

int f(char*a){char*b=a,*c=a,l=0,h=0;for(;*a;++a)*a%2?l=l>++h?l:h:h=0,*a>10?*a%5>2?*a=0,l=l>++*c?l:*c:*c=0,++c:c=b;return l;}

Try it online!

This is my first time submitting a code here, so I'm open to any improvements. I don't think I used anything past C++98. The function takes a C-string as input and modifies it.

Explanation

int f(char* a) {              // Take a C-string as input
  char* b = a;                // Preserve a pointer to the beginning
  char* c = a;                // Use the first row of a to keep track of
                              // vertical line lengths; this is tracked by c.
  char l = 0;                 // Maximal line length
  char h = 0;                 // Current horizontal line length
  
  for (; *a; ++a) {           // *a may be '\0' (0), '\n' (10), ' ' (32),
                              // '+' (43), '-' (45), or '|' (124).
    if (*a % 2) {             // Current character is '+' (43) or '-' (45)
      ++h;                    // Increment current horizontal line length
      l = l > h ? l : h;      // Update maximal line length
    }
    else {
      h = 0;                  // Reset horizontal line length
    }
    
    if (*a != 10) {
      if (*a % 5 > 2) {       // Current character is '+' (43) or '|' (124)
        *a = 0;               // Set current character to 0 (only needed
                              // for the first row)
        ++*c;                 // Increment current column's vertical line
                              // length
        l = l > *c ? l : *c;  // Update maximal line length
      }
      else {
        *c = 0;               // Reset current column's vertical line length
      }
      ++c;
    }
    else {                    // Current character is '\n' (10)
      c = b;                  // Reset column tracker
    }
  }
  return l;
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice first answer! \$\endgroup\$ Sep 30 at 16:30
  • 1
    \$\begingroup\$ Nice idea to use the string itself as scratch space for the array of current line-lengths. I was thinking about writing an asm answer and maybe using the option to take a matrix of characters so I could get the line length as an arg instead of scanning for newline (and using the asm equivalent of a C99 VLA), but this trick might be smaller in x86 asm, too. \$\endgroup\$ Oct 1 at 0:50
2
\$\begingroup\$

Retina, 74 bytes

Lw$`([-+]+)|[|+]((?<=(.)*.).*¶(?<-3>.)*(?(3)^)[|+])*
$1¶_$#2*
%C`.
N^`
0G`

Try it online! Explanation:

Lw`([-+]+)|[|+]((?<=(.)*.).*¶(?<-3>.)*(?(3)^)[|+])*

List all overlapping matches of either horizontal or vertical lines. A .NET balancing group is used to ensure that all of the characters in the vertical line are in the same column. All overlapping matches are needed to ensure that all possible lines are detected, as simple overlaps would only detect the horizontal line of an upside-down L shape.

L$`
$1¶_$#2*

For each match list the horizontal line and a string of underscores of the length of the vertical line. (There is always at least one underscore even when there was no vertical match but the horizontal match is always at least length 1 in this case anyway.)

%C`.

Count the number of characters in each line.

N^`

Sort in descending order.

0G`

Take the maximum.

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

Ruby, 103 bytes

->m{eval"(m#{e=".map{|x|x+[' ']}.join.gsub('"}|',' ')+m.transpose#{e}-',' ')).split.map(&:length).max"}

Try it online!

  • takes a 2d array as input.

We use eval to repeat e two times by interpolation.
e= adds a column of spaces, joins and calls gsub..
to swap | or - with a space, we do it on both input and input transposed.
Then we split to get our desired chunks of lines and we get the max length

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

Vyxal G, 14 bytes

∷¹ǒ∷ÞT"ƛ0ZfĠv∑

Try it Online!

-7 thanks to @AaronMiller and @emanresuA

\$\endgroup\$
3
  • \$\begingroup\$ 17 bytes \$\endgroup\$ Sep 28 at 19:35
  • \$\begingroup\$ (CC @AaronMiller) 14 bytes \$\endgroup\$
    – emanresu A
    Sep 29 at 3:29
  • \$\begingroup\$ @emanresuA AaronMiller nice !! the port now looks better \$\endgroup\$
    – wasif
    Sep 29 at 5:50
1
\$\begingroup\$

Perl 5, 94 bytes

sub{$s=$_=pop;max((map y///c,/[-+]+/g),map{map$c=/[|+]/?$c+1:0,$s=~/^.{0,$_}(.?)/mg}0..y///c)}

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ 85 bytes using a complete program and assuming input is rectangular, however i should add $c=0 \$\endgroup\$ Sep 30 at 20:29
  • \$\begingroup\$ understood the trick {0,$_}(.?) so that the empty line resets $c, 83 bytes \$\endgroup\$ Sep 30 at 20:37
  • \$\begingroup\$ golfing again Try it online! \$\endgroup\$ Sep 30 at 20:46
1
\$\begingroup\$

Wolfram, 98 bytes

Max[Length/@Flatten[Map[r|->SequenceCases[r,{#2..}],#]&@@@{{#,"-"|"+"},{Transpose@#,"|"|"+"}},2]]&

Explanation

Max[                                                    Max of
  Length /@ Flatten[                                    Length of
    Map[r |->                                             For each row
        SequenceCases[r, {#2 ..}], #] &                     Sequences of
     @@@ {{#, "-" | "+"}, {Transpose@#, "|" | "+"}},          - or + in the input
                                                              | or + in the transpose of the input
    2]] &
\$\endgroup\$
1
1
\$\begingroup\$

Charcoal, 35 bytes

WS⊞υιIL⌈⁺Eυ⌈⪪⭆ι№-+λ0E§υ⁰⌈⪪⭆υ№|+§λκ0

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings. Explanation:

WS⊞υι

Input the strings into an array.

IL⌈⁺

Output the length of the maximum line in either of the following:

Eυ⌈⪪⭆ι№-+λ0

For each string in the array, replace each character with 1 if it is - or + otherwise 0, then split the result on 0s and take the maximum string of 1s. This results in a list of strings that have the lengths of the longest line in each row.

E§υ⁰⌈⪪⭆υ№|+§λκ0

For each column, build up a string of 1s and 0s corresponding to whether each character is | or + or not, then split on 0s and take the maximum again, resulting in a list of strings that have the lengths of the longest line in each column.

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

Japt -h, 19 bytes

"-|"¬c@zY ôkXi+ÃmÊn

Try it

"-|"¬c@zY ôkXi+ÃmÊn     :Implicit input of string U
"-|"¬                   :Split "-|" into an array of characters
     c                  :Flat map
      @                 :By passing each X at 0-based index Y through the following function
       zY               :  Rotate U 90 degrees Y times
          ô             :  Split at characters that return truthy (non-empty string)
           k            :  When the following characters are removed
            Xi+         :    "+" prepended to X
               Ã        :End map
                m       :Map
                 Ê      :  Length
                  n     :Sort
                        :Implicit output of last element
\$\endgroup\$
0
\$\begingroup\$

Scala, 92 bytes

l=>(l.flatMap(_ split "[ |]")++l.transpose.flatMap(_.mkString split "[ -]")).map(_.size).max

Try it in Scastie!

Takes a Seq[String].

Slightly longer solution, 94 bytes

l=>(for((m,c)<-Seq(l->"[ |]",l.transpose->"[ -]");r<-m;p<-r.mkString split c)yield p.size).max

Try it in Scastie!

Takes input as a Seq[Seq[Char]].

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