Schneiden Sie den störenden Hintergrund ab!

13

Ist es nicht ärgerlich, wenn Sie ein Bild aufnehmen, aber der Hintergrund beeinträchtigt die tatsächliche Substanz des Bildes? Ich würde sagen, dass es so ist. Ich muss wissen, wie viel ich beschneiden soll, damit ich dieses Problem los werde! Aber wie immer bin ich ziemlich faul, also brauche ich jemanden, der das für mich macht ...

Aufgabe & Regeln

Bei einer binären Matrix darstellen , um das Bild, Ausgang der Abmessungen (Breite und Höhe) der kleinsten Untermatrix enthält , die alle 1 s in der ursprünglichen Matrix. Eine Untermatrix ist ein Block benachbarter Einträge aus der ursprünglichen Matrix. Entsprechend ist es eine neue Matrix, die durch Überlappen einer Teilmenge benachbarter Zeilen und einer Teilmenge benachbarter Spalten des Originals gebildet wird.

  • Es ist erlaubt, die Breite und die Höhe der Matrix als Eingabe zu verwenden.
  • Die Eingabe enthält garantiert mindestens eine 1 .
  • Sie können Eingaben und Ausgaben mit jeder Standardmethode vornehmen , wobei zu beachten ist, dass diese Lücken standardmäßig verboten sind. Das ist , also versuchen Sie, die Aufgabe in den wenigsten Bytes zu erledigen, die Sie in der Sprache Ihrer Wahl verwalten können.

Beispiel

[000000010100011011001010000000][101001101101010](5,3)

Testfälle

Eingabe | Ausgabe

[[0,1,0,0,0,1,0]]
-> (5,1) oder (1,5)

[[0,0,0,0,0], [0,1,0,1,0], [0,0,1,0,0]]
-> (3,2) oder (2,3)

[[1,1,1,1], [0,0,0,0], [0,0,0,0], [1,0,0,0]]
-> (4,4)

[[0,0,0,0,0,0], [0,1,0,1,0,1], [0,0,0,0,0,0]]
-> (5,1) oder (1,5)

[[0,0,0,0,0], [0,1,0,1,0], [0,0,1,0,0], [0,1,0,1,0], [ 0,0,0,0,0]]
-> (3,3)

[[0,0,0,0,0,0], [0,1,0,1,0,0], [0,1,1,0,1,1], [0,0,1, 0,1,0], [0,0,0,0,0,0]]
-> (5,3) oder (3,5)
Mr. Xcoder
quelle
1
Das kommt mir sehr bekannt vor; war es eine Weile in der Sandbox?
Shaggy
8
Dies ist in der Tat sehr nah an der verknüpften Frage, aber ich denke, es kann als eine ausreichend entfernte Teilmenge davon angesehen werden, da die Erzeugung der Matrix für die Berechnung der tatsächlichen Breite und Höhe nicht unbedingt erforderlich ist. Ein möglicher Algorithmus wäre beispielsweise, die minimale Anzahl von Randnullen für jede Zeile und Spalte zu zählen und diese von den ursprünglichen Dimensionen zu subtrahieren.
Mr. Xcoder

Antworten:

5

APL (Dyalog Unicode) , 10 Byte SBCS

Anonyme implizite Präfixfunktion.

(1+⌈/-⌊/)⍸

Probieren Sie es online!

 Indizes von 1s.

() Wenden darauf folgende implizite Funktion an:

⌊/ das Minimum (niedrigste y- Koordinate und niedrigste x- Koordinate)

⌈/- das Maximum minus das (dies gibt uns die Reichweite)

1+ eins plus das (um inklusive zu sein)

Adam
quelle
5

Oktave , 57 56 45 Bytes

Hier findmacht das schwere Heben: Es sind findsdie Zeilen- und Spaltenindizes der Nicht-Null-Einträge. Dann müssen wir nur die Differenz zwischen dem Maximum und dem Minimum (plus eins) für jeden von diesen separat finden.

Vielen Dank an @beaker und @AndrasDeak für -1 Byte und @LuisMendo für -11 Byte!

