Is there a single straight line in the matrix?

Question

_{Inspired by Wzl}

Determine if a given square binary matrix has exactly one row or column consisting of entirely 1s, and the rest of the matrix is 0s.

For example, these are all true:

0 0 0 0 0 0 0 0 0    0 0 0 0 0    1 0 0 0    0 1
0 0 0 0 0 0 0 0 0    1 1 1 1 1    1 0 0 0    0 1
0 0 0 0 0 0 0 0 0    0 0 0 0 0    1 0 0 0
0 0 0 0 0 0 0 0 0    0 0 0 0 0    1 0 0 0
0 0 0 0 0 0 0 0 0    0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1

And these are all false:

0 0 0 0 0 0 0    0 1 0 0 0    0 1 0 0    0 0 0    0 0 0    0 0 1    0 1
1 1 1 1 1 1 1    1 1 1 1 1    1 1 0 1    1 0 1    0 0 0    1 0 0    0 0
0 0 0 0 0 0 0    0 1 0 0 0    0 1 0 0    0 0 0    0 0 0    0 1 0
1 1 1 1 1 1 1    0 1 0 0 0    0 1 0 0
0 0 0 0 0 0 0    0 1 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

The reasons for the false ones:

• More than one row
• More than one row or column
• There are 1s outside the "all 1s column"
• There isn't a row or column of all 1s (describes the last 4)

You should take a square binary matrix of side length \$n \ge 2\$, in any reasonable format, and output 2 distinct, consistent values to indicate whether it has a single straight line. This is code-golf, so the shortest code in bytes wins.

---

Keep your golfing in your code, not your inputs/outputs. I'm very liberal with the I/O formats, including but not limited to:

• A multiline string
• A list of lines
• A 2D list (or matrix) consisting of two distinct consistent values (e.g. 0/1, space/'*', 5/'(')
• A flat array, and \$n\$, as separate arguments

• Two distinct consistent values (e.g. 1/0) to indicate the output
• Erroring/not erroring
• Two families of values, one of which consists of values that are truthy in your language and the other falsey (for example, natural numbers and zero)

• etc.

As a broad, general rule, so long as the input can be clearly understood and the outputs clearly distinguished, it's fair game.

---

Test cases

Input	Output
000000000 000000000 000000000 000000000 000000000 000000000 000000000 000000000 111111111	true
00000 11111 00000 00000 00000	true
1000 1000 1000 1000	true
01 01	true
0000000 1111111 0000000 1111111 0000000 0000000 0000000	false
01000 11111 01000 01000 01000	false
0100 1101 0100 0100	false
1000 0100 0010 0001	false
000 101 000	false
000 000 000	false
001 100 010	false
01 00	false

Answer 1

Python 2, 49 bytes

Takes as input a 2D binary matrix \$ a \$, and its size \$ n \$.

lambda a,n:sorted(map(sum,a+zip(*a)))[-2:]==[1,n]

Try it online!

There may be shorter approaches, but this is what I could find for now. Please let me know if the algorithm is incorrect.

Explanation

Since there is exactly one line, there should be exactly one row/column which contains \$ n \$ ones. Furthermore, since every \$ 1 \$ in the matrix exists on that line, there can be no other row/column containing more than one \$ 1 \$. Since if there were another \$ 1 \$ existing somwhere not on that line, it would create a row/column with at least two \$ 1 \$s.

Given this, it suffices to check that the two rows/columns with the largest number of \$ 1 \$s have counts of [1, n].

Answer 2

Brachylog, 8 bytes

{z|}≡ᵛ+1

Try it online!

{z|}        Either the rows or the columns
    ≡ᵛ      are all the same list
      +1    which sums to 1.

Answer 3

Ruby, 47 bytes

->m,n{m.uniq[1]?m-[[0]*n]==[[1]*n]:m[0].sum==1}

Try it online!

Explain please:

Split the two cases:

• If m has at least 2 different rows, remove all zeros and check if we are left with a single row consisting of ones.

• If not (all the rows are the same), check that the sum of the first row is one.

Answer 4

Factor + math.unicode, 59 bytes

