Detecta todas las diagonales (anti) con valores duplicados

17

Desafío:

Dada una entrada de matriz, determine la cantidad de diagonales y anti-diagonales con números duplicados.
Entonces, si tenemos una matriz como esta:

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

Todas las diagonales y anti-diagonales serían:

[[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]]

Ejemplo:

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

Todas las diagonales y anti-diagonales serían:

[[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]]

Eliminar todas las diagonales y anti-diagonales solo que contengan números únicos:

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

Entonces, la salida es la cantidad de diagonales y antiagoniales que contienen números duplicados:

6

Reglas de desafío:

  • Si la matriz de entrada está vacía, contiene solo 1 número o contiene solo números únicos en toda la matriz, la salida es siempre 0.
  • Se garantiza que la entrada solo contiene dígitos positivos [1,9](a menos que esté completamente vacía).
  • La matriz siempre será rectangular (es decir, todas las filas tienen la misma longitud).
  • I / O es flexible. La entrada se puede tomar como una lista de listas de enteros, o una matriz 2D de enteros, o un objeto Matrix, como una cadena, etc., etc. También se le permite tomar una o ambas dimensiones de la matriz como entrada adicional si guardaría bytes en su idioma de elección.

Reglas generales:

  • Este es el , por lo que la respuesta más corta en bytes gana.
    No permita que los lenguajes de código de golf lo desalienten de publicar respuestas con idiomas que no sean de código. Trate de encontrar una respuesta lo más breve posible para 'cualquier' lenguaje de programación.
  • Las reglas estándar se aplican a su respuesta con las reglas de E / S predeterminadas , por lo que puede usar STDIN / STDOUT, funciones / método con los parámetros adecuados y programas completos de tipo retorno. Tu llamada.
  • Las lagunas predeterminadas están prohibidas.
  • Si es posible, agregue un enlace con una prueba para su código (es decir, TIO ).
  • Además, se recomienda agregar una explicación para su respuesta.

Casos de prueba:

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]]
Kevin Cruijssen
fuente

Respuestas:

4

Jalea , 10 bytes

ŒD;ŒdQƑÐḟL

Pruébalo en línea! o echa un vistazo a la suite de prueba!

Alternativas:

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

¿Cómo funciona?

Œ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).
Sr. Xcoder
fuente
10

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)

Pruébalo en línea!

Explicación

Xy

X-y

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

X+y

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

Ahora split(m, x-y)y split(m, x+y)produzca las listas reales de diagonales y antiagoniales, que unimos.

Finalmente, contamos las entradas de la lista resultante donde hay duplicados presentes.

Gracias por los bytes guardados:

-4 por CriminallyVulgar
-4 por digEmAll

Kirill L.
fuente
1
Supongo que puedo agregar rowy cola mi lista de 'funciones extremadamente situacionales'. Solución realmente inteligente.
CriminallyVulgar
1
Creo que puede mover el c(m|x-y,m|x+y)directo a la llamada de muestra, eliminar la l=parte. No veo ninguna prueba fallida. Pruébalo en línea!
CriminallyVulgar
Sí, eso es correcto, simplemente me perdí que después de mi primer golf, solo quedaba una linstancia.
Kirill L.
1
Deben haber agregado las funciones rowy columna R esta mañana, porque nunca he oído hablar de ellas.
ngm
5

J , 21 20 bytes

-1 byte gracias a Jonás!

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

Pruébalo en línea!

Explicación:

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 
Galen Ivanov
fuente
1
es una locura que no puedas hacer nada mejor que (-.@-:~.)"los artículos únicos no coinciden" en J, pero también me he encontrado con esto muchas veces y no creo que puedas ... tenemos =y ~:, en uno mano, y -:y <this is missing>.
Jonás el
En realidad, conseguido afeitarse 1 byte más fuera: 1#.|.,&((~:&#~.)/.)]. Pruébalo en línea!
Jonás el
@ Jonás: uso genial de &, gracias!
Galen Ivanov
5

Japt , 31 bytes

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

Pruebe todos los casos de prueba

Explicación:

Ë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

También probé una versión basada en la respuesta Haskell de Kirill L., pero no pude encontrar una buena manera de "agrupar en función de los índices X e Y" y la alternativa que encontré no era lo suficientemente buena.

Kamil Drakari
fuente
31 bytes
Shaggy
4

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

Pruébalo en línea!

Nota

Por la forma en que se juega este código, nunca se prueba el anti-diagonal que consiste en la única celda inferior izquierda. Eso está bien porque no puede contener valores duplicados.

Comentado

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
Arnauld
fuente
4

05AB1E , 25 bytes

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

Pruébalo en línea! o como un conjunto de pruebas

Explicación

í                          # 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

Siento que me he perdido algo aquí.
Necesito probar y jugar golf más tarde.

