Finde ein maximales Rechteck von 1s

21

Hintergrund

Ich möchte ein Grundstück kaufen und darauf mein Haus bauen. Mein Haus sollte rechteckig und so groß wie möglich sein; Die verfügbaren Parzellen haben jedoch viele felsige Gebiete, auf denen ich nicht bauen kann, und ich habe Probleme, ein potenzielles Haus auf den Parzellen zu errichten. Ich möchte, dass Sie ein Programm schreiben, das die Handlungen für mich analysiert.

Ein- und Ausgabe

Ihre Eingabe ist ein rechteckiges 2D-Array von Bits mit einer Größe von mindestens 1 × 1 in einem angemessenen Format. Das Array stellt ein Grundstück dar; 1s sind "gute" Gebiete, in denen ich mein Haus bauen könnte, und0 s sind "felsige" Gebiete, in denen das Haus nicht gebaut werden kann.

Ihre Ausgabe soll die maximale Fläche eines durchgezogenen Rechtecks ​​von 1s im Eingabearray sein. Es ist die Fläche des größten Hauses, das ich auf dem Grundstück bauen konnte. Beachten Sie, dass 1der Ausgang ist , wenn der Eingang kein s enthält0 .

Beispiel

Betrachten Sie die Eingabe

101
011
111

Das größte Rechteck von 1s ist das 2 × 2-Rechteck in der unteren rechten Ecke. Dies bedeutet, dass die richtige Ausgabe ist 4.

Regeln und Wertung

Sie können ein vollständiges Programm oder eine Funktion schreiben. Die niedrigste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig.

Testfälle

0
-> 0

1
-> 1

00
00
-> 0

01
10
-> 1

01
11
-> 2

111
010
111
-> 3

101
011
111
-> 4

0111
1110
1100
-> 4

1111111
1110111
1011101
-> 7

111011000
110111100
001111110
011111111
001111110
000111100
000011000
-> 20

000110000
110110010
110111110
110011100
010011111
111111111
111101110
-> 12
Zgarb
quelle
8
Bulldozer, 4 Bytes plow.
Conor O'Brien
1
Ist es in Ordnung, wenn meine Lösung nur für Rechtecke mit einer Größe von bis zu 30 × 30 funktioniert?
Neil
1
@Neil Nein, es sollte (zumindest theoretisch) für ungefähr so ​​große Eingaben funktionieren, wie Ihre Sprache verarbeiten kann.
Zgarb
1
Ich hatte gehofft, ein bisschen herumzudrehen, aber in diesem Fall werde ich mich nicht darum kümmern.
Neil
1
Muss die Lösung die Rotation berücksichtigen?

Antworten:

13

Jelly , 21 20 18 17 Bytes

ṡṂ€€×"
‘×¥\ç"Ụ€FṀ

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

Hintergrund

Sei M eine Matrix von Bits wie

0 0 0 1 1 0 0 0 0
1 1 0 1 1 0 0 1 0
1 1 0 1 1 1 1 1 0
1 1 0 0 1 1 1 0 0
0 1 0 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 0

Wir beginnen mit der Zählung der Anzahl von 1 Bits in jeder Spalte von M und setzen die Zählung jedes Mal zurück, wenn wir auf ein 0- Bit stoßen .

Für unsere Beispielmatrix ergibt dies

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

Als nächstes berechnen wir alle zusammenhängenden Unterlisten jeder Zeile. Dies erreichen wir, indem wir alle Schichten der Länge k erzeugen , wobei k zwischen 1 variiert und der Anzahl der Einträge in jeder Zeile .

Für die vorletzte Reihe ergibt dies

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

Als nächstes ordnen wir jedem Slice das Produkt seines Minimums und seiner Länge zu. Für jedes Slice wird der Bereich des Rechtecks ​​aus 1 Bit maximaler Höhe berechnet, der das angegebene Slice als unterste Zeile enthält.

Für die Längenscheiben 3 der vorletzten Zeile unserer Beispielmatrix ergibt sich

3 3 3 3 12 6 6

Alles, was Sie tun müssen, ist, das Maximum über alle Segmente aller Zeilen zu ziehen.

Für unsere Beispielmatrix ergibt dies 12 .

Wie es funktioniert

