16
\$\begingroup\$

A Shift matrix is a binary matrix with one superdiagonal or subdiagonal formed by only ones, everything else is a zero.
A superdiagonal/subdiagonal is a diagonal parallel to the main diagonal, which is not the main diagonal, i.e. all entries \$a_{ij}\$ where \$i=j+k\$ and \$k \neq 0\$.
The main diagonal is defined to be all entries \$a_{ij}\$ where \$i=j\$.

Specs

  • The matrix is not guaranteed to be square and will consist of only zeros and ones
  • Take a nested list or a matrix as the input
  • Output a truthy/falsy result or use two distinct values to represent truthy and falsy results
  • This is , the shortest answer wins!

Examples

[[1]] -> 0

[[0, 1],
 [0, 0]] -> 1

[[0, 0, 0],
 [1, 0, 0],
 [0, 1, 0]] -> 1

[[0, 1, 0],
 [1, 0, 0],
 [0, 0, 0]] -> 0

[[0, 1, 0],
 [0, 0, 1]] -> 1

[[0, 0],
 [0, 0]] -> 0

[[0, 0, 0, 0],
 [1, 0, 0, 0],
 [0, 0, 0, 0],
 [0, 0, 1, 0]] -> 0

[[1, 1],
 [1, 1]] -> 0

[[0,1,0,0],
 [1,0,1,0],
 [0,1,0,1],
 [0,0,1,0]] -> 0

[[0,1,0],
 [1,0,0],
 [0,1,0]] -> 0

[[0,1,0],
 [0,0,1],
 [1,0,0]] -> 0

[[1,0,0],
 [0,1,0]] -> 0

[[0,0,0],
 [0,0,0],
 [0,0,0],
 [0,0,0],
 [0,0,0],
 [1,0,0]] -> 1

[[1,0,1],
 [0,1,0],
 [0,0,1]] -> 0

[[0,1,0],
 [1,0,0]] -> 0
\$\endgroup\$
12
  • 2
    \$\begingroup\$ Suggested test cases: [[1,1],[1,1]] -> 0 and [[0,1,0,0],[1,0,1,0],[0,1,0,1],[0,0,1,0]] -> 0. \$\endgroup\$ Jan 18, 2023 at 14:40
  • 4
    \$\begingroup\$ I suggest replacing "with ones only on one superdiagonal or subdiagonal" by "with one superdiagonal or subdiagonal formed by only ones". I interpreted it incorrectly until I reached the 7th test case \$\endgroup\$
    – Luis Mendo
    Jan 18, 2023 at 15:46
  • 1
    \$\begingroup\$ It seems to be "with one superdiagonal or subdiagonal formed by only ones and no other ones." from the last test case - is that correct? \$\endgroup\$ Jan 18, 2023 at 23:12
  • 1
    \$\begingroup\$ Suggested testcases: [[0,1,0],[0,0,1],[1,0,0]]->0, [[1,0,0],[0,1,0]]->0, [[0,0,0],[0,0,0],[0,0,0],[0,0,0],[0,0,0],[1,0,0]]->1, [[1,0,1],[0,1,0],[0,0,1]]->0 \$\endgroup\$
    – tsh
    Jan 19, 2023 at 2:19
  • 1
    \$\begingroup\$ I would say that your requirements would allow test case 8, 9 and 10 to be true. Nowhere you mention that the other cells need to be 0, just that (at least) one superdiagonal or subdiagonal needs to be formed by only ones \$\endgroup\$
    – Ivo
    Jan 19, 2023 at 7:35

12 Answers 12

6
\$\begingroup\$

J, 37 bytes

1=1#.([:(+./*[:*/%)/.|."1),_*<@0 1|:]

Try it online!

