Gibt es N aufeinanderfolgende Vorkommen einer Zahl in einer Zeile / Spalte in einer Matrix?

20

Nehmen Sie eine Matrix A, die aus positiven ganzen Zahlen und einer einzelnen positiven ganzen Zahl N besteht, als Eingabe und bestimmen Sie, ob in einer Zeile oder Spalte in der Matrix mindestens N aufeinanderfolgende Vorkommen derselben Zahl vorhanden sind.

Sie müssen nur horizontal und vertikal testen.

Testfälle

N = 1
A = 
1
Result: True
----------------
N = 3
A = 
1 1 1
2 2 3
Result: True
----------------
N = 4
A = 
1 1 1
2 2 3
Result: False
----------------
N = 3
A = 
3 2 3 4 2 1
4 1 4 2 4 2
4 2 3 3 4 1
1 1 2 2 3 4
3 2 3 1 3 1
1 1 2 2 3 4
Result: True
----------------
N = 1
A = 
5 2 3 8
Result: True
----------------
N = 3
111   23  12    6
111   53   2    5
112  555   5  222
Result: False
----------------
N = 2
 4  2  6  2  1  5
 2  3  3  3  3  3
11 34  4  2  9  7
Result: True

Erklärungen sind immer eine gute Sache :)

Stewie Griffin
quelle
5
Sie scheinen Matrizen zu lieben.
Okx
4
Nun, ich bin ein MATLAB-Typ ... Mat Rix Lab- Oratorium =)
Stewie Griffin
Reicht es aus, einen wahrheitsgemäßen / falschen Wert zurückzugeben?
Dennis
@ Tennis natürlich :)
Stewie Griffin
5
Es ist ärgerlich, dass Sie als Matlab-Mitarbeiter in MATLAB einfache Herausforderungen meistern, aber eine leichte Wendung haben, die die offensichtliche Lösung ausschließt ...
Sanchises,

Antworten:

7

Schale , 9 Bytes

≤▲mLṁgS+T

Nimmt ein 2D-Array und eine Zahl, gibt 0für falsche Instanzen eine positive und für wahrheitsgemäße Instanzen eine positive Zahl zurück. Probieren Sie es online!

Erläuterung

Husk ist eine funktionale Sprache, daher besteht das Programm nur aus mehreren Funktionen.

≤▲mLṁgS+T
        T  Transpose the array
      S+   and concatenate with original.
           We get a list of the rows and columns of the input array.
    ṁ      Map and concatenate
     g     grouping of equal consecutive elements.
           This gives all consecutive runs on rows and columns.
  mL       Map length over the runs,
 ▲         take the maximum of the results
≤          and see if it's at least the second input.
Zgarb
quelle
5

Dyalog APL, 27 25 23 Bytes

{1∊∊⍷∘⍵¨(⊢,⍪¨)⍺/¨⍳⌈/∊⍵}

Probieren Sie es online!

Dank an @MartinEnder und @Zgarb für jeweils -2 Bytes (Komposition macht die Verwendung von wund sinnlosen Parens überflüssig)

Benachrichtigen Sie mich bei Problemen und / oder Problemen mit dem Golfsport. Linkes Argument ist N , rechtes Argument ist A .

Erläuterung:

{1∊∊⍷∘⍵¨(⊢,⍪¨)⍺/¨⍳⌈/∊⍵}
                     ⍵    - Right argument
                    ∊     - Flatten the array
                 ⍳⌈/      - 1 ... the maximum (inclusive)
              ⍺/¨         - Repeat each item ⍺ (left argument) times.
        (⊢,⍪¨)            - Argument concatenated with their transposes.
    ⍷∘⍵¨                  - Do the patterns occur in ⍵?
   ∊                      - Flatten (since we have a vector of arrays)
 1∊                       - Is 1 a member?
{                     }   - Function brackets
Zacharý
quelle
4

Perl 6 , 60 Bytes

{(@^m|[Z,] @^m).map(*.rotor($^n=>$^n-1).map({[==] $_}).any)}