@(a){[I{1:2}]=find(a),cellfun(@range,I)}{2}+1

Probieren Sie es online!

Fehler
quelle
3

Python 2 , 92-86 Bytes

def f(a,L=len):exec"a=zip(*a[1-any(a[0]):])[::-1];"*4*L(a[0])*L(a);return L(a[0]),L(a)

Probieren Sie es online!

Chas Brown
quelle
3

Gelee , 7 Bytes

S,§t€0Ẉ

Probieren Sie es online!

Wie es funktioniert

S,§t€0Ẉ  Main link. Argument: M (matrix)

S        Take the columnwise sum. Let's call the resulting array A.
  §      Take the sum of each row. Let's call the resulting array B.
 ,       Pair; yield [A, B].
   t€0   Trim surrounding zeroes of A and B.
      Ẉ  Widths; yields the lengths of the trimmed arrays.
Dennis
quelle
3

Python 2 ,  63-55  Bytes

-8 mit Hilfe von Vincent (nimm die Eingabematrix als Numpy-Array)

lambda a:[len(`a.max(x)`[7::3].strip('0'))for x in 0,1]

Eine unbenannte Funktion, die ein 2 - d - Numpy - Array von Ganzzahlen (in {0,1} ) das eine Liste von Ganzzahlen zurückgibt.[width,height] .

Probieren Sie es online!


Non-Numpy-Version in 63 Bytes (unter Annahme einer Liste von Listen mit ganzen Zahlen in {0,1}):

lambda a:[len(`map(max,v)`[1::3].strip('0'))for v in zip(*a),a]

Probieren Sie es online!

Wie?

Wenn eine Matrix gegeben ist a, wird forjedes ( v) der Transponierten zip(*a), unda selbst wir die Höhe finden erforderlich (angesichts der transponieren dies ist die Weite).

Durch Mapping maxüber wird veine Liste von Nullen und Einsen erstellt, die angibt, ob jede Zeile vEinsen enthält. Die Zeichenfolgendarstellung dieser Liste wird mit backticks ( `...`) ermittelt. Dies ergibt eine Zeichenfolge mit einem führenden Zeichen [und den durch , (Komma + Leerzeichen) getrennten Nullen und Einsen . Wir schneiden diese Zeichenfolge beginnend mit Index eins in Dreierschritten, indem [1::3]wir nur eine Zeichenfolge mit Nullen und Einsen erhalten, wodurch wir die Zeichenfolgenfunktion verwenden können strip, um die äußeren Nullen zu entfernen (strip('0') ) .

Beispielsweise:

      a = [[0,0,0,0,0]           map(max,a)                    = [0,1,1]
          ,[0,1,0,0,0]          `map(max,a)`[1::3]             = '011'
          ,[0,0,0,1,0]]         `map(max,a)`[1::3].strip('0')  = '11'
                            len(`map(max,a)`[1::3].strip('0')) = 2

zip(*a) = [(0,0,0)         map(max,zip(*a))                    = [0,1,0,1,0]
          ,(0,1,0)        `map(max,zip(*a))`[1::3]             = '01010'
          ,(0,0,0)        `map(max,zip(*a))`[1::3].strip('0')  = '101'
          ,(0,0,1)    len(`map(max,zip(*a))`[1::3].strip('0')) = 3
          ,(0,0,0)]

    --> [len(`map(max,v)`[1::3].strip('0'))for v in zip(*a),a] = [3,2]
Jonathan Allan
quelle
57 Bytes bei Verwendung eines Numpy-Arrays.
Vincent
Wenn wir Eingaben als nicht eingebauten Typ betrachten, sollten wir dann nicht eine Art Importanweisung mitzählen, um dies zu ermöglichen? (Vielleicht müssen wir den Beitrag nur mit "Python 2 with Numpy" betiteln - da bin ich mir nicht ganz sicher) ... wenn Sie etwas Zeit haben, können Sie im Chatroom mit dem neunzehnten Byte nachfragen?
Jonathan Allan
1
... auch 55 Bytes oder?
Jonathan Allan
1
Ich konnte auf PPCG Meta keine eindeutige Antwort finden , daher bin ich mir nicht sicher. Und ja, 55 Bytes in der Tat :)
Vincent
1
Ich habe nur gefragt. Laut diesem Beitrag muss der Import nicht enthalten sein.
Vincent
1

