20
\$\begingroup\$

A band matrix is a matrix whose non-zero entries fall within a diagonal band, consisting of the main diagonal and zero or more diagonals on either side of it. (The main diagonal of a matrix consists of all entries \$a_{i,j}\$ for which \$i=j\$.) For this challenge, we will only be considering square matrices.

For example, given this matrix:

1 2 0 0
3 4 5 0
0 6 0 7
0 0 8 9

this is the band:

1 2
3 4 5
  6 0 7
    8 9

The main diagonal (1 4 0 9) and the diagonals above it (2 5 7) and below it (3 6 8) are the only places non-zero elements are found; all other elements are zero. (Some of the elements in the band may also be zero.)

The bandwidth of the matrix is the smallest number \$k\$ such that all non-zero elements are contained within a band consisting of the main diagonal, \$k\$ diagonals above it, and \$k\$ diagonals below it. The bandwidth of the above matrix is 1: all non-zero elements fall within the main diagonal, the one diagonal above it, or the one diagonal below it. For another example:

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

The bandwidth of this matrix is 2, because it takes two diagonals above and below the main diagonal to catch all non-zero elements:

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

Note that for the purposes of this challenge, the band must extend the same distance on either side of the main diagonal, which is why the diagonal 0 0 is included above.

Mathematically, the bandwidth is the smallest number \$k\$ such that for every entry \$a_{i,j}\$ in the matrix, \$a_{i,j} = 0\$ if \$|i-j|>k\$.

Challenge

Given a square matrix containing nonnegative integers, output its bandwidth.

The matrix will always have at least one nonzero entry.

This is : make your code (measured in bytes) as short as possible.

Test cases

1
=>
0

1 0 0
0 1 0
0 0 1
=>
0

1 2 0 0
3 4 5 0
0 6 0 7
0 0 8 9
=>
1

1 1 0 0
1 1 1 0
1 1 1 1
0 1 1 1
=>
2

16 18  8
 6 14 22
20 10 12
=>
2

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
=>
3
Improve this question
\$\endgroup\$
6
  • 1
    \$\begingroup\$ This makes the bandwidth of the zero matrix undefined, which I found sad as it could be with a better definition. \$\endgroup\$
    – YSC
    Feb 27, 2022 at 14:35
  • \$\begingroup\$ @YSC Hmm, what definition would you propose? \$\endgroup\$
    – DLosc
    Feb 28, 2022 at 18:17
  • \$\begingroup\$ This is probably too late, and this won't add much to this challenge anyway. If I had to define that bandwidth, I'd make it so bandwidth(Zero)=0, bandwidth(Identity)=1. \$\endgroup\$
    – YSC
    Mar 1, 2022 at 9:01
  • \$\begingroup\$ Ah, I see. I went by the definition on the Wikipedia article, which I assume is the official definition. I think if I were going to define something called bandwidth, it would be the actual width of the band (i.e. 2*k+1 if k is the bandwidth by this definition). ¯\_(ツ)_/¯ \$\endgroup\$
    – DLosc
    Mar 1, 2022 at 16:43
  • \$\begingroup\$ I'd say you were right to go with Wikipedia's definition rather than one from an unknown person on the Internet ^^ \$\endgroup\$
    – YSC
    Mar 1, 2022 at 16:57

12 Answers 12

Reset to default
8
\$\begingroup\$

Jelly, 5 bytes

ŒṪIAṀ

Try it online!

ŒṪ     -- indices of non-zero values
  I    -- reduce each index by subtraction
   A   -- get the absolute values
    Ṁ  -- select the maximum
Improve this answer
\$\endgroup\$
7
\$\begingroup\$

R, 38 bytes

function(A)max(abs(row(A)-col(A))*!!A)

Try it online!

Test harness taken from Robin Ryder's answer.

R has some weird built-ins. Given a matrix M, row will return a matrix of the same size with each entry equal to its row number, and col likewise, but with columns. That is, \$row(M)_{ij}=i\$ and \$col(M)_{ij}=j\$. So abs(row(A)-col(A)) gives us a matrix of possible bandwidths like so for a \$5\times 5\$ matrix:

     [,1] [,2] [,3] [,4] [,5]
[1,]    0    1    2    3    4
[2,]    1    0    1    2    3
[3,]    2    1    0    1    2
[4,]    3    2    1    0    1
[5,]    4    3    2    1    0

Then we "filter" the entries where A is nonzero and take the maximum to obtain the bandwidth.

Improve this answer
\$\endgroup\$
7
\$\begingroup\$

R, 41 40 bytes

-1 byte thanks to Giuseppe

function(A)max(diff(t(which(t(A)|A,T))))

Try it online!

Note that the matrix \$A|A^T\$ has the same bandwidth as the matrix \$A\$, but is symmetrical. We can therefore consider only its lower-triangular part, for which row index is greater than column index.

The formula given in the question is \$\max(|i-j|)\$ such that \$A_{ij}\neq 0\$; this is equivalent to \$\max(i-j)\$ such that \$(A|A^T)_{ij}\neq 0\$ (without the absolute value). The call which(x,T) returns a 2-column matrix listing the row and column indices of all TRUE values in x; we need to transpose the output since diff acts column-wise.

