To pytanie jest podobne do największego kwadratu w siatce .

Wyzwanie

Biorąc pod uwagę macierz 1iw 0formacie łańcuchowym "xxxx,xxxxx,xxxx,xx.."lub tablicowym ["xxxx","xxxx","xxxx",...], utworzysz funkcję, która określa obszar największej kwadratowej submatrix zawierającej wszystko 1.

Kwadratowa submatrix ma taką samą szerokość i wysokość, a twoja funkcja powinna zwrócić obszar największej submatrix, który zawiera tylko 1.

Na przykład:

Biorąc pod uwagę "10100,10111,11111,10010", wygląda to następująco:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

Możesz zobaczyć pogrubioną czcionkę, która 1tworzy największą kwadratową submatrix o rozmiarze 2x2, więc twój program powinien zwrócić obszar o wartości 4.

Zasady

• Submatrix musi mieć taką samą szerokość i wysokość
• Podmacierz musi zawierać tylko wartości 1
• Twoja funkcja musi zwrócić obszar największej submatrix
• Jeśli nie zostanie znaleziona submatrix, zwróć 1
• Możesz obliczyć obszar submatrix, licząc liczbę 1w submatrix

Przypadki testowe

Wejście: "10100,10111,11111,10010" Wyjście: 4

Wejście: "0111,1111,1111,1111" Wyjście: 9

Dane "0111,1101,0111" wyjściowe: 1

To jest golf-golf, więc wygrywa najkrótsza odpowiedź w bajtach.

Galaretka , 18 bajtów

_{+2 do obsługi wyjścia wyjściowego podlisty „nie wszystko”}

ẆZṡ¥"L€$ẎȦÐfL€Ṁ²»1

Wypróbuj online! Lub zobacz pakiet testowy

W jaki sposób?

ẆZṡ¥"L€$ẎȦÐfL€Ṁ²»1 - Link: list of lists of 1s and 0s
Ẇ                  - all slices (lists of "rows") call these S = [s1,s2,...]
       $           - last two links as a monad:
     L€            -   length of each (number of rows in each slice) call these X = [x1, x2, ...]
    "              -   zip with (i.e. [f(s1,x1),f(s2,x2),...]):
   ¥               -     last two links as a dyad:
 Z                 -       transpose (get the columns of the current slice)
  ṡ                -       all slices of length xi (i.e. squares of he slice)
        Ẏ          - tighten (to get a list of the square sub-matrices)
          Ðf       - filter keep if:
         Ȧ         -   any & all (all non-zero when flattened?)
            L€     - length of €ach (the side length)
              Ṁ    - maximum
               ²   - square (the maximal area)
                »1 - maximum of that and 1 (to coerce a 0 found area to 1)

Haskell , 113 121 118 117 bajtów

