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\$ Commented Feb 27, 2022 at 14:35
  • \$\begingroup\$ @YSC Hmm, what definition would you propose? \$\endgroup\$ Commented 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\$ Commented 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\$ Commented 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\$ Commented 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\$ Commented Feb 27, 2022 at 17:47
  • \$\begingroup\$ @Giuseppe Nice, thanks! \$\endgroup\$ Commented Feb 27, 2022 at 22:54
  • 1
    \$\begingroup\$ 38 bytes \$\endgroup\$ Commented 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\$ Commented 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\$ Commented 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\$ Commented 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\$ Commented Feb 27, 2022 at 9:24
  • \$\begingroup\$ @ovs Whoops, i got it, thanks! \$\endgroup\$ Commented 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\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.