Thanks to AndrovT for catching a bug

  • ,<@0 1|:] Append , items along main diagonal (works for non-square) multiplied by infinity to...
  • ([:(+./*[:*/%)/.|."1) Product of reciprocals of every diagonal, multipled by "is there at least a single 1". This will return 1 for all ones, infinity for partial ones, and 0 for all zeros. To get the diagonals, we combine J's built-in for anti-diagonals /. with a flip about the y-axis |."1.
  • 1#. Sum of those catted lists
  • 1= Is the sum 1?
\$\endgroup\$
2
  • 1
    \$\begingroup\$ This doesn't work for [[0, 1, 0], [1, 0, 0], [0, 1, 0]] \$\endgroup\$
    – AndrovT
    Jan 18, 2023 at 19:30
  • \$\begingroup\$ @AndrovT Thanks. Fixed but it killed the golfiness.... \$\endgroup\$
    – Jonah
    Jan 18, 2023 at 20:06
6
\$\begingroup\$

Jelly, 11 bytes

ŒDµẒ¬ṛ¦ⱮJḊċ

A monadic Link that accepts a matrix of ones and zeros and yields 1 if it's a shift matrix or 0 otherwise.

Try it online! Or see the test-suite.

How?

Constructs all diagonalised representations of shift matrices of the same dimensions as the input and counts occurrences of a diagonalised version of the input.

ŒDµẒ¬ṛ¦ⱮJḊċ - Link: matrix of [0,1], M    e.g. [[0,1,0],[0,0,1],[0,0,1]]
ŒD          - diagonals (main first)           [[0,0,1],[1,1],[0],[0],[0,0]]
  µ         - start a new monadic chain - f(D=those diagonals)
   Ẓ        - is prime? (D) (used as a zero-all entries function)
        J   - (set the right argument to) range of length (D)
       Ɱ    - map with:
      ¦     -   sparse application (to elements of D)...
     ṛ      -   ...at indices: right argument (i.e. one of [1..length(D)])
    ¬       -   ...apply: logical NOT (making that single diagonal all ones)
         Ḋ  - dequeue (removing the only non-shift matrix (main diagonal one))
          ċ - count occurrences of (D)
\$\endgroup\$
6
\$\begingroup\$

JavaScript (Node.js), 59 bytes

m=>m.every((r,y)=>r.every((c,x)=>+m?x-y==m==c:c?m=x-y:1))*m

Try it online!

Output falsy (0, -0, NaN) if input is not a shift matrix, output truthy (\$k\$) otherwise.

\$\endgroup\$
5
\$\begingroup\$

Vyxal, 10 bytes

ÞD₌~aḢ~AẊ₃

Try it online or verify all test cases.

ÞD         # list of all diagonals
  ₌        # apply the next two elements in parallel:
   ~a      #   filter by Any
     Ḣ     #   remove head (removes the main diagonal)
      ~A   # filter by All
           # Now the stack has the the list of diagonals that have at least one 1
             and list of all sub/superdiagonals that don't contain 0
        Ẋ  # cartesian product
         ₃ # is length equal to 1?
\$\endgroup\$
1
  • \$\begingroup\$ woah, nice idea \$\endgroup\$
    – math scat
    Jan 18, 2023 at 20:40
5
\$\begingroup\$

MATL, 14 bytes

&fyh!dt&=bd1=v

Outputs a truthy or falsy column array.

Try it online! (includes truthy/falsy test; delete footer to see actual output). Or verify all test cases.

How it works

Consider [0 0 0 0; 1 0 0 0; 0 0 0 0; 0 0 1 0] as example input.

&f    % Implicit input. Two-output find: row and column indices of non-zeros
      % STACK: [2; 4], [1 ;3]
yh    % Duplicate from below. Concatenate horizontally
      % STACK: [2; 4], [1 2; 3 4]
!     % Transpose
      % STACK: [2; 4], [1 3; 2 4]
d     % Vertical onsecutive differences
      % STACK: [2; 4], [1 1] 
t&=   % Duplicate. All pairwise equality comparisons
      % STACK: [2; 4], [1 1], [1 1; 1 1]
bd    % Bubble up third-topmost entry. Consecutive differences
      % STACK: [1 1], [1 1; 1 1], 2
1=    % Equal to 1?, element-wise
      % STACK: [1 1], [1 1; 1 1], 0
v     % Concatenate vertically, converting to column vectors if non-matching sizes
      % STACK: [1; 1; 1; 1; 1; 1; 0]
\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js), 72 bytes

A=>A.map((B,i)=>B.map((C,j)=>N-=i*j?A[i-1][j-1]-C&&9:i-j?C:2*C),N=1)&&!N

Try it online!

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

05AB1E, 29 bytes

εI˜d·«NFÀ]øJ2мõK€SDPsOĀ+ćÌL¢J

