14
\$\begingroup\$

Related challenge

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 \$A\$ 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 0
3 4 5 0 0
0 6 0 7 0
0 0 8 9 1
0 0 0 2 3

this is the band:

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

The main diagonal (1 4 0 9 3) and the diagonals above it (2 5 7 1) and below it (3 6 8 2) 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.)

One nice feature of band matrices is that they can be stored more efficiently: only the elements in the band need to be stored. For example, our 5-by-5 matrix above can instead be stored as a 5-by-3 matrix, where each column represents one diagonal of the original matrix:

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

Note how the shorter diagonals are padded with zeros: diagonals below the main diagonal are padded at the beginning, while diagonals above the main diagonal are padded at the end.

In this challenge, the band to be stored must be symmetrical about the main diagonal. For example, this matrix:

2 3 4 0 0 0
1 2 3 4 0 0
0 1 2 3 4 0
0 0 1 2 3 4
0 0 0 1 2 3
0 0 0 0 1 2

has this band:

2 3 4
1 2 3 4
0 1 2 3 4
  0 1 2 3 4
    0 1 2 3
      0 1 2

and so it is stored as:

0 0 2 3 4
0 1 2 3 4
0 1 2 3 4
0 1 2 3 4
0 1 2 3 0
0 1 2 0 0

In this case, one of the diagonals to be stored consists entirely of 0s, but that diagonal must be included because it is symmetric to the nonzero diagonal consisting of 4s. (This rule means the output matrix will always have an odd number of columns.)

Challenge

Given an \$N\$-by-\$N\$ band matrix containing nonnegative integers, output/return its rearranged version.

If \$B\$ is the number of diagonals in the band, the resulting matrix will be \$N\$ rows by \$B\$ columns. If you prefer, you may output the result matrix transposed (that is, a matrix of \$B\$ rows by \$N\$ columns).

You may assume that \$B < N\$. In other words, no input that would generate output the same size or larger needs to be handled.

The matrix will always have at least one nonzero entry.

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

Test cases

1 0
0 1
=>
1
1

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

0  0  0
0  0  0
0  0 42
=>
 0
 0
42

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

1 2 0 0 0
3 4 5 0 0
0 6 0 7 0
0 0 8 9 1
0 0 0 2 3
=>
0 1 2
3 4 5
6 0 7
8 9 1
2 3 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 1
0 0 0
0 0 0
0 0 0
0 0 0

2 3 4 0 0 0
1 2 3 4 0 0
0 1 2 3 4 0
0 0 1 2 3 4
0 0 0 1 2 3
0 0 0 0 1 2
=>
0 0 2 3 4
0 1 2 3 4
0 1 2 3 4
0 1 2 3 4
0 1 2 3 0
0 1 2 0 0
\$\endgroup\$
0

10 Answers 10

7
\$\begingroup\$

R, 94 84 83 78 bytes

Edit: -5 bytes thanks to Giuseppe

function(m,b=max(abs(row(m)-col(m))*!!m))matrix(c(!1:b,m),dim(m)+1)[-b:b+b+1,]

Try it online!