Probieren Sie es online!

  • @^mist die Eingabematrix (erstes Argument) und $^ndie Anzahl aufeinanderfolgender Vorkommen, auf die geprüft werden soll (zweites Argument).
  • [Z,] @^m ist die Transponierte der Eingangsmatrix.
  • (@^m | [Z,] @^m)ist eine Oder-Verknüpfung der Eingangsmatrix und ihrer Transponierten. Das Folgende wird mapzu einem Wahrheitswert ausgewertet, wenn $^naufeinanderfolgende gleiche Werte in einer Zeile des Aufrufers auftreten. Wird sie auf die Eingabematrix ODER ihre Transponierung angewendet, ergibt sie einen Wahrheitswert, wenn entweder die Eingabematrix oder ihre Transponierung $^naufeinanderfolgende gleiche Werte in einer Zeile enthält. Wenn die Transponierte diese Bedingung erfüllt, bedeutet dies, dass die Eingabematrix $^naufeinanderfolgende gleiche Werte in einer ihrer Spalten enthält.
  • *.rotor($^n => $^n - 1)verwandelt jede Zeile in eine Folge von $^n-Element-Slices. Wenn beispielsweise $^n3 und eine Zeile 3 ist <1 2 2 2 3>, wird dies zu ausgewertet (<1 2 2>, <2 2 2>, <2 2 3>).
  • .map({ [==] $_ })verwandelt jedes Slice in einen Booleschen Wert, der angibt, ob alle Elemente des Slice gleich sind. Fortsetzung des vorherigen Beispiels wird dies (False, True, False).
  • .any verwandelt diese Folge von Booleschen Werten in eine Oder-Verknüpfung, die wahr ist, wenn einer der Booleschen Werte wahr ist.

Die Ausgabe ist ein Wahrheits- oder Verknüpfungswert, der wahr ist, wenn entweder die Eingabematrix oder ihre Transponierte eine beliebige Zeile haben, in der $^naufeinanderfolgende Werte gleich sind.

Sean
quelle
4

MATL , 12 Bytes

t!YdY'wg)>~a

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

Eine nicht quadratische Matrix kann weder vertikal noch horizontal ordnungsgemäß mit ihrer Transponierten verknüpft werden. Der Code verkettet sie also diagonal , indem er eine blockdiagonale Matrix erstellt.

Die resultierende Matrix wird in Spaltenhauptordnung und Lauflängencodierung linearisiert. Die aus der blockdiagonalen Verkettung resultierenden Nullen dienen dazu, die Läufe der Istwerte zu isolieren.

Die Ergebnisse der Lauflängencodierung sind ein Array von Werten und ein Array von Lauflängen. Die Lauflängen, die Nicht-Null-Werten entsprechen, werden beibehalten. Die Ausgabe erfolgt, 1wenn einige dieser Längen größer oder gleich der Eingabenummer sind, und0 andernfalls.

Lassen Sie uns die Zwischenergebnisse sehen, um es klarer zu machen. Betrachten Sie Eingaben

[10 10 10;
 20 20 30]

und

3

Die Blockdiagonalmatrix mit der Eingangsmatrix und ihrer Transponierung (Code t!Yd) lautet:

10 10 10  0  0
20 20 30  0  0
 0  0  0 10 20
 0  0  0 10 20
 0  0  0 10 30

Diese Matrix ist implizit linearisiert in der Hauptreihenfolge der Spalten (unten, dann quer):

10 20  0  0  0 10 20  0  0  0 10 30  0  0  0  0  0 10 10 10  0  0 20 20 30

Die Lauflängencodierung (Code Y') ergibt die folgenden zwei Vektoren (hier als Zeilenvektoren gezeigt; tatsächlich sind sie Spaltenvektoren): Vektor mit Werten

10 20  0 10 20  0 10 30  0 10  0 20 30

und Vektor mit Lauflängen

1 1 3 1 1 3 1 1 5 3 2 2 1

Wenn Sie nur die Längen einhalten, die Nicht-Null-Werten (Code wg)) entsprechen, erhalten Sie

1 1 1 1 1 1 3 2 1

Wenn man vergleicht, um zu sehen, welche Längen größer oder gleich der eingegebenen Nummer (Code >~) sind, wird der Vektor erzeugt

0 0 0 0 0 0 1 0 0

Schließlich sollte die Ausgabe true(angezeigt als 1) sein, wenn der obige Vektor mindestens einen trueEintrag (Code a) enthält. In diesem Fall ist das Ergebnis

1
Luis Mendo
quelle
4

Oktave, 77-70 Bytes