Outputs a 05AB1E truthy/falsey result (only 1 is truthy in 05AB1E): 01 if truthy; anything else (e.g. 0000, 20, 11, 0100, etc.) if falsey.

Try it online or verify all test cases.

Explanation:

05AB1E lacks a builtin to get all (anti-)diagonals, so the first 18 bytes of the code is to do just that..

Step 1: Get a list of all diagonals, starting with the main diagonal:

ε       # Map over each row of the (implicit) input-matrix:
 I˜     #  Push the input-matrix again, and flatten it
   d    #  Transform every 0 to a 1 as well, so we have a list of 1s
    ·   #  Double each to a list of 2s
     «  #  Merge it to the current row
 NF     #  Loop the 0-based map-index amount of times:
   À    #   Rotate the row-list once towards the left
]       # Close both the inner loop and outer map
 ø      # Zip/transpose; swapping rows/columns
  J     # Join each inner row together
   2м   # Remove all 2s in every string
     õK # Remove all empty strings from the list
  €S    # Convert each inner string back to a list of digits

For a matrix [[a,b,c],[d,e,f],[g,h,i]], the order of the list of diagonals will be [[a,e,i],[b,f],[c],[g],[d,h]].

Try just step 1 online.

Step 2: Check whether it's a valid Shift Matrix, so there is exactly one diagonal consisting solely of 1s without any 1s in another diagonal, and it's not the first main diagonal:

D       # Duplicate the list of diagonals
 P      # Get the product of each, to check which diagonals consists solely of 1s
s       # Swap so the list of diagonals is at the top again
 OĀ     # Sum and Python-style truthify (!=0), to check which diagonals contain a 1
+       # Add the two list of checks together
ć       # Extract the head; push remainder-list and first item separately
 Ì      # Increase this first item (check of the main diagonal) by 2
  L     # Pop and push a list in the range [1,value]
   ¢    # Count for each value in this list how many times it occurs
    J   # Join these counts together
        # (after which the result is output implicitly)

Try both steps online, with added debug-lines.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ I believe I forgot to add the truthy/falsy result line, it's allowed. \$\endgroup\$
    – math scat
    Jan 18, 2023 at 15:40
  • \$\begingroup\$ @mathcat Thanks, modified my answer accordingly. :) \$\endgroup\$ Jan 18, 2023 at 16:06
  • \$\begingroup\$ @tsh Huh.. Why thought? The main diagonal of [[a,b,c],[d,e,f],[g,h,i],[j,k,l],[m,n,o],[p,q,r]] is [a,e,i], so the superdiagonal/subdiagonal are [b,f] and [d,h,l] respectively. \$\endgroup\$ Jan 19, 2023 at 7:49
  • \$\begingroup\$ @tsh Nvm, I misread the 'parallel' word in the challenge as adjacent to the main diagonal.. Also, the current test cases are anything but covering in that case. :/ I'll delete and try to fix it. \$\endgroup\$ Jan 19, 2023 at 7:54
  • \$\begingroup\$ @tsh Should be fixed at the cost of 11 bytes.. \$\endgroup\$ Jan 19, 2023 at 9:05
3
\$\begingroup\$

R, 76 69 66 bytes

Edit: -3 bytes thanks to pajonk

\(m)all(d<-diff(t(which(m>0,T))),d==max(dim(m)-sum(m))*sign(d[1]))

Attempt This Online!

