33
\$\begingroup\$

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 , 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
\$\endgroup\$
6
  • 1
    \$\begingroup\$ May we take \$n\$ along with a non-flat array? \$\endgroup\$
    – chunes
    Jun 17, 2021 at 2:12
  • 2
    \$\begingroup\$ @chunes Yep, that's fine \$\endgroup\$ Jun 17, 2021 at 2:16
  • 1
    \$\begingroup\$ suggested test case: a matrix with the right amount of ones but not in a line \$\endgroup\$
    – MarcMush
    Jun 17, 2021 at 11:29
  • 3
    \$\begingroup\$ I really like this kind of problem, where at face value it's very simple, but ends up generating many conceptually different solutions, some involving higher math (matrix algebra in this case). \$\endgroup\$
    – Jonah
    Jun 17, 2021 at 12:41
  • 2
    \$\begingroup\$ Nice use of markdown tables for test cases. I should do that \$\endgroup\$
    – qwr
    Jun 17, 2021 at 23:24

25 Answers 25

28
\$\begingroup\$

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].

\$\endgroup\$
2
  • \$\begingroup\$ @DLosc Brilliant idea! I had suspected my solution could be improved upon. Would you like to post a new answer? \$\endgroup\$ Jun 17, 2021 at 23:24
  • \$\begingroup\$ All right, done! It's mostly your idea, so I wanted to give you the option of integrating it first. It is exciting to get to post a Python golf--normally my answer is both longer and later than other people's. ;^) \$\endgroup\$
    – DLosc
    Jun 18, 2021 at 17:27
13
\$\begingroup\$

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.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ An alternate, ASCII-only version (same number of bytes): replace ≡ᵛ with =h. \$\endgroup\$
    – DLosc
    Jun 17, 2021 at 22:22
11
\$\begingroup\$

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.

\$\endgroup\$
10
\$\begingroup\$

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?
\$\endgroup\$
10
\$\begingroup\$

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!

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Unfortunately, this doesn't work if the ones are the first row of the matrix (not one of the test cases). To fix this, replace \2* with [^1]* at the cost of two characters. However, you don't need the grouping in (\1+\n) so you can save two characters to get back to 46. \$\endgroup\$ Jun 17, 2021 at 21:35
  • \$\begingroup\$ @PertinentDetail Good catch and nice fix. Thanks! \$\endgroup\$
    – Arnauld
    Jun 17, 2021 at 21:57
8
\$\begingroup\$

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?
\$\endgroup\$
8
\$\begingroup\$

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.

\$\endgroup\$
10
  • 3
    \$\begingroup\$ I think it should be fine to strip the if statement entirely (giving true or false). \$\endgroup\$
    – Bubbler
    Jun 17, 2021 at 6:29
  • \$\begingroup\$ I don't have mathematica but it seems like this only counts if there is the right amount of 1s Try it online with Julia! \$\endgroup\$
    – MarcMush
    Jun 17, 2021 at 11:28
  • \$\begingroup\$ @MarcMush I tried your test matrix, and it correctly returned False. "norm" seems to means something different in Julia—according to discourse.julialang.org/t/performance-of-norm-function/14709/9, it instead computes the Frobenius norm. In Mathematica, when Norm is applied to a matrix, it does a singular value decomposition, and then selects the element with the maximum value. So, for your matrix m= {{1, 0, 0}, {1, 0, 0}, {0, 1, 0}}, [continued] \$\endgroup\$
    – theorist
    Jun 17, 2021 at 11:56
  • 1
    \$\begingroup\$ here are all test cases: Try it online! \$\endgroup\$
    – ZaMoC
    Jun 17, 2021 at 12:04
  • 5
    \$\begingroup\$ Fails on {{1, 1, 0, 0}, {1, 1, 0 ,0}, {0, 0, 0, 0}, {0, 0, 0, 0}, which has operator norm 2. \$\endgroup\$
    – Nitrodon
    Jun 17, 2021 at 13:55
7
\$\begingroup\$

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

\$\endgroup\$
2
  • 2
    \$\begingroup\$ You can remove for -1 (because the input hasn't cycled back to the input list) \$\endgroup\$
    – lyxal
    Jun 17, 2021 at 4:17
  • 2
    \$\begingroup\$ Good job! You beat the creator of the language. \$\endgroup\$
    – user100690
    Jun 17, 2021 at 5:15
7
\$\begingroup\$

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
\$\endgroup\$
0
6
\$\begingroup\$

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] ?
\$\endgroup\$
0
6
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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?
\$\endgroup\$
7
  • \$\begingroup\$ Fails with inputs like 1101 0010 0000 0000. \$\endgroup\$
    – Bubbler
    Jun 17, 2021 at 4:35
  • \$\begingroup\$ Ugh, nice catch. \$\endgroup\$
    – Jonah
    Jun 17, 2021 at 4:35
  • \$\begingroup\$ @Bubbler Fixed. I really wanted to find a solution with using diagonal /. sums, which produce a string of # ones and zero elsewhere iff valid input. But golfing that condition was cumbersome. Maybe you can make it work. \$\endgroup\$
    – Jonah
    Jun 17, 2021 at 5:00
  • \$\begingroup\$ Why do you need to square element wise? The matrix always has 0 or 1 in it, and squaring either of those (or any product involving those) does nothing \$\endgroup\$ Jun 17, 2021 at 13:56
  • 2
    \$\begingroup\$ Fails with 1100 1100 0000 0000 – which suggests that it is the same algorithm as theorist's answer, that also fails with this case. :-) \$\endgroup\$
    – xash
    Jun 17, 2021 at 15:16
5
\$\begingroup\$

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?
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ Can you add an explanation? I'm starting to learn Wolfram. \$\endgroup\$
    – Jonah
    Jun 17, 2021 at 5:38
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.

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

Julia, 37 bytes

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

Try it online!

uses Razetime's approach

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

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]   
\$\endgroup\$
2
\$\begingroup\$

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

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

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
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 27 bytes

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

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

WS⊞υι

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
\$\endgroup\$
1
\$\begingroup\$

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?
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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 
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 121 bytes

l;e;r;o;a;f(m,n)int*m;{r=l=o=0;a=~0;for(e=1;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!

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