‘×¥\ç"Ụ€FṀ  Main link. Argument: M (2D list of bits)

   \        Reduce the columns of M by the link to the left.
  ¥           Combine the two atoms to the left into a dyadic chain.
‘               Increment the left argument.
 ×              Multiply the result with the right argument.
      Ụ€    Grade up each; yield the indices of each row of M, sorted by their
            values. The order is not important here; we just need the indices.
    ç"      Apply the helper link to each element of the result to the left and
            the corresponding element of the result to the right.
        F   Flatten the resulting, nested list.
         Ṁ  Extract the maximum.


ṡṂ€€×"      Helper link. Arguments: R (row), X (indices of R)

ṡ           For each k in X, split R into overlapping slices of length k.
 Ṁ€€        Compute the minimum of each individual slice.
    ×"      Multiply the minima of all slices of length k by k.
Dennis
quelle
7
Ich wusste nicht, wo du so reich bist, Dennis. € $ €€€
orlp
5
Es geht nur ums Geld. Tauschen Sie $ gegen ¥ gespeicherte 2 Bytes.
Dennis
1
Wie um alles in der Welt kommen Sie immer auf solche klugen Ansätze?
Undichte Nonne
Weil man Dennis nicht einfach outgolft!
Gryphon - Reinstate Monica
6

MATL, 32 31 27 Bytes

n:"@:"@1M2$ltntG4$bZ+=a*vX>

Hierbei wird ein auf Brute-Force-2D-Faltung basierender Ansatz verwendet. Alle möglichen Rechteckgrößen werden mit dem Gelände erstellt und gefaltet. Das maximale Ergebnis aller Windungen ist die maximale Rechteckfläche.

Dies ist eine äußerst ineffiziente Lösung, da zum Speichern von Bytes Kernel für alle Rechtecke zwischen [1, 1]und erstellt werden, [numel(input) numel(input)]anstatt die Anzahl der Zeilen / Spalten in der Eingabe zu bestimmen, um die richtigen Dimensionsbereiche für Rechtecke zu bestimmen.

Vielen Dank an @Luis für den Hinweis auf die Verwendung Mund das Weglassen des ]].

Probieren Sie es online!

Erläuterung

        % Implicitly grab input as a 2D numeric array
n       % Compute the number of elements in the input (over estimation of max kernel size)
:       % Create array 1:n
"       % For each value
  @     % Current loop index
  :     % Create an array from 1:(current_index)
  "     % For each of these values   
    @   % Push the current index onto the stack
    1M  % Grab the input to the previous function call (the outer index)
    2$l % Create an array of 1's whose dimensions are specified by top two stack elements
    tn  % Duplicate this array and compute number of elements
    t   % Duplicate this number
    G   % Explicitly grab input
    4$b % Bubble up the 4th element from the stack (the kernel)
    Z+  % Perform 2D convolution of this kernel and the input
    =a  % Determine if any convolution result (in each column) is equal to the area of the kernel.
        % This yields a row vector
    *   % Multiply the logical result by the area
    v   % Vertically concatenate all results (forces the row vectors above to be column vectors)
    X>  % Compute the maximum yielding the largest area
        % Implicitly display the result.
Suever
quelle
5

Julia, 83 60 57 53 Bytes

!M=M1?sum(M):maximum(t->!rotr90(M,t)[2:end,:],0:3)

Probieren Sie es online! Der letzte Testfall überschreitet das Zeitlimit von TIO, aber ich habe es lokal überprüft.

Wie es funktioniert

Erstens ! überprüft , ob seine Matrix Argument M vollständig besteht aus 1 s.

  • Wenn ja ! Gibt die Summe der Einträge von M zurück , die der Fläche von M entspricht.

  • Wenn nicht ! macht folgendes:

    1. Rotate M von 0 ° , 90 ° , 180 ° und 270 ° im Uhrzeigersinn.

    2. Entfernen Sie die erste Zeile jeder der vier Drehungen, effektiv eine der oberen Reihe zu entfernen, untere Reihe, Spalte ganz links und am weitesten rechts liegenden Spalte von M .

    3. Rufen Sie sich rekursiv auf jeder der Submatrizen auf.

    4. Gibt das Maximum der Rückgabewerte aus den rekursiven Aufrufen zurück.

Dennis
quelle
4

JavaScript (ES6), 97 Byte