x!s=[0..length x-s]
t#d=take t.drop d
f x=last$1:[s*s|s<-min(x!0)$x!!0!0,i<-x!!0!s,j<-x!s,all(>'0')$s#i=<<(s#j)x,s>0]

Wypróbuj online!

_{-3 bajty dzięki Laikoni !}

_{-1 bajt dzięki Lynn !}

_{+8 bajtów za absurdalny wymóg zwrócenia 1 dla podmacierzy all-1s.}

Wyjaśnienie / Niegolfowany

Następująca funkcja pomocnicza tworzy po prostu przesunięcia xumożliwiające ich zmniejszenie s:

x!s=[0..length x-s]

x#yusunie yelementy z listy, a następnie weźmie x:

t#d=take t.drop d

Funkcja fzapętla wszystkie możliwe rozmiary podmacierzy w kolejności, generuje każdą podmacierz o odpowiednim rozmiarze, sprawdza, czy zawiera tylko '1's i zapisuje rozmiar. Tak więc rozwiązaniem będzie ostatni wpis na liście:

--          v prepend a 1 for no all-1s submatrices
f x= last $ 1 : [ s*s
                -- all possible sizes are given by the minimum side-length
                | s <- min(x!0)$x!!0!0
                -- the horizontal offsets are [0..length(x!!0) - s]
                , i <- x!!0!s
                -- the vertical offsets are [0..length x - s]
                , j <- x!s
                -- test whether all are '1's
                , all(>'0') $
                -- from each row: drop first i elements and take s (concatenates them to a single string)
                              s#i =<<
                -- drop the first j rows and take s from the remaining
                                      (s#j) x
                -- exclude size 0...........................................
                , s>0
                ]

Haskell , 99 97 bajtów

b s@((_:_):_)=maximum$sum[length s^2|s==('1'<$s<$s)]:map b[init s,tail s,init<$>s,tail<$>s]
b _=1

Sprawdza, czy dane wejściowe są macierzą kwadratową tylko tych z s==('1'<$s<$s), jeśli tak, odpowiedź ma długość ^ 2, w przeciwnym razie 0. Następnie rekurencyjnie przecina pierwszą / ostatnią kolumnę / wiersz i przyjmuje maksymalną wartość, jaką znajdzie gdziekolwiek.

Wypróbuj online!

K (ngn / k) , 33 28 bajtów

{*/2#+/|/',/'{0&':'0&':x}\x}

Wypróbuj online!

J , 33 27 bajtów

-6 bajtów dzięki FrownyFrog!

[:>./@,,~@#\(#**/)@,;._3"$]

Wypróbuj online!

Wyjaśnienie:

W wyjaśnieniu użyję pierwszego przypadku testowego:

    ] a =. 3 5$1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1

Generuję wszystkie możliwe kwadratowe submatrice o rozmiarze od 1 do liczby rzędów danych wejściowych.

,~@#\tworzy listę par dla rozmiarów podmacierzy, ,.łącząc je, aby długość kolejnych prefiksów #\danych wejściowych:

   ,~@#\ a
1 1
2 2
3 3

Następnie używam ich do cięcia x u ;. _3 ydanych wejściowych na podmacierze. Mam już x(listę rozmiarów); yjest właściwym argumentem ](dane wejściowe).

 ((,~@#\)<;._3"$]) a
┌─────┬─────┬─────┬───┬─┐
│1    │0    │1    │0  │0│
│     │     │     │   │ │
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│1    │0    │1    │1  │1│
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│1    │1    │1    │1  │1│
└─────┴─────┴─────┴───┴─┘

┌─────┬─────┬─────┬───┬─┐
│1 0  │0 1  │1 0  │0 0│ │
│1 0  │0 1  │1 1  │1 1│ │
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│1 0  │0 1  │1 1  │1 1│ │
│1 1  │1 1  │1 1  │1 1│ │
├─────┼─────┼─────┼───┼─┤
│     │     │     │   │ │
└─────┴─────┴─────┴───┴─┘

┌─────┬─────┬─────┬───┬─┐
│1 0 1│0 1 0│1 0 0│   │ │
│1 0 1│0 1 1│1 1 1│   │ │
│1 1 1│1 1 1│1 1 1│   │ │
├─────┼─────┼─────┼───┼─┤
│     │     │     │   │ │
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│     │     │     │   │ │
└─────┴─────┴─────┴───┴─┘

Dla każdej submatrix sprawdzam, czy składa się ona w całości z 1: (#**/)@,- spłaszcz macierz i mnoż liczbę przedmiotów według ich produktu. Jeśli wszystkie elementy mają wartość 1, wynikiem będzie ich suma, w przeciwnym razie - 0:

   (#**/)@, 3 3$1 0 0 1 1 1 1 1 1
0
   (#**/)@, 2 2$1 1 1 1
4 

   ((,~@#\)(+/**/)@,;._3"$]) a
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1

0 0 0 0 0
0 0 4 4 0
0 0 0 0 0

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

Na koniec spłaszczam listę wyników dla każdej submatrix i znajduję maksimum:

>./@,

   ([:>./@,,~@#\(+/**/)@,;._3"$]) a
4

APL (Dyalog Unicode) , 35 34 32 bajty

{⌈/{×⍨⍵×1∊{∧/∊⍵}⌺⍵ ⍵⊢X}¨⍳⌊/⍴X←⍵}

Wypróbuj online!

SBCS Adáma ma wszystkie znaki w kodzie

Wyjaśnienie nadchodzi w końcu!

Siatkówka , 143 bajty

%`$
,;#
+%(`(\d\d.+;#)#*
$1¶$&¶$&#
\G\d(\d+,)|\G((;#+¶|,)\d)\d+
$1$2
)r`((11)|\d\d)(\d*,;?#*)\G
$#2$3
1,
#
Lv$`(#+).*;\1
$.($.1*$1
N`
-1G`
^$
1

Wypróbuj online! Link zawiera przypadki testowe. Pobiera dane wejściowe jako ciągi rozdzielone przecinkami. Wyjaśnienie:

%`$
,;#

Dodaj a, ,aby zakończyć ostatni ciąg, a, ;aby oddzielić ciągi od #si #jako a jako licznik.

+%(`
)

Powtarzaj blok, aż nie dojdzie już do żadnych zmian (ponieważ każdy ciąg ma teraz tylko jedną cyfrę).

(\d\d.+;#)#*
$1¶$&¶$&#

Potrój trzykrotnie linię, ustawiając licznik na 1 w pierwszym wierszu i zwiększając go w ostatnim wierszu.

\G\d(\d+,)|\G((;#+¶|,)\d)\d+
$1$2

W pierwszym wierszu usuń pierwszą cyfrę każdego ciągu, a w drugim wierszu usuń wszystkie cyfry oprócz pierwszej.

r`((11)|\d\d)(\d*,;?#*)\G
$#2$3

W trzeciej linii bitowo i pierwsze dwie cyfry razem.

1,
#

W tym momencie każda linia składa się z dwóch wartości: a) licznika szerokości poziomej ib) bitowego oraz tylu bitów pobranych z każdego łańcucha. Konwertuj pozostałe 1s na #s, aby można je było porównać z licznikiem.

Lv$`(#+).*;\1
$.($.1*$1

Znajdź dowolne przebiegi bitów (pionowo), które pasują do licznika (poziomo), odpowiadające kwadratom 1s na oryginalnym wejściu, i wyprostuj długość.

N`

Sortuj numerycznie.

-1G`

Weź największy.

^$
1

Specjalny przypadek macierzy zerowej.

JavaScript, 92 bajty

a=>(g=w=>a.match(Array(w).fill(`1{${w}}`).join(`..{${W-w}}`))?w*w:g(w-1))(W=a.indexOf`,`)||1

f=
a=>(g=w=>a.match(Array(w).fill(`1{${w}}`).join(`..{${W-w}}`))?w*w:g(w-1))(W=a.indexOf`,`)||1
console.log(f('0111,1111,1111,1111'));
console.log(f('10100,10111,11111,10010'));
console.log(f('0111,1101,0111'));

APL (Dyalog Classic) , 21 20 bajtów

×⍨{1∊⍵:1+∇2×/2×⌿⍵⋄0}

Wypróbuj online!

Python 2 , 117 109 bajtów

Podziękowania dla @etene za wskazanie nieefektywności, która kosztowała mnie dodatkowy bajt.

lambda s:max(i*i for i in range(len(s))if re.search(("."*(s.find(',')-i+1)).join(["1"*i]*i),s))or 1
import re

Wypróbuj online!

Pobiera dane wejściowe jako ciąg rozdzielany przecinkami. Jest to podejście oparte na wyrażeniach regularnych, które próbuje dopasować ciąg wejściowy do wzorców formularza 111.....111.....111dla wszystkich możliwych rozmiarów kwadratu.

W moich obliczeniach robienie tego z anonimową lambda jest tylko odrobinę krótsze niż zdefiniowana funkcja lub pełny program. or 1Część w końcu jest tylko niezbędne do obsługi dziwny przypadek krawędzi, gdzie musimy wyjście 1, jeżeli nie ma w nich wejścia.

Python 2 , 116 115 117 109 bajtów

Podziękowania dla @Kirill za to, że pomógł mi jeszcze bardziej w golfa i za jego sprytne i wczesne rozwiązanie

Edycja : 1-bajtowy golf za pomocą lambda, nie wiedziałem, że przypisanie go do zmiennej nie wlicza się do liczby bajtów.

Edycja 2 : Kirill wskazał, że moje rozwiązanie nie działa w przypadkach, w których dane wejściowe zawierają tylko 1s, musiałem to naprawić i straciłem dwa cenne bajty ...

Edycja 3 : więcej golfa dzięki Kirill

Bierze ciąg oddzielony przecinkami, zwraca liczbę całkowitą.

lambda g:max(i*i for i in range(len(g))if re.search(("."*(g.find(",")+1-i)).join(["1"*i]*i),g))or 1
import re

Wypróbuj online!

Niezależnie znalazłem odpowiedź, która jest zbliżona do odpowiedzi Kirila, tj. Oparta na wyrażeniach regularnych, z wyjątkiem tego, że używam re.search i adef .

Używa wyrażenia regularnego zbudowanego podczas każdej pętli, aby dopasować przyrostowo większy kwadrat i zwraca największy, lub 1.

Rubinowy -n , 63 bajty

p (1..l=$_=~/,|$/).map{|i|/#{[?1*i]*i*(?.*(l-i+1))}/?i*i:1}.max

Wypróbuj online!

Wersja Ruby mojej odpowiedzi w języku Python . Golfier jako pełny program. Alternatywnie, anonimowa lambda:

Rubinowy , 70 68 bajtów

->s{(1..l=s=~/,|$/).map{|i|s=~/#{[?1*i]*i*(?.*(l-i+1))}/?i*i:1}.max}

Wypróbuj online!

Perl 6 , 61 60 58 bajtów

{(^$_ X.. ^$_).max({[~&](.[|$^r||*])~~/$(1 x$r)/&&+$r})²}

Wypróbuj online!

Python 2 , 138 128 bajtów

def f(m):j=''.join;L=j(m);k=map(j,zip(*m));return len(L)and max(len(L)*(len(m)**2*'1'==L),f(k[1:]),f(k[:-1]),f(m[1:]),f(m[:-1]))

Wypróbuj online!

Zapisano

• -10 bajtów dzięki ovs

Clojure, 193 bajtów

#(apply max(for [f[(fn[a b](take-while seq(iterate a b)))]R(f next %)R(f butlast R)n[(count R)]c(for[i(range(-(count(first R))n -1)):when(apply = 1(for[r R c(subvec r i(+ i n))]c))](* n n))]c))

Wow, rzeczy się eskalowały: o

Mniej golfa:

(def f #(for [rows (->> %    (iterate next)    (take-while seq)) ; row-postfixes
              rows (->> rows (iterate butlast) (take-while seq)) ; row-suffixes
              n    [(count rows)]
              c    (for[i(range(-(count(first rows))n -1)):when(every? pos?(for [row rows col(subvec row i(+ i n))]col))](* n n))] ; rectangular subsections
          c))