17
\$\begingroup\$

Challenge:

Given a matrix input, determine the amount of diagonals and anti-diagonals with duplicated numbers.
So if we have a matrix like this:

[[aa,ab,ac,ad,ae,af],
 [ba,bb,bc,bd,be,bf],
 [ca,cb,cc,cd,ce,cf],
 [da,db,dc,dd,de,df]]

All diagonals and anti-diagonals would be:

[[aa],[ab,ba],[ac,bb,ca],[ad,bc,cb,da],[ae,bd,cc,db],[af,be,cd,dc],[bf,ce,dd],[cf,de],[df],
 [af],[ae,bf],[ad,be,cf],[ac,bd,ce,df],[ab,bc,cd,de],[aa,bb,cc,dd],[ba,cb,dc],[ca,db],[da]]

Example:

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

All diagonals and anti-diagonals would be:

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

Removing all diagonals and anti-diagonals only containing unique numbers:

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

So the output is the amount of diagonals and anti-diagonals containing duplicated numbers:

6

Challenge rules:

  • If the input matrix is empty, contains only 1 number, or contains only unique numbers across the entire matrix, the output is always 0.
  • Input is guaranteed to only contain positive digits [1,9] (unless it's completely empty).
  • The matrix will always be rectangular (i.e. all the rows are the same length).
  • I/O is flexible. Input can be taken as a list of lists of integers, or 2D array of integers, or a Matrix-object, as a string, etc. etc. You are also allowed to take one or both of the dimensions of the matrix as additional input if it would save bytes in your language of choice.

General rules:

  • This is , so shortest answer in bytes wins.
    Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
  • Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
  • Default Loopholes are forbidden.
  • If possible, please add a link with a test for your code (i.e. TIO).
  • Also, adding an explanation for your answer is highly recommended.

Test cases:

Input:                     Output:

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

[[]]                       0

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

[[1,1],                    2
 [1,1]]

[[9,9,9],                  6
 [9,9,9],
 [9,9,9]]

[[7,7,7,7],                8
 [7,7,7,7],
 [7,7,7,7]]

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

[[1,8,4,2,9,4,4,4],        12
 [5,1,2,7,7,4,2,3],
 [1,4,5,2,4,2,3,8],
 [8,5,4,2,3,4,1,5]]

[[1,2,3,4],                4
 [5,6,6,7],
 [8,6,6,9],
 [8,7,6,5]]
\$\endgroup\$

14 Answers 14

4
\$\begingroup\$

Jelly, 10 bytes

ŒD;ŒdQƑÐḟL

Try it online! or Check out the test suite!

Alternatives:

ŒD;ŒdQƑ€¬S
ŒD;ŒdQƑ€ċ0

How it works?

ŒD;ŒdQƑÐḟL – Monadic link / Full program.
  ;        – Join:
ŒD           – The diagonals
             with
   Œd        – The anti-diagonals.
       Ðḟ  – Discard the lists that are not:
     QƑ      – Invariant under deduplication.
         L – Length (count them).
\$\endgroup\$
10
\$\begingroup\$

R, 92 86 82 78 bytes

function(m,x=row(m),y=col(m),`|`=split,`^`=Map)sum(max^table^c(m|x-y,m|x+y)>1)

Try it online!

Explanation

First, we declare additional variables \$x\$ and \$y\$ that stand for row and column indices, respectively. Then we can delineate the diagonals and anti-diagonals by taking their difference and sum. E.g., for a 4x4 matrix:

\$x-y\$ gives:

0 -1 -2 -3 1 0 -1 -2 2 1 0 -1 3 2 1 0

\$x+y\$ gives:

2 3 4 5 3 4 5 6 4 5 6 7 5 6 7 8

Now split(m, x-y) and split(m, x+y) produce the actual lists of diagonals and anti-diagonals, which we join together.

Finally, we count the entries of the resulting list where duplicates are present.

Thanks for bytes saved:

-4 by CriminallyVulgar
-4 by digEmAll

\$\endgroup\$
  • 1
    \$\begingroup\$ Guess I can add row and col to my list of 'extremely situational functions'. Really clever solution. \$\endgroup\$ – CriminallyVulgar Jan 25 at 14:03
  • 1
    \$\begingroup\$ I think you can move the c(m|x-y,m|x+y) straight into the sapply call, remove the l= part. I don't see any failed tests. Try it online! \$\endgroup\$ – CriminallyVulgar Jan 25 at 14:11
  • \$\begingroup\$ Yep, that's correct, I just missed that after my first golf, there was only a single l instance remaining. \$\endgroup\$ – Kirill L. Jan 25 at 14:17
  • 1
    \$\begingroup\$ They must have added the row and column functions to R this morning, because I've never heard of them. \$\endgroup\$ – ngm Jan 25 at 15:05
5
\$\begingroup\$

J, 21 20 bytes

-1 byte thanks to Jonah!

1#.|.,&((~:&#~.)/.)]

Try it online!

Explanation:

1#.                   find the sum of the  
     ,                concatenation of
       (          )   the result of the verb in the parentheses applied to
                   ]  the input
      &               and
   |.                 the reversed input
        (      )/.    for each diagonal
         ~:&#~.       check if all elements are unique and negate the result 