(of which 38 bytes are shamefully copied from Giuseppe's method to calculate the bandwidth: upvote that!)

As noticed by @pajonk, there are 2 'rearranged versions' of any square 'band matrix', depending on how 'rows' and 'columns' are assigned: add +3 bytes (corresponding to transposing the input matrix) to flip this.

How?

For an nxn matrix, we first calculate the bandwidth b and prepend b zeros to the front of the matrix elements as a 1d-vector. We then split this up again into a matrix with n+1 rows: this aligns the diagonals, placing the 'bands' in the first 2b+1 rows. The 'rearranged version' is now just the 2b+1xn submatrix of this.

\$\endgroup\$
8
  • \$\begingroup\$ I guess you take your input transposed, so the results are weird after correcting this Try it online! I hope this is fine, but I think a fix would just require some work on indices. \$\endgroup\$
    – pajonk
    May 10, 2022 at 19:40
  • 1
    \$\begingroup\$ @Arnauld - I think that your example has B>N, which isn't an allowed input, right? \$\endgroup\$ May 10, 2022 at 21:54
  • \$\begingroup\$ Oh I see. I overlooked that part of the spec. \$\endgroup\$
    – Arnauld
    May 10, 2022 at 21:56
  • 1
    \$\begingroup\$ @DominicvanEssen Yeah, that's what I meant with "I hope this is fine". My point was just to avoid confusion when someone goes with the standard representation (printing the matrix vs test-cases in question). \$\endgroup\$
    – pajonk
    May 11, 2022 at 4:20
  • 1
    \$\begingroup\$ what is the [...,-n] for? \$b\$ is at most \$n-1\$ since \$M\$ is square, so you'll have at most \$n^2+n-1\$ elements in your matrix (before recycling), hence when you add a row you will still be short of it being an \$(n+1)\times (n+1)\$ matrix? Or is there some other consideration I'm missing. \$\endgroup\$
    – Giuseppe
    May 11, 2022 at 13:26
4
\$\begingroup\$

J, 66 53 bytes

#{.#|.-@$(#"1~0{](]#~[-:"2*"2)#\>/#\|@-/#\)@|.]{.~3*$

Try it online!

Basic Strategy

We want to avoid special casing the "pad the partial top rows on the left", and "pad the partial bottom rows on the right". If we extend the input "offscreen" in both directions, a solution which automatically handles these cases falls out for free.

Explanation

Consider:

1 2 0 0
3 4 5 0
0 6 0 7
0 0 8 9
  • ]{.~3*$ Extend the input so its shape is 3 times its original shape:

    1 2 0 0 0 0 0 0 0 0 0 0
    3 4 5 0 0 0 0 0 0 0 0 0
    0 6 0 7 0 0 0 0 0 0 0 0
    0 0 8 9 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
    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 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0
    
  • -@$(...)@|. And rotate it so the original is centered:

    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 0 0 0 0
    0 0 0 0 1 2 0 0 0 0 0 0
    0 0 0 0 3 4 5 0 0 0 0 0
    0 0 0 0 0 6 0 7 0 0 0 0
    0 0 0 0 0 0 8 9 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 0 0 0 0 0 0 0 0
    
  • #\>/#\|@-/#\ Generate all possible bands:

    1 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 1 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 1 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 1 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 1 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 1 0
    0 0 0 0 0 0 0 0 0 0 0 1
    
    1 1 0 0 0 0 0 0 0 0 0 0
    1 1 1 0 0 0 0 0 0 0 0 0
    0 1 1 1 0 0 0 0 0 0 0 0
    0 0 1 1 1 0 0 0 0 0 0 0
    0 0 0 1 1 1 0 0 0 0 0 0
    0 0 0 0 1 1 1 0 0 0 0 0
    0 0 0 0 0 1 1 1 0 0 0 0
    0 0 0 0 0 0 1 1 1 0 0 0
    0 0 0 0 0 0 0 1 1 1 0 0
    0 0 0 0 0 0 0 0 1 1 1 0
    0 0 0 0 0 0 0 0 0 1 1 1
    0 0 0 0 0 0 0 0 0 0 1 1
    
    1 1 1 0 0 0 0 0 0 0 0 0
    1 1 1 1 0 0 0 0 0 0 0 0
    1 1 1 1 1 0 0 0 0 0 0 0
    0 1 1 1 1 1 0 0 0 0 0 0
    0 0 1 1 1 1 1 0 0 0 0 0
    0 0 0 1 1 1 1 1 0 0 0 0
    0 0 0 0 1 1 1 1 1 0 0 0
    0 0 0 0 0 1 1 1 1 1 0 0
    0 0 0 0 0 0 1 1 1 1 1 0
    0 0 0 0 0 0 0 1 1 1 1 1
    0 0 0 0 0 0 0 0 1 1 1 1
    0 0 0 0 0 0 0 0 0 1 1 1
    
    ... etc
    
  • ](]#~[-:"2*"2) Filter only those that, when multiplied elementwise with the extended input, return the input unchanged:

    1 1 0 0 0 0 0 0 0 0 0 0
    1 1 1 0 0 0 0 0 0 0 0 0
    0 1 1 1 0 0 0 0 0 0 0 0
    0 0 1 1 1 0 0 0 0 0 0 0
    0 0 0 1 1 1 0 0 0 0 0 0
    0 0 0 0 1 1 1 0 0 0 0 0
    0 0 0 0 0 1 1 1 0 0 0 0
    0 0 0 0 0 0 1 1 1 0 0 0
    0 0 0 0 0 0 0 1 1 1 0 0
    0 0 0 0 0 0 0 0 1 1 1 0
    0 0 0 0 0 0 0 0 0 1 1 1
    0 0 0 0 0 0 0 0 0 0 1 1
    
    1 1 1 0 0 0 0 0 0 0 0 0
    1 1 1 1 0 0 0 0 0 0 0 0
    1 1 1 1 1 0 0 0 0 0 0 0
    0 1 1 1 1 1 0 0 0 0 0 0
    0 0 1 1 1 1 1 0 0 0 0 0
    0 0 0 1 1 1 1 1 0 0 0 0
    0 0 0 0 1 1 1 1 1 0 0 0
    0 0 0 0 0 1 1 1 1 1 0 0
    0 0 0 0 0 0 1 1 1 1 1 0
    0 0 0 0 0 0 0 1 1 1 1 1
    0 0 0 0 0 0 0 0 1 1 1 1
    0 0 0 0 0 0 0 0 0 1 1 1
    
    ...etc
    
  • 0{ Take the first:

    1 1 0 0 0 0 0 0 0 0 0 0
    1 1 1 0 0 0 0 0 0 0 0 0
    0 1 1 1 0 0 0 0 0 0 0 0
    0 0 1 1 1 0 0 0 0 0 0 0
    0 0 0 1 1 1 0 0 0 0 0 0
    0 0 0 0 1 1 1 0 0 0 0 0
    0 0 0 0 0 1 1 1 0 0 0 0
    0 0 0 0 0 0 1 1 1 0 0 0
    0 0 0 0 0 0 0 1 1 1 0 0
    0 0 0 0 0 0 0 0 1 1 1 0
    0 0 0 0 0 0 0 0 0 1 1 1
    0 0 0 0 0 0 0 0 0 0 1 1
    
  • #"1~ Use these masks to filter the extended input, row-wise:

    0 0 0
    0 0 0
    0 0 0
    0 0 0
    0 1 2
    3 4 5
    6 0 7
    8 9 0
    0 0 0
    0 0 0
    0 0 0
    0 0 0
    
  • #{.#|. To extract only the middle portion that is our final answer, rotate left the length of the original input, and then take the length of the original input:

    0 1 2
    3 4 5
    6 0 7
    8 9 0
    
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 28 bytes

≔⌈Eθ⌈Eι∧λ↔⁻μκηIEθE⁺κ…·±ηη§ιλ

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

≔⌈Eθ⌈Eι∧λ↔⁻μκη

Calculate the width of the band.

IEθE⁺κ…·±ηη§ιλ

Output the relevant cyclic diagonals.

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

05AB1E, 24 20 bytes

ĀDƶsøƶøαàUεNX-._X·>£

-4 bytes thanks to @Neil.

Try it online or verify all test cases.

Explanation:

Step 1: Get the bandwidth of the input-matrix, using the same exact code as my answer in the related challenge:

Ā        # Transform each non-0 integer in the (implicit) 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

Step 2: Leave the actual diagonal band matrix using the \$bandwidth\times2+1\$, and output it as result:

       U # Pop and store the bandwidth in variable `X`
ε        # Map over the rows of the (implicit) input-matrix
 NX-     #  Push N-X, where `N` is the 0-based map-index
    ._   #  Rotate the current row that many times towards the left,
         #  where negative values will rotate towards the right instead
 X·>     #  Push 2X+1, where `X` is still the bandwidth
    £    #  Leave that many leading items from the current rotated row
         # (after which the mapped matrix is output implicitly as result)
\$\endgroup\$
3
  • \$\begingroup\$ εXÅ0.øN._X·>£ saves a byte. \$\endgroup\$
    – Neil
    May 11, 2022 at 7:16
  • 1
    \$\begingroup\$ Actually, since B<N, you can use εNX-._X·>£ to save four bytes. \$\endgroup\$
    – Neil
    May 11, 2022 at 7:30
  • \$\begingroup\$ @Neil Smart! Thanks for -4. :) \$\endgroup\$ May 11, 2022 at 7:45