Retina 0.8.2 , 83 Bytes

+`^0+¶|¶0+$

+1`((.)*).(¶(?<-2>.)*).(?<=(1)¶.*|(.))
$1$3$4$5
(¶?)*0*(.*1)0*
$#1 $.2

Probieren Sie es online! Erläuterung:

+`^0+¶|¶0+$

Löschen Sie führende und nachfolgende Nullzeilen.

+1`((.)*).(¶(?<-2>.)*).(?<=(1)¶.*|(.))
$1$3$4$5

Entfernen Sie alle 0s in den Zeilen über dem letzten. Entfernen Sie alle 1s zwei, aber ändern Sie 1in diesem Fall die Ziffer in der nächsten Zeile in a . Dies ist bitweise oder die Zeilen zusammen.

(¶?)*0*(.*1)0*
$#1 $.2

Zählen Sie die Anzahl der Zeilen als Anzahl der Zeilenumbrüche plus 1 und die Anzahl der Spalten als Anzahl der Stellen zwischen der ersten und der letzten 1.

Neil
quelle
1

J , 31 Bytes

[:$([:|.@|:}.^:(0=1#.{.))^:4^:_

Probieren Sie es online!

Erläuterung:

                            ^:_ - repeat until the result stops changing
   (                    )^:4    - repeat 4 times
             ^:(        )       - is
                  1#.           - the sum of
                      {.        - the first row
                 =              - equal 
                0               - to 0
           }.                   - if yes, drop the first row
    [:|.@|:                     - transpose and reverse (rotate 90 degrees) 
[:$                             - what's the shape of the result?
Galen Ivanov
quelle
1

q / kdb +, 16 Bytes

sum@'(|/;|/')@\:
Thomas Smyth
quelle
1

Mathematica, 34 Bytes

Max@#-Min@#+1&/@(#~Position~1)&

Funktion pur. Nimmt eine verschachtelte Liste von Ganzzahlen als Eingabe und gibt eine Liste von zwei Ganzzahlen (die Höhe, gefolgt von der Breite) als Ausgabe zurück. Das Unicode-Zeichen ist U + F3C7 für \[Transpose].

LegionMammal978
quelle
1

05AB1E , 11 9 Bytes

ζ‚Oε0Û0Üg

-2 Bytes dank @ Mr.Xcoder .

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Erläuterung:

ζ            # Swap the rows and columns of the (implicit) input-list
            # Pair it with the (implicit) input-list
  O          # Take the sum of each column and row
   ε         # Map Both the list of column-sums and list of row-sums to:
    0Û       #  Remove all leading zeros
      0Ü     #  Remove all trailing zeros
        g    #  Take the length of the remaining lists
Kevin Cruijssen
quelle
1
ζ‚Oε0Û0ÜgSpart 2 Bytes.
Mr. Xcoder
@ Mr.Xcoder Ah, natürlich. Ich war schon nicht sehr glücklich über diesen Tausch. Ich kann nicht glauben, dass ich nicht darüber nachgedacht habe, zuerst das Paar und dann die Summe zu machen.
Kevin Cruijssen
0

Haskell , 76 Bytes

f x=length.s.reverse.s<$>[foldr(zipWith(:))e x,x]
e=[]:e
s=snd.span(all(<1))

Probieren Sie es online!

Laikoni
quelle
0

Japt, 16 15 Bytes

[UUy]®=ðd)ÎaZÌÄ

Probieren Sie es aus oder führen Sie alle Testfälle aus


Erläuterung

[   ]               :Create an array containing
 U                  : The input and
  Uy                : The input transposed
     ®              :Map each Z
       ð            : Indices of elements where
        d           :  Any element is truthy (not 0)
      =  )          : Reassign to Z
          Î         : First element
           a        : Absolute difference with
            ZÌ      :  Last element
              Ä     :   Plus 1
Zottelig
quelle