\$\endgroup\$
  • 1
    \$\begingroup\$ it's kind of crazy that you can't do better than (-.@-:~.) for "the unique items don't match" in J but i've encountered this many times too and i don't think you can... we have = and ~:, on one hand, and -: and <this is missing>. \$\endgroup\$ – Jonah Jan 25 at 18:23
  • \$\begingroup\$ Actually, managed to shave 1 more byte off: 1#.|.,&((~:&#~.)/.)]. Try it online! \$\endgroup\$ – Jonah Jan 25 at 23:40
  • \$\begingroup\$ @Jonah: cool use of &, thanks! \$\endgroup\$ – Galen Ivanov Jan 26 at 7:46
5
\$\begingroup\$

Japt, 31 bytes

ËcUî
ËéEÃÕc¡XéYnÃÕ mf fÊk_eZâÃl

Try all test cases

Explanation:

Ëc                            #Pad each row...
  Uî                          #With a number of 0s equal to the number of rows

ËéEÃÕ                         #Get the anti-diagonals:
ËéEÃ                          # Rotate each row right a number of times equal to the row's index
    Õ                         # Get the resulting columns
     c                        #Add to that...
      ¡XéYnÃÕ                 #The diagonals:
      ¡XéYnà                  # Rotate each row left a number of times equal to the row's index
            Õ                 # Get the resulting columns
              mf              #Remove the 0s from each diagonal
                 fÊ           #Remove the all-0 diagonals
                   k_   Ã     #Remove the ones where:
                     eZâ      # The list contains no duplicates
                         l    #Return the number of remaining diagonals

I also tried a version based on Kirill L.'s Haskell answer, but couldn't find a good way to "group by a function of the X and Y indices" and the alternative I found wasn't good enough.

\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6),  107 105 101  98 bytes

f=(m,d=s=1)=>(m+0)[s-=~d/2]?m.some(o=(r,y)=>!r.every((v,x)=>x+d*y+m.length-s?1:o[v]^=1))+f(m,-d):0

Try it online!

Note

The way this code is golfed, the anti-diagonal consisting of the sole bottom-left cell is never tested. That's OK because it can't possibly contain duplicated values.

Commented

f = (                    // f = recursive function taking:
  m,                     //   m[] = input matrix
  d =                    //   d   = direction (1 for anti-diagonal or -1 for diagonal)
  s = 1                  //   s   = expected diagonal ID, which is defined as either the sum
) =>                     //         or the difference of x and y + the length of a row
  (m + 0)[               //
    s -= ~d / 2          // increment s if d = -1 or leave it unchanged otherwise
  ] ?                    // if s is less than twice the total number of cells:
    m.some(o =           //   o = object used to store encountered values in this diagonal
    (r, y) =>            //   for each row r[] at position y in m[]:
      !r.every((v, x) => //     for each cell of value v at position x in r[]:
        x + d * y +      //       x + d * y + m.length is the ID of the diagonal
        m.length - s ?   //       if it's not equal to the one we're looking for:
          1              //         yield 1
        :                //       else:
          o[v] ^= 1      //         toggle o[v]; if it's equal to 0, v is a duplicate and
                         //         every() fails which -- in turn -- makes some() succeed
      )                  //     end of every()
    )                    //   end of some()
    + f(m, -d)           //   add the result of a recursive call in the opposite direction
  :                      // else:
    0                    //   stop recursion