Emigna
fuente
1
No ayuda en absoluto, pero rotate N leftlo sería N._ahora. Así í‚εεygÅ0«N._]también funciona. También puede eliminar el aplanamiento con este nuevo cambio ... aunque todavía no hay ahorro de bytes:í‚vyεygÅ0«N._}ø}«ʒ0KDÙÊ}g
Urna de pulpo mágico el
1
@MagicOctopusUrn: Interesante. Me había perdido ese comando. Sin embargo, solo queda una izquierda. Eso es raro.
Emigna
1
@Emigna Puedes ir a la derecha N(._, supongo, pero tu NFÁ}es de la misma longitud, e incluso más corta en este caso debido al ]cierre simultáneo del bucle y los mapas. En general, el uso de ._solo es útil cuando se va a la izquierda para guardar 1 byte, en comparación con NFÀ}.
Kevin Cruijssen
@KevinCruijssen: Ah, genial. Aunque como dices, no es muy útil.
Emigna
3

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

Pruébalo en línea!

TFeld
fuente
3

Octava , 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))])

Pruébalo en línea!

Sanchises
fuente
1
¿Las matrices son realmente divertidas? ; p
Kevin Cruijssen
¡Y gracias por preparar los casos de prueba en formato Octave!
Luis Mendo
2
@KevinCruijssen ¡No solo matrices! Puedes tener cellfuntambién, y para los masoquistas, structfuntambién. En Octave, ¡es un bucle for o está teniendo fun!
Sanchises
¡Y no olvides b-sx-fun!
Luis Mendo
3

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)

Pruébalo en línea!

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    ]
--  |
--  | ....
nimi
fuente
2

Carbón , 61 56 53 bytes

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

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

F²

Pase sobre diagonales hacia adelante y hacia atrás; i=0representa diagonales hacia adelante mientras que i=1representa diagonales inversas.

FLθ

Pase sobre cada índice de fila. Esto representa el índice del inicio de la diagonal.

FL§θ⁰«

Pase sobre el índice de cada columna.

F⟦⁻κ×⊖⊗ιλ⟧

Calcule el índice de fila de la diagonal en este índice de columna. Utilizo un forbucle sobre una matriz de un solo elemento en lugar de una asignación, ya que esto evita tener que ajustar la asignación en un bloque con la siguiente instrucción, lo que ahorra un byte.

⎇∧λ﹪⁺μιLθ

Compruebe si esta es la primera columna o si la diagonal está a punto de envolverse entre la parte inferior y la superior.

⊟υ

Si no es así, pop la última lista de la lista de listas.

⟦⟧

si es así, comience una nueva lista vacía.

⊞O...§§θμλ

Agregue la entrada diagonal actual a esa lista.

⊞υ

Y empuje esa lista (atrás) a la lista de listas.

ILΦυ⊙ι‹⌕ιλμ

Cuente el número de listas que contienen duplicados.

Tomemos un ejemplo cuando i=0y k=1. Esto significa que ya hemos recogido dos diagonales, [[1,1,5,2],[9,4,3,5]]. Aquí está nuestra entrada:

 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

Luego pasamos lde 0a 7. Esto avanza tanto la fila como la columna en 1 cada vez:

 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

La lista es ahora [[1,1,5,2],[9,4,3,5],[5,4,4]]. Sin embargo, cuando les 3, tenemos k+l=4, un múltiplo de la altura de la matriz. Esto significa que tenemos que empezar una nueva lista: [[1,1,5,2],[9,4,3,5],[5,4,4],[]]. Luego continuamos recolectando elementos diagonales:

 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

La lista es ahora [[1,1,5,2],[9,4,3,5],[5,4,4],[2,7,2,1]]. Ahora cuando les 7, tenemos k+l=8, otro múltiplo de la altura de la matriz. Esto significa que tenemos que empezar una nueva lista, que termina con el último elemento de la diagonal que: [[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

Al recopilar diagonales de envoltura que comienzan en el primer elemento de cada fila, eventualmente acumulamos todas las diagonales de la matriz.

Neil
fuente
2

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

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

Pruébalo en línea!

  • Function[a,a~Diagonal~#&/@Range[t=-#~Total~2,-t]]obtiene todas las diagonales de a, lo que funciona porque #~Total~2es más grande que cualquier dimensión de a.
lirtosiast
fuente
1

APL + WIN, 69 bytes

Solicita una matriz 2D de la forma 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

Esto produce:

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

Pruébalo en línea! Cortesía de Dyalog Classic.

Explicación:

(⌽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

Rendimientos:

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
Graham
fuente
1

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

Nahuel Fouilleul
fuente
1

TSQL, 140 128 bytes

Encontré una manera de jugar al golf 12 personajes. Esta ya no es la solución más larga.

Golfizado:

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

Sin golf:

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

Pruébalo

t-clausen.dk
fuente