@(A,N)any(([x y]=runlength([(p=padarray(A,[1 1]))(:);p'(:)]))(!!y)>=N)

Probieren Sie es online!

Erläuterung: Da die Matrix nur Ganzzahlen ungleich Null enthält, können wir der Matrix einen Rand von Nullen hinzufügen und die Lauflängencodierung der Matrix berechnen (in einen Vektor umgeformt).

@(A,N)any(([x y]=runlength([(p=padarray(A,[1 1]))(:);p'(:)]))(!!y)>=N)
                             p=padarray(A,[1 1])                        % add a border of 0s around the matrix 
                            (                   )(:)                    % reshape the matrix to a column vector
                                                     p'(:)              % transpose of the matrix reshaped to a column vector
                           [                        ;     ]             % concatenate two vectors vertically
           [x y]=runlength(                                )            % runlength encoding of the vector[x=count,y=value]
          (                                                 )           % take x,counts.
                                                             (!!y)      % extrect those counts that their valuse aren't 0
      any(                                                        >=N)  % if we have at least a count that is greater than or equal to N                                                              
rahnema1
quelle
3
Ich mag Ihre Lösungen (nicht nur diese) wirklich, aber sie könnten definitiv von einigen Erklärungen profitieren! :) Ich wusste nicht, dass Octave hatte runlength... Lernen Sie jeden Tag etwas Neues ...
Stewie Griffin
Danke, dass du mich daran erinnert hast runlength! Da ich mich mehr auf Matlab konzentrierte, erinnerte ich mich nicht daran, dass es in Octave
Luis Mendo,
@StewieGriffin Danke, Antwort nach dem Aufwachen aktualisiert!
rahnema1
@LuisMendo Nach einem Ihrer Beiträge bin ich auf eine Funktion namens aufmerksam geworden runlength.
rahnema1
4

Gelee , 9 8 Bytes

;ZjṡƓE€S

Nimmt die Matrix als Argumente und liest die Ganzzahl aus STDIN.

Probieren Sie es online!

Wie es funktioniert

;ZjṡƓE€S  Main link. Argument: M (matrix / row array)

 Z        Zip/transpose M.
;         Concatenate the row array with the column array.
  j       Join the rows and columns, separating by M.
    Ɠ     Read an integer n from STDIN.
   ṡ      Split the result to the left into overlapping slices of length 2.
     E€   Test the members of each resulting array for equality.
       S  Take the sum.

Beispiellauf

;ZjṡƓE€S  Argument: [[1, 2], [3, 2]]. STDIN: 2

 Z        [[1, 3], [2, 2]]

;         [[1, 2], [3, 2], [1, 3], [2, 2]]

  j       [1, 2, [1, 2], [3, 2], 3, 2, [1, 2], [3, 2], 1, 3, [1, 2], [3, 2], 2, 2]

    Ɠ     2

   ṡ      [[1, 2],             [2, [1, 2]],        [[1, 2], [3, 2]],   [[3, 2], 3],
           [3, 2],             [2, [1, 2]],        [[1, 2], [3, 2]],   [[3, 2], 1],
           [1, 3],             [3, [1, 2]],        [[1, 2], [3, 2]],   [[3, 2], 2],
           [2, 2]                                                                 ]

     E€   [     0,                       0,                       0,             0,
                0,                       0,                       0,             0,
                0,                       0,                       0,             0,
                1                                                                 ]

       S  1
Dennis
quelle
Ich hatte die gleiche Idee mit ;Z, obwohl in Japt statt Jelly ...
ETHproductions
Jetzt verstehe ich, warum Sie nach wahrheitsgemäßen / falschen Werten gefragt haben . Diese Definition in Jelly wurde von MATLAB (oder MATL) inspiriert, nicht wahr?
Stewie Griffin
Nein, Jelly verwendet intern Pythons Bedingungen. Das ȦAtom wurde jedoch von MATL inspiriert.
Dennis
Na Eja, meins war viel zu lang. Richtig, das Eingebaute war der Weg, es zu tun. Schön :)
HyperNeutrino
3

Python 2 , 60 92 91 Bytes

def f(n,x):x=[map(str,i)for i in x];print any(`[i]*n`[1:-1]in`x+zip(*x)`for i in sum(x,[]))

Probieren Sie es online!

Anstatt zu zählen, wird eine Liste mit der Größe n(für jedes Element in der Matrix) erstellt und überprüft, ob es sich in der Matrix befindet

Ohne Zeichenketten 94 Bytes

lambda n,x:any((e,)*n==l[i:i+n]for l in x+zip(*x)for i in range(len(l)-n+1)for e in sum(x,()))

Probieren Sie es online!

Stange
quelle
Ich denke, dies kann bei mehrstelligen Zahlen zu Fehlalarmen führen.
Xnor
@ xnor dort, behoben
Rod
3

Japt , 18 15 14 Bytes

cUy)d_ò¦ d_ʨV

Probier es aus

  • Mit Hilfe von ETHproductions 3 Bytes gespart.

Erläuterung

    :Implicit input of 2D array U and integer V
c   :Append to U...
Uy  :U transposed.
d   :Check if any of the elements (sub-arrays) in U return true when...
_   :Passed through a function that...
ò   :Partitions the current element by...
¦   :Checking for inequality.
d   :Check if any of the partitions return true when...
_   :Passed through a function that checks if...
Ê   :The length of the current element...
¨V  :Is greater than or equal to V.
    :Implicit output of resulting boolean.
Zottelig
quelle
1
Oh wow, ich habe das nicht gesehen, bevor ich es gepostet habe. Sie könnten mit cUy)®ò¦ d_l ¨V\ndund mit 2 Bytes einsparen cUy)d_ò¦ d_l ¨V, und dann haben Sie praktisch meine (gelöschte) Lösung.
ETHproductions
Haha; Großartige Köpfe ..., @ETHproductions :) Ich bin schockiert, dass ich der schnellste Finger war, nachdem obarakon mich heute den ganzen Tag geschlagen hat! Danke für die Tipps, die man schon gesehen hatte, die andere aber noch nicht.
Shaggy
2

CJam , 16 Bytes

q~_z+N*e`:e>0=>!

Probieren Sie es online!

Erläuterung

q~    e# Read and eval input.
_z+   e# Append the matrix's transpose to itself.
N*    e# Join with linefeeds to flatten without causing runs across rows.
e`    e# Run-length encode.
:e>   e# Get maximum run (primarily sorted by length).
0=    e# Get its length.
>!    e# Check that it's not greater than the required maximum.
Martin Ender
quelle
Ich habe mich immer gefragt, warum CJams RLE zuerst die Lauflänge und dann den Wert angibt. Nun, es stellt sich als nützlich heraus, hier :-)
Luis Mendo
@ LuisMendo Ich denke, weil du es so sagen würdest "3 a, 5 b, 2 c". Ich finde diese Reihenfolge tatsächlich ziemlich oft nützlich.
Martin Ender
Tatsächlich gibt die Octave- runlengthFunktion die Ausgänge auch in dieser Reihenfolge aus. Aber irgendwie fühle ich die Reihenfolge value, lengthnatürlicher
Luis Mendo
2

Python 3 , 129 128 125 120 104 101 Bytes

Vielen Dank an @Zachary T, @Stewie Griffin, @Mr. Xcoder, @Rod, @totallyhuman für die deutliche Verbesserung.

def f(n,m):
 a=b=c=0;m+=zip(*m)
 for r in m:
  for i in r:b,a=[1,b+1][a==i],i;c=max(c,b)
 return n<=c

Probieren Sie es online!

verletzt
quelle
Sie brauchen kein Leerzeichen zwischen 1und if.
Zacharý
Speichern vier Bytes durch den Austausch a=b;b=0;c=0mita=b=c=0
Herr Xcoder
(Ich bin mir nicht sicher), aber ich denke, dass Sie m+zip(*m)stattdessen min der 4. Zeile die 1. Zeile ganz weglassen n<=max()und die letzte Zeile verschieben könnten alsn<=c
Rod
120 Bytes
totalhuman
Anstatt zu b=b+1benutzenb+=1 ... Ahh, Ninja'd von @StewieGriffin
Herr Xcoder
2

05AB1E , 16 14 12 Bytes

Døìvyγ€gM²‹_

Probieren Sie es online!

Dø           # Duplicate the input and transpose one copy
  ì          # Combine the rows of both matrixes into one array
   vy        #   For each row...
     γ       #     Break into chunks of the same element
      €g     #     get the length of each chunk
        M    #     Get the largest length so far
         ²‹_ #     Check if that is equal to or longer than required
Riley
quelle
1
@MagicOctopusUrn Ich bin mir nicht sicher, was du meinst. In diesem Beispiel befinden sich 3 aufeinanderfolgende 0s in der zweiten Zeile. Es sollte also wahr sein.
Riley
@MagicOctopusUrn Wenn Sie diesen Lauf (TIO) unterbrechen, wird false zurückgegeben.
Riley
Verkettet der dritte Befehl die transponierten Zeilen nicht mit den ursprünglichen Zeilen?
Magic Octopus Urn
Außerdem dachte ich, es sollte nur für 3 wahr zurückkehren, wenn es gibt [3,3,3]. Ich habe die Herausforderung in diesem Fall falsch verstanden, also denke ich, dass ich hier falsch liege.
Magic Octopus Urn
@MagicOctopusUrn Mit den ersten drei Befehlen wird ein Array erstellt, das jede Zeile und jede Spalte als einzelne Elemente enthält.
Riley
1

Jelly , 18 Bytes

ŒrFUm2<⁴$ÐḟL
ZÇo³Ç

Probieren Sie es online!

ŒrFUm2<⁴$ÐḟL  Helper Link
Œr            Run-length encode
  F           Flatten the whole thing, giving the numbers in the odd indices and the lengths of the runs in the even indices
   U          Reverse
    m2        Take every other element (thus only keeping the run lengths)
         Ðḟ   Discard the elements that are
      <⁴$                                   less than the required run length
           L  And find the length
ZÇo³Ç         Main Link
Z             Zip the matrix
 Ç            Call the helper link on it
   ³Ç         Call the helper link on the original matrix
  o           Are either of these truthy?

Gibt 0für false und für truthy eine Ganzzahl ungleich Null zurück.

Ew, das ist schlecht. Und sehr lange. Golftipps wären willkommen :)