\$\endgroup\$
4
\$\begingroup\$

05AB1E, 25 bytes

í‚εεygÅ0«NFÁ]€ø`«ʒ0KDÙÊ}g

Try it online! or as a Test Suite

Explanation

í                          # reverse each row in input
 ‚                         # and pair with the input
  ε                        # for each matrix
   ε                       # for each row in the matrix
    ygÅ0«                  # append len(row) zeroes
         NFÁ               # and rotate it index(row) elements to the right
            ]              # end loops
             €ø            # transpose each matrix
               `«          # append them together
                 ʒ     }   # filter, keep only rows that
                  0K       # when zeroes are removed
                    DÙÊ    # are not equal to themselves without duplicate values                           
                        g  # push length of the result

I feel like I've missed something here.
Need to try and golf this more later.

\$\endgroup\$
  • 1
    \$\begingroup\$ Doesn't help at all, but rotate N left would be N._ now. So í‚εεygÅ0«N._] also works. Can also remove the flatten with this new change... still no byte savings though: í‚vyεygÅ0«N._}ø}«ʒ0KDÙÊ}g \$\endgroup\$ – Magic Octopus Urn Jan 29 at 19:45
  • 1
    \$\begingroup\$ @MagicOctopusUrn: Interesting. I had missed that command. Only a left though. Thats weird. \$\endgroup\$ – Emigna Jan 29 at 21:24
  • 1
    \$\begingroup\$ @Emigna You can go right with N(._ I guess, but your NFÁ} is the same length, and even shorter in this case due to ] closing the loop and maps simultaneously. Overall the use of ._ is only useful when going left to save 1 byte, in comparison to NFÀ}. \$\endgroup\$ – Kevin Cruijssen Jan 31 at 8:26
  • \$\begingroup\$ @KevinCruijssen: Ah, cool. Although as you say, not very useful. \$\endgroup\$ – Emigna Jan 31 at 8:59
3
\$\begingroup\$

Python 2, 144 136 bytes

lambda m:sum(l(set(d))<l(d)for d in[[r[i*x+o]for i,r in enumerate(m)if-1<i*x+o<l(r)]for o in range(-l(`m`),l(`m`))for x in[-1,1]])
l=len

Try it online!

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

Octave, 98 bytes

@(A)nnz([(q=@(Q)arrayfun(@(n)nnz(z=diag(Q,n))-nnz(unique(z)),-([m,n]=size(Q)):n))(A),q(rot90(A))])

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Are arrays indeed fun? ;p \$\endgroup\$ – Kevin Cruijssen Jan 25 at 14:28
  • \$\begingroup\$ And thanks for preparing the test cases in Octave format! \$\endgroup\$ – Luis Mendo Jan 26 at 1:05
  • 2
    \$\begingroup\$ @KevinCruijssen Not just arrays! You can have cellfun too, and for the masochistic, structfun as well. In Octave, it's either a for-loop or having fun! \$\endgroup\$ – Sanchises Jan 26 at 7:06
  • \$\begingroup\$ And don’t forget b-sx-fun! \$\endgroup\$ – Luis Mendo Jan 26 at 10:24
3
\$\begingroup\$

Haskell, 118 112 bytes

import Data.List
r#(a:b)=sum[1|(/=)=<<nub$[h|h:_<-a:r]]+[t|_:t<-a:r]#b
[]#_=0
a#_=a#[[]]
h x=[]#x+[]#(reverse x)

Try it online!