[ [ concat Σ = ] keep dup flip [ all-equal? ] bi@ or and ]

Try it online!

Takes \$n\$ and a matrix of \$1\$s and \$0\$s, in that order.

• [ concat Σ = ] keep Is the sum of the matrix equal to \$n\$?
• dup flip [ all-equal? ] bi@ or and And are all the rows in either the original matrix or its transposition equal?

Answer 5

JavaScript (ES6), 46 bytes

Thanks to @PertinentDetail for a bug fix

Expects a multiline string with a trailing line feed. Returns a Boolean value.

s=>/^(0*10*\n)\1*$|^(0+\n)*1+\n[^1]*$/.test(s)

Try it online!

Answer 6

Jelly, 9 bytes

S;§ṢIṪ‘=L

Try it online!

Slightly modified port of dingledooper's algorithm.

How it works

S;§ṢIṪ‘=L    Monadic link; input = matrix M
S;§          Column sums of M ++ Row sums of M
   Ṣ         Sort
    I        Increments; (next - previous) for each adjacent pair
     Ṫ       Last item
      ‘      +1
       =L    Equals the length of M?

Jelly, 9 bytes

ZEȯE×SS=L

Try it online!

Slightly modified port of chunes's algorithm.

How it works

ZEȯE×SS=L    Monadic link; input = matrix M
ZE           1 if transpose(M) has all rows equal
  ȯE           or M has all rows equal, 0 otherwise
    ×SS      times column sum, and sum again
             (= times the sum of the entire matrix)
       =L    equals the length of M?

Answer 7

Wolfram Language (Mathematica), 21 13 35 bytes

Norm@#==#2&&Norm@Eigenvectors@#>#2&

Try It Online! (Thanks to @ZaMoC for configuring this.)

Takes # as the matrix, and #2 as the square root of the side length, n. Returns True if the conditions are met, and False otherwise

Explanation

In Mathematica, the Norm function, when applied to a matrix, will perform a singular value decomposition and then identify and return, from among the resulting matrices, the element with the largest value. For most square binary matrices with n ≥ 2, the conditions will be met IFF the Norm of the matrix equals sqrt(n), i.e., if the following returns True:

Norm@#==#2& 

However @Nitroden found an exception, which can be generalized as follows: If sqrt(n) is an integer, and the matrix contains a sqrt(n) x sqrt(n) submatrix that is all 1's, and has 0's everywhere else, its Norm will also equal sqrt(n).

Thus, to eliminate those, I added an additional test: that the Norm of the Eignevectors of the matrix is greater than sqrt(n).

My Try It Online! link contains all the OP's test matrices and, at the end, Norden's case plus three additional matrices of that form. These now all return False.

Alas, Mathematica's Eigenvectors function is 12 bytes.

Thanks to @Bubbler for the tip that my If wrapper was unnecessary.

Answer 8

Vyxal, 12 bytes

:∑$v∑Js¯Nt›=

Try it Online!

Yay! Beating Lyxal by 1 byte with a different approach!!!

-1 byte from @Lyxal himself thanks

Answer 9

05AB1E, 8 bytes

Based on the first part of Bubblers Jelly answer, which uses dingledooper's algorithm.

Input is a 2d matrix and the side length, output is 1 for truthy inputs and any other integer for falsy ones. This is the definition of truthiness in 05AB1E.

