Finde alle (Anti) Diagonalen mit doppelten Werten

17

Herausforderung:

Bestimmen Sie bei einer Matrixeingabe die Anzahl der Diagonalen und Antidiagonalen mit doppelten Zahlen.
Wenn wir also eine Matrix wie diese haben:

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

Alle Diagonalen und Antidiagonalen wären:

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

Beispiel:

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

Alle Diagonalen und Antidiagonalen wären:

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

Entfernen aller Diagonalen und Antidiagonalen, die nur eindeutige Zahlen enthalten:

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

Die Ausgabe ist also die Menge der Diagonalen und Antidiagonalen, die doppelte Zahlen enthalten:

6

Herausforderungsregeln:

  • Wenn die Eingabematrix leer ist, nur 1 Zahl enthält oder in der gesamten Matrix nur eindeutige Zahlen enthält, erfolgt die Ausgabe immer 0.
  • Die Eingabe enthält garantiert nur positive Ziffern [1,9](es sei denn, sie ist vollständig leer).
  • Die Matrix ist immer rechteckig (dh alle Zeilen sind gleich lang).
  • I / O ist flexibel. Die Eingabe kann als Liste von Listen mit ganzen Zahlen oder als 2D-Array von ganzen Zahlen oder als Matrix-Objekt als Zeichenfolge usw. usw. erfolgen. Sie können auch eine oder beide Dimensionen der Matrix als zusätzliche Eingabe verwenden wenn es Bytes in der Sprache Ihrer Wahl sparen würde.

Allgemeine Regeln:

  • Das ist , also gewinnt die kürzeste Antwort in Bytes.
    Lassen Sie sich von Code-Golf-Sprachen nicht davon abhalten, Antworten mit Nicht-Codegolf-Sprachen zu veröffentlichen. Versuchen Sie, für jede Programmiersprache eine möglichst kurze Antwort zu finden.
  • Für Ihre Antwort gelten Standardregeln mit Standard-E / A-Regeln. Daher dürfen Sie STDIN / STDOUT, Funktionen / Methoden mit den richtigen Parametern und vollständige Programme vom Rückgabetyp, verwenden. Ihr Anruf.
  • Standardlücken sind verboten.
  • Fügen Sie nach Möglichkeit einen Link mit einem Test für Ihren Code hinzu (z. B. TIO ).
  • Außerdem wird dringend empfohlen, eine Erklärung für Ihre Antwort hinzuzufügen.

Testfälle:

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
quelle

Antworten:

4

Gelee , 10 Bytes

ŒD;ŒdQƑÐḟL

Probieren Sie es online! oder Schauen Sie sich die Testsuite an!

Alternativen:

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

Wie es funktioniert?

Œ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).
Mr. Xcoder
quelle
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)

Probieren Sie es online!

Erläuterung

Zunächst deklarieren wir zusätzliche Variablen und , die für Zeilen- bzw. Spaltenindizes stehen. Dann können wir die Diagonalen und Antidiagonalen abgrenzen, indem wir ihre Differenz und Summe nehmen. ZB für eine 4x4 Matrix:xy

x-y gibt:

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

x+y ergibt:

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

Jetzt split(m, x-y)und split(m, x+y)produzieren die tatsächlichen Listen von Diagonalen und anti-Diagonalen, die wir miteinander zu verbinden.

Schließlich zählen wir die Einträge der resultierenden Liste, in denen Duplikate vorhanden sind.

Danke für die Bytes gespeichert:

-4 von CriminallyVulgar
-4 von digEmAll

Kirill L.
quelle
1
Ich denke, ich kann rowund colzu meiner Liste der "extrem situativen Funktionen" hinzufügen . Wirklich clevere Lösung.
CriminallyVulgar
1
Ich denke, Sie können die c(m|x-y,m|x+y)gerade in den sapply Anruf bewegen , das l=Teil entfernen . Ich sehe keine fehlgeschlagenen Tests. Probieren Sie es online!
CriminallyVulgar
Ja, das stimmt, ich habe nur übersehen, dass nach meinem ersten Golfspiel nur noch eine lInstanz übrig war.
Kirill L.
1
Sie müssen R heute Morgen die Funktionen rowund hinzugefügt haben column, weil ich noch nie von ihnen gehört habe.
ngm
5

J , 21-20 Bytes

-1 Byte danke an Jonah!

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

Probieren Sie es online!

Erläuterung:

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
quelle
1
Es ist ein bisschen verrückt, dass man es nicht besser machen kann als (-.@-:~.)mit "Die einzigartigen Gegenstände stimmen nicht überein" in J, aber ich bin auch schon oft darauf gestoßen und ich glaube nicht, dass man ... wir haben =und ~:, eines Hand, und -:und <this is missing>.
Jona
Tatsächlich gelang, 1 Byte mehr zu scheren: 1#.|.,&((~:&#~.)/.)]. Probieren Sie es online!
Jona
@Jonah: coole Verwendung von &, danke!
Galen Ivanov
5

Japt , 31 Bytes

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

Probieren Sie alle Testfälle aus

Erläuterung:

Ë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

Ich habe auch eine Version ausprobiert, die auf Kirill Ls Haskell-Antwort basierte, konnte aber keinen guten Weg finden, um "nach einer Funktion des X- und Y-Index zu gruppieren", und die Alternative, die ich fand, war nicht gut genug.

Kamil Drakari
quelle
31 Bytes
Shaggy
4

JavaScript (ES6),  107 105 101  98 Byte

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

Probieren Sie es online!

Hinweis

Bei der Art und Weise, wie dieser Code gespielt wird, wird die Anti-Diagonale, die aus der einzigen unteren linken Zelle besteht, niemals getestet. Das ist in Ordnung, weil es möglicherweise keine doppelten Werte enthalten kann.