a=>a.map((b,i)=>a.slice(i).map((c,j)=>c.map((d,k)=>(n=(b[k]&=d)&&n+j+1)>r?r=n:0,n=0),c=[]),r=0)|r

Es stellt sich heraus, dass ein bisschen Twiddling noch gewinnt. Akzeptiert ein Array mit ganzen Zahlen. Ungolfed:

function rect(array) {
    var max = 0;
    for (var i = 0; i < array.length; i++) {
        var bits = array[i];
        for (var j = 0; i + j < array.length;) {
            var row = array[i + j];
            j++;
            var size = 0;
            for (var k = 0; k < row.length; k++) {
                if (!row[k]) bits[k] = 0;
                size = ones[k] ? size + j : 0;
                if (size > max) max = size;
            }
        }
    }
    return max;
}

Das Array wird nach den anderen Antworten in Zeilen aufgeteilt, sodass jeder mögliche Zeilenbereich durchlaufen wird. Bei einem gegebenen Zeilenbereich besteht der nächste Schritt darin, die verfügbaren Rechtecke zu messen. Dies wird erreicht, indem die Zeilen bitweise UND-verknüpft werden. das Ergebnis ist eine Liste von Bits, die im gesamten Zeilenbereich gesetzt wurden. Es bleibt dann übrig, die maximale Länge der gesetzten Bits in der Reihe zu finden und diese mit der Höhe des Bereichs zu multiplizieren. Test schamlos von @ ed65 gestohlen:

f=
a=>a.map((b,i)=>a.slice(i).map((c,j)=>c.map((d,k)=>(n=(b[k]&=d)&&n+j+1)>r?r=n:0,n=0),c=[]),r=0)|r

// test cases as strings, converted to 2d arrays
result.textContent = [
  ['0', 0],
  ['1', 1], 
  ['00 00', 0],
  ['01 10', 1],
  ['01 11', 2],
  ['111 010 111', 3],
  ['101 011 111', 4],
  ['0111 1110 1100', 4],
  ['1111111 1110111 1011101', 7],
  ['111011000 110111100 001111110 011111111 001111110 000111100 000011000', 20],
  ['000110000 110110010 110111110 110011100 010011111 111111111 111101110', 12]
].map(t => t[0].replace(/ /g, '\n') + '\n' + t[1] + '\n' + f(t[0].split` `.map(r => [...r]))).join`\n\n`
<pre id=result></pre>

Neil
quelle
1
Ich würde positiv stimmen, aber da Ihr Ruf genau 10000000000000 in binär ist, denke ich, dass ich es eine Weile belassen werde.
Level River St
Ich bin dran, es zu verwirren: D, eine ähnliche Idee kam mir in den Sinn, aber ich komme immer zu spät: p
Abr001am
4

Python 2.7, 93 91 89 81 79 Bytes

f=lambda M,t=1:max(f(M[1:]),f(zip(*M)[::-1],t+1))if`t/3`in`M`else`M`.count(`t`)

Input ist eine Liste von Tupeln. Überprüfen Sie die kleineren Testfälle hier und die größeren Testfälle hier .

Ohne Memo überschreiten die letzten beiden Testfälle das Zeitlimit von Ideone, da sie Aufrufe an f erfordern ( 1.530.831.935 und 2.848.806.121) , was auf meinem Computer 39 und 72 Minuten dauert .

Algorithmus

Für eine gegebene Matrix M besteht die allgemeine Idee darin, über alle Untermatrizen von M zu iterieren, indem obere Reihen entfernt und Viertelumdrehungen gegen den Uhrzeigersinn gedreht werden, wobei die Größe der angetroffenen Untermatrizen verfolgt wird, die vollständig aus 1 Bit bestehen.

Das Golfspielen einer einfachen rekursiven Implementierung der obigen Idee führte zu einer Funktion f (M) , die das Folgende tut.

  1. Wenn M keine enthält 0- Bits enthält, geben Sie die Anzahl der 1- Bits zurück.

  2. Wenn wir M schon zweimal gedreht haben und es keine 1 enthält Bits enthält, geben Sie 0 zurück .

  3. Wenn wir M bereits fünfmal gedreht haben , geben Sie 0 zurück .

  4. Rufen Sie rekursiv f auf M ohne die oberste Zeile auf.

  5. Rufen Sie rekursiv f auf M auf, und drehen Sie es um eine Vierteldrehung gegen den Uhrzeigersinn.

  6. Gibt das Maximum der Rückgabewerte aus den rekursiven Aufrufen zurück.