HyperNeutrino
quelle
1

JavaScript (ES6), 99 Byte

Übernimmt die Matrix mund die erwartete Anzahl der Vorkommen nin der Currying-Syntax (m)(n). Gibt einen Booleschen Wert zurück.

m=>n=>[',',`(.\\d+?){${m[0].length-1}}.`].some(s=>m.join`|`.match(`(\\b\\d+)(${s}\\1){${n-1}}\\b`))

Wie?

Dieser Code ist nicht besonders kurz, aber ich wollte einen Ansatz ausprobieren, der ausschließlich auf regulären Ausdrücken basiert.

Umwandlung der Matrix in einen String

Wir verwenden, m.join('|')um das 2D-Array in einen String umzuwandeln. Dies bewirkt zunächst einen impliziten Zwang der Matrixzeilen zu durch Kommas getrennten Zeichenfolgen.

Zum Beispiel diese Eingabe:

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

wird umgewandelt in:

"1,2,3|4,5,6"

Zeilenabgleich

Wir suchen nach aufeinanderfolgenden Vorkommen in einer Reihe mit:

/(\b\d+)(,\1){n-1}\b/

Das passt zusammen:

  • \b eine Wortgrenze
  • \d+ gefolgt von einer Nummer
  • (){n-1}n-1 mal gefolgt von:
    • , ein Komma
    • \1 gefolgt von unserer Referenz: eine Wortgrenze + die erste Zahl
  • \b gefolgt von einer Wortgrenze