Kommentiert

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
quelle
4

05AB1E , 25 Bytes

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

Probieren Sie es online! oder als Testsuite

Erläuterung

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

Ich habe das Gefühl, hier etwas verpasst zu haben.
Versuchen Sie es später noch einmal.

Emigna
quelle
1
Hilft gar nicht, rotate N leftwäre aber N._jetzt. So í‚εεygÅ0«N._]funktioniert das auch. Kann auch die Abflachung mit dieser neuen Änderung entfernen ... immer noch keine Byte-Einsparungen:í‚vyεygÅ0«N._}ø}«ʒ0KDÙÊ}g
Magic Octopus Urn
1
@MagicOctopusUrn: Interessant. Ich hatte diesen Befehl verpasst. Nur noch eine. Das ist komisch.
Emigna
1
@Emigna Du kannst mit Recht gehen N(._, aber deine NFÁ}Länge ist gleich und in diesem Fall sogar noch kürzer, da sich ]die Schleife und die Maps gleichzeitig schließen. Insgesamt ist die Verwendung von ._nur dann sinnvoll, wenn im Vergleich zu 1 Byte gespart werden soll NFÀ}.
Kevin Cruijssen
@ KevinCruijssen: Ah, cool. Obwohl, wie Sie sagen, nicht sehr nützlich.
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

Probieren Sie es online!

TFeld
quelle
3

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

Probieren Sie es online!

Sanchises
quelle
1
Sind Arrays wirklich lustig? ; p
Kevin Cruijssen
Und vielen Dank für die Vorbereitung der Testfälle im Octave-Format!
Luis Mendo
2
@ KevinCruijssen Nicht nur Arrays! Das kannst du cellfunauch, und für die Masochisten structfunauch. In Octave ist es entweder eine for-Schleife oder eine having fun!
Sanchises
Und vergiss nicht 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)

Probieren Sie es 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    ]
--  |
--  | ....
nimi
quelle
2

Charcoal , 61 56 53 Bytes

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

F²

Schleife über Vorwärts- und Rückwärtsdiagonalen; i=0stellt Vorwärtsdiagonalen dar, während i=1umgekehrte Diagonalen darstellt.

FLθ

Schleife über jeden Zeilenindex. Dies ist der Index für den Beginn der Diagonale.

FL§θ⁰«

Schleife über jeden Spaltenindex.

F⟦⁻κ×⊖⊗ιλ⟧

Berechnen Sie den Zeilenindex der Diagonale an diesem Spaltenindex. Ich verwende eine forSchleife über ein einzelnes Elementarray anstelle einer Zuweisung, da dies vermeidet, dass die Zuweisung mit der folgenden Anweisung in einen Block eingeschlossen werden muss, wodurch ein Byte gespeichert wird.

⎇∧λ﹪⁺μιLθ

Überprüfen Sie, ob dies die erste Spalte ist oder ob die Diagonale zwischen unten und oben gewickelt werden soll.

⊟υ

Ist dies nicht der Fall, entfernen Sie die letzte Liste aus der Liste der Listen.

⟦⟧

Wenn dies der Fall ist, starten Sie eine neue leere Liste.

⊞O...§§θμλ

Fügen Sie der Liste den aktuellen diagonalen Eintrag hinzu.

⊞υ

Und schieben Sie diese Liste (zurück) zur Liste der Listen.

ILΦυ⊙ι‹⌕ιλμ

Zählen Sie die Anzahl der Listen, die Duplikate enthalten.

Nehmen wir ein Beispiel, wann i=0und k=1. Dies bedeutet, dass wir bereits zwei Diagonalen gesammelt haben [[1,1,5,2],[9,4,3,5]]. Hier ist unser 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

Wir machen dann eine Schleife lvon 0bis 7. Dies erhöht sowohl die Zeile als auch die Spalte jedes Mal um 1:

 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

Die Liste ist jetzt [[1,1,5,2],[9,4,3,5],[5,4,4]]. Wenn dies jedoch der Fall list 3, haben wir k+l=4ein Vielfaches der Höhe des Arrays. Dies bedeutet , dass wir brauchen , um eine neue Liste zu starten: [[1,1,5,2],[9,4,3,5],[5,4,4],[]]. Wir sammeln dann weiterhin diagonale Elemente:

 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

Die Liste ist jetzt [[1,1,5,2],[9,4,3,5],[5,4,4],[2,7,2,1]]. Nun, wann list 7, haben wir ein k+l=8weiteres Vielfaches der Höhe des Arrays. Dies bedeutet , dass wir brauchen , um eine neue Liste beginnen, die mit dem letzten Element dieser Diagonale endet: [[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

Durch das Sammeln von Umhüllungsdiagonalen beginnend mit dem ersten Element jeder Reihe akkumulieren wir schließlich alle Diagonalen des Arrays.

Neil
quelle
2

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

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

Probieren Sie es online!

  • Function[a,a~Diagonal~#&/@Range[t=-#~Total~2,-t]]erhält alle Diagonalen von a- was funktioniert, weil #~Total~2größer ist als jede Dimension von a.
Lirtosiast
quelle
1

APL + WIN, 69 Bytes

Fordert zur Eingabe einer 2D-Matrix der 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 2 1 auf

Dies ergibt:

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

Probieren Sie es online! Mit freundlicher Genehmigung von Dyalog Classic

Erläuterung:

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

Erträge:

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
quelle
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
quelle
1

TSQL, 140 128 Bytes

Es wurde ein Weg gefunden, 12 Charaktere zu spielen. Dies ist nicht mehr die längste Lösung.

Golf gespielt:

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

Versuch es

t-clausen.dk
quelle