\$\endgroup\$
3
  • \$\begingroup\$ -3 bytes? \$\endgroup\$
    – pajonk
    Jan 20, 2023 at 19:56
  • \$\begingroup\$ @pajonk - I'll take 1-byte for the in-line definition of d: thanks! Swapping the sum of m for the length of d fails for some cases, unfortunately: try it... \$\endgroup\$ Jan 20, 2023 at 20:13
  • \$\begingroup\$ @pajonk - sorry - re-read the spec and see that the matrix is all zeros & ones. Your suggestion is perfect: thanks again! \$\endgroup\$ Jan 20, 2023 at 20:16
2
\$\begingroup\$

Python, 138 bytes

lambda d:any(i for i in range(-len(d)-len(d[0]),len(d)+len(d[0]))if all(d[j][k]==(j-k==i)for j in range(len(d))for k in range(len(d[0]))))

Attempt This Online!

\$\endgroup\$
1
  • \$\begingroup\$ 120 \$\endgroup\$
    – naffetS
    Jan 18, 2023 at 21:54
2
\$\begingroup\$

PHP, 139 bytes

fn($m)=>$m[0][0]?!1:(count($f=array_merge(...array_map(fn($v)=>array_keys($v,1),$m)))>1?$f==range(min($f),max($f)):end($m)[0]||end($m[0]));

Try it online!

Ungolfed

fn($m) => 
  $m[0][0] ? !1 :
  (count($f = array_merge(...array_map(fn($v) => array_keys($v, 1), $m))) > 1
  ? $f == range(min($f), max($f))
  : end($m)[0] || end($m[0]));
\$\endgroup\$
4
  • \$\begingroup\$ I'm not very good at PHP, but this looks cool \$\endgroup\$
    – math scat
    Jan 18, 2023 at 21:26
  • 1
    \$\begingroup\$ You have an extra space after ? \$\endgroup\$
    – naffetS
    Jan 18, 2023 at 21:42
  • \$\begingroup\$ [[1,0,0],[0,1,0]] should be falsy. \$\endgroup\$
    – tsh
    Jan 19, 2023 at 2:24
  • \$\begingroup\$ Fixed the main diagonal being considered a true case \$\endgroup\$
    – dneustadt
    Jan 19, 2023 at 10:45
2
\$\begingroup\$

Julia 1.0, 118 bytes

using LinearAlgebra
~A=((m,n)=size(A);X=map(i->diag(A,i),1-m:n-1);!i=sum(all.(==(i),X));A[1]<1&&!1>0&&!0==length(X)-1)

Try it online!

The function ~A returns true if A[1,1] is not 1 (main diagonal check), one diagonal contains all 1's, and all but one diagonal contains all 0's. Otherwise, it returns false. The intermediate value X is a vector of all A's diagonals, and the intermediate function !i determines if all elements in a diagonal equal the value i.

Note: As in a somewhat related answer, LinearAlgebra is imported only for the function diag(A,k), which returns the kth diagonal of A. If the diagonal k doesn't exist, no error results, but an empty set is returned. If these are filtered out, the bounds don't need to be specified precisely; using the range -9:9 would work for all test cases and eliminate the need for calculating size(A).

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

Charcoal, 38 bytes

WS⊞υι≔ΣEυ⁻⌕Aι1κθ¿⌈θ¿⁼⌈θ⌊θ¬№ΣEυ⁻⌕Aι0κ⌈θ

Attempt This Online! Link is to verbose version of code. Takes input as a list of newline-terminated binary strings and outputs a Charcoal boolean i.e. - for a shift matrix, nothing if not. Explanation:

WS⊞υι

Input the matrix.

≔ΣEυ⁻⌕Aι1κθ

Find the diagonals of all of the 1s in the matrix.

¿⌈θ

If there is at least one 1 not on the main diagonal*, and ...

¿⁼⌈θ⌊θ

... if all of the 1s are on the same diagonal, ...

¬№ΣEυ⁻⌕Aι0κ⌈θ

... check whether there are any 0s on that diagonal.

*Strictly speaking this tests that either at least one 1 is above the diagonal or there are 1s that are only below the diagonal.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.