Spaltenübereinstimmung

Wir suchen nach aufeinanderfolgenden Vorkommen in einer Spalte mit:

/(\b\d+)((.\d+?){L-1}.\1){n-1}\b/

wo List die Länge einer Reihe.

Das passt zusammen:

  • \b eine Wortgrenze
  • \d+ gefolgt von einer Nummer
  • (){n-1}n-1 mal gefolgt von:
    • (){L-1} L-1 mal:
      • . Beliebiges Zeichen (effektiv: entweder ein Komma oder eine Pipe)
      • \d+? gefolgt von einer Zahl (diese darf nicht gierig sein)
    • . gefolgt von einem beliebigen Zeichen (erneut: entweder ein Komma oder eine Pipe)
    • \1 gefolgt von unserer Referenz: eine Wortgrenze + die erste Zahl
  • \b gefolgt von einer Wortgrenze

Testfälle

Arnauld
quelle
0

Clojure, 77 Bytes

#((set(for[I[%(apply map vector %)]i I p(partition %2 1 i)](count(set p))))1)

Erstellt alle aufeinander folgenden Partitionen pder Länge N(Symbol %2) und zählt, wie viele unterschiedliche Werte es hat. Dann bildet es die Menge dieser Längen und gibt zurück, 1ob es aus der Menge und nilanderen gefunden wird. forDas Konstrukt passte perfekt dazu, mein ursprünglicher Versuch flatten, concatoder so etwas in der Art.

NikoNyrh
quelle