3
\$\begingroup\$

Vyxal, 37 26 18 17 bytes

vT:ẏεfG£¨2Ǔ¥ǔ¥d›Ẏ

Try it Online!

How?

vT:ẏεfG£¨2Ǔ¥ǔ¥d›Ẏ
vT                  # For each row, get the indices of truthy elements
  :ẏ                # Duplicate and push a range in [0..length of list)
    ε               # Vectorizing absolute difference
     fG             # Get the flattened maximum difference
       £            # Store in the register
        ¨2          # Open dyadic map lambda on (implicit) input, pushing both item and index
          Ǔ         # Rotate row left by index
           ¥ǔ       # Rotate row right by the contents of the register
             ¥d›    # Push 2*register+1
                Ẏ   # Leave that many leading items in the current rotated row

-10 bytes thanks to Neil, and another -9 from myself

\$\endgroup\$
3
  • \$\begingroup\$ ¨2$¥0ẋ:∇pp$Ǔ¥d1+Ẏ saves three bytes. \$\endgroup\$
    – Neil
    May 11, 2022 at 7:28
  • 1
    \$\begingroup\$ Actually, since B<N, you can use ¨2Ǔ¥ǔ¥d1+Ẏ to save ten bytes. \$\endgroup\$
    – Neil
    May 11, 2022 at 7:42
  • \$\begingroup\$ Oh, I see now, that's a ... and here was me thinking it was a > and wondering why it wasn't incrementing... \$\endgroup\$
    – Neil
    May 12, 2022 at 0:29