Code

In der Implementierung verwenden wir ein zusätzliches Funktionsargument t , das standardmäßig 1 ist , um zu verfolgen, wie oft wir diese bestimmte Matrix bereits gedreht haben. Auf diese Weise können Sie die Schritte 1 bis 3 in einem einzigen Schritt zusammenfassen, indem Sie testen ​`t/3`in`M`​und zurückkehren, ​`M`.count(`t`)​wenn der Test fehlschlägt.

  1. Wenn t = 1 ist , haben wir diese bestimmte Untermatrix zuvor in diesem Zweig nicht gedreht.

    T / 3 = 0 , so ​`t/3`in`M`​kehrt Wahr iff der Stringdarstellung von M enthält das Zeichen 0 .

    Wenn es nicht der Fall ist, fahren wir zurück ​`M`.count(`t`)​, die Anzahl der Male das Zeichen 1 erscheint in der String - Darstellung von M .

    Es ist zu beachten, dass eine Matrix ohne 0 Bits nur dann auftreten kann, wenn t = 1 ist , da wir in diesem Fall keine Rekursion durchführen.

  2. Wenn 3 ≤ t ≤ 5 , haben wir diese bestimmte Untermatrix zuvor mindestens zweimal in diesem Zweig gedreht.

    t / 3 = 1 , so ​`t/3`in`M`​wird das Rück Wahr iff die Stringdarstellung M das Zeichen 1 .

    Wenn es nicht der Fall ist, geht es zurück 0 berechnet , wie ​`M`.count(`t`)​die Anzahl , wie oft die Zeichenfolgendarstellung t ( das heißt, das Zeichen 3 , 4 oder 5 ) erscheint in der Stringdarstellung von M .

  3. Wenn t = 6 , haben wir diese Submatrix zuvor fünfmal in diesem Zweig gedreht.

    t / 3 = 2 , so ​`t/3`in`M`​wird wieder falsch , weil die Stringdarstellung von M nicht den Charakter enthält 2 .

    Wir kehren 0 berechnet , wie ​`M`.count(`t`)​die Anzahl , wie oft die Zeichen 6 erscheint in der Zeichenfolgendarstellung M .

Wenn f nicht bereits zurückgekehrt ist, werden die verbleibenden Schritte ausgeführt.

  1. f(M[1:])ruft f auf M ohne die oberste Zeile auf. Da t nicht angegeben ist, ist es standardmäßig 1 , was signalisiert, dass dies das erste Mal ist, dass f auf diese bestimmte Untermatrix in diesem Zweig trifft.

  2. f(zip(*M)[::-1],t+1)ruft f auf M eine viertel Umdrehung gegen den Uhrzeigersinn gedreht und erhöht t , um die Zeit zu verfolgen, die wir für diese bestimmte Untermatrix in diesem Zweig gedreht haben.

    Die Vierteldrehung wird erhalten, indem die Reihen von M miteinander gezippt werden , Tupel der entsprechenden Elemente der Reihen von M zurückgegeben werden , wodurch M transponiert und dann die Reihenreihenfolge umgekehrt wird (dh die obere Reihe wird unten platziert und umgekehrt) ).

  3. Schließlich maxgibt das Maximum der Rückgabewerte aus den rekursiven Aufrufen.

Dennis
quelle
hmm all diese einsendungen sind ausgezeichnete ideen? Ziemlich faszinierend, was macht die Zip-Funktion?
7.
zipgibt eine Liste von Tupeln der entsprechenden Elemente seiner Argumente zurück. Bei einer entpackten 2D-Liste (Matrix) *Mwerden Zeilen und Spalten im Wesentlichen transponiert, sodass zip(*M[::-1])eine 90 ° -Drehung im Uhrzeigersinn ausgeführt wird.
Dennis
thx, Python ist ein Zauber, ich werde es eines Tages lernen.
7.
2

JavaScript (ES6), 154 176

Bearbeiten versucht, ein wenig zu verkürzen, kann sich aber nicht mit der Lösung von @ Neil messen