r#(a:b)                      -- function '#' calculates the ant-diagonals of a matrix
                             -- where 'a' is the first row and 'b' all the others
                             -- as we recursively walk down the rows of the matrix,
                             -- 'r' holds the rows from before with the respective
                             -- head dropped
                             --
          [h|h:_<-a:r]       -- if the heads of the the current row and the rows
                             -- before
       (/=)=<<nub$           -- contain duplicates
    [1|                ]     -- make a singleton list [1] (else the empty list)
 sum                         -- and take the sum thereof
      +                      -- and add
             #               -- a recursive call with
 [t|_:t<-a:r]                -- the tails of the current row and the rows before
              b              -- and the rows below
                             --
[]#_=0                       -- base case if there aren't any tails anymore, return 0
a#_=a#[[]]                   -- if there are tails, but no further rows below,
                             -- continue with tails

h x=[]#x+[]#(reverse x)      -- main function, call '#' with input matrix 'x'
                             -- and the reverse of it to get the number of diagonals
                             -- and anti-diagonals. Recursion starts with no
                             -- rows before the 1st row.

-- example trace of function '#'
-- input matrix:
--   [[1,2,3,4],
--    [5,6,7,8],
--    [9,9,9,9]]
--
--  | r         a          b              a:r          heads   tails (r of next call)
-- -+----------------------------------------------------------------------------------
-- 1| []        [1,2,3,4]  [[5,6,7,8],    [[1,2,3,4]]  [1]     [[2,3,4]]
--  |                       [9,9,9,9]]
--  | 
-- 2| [[2,3,4]]  [5,6,7,8]  [[9,9,9,9]]   [[5,6,7,8],  [5,2]   [[6,7,8],
--  |                                      [2,3,4  ]]           [3,4  ]]
--  |
-- 3| [[6,7,8],  [9,9,9,9]  []            [[9,9,9,9],  [9,6,3] [[9,9,9],
--  |  [3,4  ]]                            [6,7,8  ],           [7,8  ]
--  |                                      [3,4    ],           [4    ]
--  |
--  | ....
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 61 56 53 bytes

F²FLθFL§θ⁰F⟦⁻κ×⊖⊗ιλ⟧⊞υ⊞O⎇∧λ﹪⁺μιLθ⊟υ⟦⟧§§θμλILΦυ⊙ι‹⌕ιλμ

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

F²

Loop over forward and reverse diagonals; i=0 represents forward diagonals while i=1 represents reverse diagonals.

FLθ

Loop over each row index. This represents the index of the start of the diagonal.

FL§θ⁰«

Loop over each column index.

F⟦⁻κ×⊖⊗ιλ⟧

Calculate the row index of the diagonal at this column index. I use a for loop over a single-element array instead of an assignment as this avoids having to wrap the assignment into a block with the following statement, thus saving a byte.

⎇∧λ﹪⁺μιLθ

Check whether this is the first column or the diagonal is about to wrap around between bottom and top.

⊟υ

If it isn't then pop the last list from the list of lists.

⟦⟧

if it is then start a new empty list.

⊞O...§§θμλ

Add the current diagonal entry to that list.

⊞υ

And push that list (back) to the list of lists.

ILΦυ⊙ι‹⌕ιλμ

Count the number of lists that contain duplicates.

Let's take an example when i=0 and k=1. This means that we've already collected two diagonals, [[1,1,5,2],[9,4,3,5]]. Here's our input:

 1 8 4 2 9 4 4 4
[5]1 2 7 7 4 2 3
 1 4 5 2 4 2 3 8
 8 5 4 2 3 4 1 5

We then loop l from 0 to 7. This advances both the row and column by 1 each time:

 1 8 4 2 9 4 4 4
[5]1 2 7 7 4 2 3
 1[4]5 2 4 2 3 8
 8 5[4]2 3 4 1 5

The list is now [[1,1,5,2],[9,4,3,5],[5,4,4]]. However when l is 3, we have k+l=4, a multiple of the height of the array. This means that we need to start a new list: [[1,1,5,2],[9,4,3,5],[5,4,4],[]]. We then continue to collect diagonal elements:

 1 8 4[2]9 4 4 4
[5]1 2 7[7]4 2 3
 1[4]5 2 4[2]3 8
 8 5[4]2 3 4[1]5

The list is now [[1,1,5,2],[9,4,3,5],[5,4,4],[2,7,2,1]]. Now when l is 7, we have k+l=8, another multiple of the height of the array. This means that we need to start a new list, which ends up with the last element of that diagonal: [[1,1,5,2],[9,4,3,5],[5,4,4],[2,7,2,1],[4]].

 1 8 4[2]9 4 4[4]
[5]1 2 7[7]4 2 3
 1[4]5 2 4[2]3 8
 8 5[4]2 3 4[1]5

By collecting wrapping diagonals starting at the first element of each row we eventually accumulate all of the diagonals of the array.

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

Wolfram Language (Mathematica), 99 98 96 94 83 bytes

Count[DuplicateFreeQ@Diagonal[#,i]~Table~{i,-t,t=#~Total~2}&/@{#,Reverse@#},1<0,2]&

Try it online!

  • Function[a,a~Diagonal~#&/@Range[t=-#~Total~2,-t]] gets all diagonals of a-- which works because #~Total~2 is larger than any dimension of a.
\$\endgroup\$
1
\$\begingroup\$

APL+WIN, 69 bytes

Prompts for a 2d matrix of the form 4 6⍴1 2 1 2 1 2 1 2 3 4 5 6 6 5 4 3 2 1 2 1 2 1 2 1

This yields:

1 2 1 2 1 2
1 2 3 4 5 6
6 5 4 3 2 1
2 1 2 1 2 1

+/~(v⍳¨v)≡¨⍳¨⍴¨v←(v←⊂[1](⌽0,⍳1↓n)⌽(n⍴0),m,((n←0 ¯1+↑⍴m)⍴0),⌽m←⎕)~¨0

Try it online! Courtesy of Dyalog Classic

Explanation:

(⌽0,⍳1↓n)⌽(n⍴0),m pad m with zeros to isolate diagonals

((n←0 ¯1+↑⍴m)⍴0),⌽m pad rotated m with zeros to isolate anti-diagonals

Yields:

1 2 1 2 1 2 0 0 0 2 1 2 1 2 1 0 0 0
0 1 2 3 4 5 6 0 0 0 6 5 4 3 2 1 0 0
0 0 6 5 4 3 2 1 0 0 0 1 2 3 4 5 6 0
0 0 0 2 1 2 1 2 1 0 0 0 1 2 1 2 1 2

v←(v←⊂[1](.....)~¨0 enclose the diagonals as a nested vector with padded zeros removed

+/~(v⍳¨v)≡¨⍳¨⍴¨v identify diagnols with duplicate entries and sum
\$\endgroup\$
1
\$\begingroup\$

Perl 5, 89 82 bytes

map{$i=0;map{$a[$x+$i].=$_;$b[@F-$x+$i++].=$_}/\d/g;$x++}@F;$_=grep/(.).*\1/,@a,@b

TIO

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

TSQL, 140 128 bytes

Found a way to golf 12 characters. This is no longer the longest solution.

Golfed:

SELECT sum(iif(y+x=j+i,1,0)+iif(y-x=j-i,1,0))FROM
@,(SELECT x i,y j,max(y)over()m,v w
FROM @)d WHERE(x*y=0or m=y)and v=w and x<i

Ungolfed:

DECLARE @ table(v int,x int,y int)
-- v = value
-- x = row 
-- y = column
INSERT @ values
(1,0,0),(2,0,1),(1,0,2),(2,0,3),(1,0,4),(2,0,5),
(1,1,0),(2,1,1),(3,1,2),(4,1,3),(5,1,4),(6,1,5),
(6,2,0),(5,2,1),(4,2,2),(3,2,3),(2,2,4),(1,2,5),
(2,3,0),(1,3,1),(2,3,2),(1,3,3),(2,3,4),(1,3,5)


SELECT sum(iif(y+x=j+i,1,0)+iif(y-x=j-i,1,0))
FROM @,(SELECT x i,y j,max(y)over()m,v w FROM @)d
WHERE
  (x*y=0or m=y)
  and v=w
  and x<i

Try it out

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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