This saves 3 bytes compared to the more obvious strategy:

function(A)max(abs(which(!!A,T)%*%c(1,-1)))

Edit: Outgolfed by Giuseppe's 38 byte answer.

Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ 40 bytes \$\endgroup\$
    – Giuseppe
    Feb 27, 2022 at 17:47
  • \$\begingroup\$ @Giuseppe Nice, thanks! \$\endgroup\$
    – Robin Ryder
    Feb 27, 2022 at 22:54
  • 1
    \$\begingroup\$ 38 bytes \$\endgroup\$
    – Giuseppe
    Feb 28, 2022 at 18:27
  • \$\begingroup\$ @Giuseppe That's very different and much better, you should post it separately. I didn't know about the row and col functions! \$\endgroup\$
    – Robin Ryder
    Feb 28, 2022 at 19:51
4
\$\begingroup\$

Python 3, 68 bytes

lambda a,e=enumerate:max(abs(i-j)for i,r in e(a)for j,c in e(r)if c)

Try it online!

Finds the largest \$|i-j|\$ among all entries \$a_{ij} \neq 0\$.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Charcoal, 13 bytes

Ｉ⌈ＥＡ⌈Ｅι∧λ↔⁻μκ

Try it online! Link is to verbose version of code. Explanation:

   Ａ            Input array
  Ｅ             Map over rows
      ι         Current row
     Ｅ          Map over elements
        λ       Current element
       ∧        Logical And
           μ    Column index
          ⁻     Subtract
            κ   Row index
         ↔      Absolute value
    ⌈           Take the maximum
 ⌈              Take the maximum
Ｉ               Cast to string
                Implicitly print
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

MATL, 10 6 bytes

&f-|X>

Try it online!

Port of @ovs's Jelly solution.

(-4 bytes thanks to @LuisMendo)

Older

MATL, 16 bytes

&+t"tX@&Rs~?X@q.

Try it out! Check all cases

Outputs a transformed version of the input (input + input's transpose) and then the bandwidth. Not sure if extraneous output like this is usually allowed; if not, the "cleaner" version is just 1 byte longer: &+XH"HX@&Rs~?X@q. Try it out

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ @LuisMendo I see them (ovs's and Lynn's methods) as pretty much the same thing? The trouble is getting the \$i\$ and \$j\$, half of the bytes are spent in ind2sub to get them. \$\endgroup\$
    – Sundar R
    Feb 27, 2022 at 0:05
  • 1
    \$\begingroup\$ @LuisMendo :facepalm: I literally checked f's alternate specification when I read your (original) comment, but for some reason was looking at the input spec and thought there's no & form at all. Thanks! \$\endgroup\$
    – Sundar R
    Feb 27, 2022 at 0:09
3
\$\begingroup\$

Pari/GP, 50 bytes

a->m=0;matrix(#a,,i,j,a[i,j]&&m=max(m,abs(i-j)));m

Try it online!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

J, 38 31 23 bytes

>./@,@(~:&0*|@-/~@i.@#)

-7 bytes by removing some useless parentheses
-8 bytes, thanks @ovs (see comment below)

Try it online!

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Both @,&0 and the parentheses around -/~ can be removed. You might also want to look at an arithmetic based way to do ~:&0#"1 (setting values to zero would have the same effect as removing them) \$\endgroup\$
    – ovs
    Feb 27, 2022 at 9:24
  • \$\begingroup\$ @ovs Whoops, i got it, thanks! \$\endgroup\$
    – sinvec
    Feb 27, 2022 at 12:10
2
\$\begingroup\$

JavaScript (Node.js), 63 bytes

x=>x.map((r,i)=>r.map((c,j)=>v=c?Math.max(i-j,j-i,v):v),v=0)&&v

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES7),  58  55 bytes

m=>m.map(q=(r,y)=>r.map(v=>q=!v|(n=y*y--)<q?q:n))|q**.5

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 9 bytes

ĀDƶsøƶøαà

(Or ø‚Ā€ƶ`øαà as minor alternative.)

Try it online or verify all test cases.

Explanation:

Ā        # Transform each non-0 integer in the input-matrix to a 1
 D       # Duplicate this matrix of 0s/1s
  ƶ      # Multiply each inner value by its 1-based row-index
 s       # Swap so the matrix of 0s/1s is at the top again
  øƶø    # Do the same for the columns
         # (where `ø` is a zip/transpose, to swap rows/columns)
     α   # Take the absolute difference of the values at the same positions
      à  # Pop and push the flattened maximum
         # (which is output implicitly as result)
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Vyxal G, 7 bytes

vT:ẏ-ȧf

Try it Online! or Run all the test cases!

Port of Jelly answer.

How?

vT:ẏ-ȧf
vT      # Get the truthy indices of each
  :ẏ    # Duplicate and get length range [0, length)
    -ȧ  # Subtract the two and get the absolute values (implicit vectorization with both)
      f # Flatten
        # G flag takes the maximum of the top of the stack
Improve this answer
\$\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.