Probieren Sie jedes mögliche Rechteck aus und geben Sie die maximale Größe zurück. Wahrscheinlich der gleiche Algorithmus wie bei der Matl-Antwort, nur 6-mal länger.
Eingabe als 2D-Array von Ganzzahlen

g=>g.map((r,i)=>r.map((x,j)=>v=s(r,j,(_,l)=>s(g,i,(_,k)=>!s(g,k,r=>s(r,l,x=>!x,l+j+1),k+i+1)))&(t=-~i*-~j)>v?t:v),s=(a,i,l,j)=>a.slice(i,j).some(l),v=0)|v

Weniger golfen

Dies ist der ursprüngliche Algorithmus, die Golf-Version missbraucht eine Menge Array-Traversing-Funktion anstelle von Schleifen

g=>{
  v = 0
  for(i = h = g.length; i; i--)
    for(j = w = g[0].length; j; j--)
    {
      p = true
      for(k=0; p && k <= h-i; k++)
        for(l=0; p && l <= w-j; j++)
          p = g.slice(k, k+i).some(r=>r.slice(l, l+j).some(x=>!x));
      if (!p && i*j<v)
        v = i*j
    }
  return v
}

Prüfung

f=g=>g.map((r,i)=>r.map((x,j)=>v=s(r,j,(_,l)=>s(g,i,(_,k)=>!s(g,k,r=>s(r,l,x=>!x,l+j+1),k+i+1)))&(t=-~i*-~j)>v?t:v),s=(a,i,l,j)=>a.slice(i,j).some(l),v=0)|v

console.log=(...x)=>O.textContent+=x+'\n'

// test cases as strings, converted to 2d arrays
;[
  ['0',0],['1',1],['00 00',0],['01 10',1],['01 11',2],
  ['111 010 111',3],['101 011 111',4],
  ['0111 1110 1100',4],['1111111 1110111 1011101',7],
  ['111011000 110111100 001111110 011111111 001111110 000111100 000011000',20],
  ['000110000 110110010 110111110 110011100 010011111 111111111 111101110',12]
].forEach(t=>{
  var k=t[1]
  var p=t[0].split` `.map(r=>[...r].map(x=>+x))
  var r=f(p)
  console.log((r==k?'OK':'KO')+' '+r+(r==k?'':' expected '+k)+'\n'+p.join`\n`+'\n')
  })
<pre id=O></pre>

edc65
quelle
2

APL (Dyalog Extended) , 27 23 20 Bytes

-3 Bytes von Adám und ngn

{⌈/∊(×/×⍵⍷⍨⍴∘1)¨⍳⍴⍵}

Probieren Sie es online!

{⌈/∊(×/×⍵⍷⍨⍴∘1)¨⍳⍴⍵}    Monadic function taking an argument ⍵:
                 ⍳⍴⍵     Indices: e.g. for a 3x7 array
                                       (1 1) (1 2) ...  (1 7)
                                       (2 1) (2 2)  ... (2 7)
                                       (3 1) (3 2)  ... (3 7)
    (×/×⍵⍷⍨⍴∘1)         Helper fn: Takes  and x (e.g. (2 2))
            ⍴∘1             Make an array of 1s of shape x. Call it a.
        ⍵⍷⍨                 All places where a exists in x
     ×/                      Product of x's dims (size of a)
       ×                 Size of a where a is in ⍵, and 0 elsewhere.
    (×/×⍵⍷⍨⍴∘1)¨        Call the helper function on x and each (¨) index.
                            We now have a nested list containing sizes of blocks in ⍵
                            and many 0s.
   ∊                        Flatten
 ⌈/                        Find the maximum value.
Lirtosiast
quelle
{⌈/,(×/×1∊⍵⍷⍨⍴∘1)¨⍳⍴⍵}ist kürzer und einfacher (benötigt nicht einmal Extended).
Adám
1
@lirtosiast @ Adám{⌈/∊(×/×⍵⍷⍨⍴∘1)¨⍳⍴⍵}
ngn
2

Brachylog , 20 17 15 Bytes

Danke an Kroppeb für 2 Bytes

{s\sc≡ᵛ¹l}ᶠ⌉|hh

Probieren Sie es online!

Erläuterung