Dø«O{¥θα

Try it online! or Try all cases!

D         # push two copies of the input matrix
 ø        # transpose one copy to get a list of columns
  «       # concatenate to the list of rows
   O      # sum each sublist
    {     # sort the row and column sums
     ¥    # take consecutive differences
      θ   # get the last one (largest value - second largest value)
       α  # absolute difference with the second input

Answer 10

Jelly, 10 bytes

S;§>Ƈ1⁼LW$

Try it online!

Uses Unrelated string's test suite.

Fixed with some help from Unrelated string.

Explanation

S;§>Ƈ1⁼LW$
S           sums of columns
 ;          concat with
  §         sums of rows
    Ƈ       keep the sums which are:
   > 1       greater than 1
      ⁼LW$  = [length] ?

Answer 11

Jelly, 9 bytes

ŒṪZEƇȧiɗJ

Try it online!

The fourth totally different Jelly 9 byter. Returns either 1 or 2 for truthy and either an empty list or the number 0 for falsy. Also the program structure is more convoluted.

How it works

ŒṪZEƇȧiɗJ    Monadic link. Input: the matrix M of size n
ŒṪZ          Take the transpose of multi-dimensional indices of 1
             the result is a 2-row matrix X;
             in order to satisfy the condition, one of the rows must be
             all-equal, and the other must be identical to 1..n
   ....ɗJ    A dyad with ^ as left arg and 1..n as right:
   EƇ          Collect every row that is all-equal from X
     ȧ         Chain onto Python's `and`...
      i        Get 1-based index of 1..n in X, 0 if not found

Answer 12

J, 25 bytes

(1:0}0"0)e.],&(#\|."{])|:

Try it online!

Not the shortest (my previous translation of dingledooper's was a couple bytes shorter), but I wanted to come up with a different approach:

• (1:0}0"0) Is the matrix with all ones in the first row and zeros elsewhere...
• e. an elment of...
• ],&(#\|."{])|: All possible rotations of the input, and all possible rotations of its transpose, catted together?

Answer 13

Jelly, 9 bytes

,ZfJṁ=ⱮJƲ

Try it online!

Idea stolen from Razetime in TNB

,            Pair the input with
 Z           its transpose.
  f          Filter the pair to elements contained in
   Jṁ=ⱮJƲ    every matrix of the same dimensions with a single column of 1s.

   Jṁ        Mold [1 .. len(input)] to the shape of the input.
      ⱮJ     For each 1 .. len(input),
     =       is each element equal to it?

Answer 14

Wolfram Language (Mathematica), 25 bytes

#||#/.{a_..}:>Tr@a==1&

Try it online!

Returns True if the matrix has a single line, and nonTrue otherwise.

#||#                   input OR its tranpose
     /.{a_..}:>         replace lists of repeated elements with
               Tr@a==1      (is the sum of that element equal to 1?)

Then, any Or expression with True as an argument gets reduced to True.

Answer 15

Python 2, 43 bytes

Heavily based on dingledooper's answer, which you should upvote.

lambda a,n:set(map(sum,a+zip(*a)))=={0,1,n}

Try it online!

Or:

Python 3, 44 bytes:

lambda a,n:{*map(sum,a+[*zip(*a)])}=={0,1,n}

Saves bytes with set unpacking, but loses bytes because zip doesn't return a list. Try it online!

Explanation

In a truthy input, the sum of a row or column must be one of these three numbers:

• \$0\$, if it is parallel to the line of \$1\$s
• \$1\$, if it is perpendicular to the line of \$1\$s
• \$n\$, if it is the line of \$1\$s

Any number other than these three indicates the existence of multiple lines or a partial line.

Furthermore, all three of these numbers must be represented among the list of sums:

• If \$n\$ is missing, there is no row or column that contains all \$1\$s.
• If \$1\$ is missing, there are multiple rows and columns containing \$1\$s.
• If \$0\$ is missing, the input has two perpendicular lines of \$1\$s (as in the second falsey test case). Conveniently, we don't have to worry about the case of a \$1 \times 1\$ matrix, because we're given that \$n \geq 2\$.

Therefore:

set(                  )           # The set of
    map(sum,         )            # the sums of each
            a+                    # row and
              zip(*a)             # column
                       ==         # must be exactly
                         {0,1,n}  # that set

Answer 16

Retina 0.8.2, 32 bytes

^(0*10*)(¶\1)*$|^(0+¶)*1+(¶0+)*$

Try it online! Turns out to be much like @Arnauld's answer, except I wanted to solve it for no trailing newline instead.

Answer 17

Julia, 37 bytes

x$n=(l=sum([x x'],dims=1))[l.>1]==[n]

Try it online!

uses Razetime's approach

Answer 18

Vyxal, 14 bytes

:ÞTJv∑s2Nȯ1?"⁼

Try it Online!

Another stealing of the python answer.

Explained

:ÞTJv∑s2Nȯ1?"⁼
:ÞTJ           # merge the input list with itself transposed.
    v∑s        # sort the list that results from getting the sum of each item
       2Nȯ     # take the last two items of that list
          1?"⁼ # and check for equality with the list [1, second_input]   

Answer 19

T-SQL, 152 bytes

Input is a table variable

Returns 1 for true, 0 for false

To save bytes, this can only handle matrix up to length 10

SELECT top 1iif(x=replace(a,0,'')or
sum(x)over()=x*2-1and a not like'%0%'and
0=min(a)over(),1,0)FROM(SELECT
rank()over(order by a)x,*FROM @)c ORDER BY-x

Try it online

Answer 20

tinylisp, 88 bytes

(load library
(d _(q((M)(e 1(*(sum(map all M))(sum(map any M
(q((M)(+(_ M)(_(transpose M

The solution is the anonymous function in the last line. Try it online!

Here's an ungolfed version that verifies all test cases: Try it online!

Explanation

Define a helper function _ that takes a matrix (list of lists) M:

      (sum(map all M))                    Number of rows that are all 1s
                      (sum(map any M))    Number of rows that have any 1s
    (*                                )   Multiply those two numbers
(e 1                                   )  Is the product equal to 1?

In other words, is there exactly one row that has all 1s, which is also the only row that has any 1s?

Then our main function needs only apply _ to the matrix and its transpose, and return truthy if either result is truthy:

  (_ M)                   Test M
       (_(transpose M))   Test transpose(M)
(+                     )  Add the two results

Answer 21

Charcoal, 27 bytes

ＷＳ⊞υι∨∧⁼⌊υ⌈υ⁼¹Σ⌈υ⁼ΦυΣι⟦⭆⌈υ¹

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

ＷＳ⊞υι

Input the matrix.

  ⁼⌊υ⌈υ                 All rows are identical
 ∧                      Logical And
         Σ⌈υ            The sum of a row
       ⁼¹               Equals literal `1`
∨                       Logical Or
              υ         Input array
             Φ          Filtered where
                ι       Current row
               Σ        Is non-zero
            ⁼           Equals
                  ⭆⌈υ¹  Row of 1s
                 ⟦      As a 1-row 2D array

Answer 22

APL (Dyalog Unicode), 63 55 bytes

{(F⍉⍵)+(F←{(1↑⍴⍵)=(+/,⍵)×+/∧/⍵})⍵}

Try it online!

• changed approach
• F used on input + input transposed

×+/∧/⍵  ⍝ number of all 1s lines multiplied by
(+/,⍵)    ⍝ total 1s 
(1↑⍴⍵)=  ⍝ equal to side length?

Answer 23

PowerShell, 49 45 46 bytes

inspired by Arnauld's and Neil's answers.

+1 bytes with additional Test cases.

"$args "-match'^(0*10* )\1+$|^(0+ )*1+ [0 ]*$'

Try it online!

• convert the arguments to a string with space char as separator
• add the trail space char
• match with regexp

Answer 24

GNU-APL, 34 bytes

{+/(⍺≡+/,⍵)∧(⍵∧.=⍺⍴1)∨((⍺⍴1)∧.=⍵)}

Input the size of the matrix, and the matrix itself.

⍵∧.=⍺⍴1    finds the row with all ones, a1=1∧a2=1∧a3=1 ...
(⍺⍴1)∧.=⍵  finds the column with all ones
           The disjunction of the above two ensures atleast one of them happends
⍺≡+/,⍵     ensures that only required numbers of ones are present 

Answer 25

C (gcc), 121 119 bytes

-2 bytes thanks to ceilingcat

l;e;r;o;a;f(m,n)int*m;{r=l=o=0;for(e=a=~0;r++<n;o|=*m,a&=*m++)~*m<<32-n?e&=!*m:++l;for(o-=a;a;a/=2)l+=a&1;r=l<2&&e^!o;}

This has entire rows stored in integer arrays, making the maximum matrix size 32.

Try it online!

Answer 26

jq, 38 bytes

Reads a 2D array, outputs a boolean.

(.+transpose|map(add)-[0,1])==[length]

Try it online!