1
\$\begingroup\$

PARI/GP, 89 bytes

m->a=0;matrix(#m,,i,j,m[i,j]&&a=max(a,abs(i-j)));matrix(#m,2*a+1,i,j,m[i,(i+j-a-2)%#m+1])

Attempt This Online!

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

Python NumPy, 126 bytes

def f(*a):x=triu(tri(l:=len(a),2*l-1,l-1))[::-1];x[x>0]=r_[a];j=min(where(x+x[:,::-1])[1]);return x[:,j:-j]
from numpy import*

Attempt This Online!

Rather opportunistically takes the splatted array (this saves three bytes) as input.

How?

Uses the properties of masked assignment to map all diagonals by the deceptively short statement x[x>0]=r_[a]. The actual work is in setting up the initial mask x. And in trimming excess columns afterwards.

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

JavaScript (ES6),  118  116 bytes

f=(m,k,q=m.map(_=>0),M=m.map((r,y)=>q.concat(r,q[S='slice'](~y),0)[S](y+k,~k)))=>M.some(r=>r[0]|r[S](-1))?M:f(m,-~k)

Try it online!

How?

Given a matrix \$m\$ of size \$N\times N\$, we build a vector \$q\$ of size \$N\$ filled with \$0\$'s:

q = m.map(_ => 0)

For each row \$r\$ at position \$y\$ (0-indexed) in \$m\$, we use \$q\$ to append \$N\$ leading \$0\$'s and \$y+2\$ trailing \$0\$'s:

q.concat(r, q.slice(~y), 0)

For instance:

[ 1 2 3 ] --> [ 0 0 0 1 2 3 0 0 ]
[ 4 5 6 ] --> [ 0 0 0 4 5 6 0 0 0 ]
[ 7 8 9 ] --> [ 0 0 0 7 8 9 0 0 0 0 ]

Starting with \$k=0\$, we then remove \$y+k\$ leading \$0\$'s and \$k+1\$ trailing \$0\$'s:

.slice(y + k, ~k)

Which gives a new matrix \$M_k\$ of width \$2(N-k)+1\$:

[ 0 0 0 1 2 3 0 0 ]     --> [ 0 0 0 1 2 3 0 ]
[ 0 0 0 4 5 6 0 0 0 ]   --> [ 0 0 4 5 6 0 0 ]
[ 0 0 0 7 8 9 0 0 0 0 ] --> [ 0 7 8 9 0 0 0 ]

We increment \$k\$ and repeat the whole process on the original matrix until there's at least one non-zero value in either the first or the last column of \$M_k\$:

M.some(r => r[0] | r.slice(-1))

NB: r.slice(-1) returns an atomic array which is coerced to an integer by the bitwise operator.

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

Python, 203 193 bytes

-10 bytes thanks to @Steffan

def f(m):R=range;n=len(m);r=R(n);d=[*map(any,c:=[[m[i][i+d]if i+d in r else 0for i in r]for d in R(-n,n+1)])];k=min(d.index(1),d[::-1].index(1));return[[c[i][j]for i in R(k,n+n-k+1)]for j in r]

Attempt This Online!

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

APL+WIN, 64 bytes

Prompts for input matrix. Index origin = 0

b←⌈/⌈/¨+/¨^\¨b(⌽b←×0 1↓a←(⍳n←¯1↑r←↑⍴m)⌽m←⎕)⋄((r,-b)↑a),(r,1+b)↑a

Try it online! Thanks to Dyalog Classic

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