{        }ᶠ      Find all possible outputs of the following predicate:
 s                Find a sublist of the array (i.e. remove 0 or more rows from the top
                  and/or bottom)
  \               Transpose the array
   s              Find a sublist again
                  The result is some sub-rectangle of the array
    c             Concatenate all the rows in that rectangle into one list
     ≡ᵛ¹          Verify that all the elements are 1
        l         Get the length (i.e. how many 1's make up the rectangle)
                 Now we have a list of the sizes of all possible 1-rectangles
           ⌉     Take the maximum

            |    If no 1-rectangles could be found:
             hh   Take the head of the head of the array (i.e. the top left element)
                 Since the array contains no 1's in this case, this will give 0
DLosc
quelle
aakann durch s Online testen
Kroppeb
1

R , 129 122 Bytes

function(M,D=dim(M),L=`for`){L(i,1:D,L(j,1:D[2],L(r,0:(D-i),L(c,0:(D[2]-j),F<-max(F,i*j*(i*j==sum(M[r+1:i,c+1:j])))))))
F}

Probieren Sie es online!

Schlichter und einfacher Brute-Force-Ansatz.

Abgerollter Code und Erklärung:

function(M){                       # M is the matrix of 0/1
n = 0                              # n is the biggest rectangle found
R=nrow(M)
C=ncol(M)
for(i in 1:R)                      # for each possible num of rows of the rectangle
  for(j in 1:C)                    # for each possible num of cols of the rectangle
    for(r in 0:(R-i))              # for each possible position offset on the rows
      for(c in 0:(C-j){            # for each possible position offset on the cols

         subM = M[1:i+r,1:j+c]     # sub-set the matrix given the size of rectangle and offsets

         if(sum(subM)==i*j)        # if sub-matrix is full of 1's
            rec = i*j              # (i.e. nrow*ncol == sum of values in sub-matrix)
         else                      # store the rectangle area
            rec = 0                # otherwise store 0

         n = max(n,rec)            # keep the maximum rectangle found
      }
}
digEmAll
quelle
0

Matlab 106 Bytes

x=input('');[n,k]=size(x);r=0;for p=1:n;for m=1:k;r=max([p*m*(any(conv2(x,ones(p,m))==p*m)),r]);end;end;r

Ungolfed:

x=input(''); %//Take input
[n,k]=size(x); %//Determine array size
r=0; %//Variable for output. Initially zero
for p=1:n; %// Loop through the columns
    for m=1:k; %// Loop through the rows
        r=max([p*m*(any(conv2(x,ones(p,m))==p*m)),r]);%//See explanation below
    end;
end;
r %//Display result

Die Operation in der Schleife beginnt mit der 2D-Faltung conv2()des Eingangs-Arrays mit dem p*mEinsen-Array. ==p*mprüft, ob das resultierende Array ein Element gleich enthält p*m. Das entsprechende Element wird gedreht 1, alle anderen Elemente werden gedreht 0. any()verwandelt das Array in einen Vektor. 1Ansonsten werden Spalten mit mindestens einem Eintrag ungleich Null angezeigt 0. p*m*()multipliziert den Vektor, indem p*mall 1-s zu wird p*m. [__,r]Eckige Klammern verketten das erhaltene Ergebnis mit dem vorherigen Maximalbereich, der in gespeichert ist r. Schließlich max()findet den Maximalwert in dem resultierenden Vektor.

brainkz
quelle
Was macht die Funktion überhaupt?
7.
@ Agawa001 für jede Spalte in einem 2D-Array gibt any()zurück, 1ob die Spalte ein Element ungleich Null enthält, 0andernfalls.
Brainkz
0

Matlab (222)(209)

Eigentlich bringt mich diese Lösung in die Schande, dass ich doppelt so groß bin wie die gleiche Sprache, aber ... verdammt, ich hatte 6 Stunden lang darüber nachgedacht! und der Trick ist ein etwas anderer Aufbau als die Antworten von Dennis und Neil.

    function p=g(x,a,u,i,j),i=i+~u;j=j+u;p=0;if(j*u+i*~u>=size(a,2-u))return;end,x=circshift(x,[0-u -1+u]),a=(x+a).*~~x.*~~a;for h=0+u:1,p=max([p,reshape(a(1:end-j,1:end-i),1,[]),g(~u*(a*h+x*~h)+u*x,a,h,i,j)]);end
  • Die Funktion heißt

    y=[1 1 1 0 1 1 0 0 0;
    1 1 0 1 1 1 1 0 0;
    0 0 1 1 1 1 1 1 0;
    0 1 1 1 1 1 1 1 1;
    0 0 1 1 1 1 1 1 0;];
    t=g(y,y,[],0,0,0);t,
    
  • Ich könnte mehr Bytes einsparen, wenn die eingeführte Matrixlänge in die Abmessungen der Funktion eingeht, obwohl mehr Golf gespielt wird.

  • Wie läuft das ab?

    Dieser Algorithmus fügt die eigentliche Matrix selbst hinzu und verschiebt sie mit ein wenig Drehen (&) nach links. In jedem Stadium wird die resultierende Matrix als initial festgelegt und zu sich selbst hinzugefügt, wiederholt nach oben verschoben und dann von Anfang an mit der neuen Matrix neu verschoben. Alle Unterelemente aller durch diese Operation erzeugten Matrizen (original_matrix+shifted_matrix)&shifted_and_original_matrices)werden auf die Ausgabe maximiert.

Beispiel:

     1 1 1         1 1 0                      2 2 0                  0 2 0                        0 4 0
 M0= 0 1 1  M0<<1= 1 1 0  M1=(M0+M0<<1)&both= 0 2 0    shift(M1,up)= 2 0 0  M2=(M1+sh(M1,u)&both= 0 0 0  
     1 1 0         1 0 0                      2 0 0                  0 0 0                        0 0 0
                        2 0 0                               4 0 0
 M3=(M0<<1+M0<<2)&both= 2 0 0 , M4=(M3+shift(M3,up))&both=  0 0 0
                        0 0 0                               0 0 0

                3 0 0                             
 M5=(M1+M0<<2)= 0 0 0 , M6=(M5+shift(M5,up))&both=zeros(3,3).
                0 0 0

 Max_of_all_values=Max(0,1,2,3,4)=4
Abr001am
quelle
0

Japt , 30 Bytes

®åÏ*°X}ÃÕ®£ZãYÄÃm®rm *Zl}Ãc rw

Probieren Sie alle Testfälle aus

Etwa eine Portierung von Dennis 'Jelly-Antwort. Die Testfälle sind einfach 2D-Arrays von Zahlen, die mit dieser Methode aus dem Format der Frage konvertiert werden .

Erläuterung:

®      Ã                          #For each row:
 å    }                           # Replace each number with this running total:
    °X                            #  Increment the previous total
  Ï*                              #  Multiply it by the current number
        Õ                         #Transpose rows and columns
         ®               Ã        #For each column:
          £    Ã                  # Iterate over the range [0..length) as Y:
           ZãYÄ                   #  Get the subsections of that column with length Y+1
                m®      }         # For each subsection:
                  rm              #  Get the minimum
                     *Zl          #  Multiply it by the length
                          c       #Flatten everything to a single list of possible rectangle sizes
                            rw    #Get the maximum
Kamil Drakari
quelle
0

J , 38 Bytes

,"0/&(1+i.)/@$>./@,@:((#**/)@,;._3"$)]

Probieren Sie es online!

Wie

,"0/&(1 + i.)/@$ >./@,@:((# * */)@,;._3"$) ]
              @$                             NB. pass the shape of
                                             NB. the input (rows, cols)
                                             NB. to...
,"0/&(1 + i.)/                               NB. this verb, which will
    &(1 + i.)/                               NB. will first create 2
                                             NB. lists: 1...num rows
                                             NB. and 1...num cols.
,"0/                                         NB. and then creat a cross
                                             NB. of every possible 
                                             NB. concatenation of the two,
                                             NB. giving us all possible 
                                             NB. rectangle sizes. pass 
                                             NB. that and...
                                           ] NB. the original input
                 >./@,@:((# * */)@,;._3"$)   NB. to this verb, which
                                   ;._3"$    NB. will take every 
                                             NB. possible rectangle of
                                             NB. every size,
                                 @,          NB. flatten it and...
                         (# * */)            NB. multiply the size of
                                             NB. the list by the list's 
                                             NB. product, yielding the
                                             NB. size of the list if it's
                                             NB. all ones, zero otherwise.
                     ,@:                     NB. Flatten all those results
                                             NB. into one big list
                 >./@                        NB. and take the max.
Jona
quelle