9

Pertanyaan ini mirip dengan Biggest Square di kotak .

Tantangan

Diberikan matriks 1dan 0dalam format string "xxxx,xxxxx,xxxx,xx.."atau format array ["xxxx","xxxx","xxxx",...], Anda akan membuat fungsi yang menentukan area submatrix persegi terbesar yang berisi semua 1.

Submatrix kuadrat adalah salah satu dari lebar dan tinggi yang sama, dan fungsi Anda harus mengembalikan area submatrix terbesar yang hanya berisi 1.

Sebagai contoh:

Diberikan "10100,10111,11111,10010", ini terlihat seperti matriks berikut:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

Anda dapat melihat bolded 1membuat submatrix kuadrat terbesar dengan ukuran 2x2, sehingga program Anda harus mengembalikan area yang 4.

Aturan

Submatrix harus memiliki lebar dan tinggi yang sama
Submatrix harus hanya berisi nilai 1
Fungsi Anda harus mengembalikan area submatrix terbesar
Jika tidak ada submatrix yang ditemukan, kembalikan 1
Anda dapat menghitung area submatrix dengan menghitung jumlah 1dalam submatrix

Uji kasus

Input: "10100,10111,11111,10010" Keluaran: 4

Input: "0111,1111,1111,1111" Keluaran: 9

Input "0111,1101,0111" Output: 1

Ini adalah kode-golf , jadi jawaban tersingkat dalam byte menang.

code-golf matrix Luis felipe De jesus Munoz
sumber

3

Mengapa format string?

Stewie Griffin

3

Bisakah kita mengambil input sebagai matriks biner (numerik)?

Stewie Griffin

5

Untuk [0] masih diperlukan untuk output 1?

14m2

6

Tunggu sebentar, mengapa mengembalikan 1 ketika tidak ada semua-1 sub-matriks ditemukan, bukankah 0 lebih masuk akal? (Kalau tidak itu hanya kasus khusus untuk menangani)

Jonathan Allan

2

Seperti berdiri saya pikir kedua penjawab tidak akan keberatan jika Anda mengubah spesifikasi dan saya sangat menyarankan melakukannya karena tidak ada gunanya mengembalikan 1 dan itu tidak membuat pengiriman lebih menarik.

ბიმო

2

Jelly , 18 byte

_{+2 untuk menangani output hadir sublist no-all-1}

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

Cobalah online! Atau lihat test-suite

Bagaimana?

Ẇ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)

Jonathan Allan
sumber

Luar biasa. Bisakah Anda menambahkan beberapa penjelasan?

Luis felipe De jesus Munoz

Aku akan, aku mencoba memikirkan yang lebih pendek dulu ...

Jonathan Allan

@ Mr.Xcoder Saya telah memperbarui untuk menangani persyaratan untuk saat ini

Jonathan Allan

5

Haskell , 113 121 118 117 byte

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]

Cobalah online!

_{-3 byte terima kasih kepada Laikoni !}

_{-1 byte terima kasih kepada Lynn !}

_{+8 byte untuk persyaratan konyol mengembalikan 1 tanpa sub-matriks semua-1 ..}

Penjelasan / Tidak Diundang

Fungsi pembantu berikut ini hanya membuat offset untuk xmemungkinkan untuk mengurangi mereka dengan s:

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

x#yakan ymengeluarkan elemen dari daftar lalu mengambil x:

t#d=take t.drop d

Fungsi floop atas semua ukuran yang mungkin untuk sub-matriks secara berurutan, menghasilkan setiap sub-matriks dari ukuran yang sesuai, menguji apakah hanya berisi '1's dan menyimpan ukuran. Dengan demikian solusinya akan menjadi entri terakhir dalam daftar:

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

ბიმო
sumber

4

Haskell , 99 97 byte

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

Periksa apakah input adalah matriks kuadrat dari orang-orang dengan s==('1'<$s<$s), jika ya, jawabannya adalah panjang ^ 2, atau 0. Kemudian secara rekursif memotong pertama / kolom terakhir / baris dan mengambil nilai maksimum yang ditemukan di mana saja.

Cobalah online!

Angs
sumber

3

K (ngn / k) , 33 28 byte

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

Cobalah online!

ngn
sumber

Saya tidak pernah tahu Anda memiliki versi K!

Zacharý

3

J , 33 27 byte

-6 byte terima kasih kepada FrownyFrog!

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

Cobalah online!

Penjelasan:

Saya akan menggunakan test case pertama dalam penjelasan saya:

    ] 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

Saya menghasilkan semua kemungkinan pendatang persegi dengan ukuran dari 1 hingga jumlah baris input.

,~@#\membuat daftar pasangan untuk ukuran submatrices dengan menjahit ,.togehter panjang awalan berurutan #\input:

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

Lalu saya menggunakannya untuk memotong x u ;. _3 yinput menjadi submatrices. Saya sudah punya x(daftar ukuran); yadalah argumen yang tepat ](input).

 ((,~@#\)<;._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│   │ │
├─────┼─────┼─────┼───┼─┤
│     │     │     │   │ │
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│     │     │     │   │ │
└─────┴─────┴─────┴───┴─┘

Untuk setiap submatrix saya periksa apakah seluruhnya terdiri dari 1s: (#**/)@,- ratakan matriks, dan gandakan jumlah item dengan produk mereka. Jika semua item adalah 1d, hasilnya akan menjadi jumlah mereka, jika tidak - 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

Akhirnya saya meratakan daftar hasil untuk setiap submatrix dan menemukan maksimum:

>./@,

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

Galen Ivanov
sumber

1

,~@#\dan "1 2->"$

FrownyFrog

@FrownyFrog Terima kasih! Saya tidak tahu tentang"$

Galen Ivanov

1

#lebih pendek dari menjumlahkan 1s.

FrownyFrog

@ FrownyFrog Hmm, benar-benar. Keren Terimakasih!

Galen Ivanov

3

APL (Dyalog Unicode) , 35 34 32 byte

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

Cobalah online!

SBCS Adám memiliki semua karakter dalam kode

Penjelasan akan datang akhirnya!

Zacharý
sumber

2

Retina , 143 byte

%`$
,;#
+%(`(\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

Cobalah online! Tautan termasuk kasus uji. Mengambil input sebagai string yang dipisahkan koma. Penjelasan:

%`$
,;#

Tambahkan a ,untuk mengakhiri string terakhir, a ;untuk memisahkan string dari #s dan a #sebagai penghitung.

+%(`
)

Ulangi blok sampai tidak ada lagi subsitusi (karena setiap string sekarang hanya memiliki satu digit).

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

Rangkap tiga baris, atur penghitung ke 1 di baris pertama dan tambahkan di baris terakhir.

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

Di baris pertama, hapus digit pertama dari setiap string, sementara di baris kedua, hapus semua digit kecuali yang pertama.

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

Pada baris ketiga, bitwise dan dua digit pertama bersamaan.

1,
#

Pada titik ini, setiap baris terdiri dari dua nilai, a) penghitung lebar horisontal dan b) bitwise dan dari itu banyak bit diambil dari setiap string. Konversikan sisa 1s menjadi #s sehingga dapat dibandingkan dengan penghitung.

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

Temukan sembarang bit (vertikal) yang cocok dengan penghitung (horizontal), sesuai dengan kuadrat 1s pada input asli, dan kuadratkan panjangnya.

N`

Sortir secara numerik.

-1G`

Ambil yang terbesar.

^$
1

Huruf nol matriks khusus.

Neil
sumber

2

JavaScript, 92 byte

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

Tampilkan cuplikan kode

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'));

Luaskan cuplikan

tsh
sumber

2

APL (Dyalog Classic) , 21 20 byte

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

Cobalah online!

ngn
sumber

Pengulangan! Bagus!

Zacharý

@ Zacharý Terima kasih. Sebenarnya, daripada rekursi saya lebih suka sesuatu seperti k's f \ x untuk f monadik, yaitu (x; fx; ffx; ...) sampai konvergensi, tetapi tidak ada yang setara dalam APL (belum). Melakukannya dengan ⍣≡ membutuhkan terlalu banyak byte.

ngn

2

Python 2 , 117 109 byte

Kredit ke @etene untuk menunjukkan inefisiensi yang membuat saya byte tambahan.

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

Cobalah online!

Mengambil input sebagai string yang dipisahkan koma. Ini adalah pendekatan berbasis regex yang mencoba mencocokkan string input terhadap pola formulir 111.....111.....111untuk semua ukuran yang mungkin dari kuadrat.

Dalam perhitungan saya, melakukan ini dengan lambda anonim hanya sedikit lebih pendek dari fungsi yang ditentukan atau program lengkap. Bagian or 1pada akhirnya hanya diperlukan untuk menangani case edge yang aneh, di mana kita harus menampilkan 1jika tidak ada yang ada di input.

Kirill L.
sumber

2

Python 2 , 116 115 117 109 byte

Kredit ke @ Kirill untuk membantu saya golf lebih dan untuk solusi pintar & awal nya

Edit : Golf 1 byte dengan menggunakan lambda, saya tidak tahu menugaskannya ke variabel tidak dihitung terhadap jumlah byte.

Sunting 2 : Kirill menunjukkan solusi saya tidak berfungsi untuk kasus di mana input hanya berisi 1s, saya harus memperbaikinya dan kehilangan dua byte berharga ...

Edit 3 : lebih banyak bermain golf berkat Kirill

Mengambil string yang dipisahkan koma, mengembalikan integer.

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

Cobalah online!

Saya secara mandiri menemukan jawaban yang dekat dengan jawaban Kiril, yaitu berdasarkan regex, kecuali yang saya gunakan re.search ~~dan adef~~ .

Ini menggunakan regex yang dibangun selama setiap loop untuk mencocokkan kuadrat yang lebih besar secara bertahap dan mengembalikan yang terbesar, atau 1.

etene
sumber

1

Bagus, entah bagaimana saya secara otomatis membuang ifpendekatan sebagai "terlalu lama pasti", tetapi kemudian harus membuat beberapa cara lain untuk membuat nilai bool dari pertandingan. Sayangnya, solusi Anda kehilangan satu poin - Anda tidak bisa hanya memiliki range(l)- itu akan kehilangan kasus ketika tidak ada nol sama sekali. Misalnya, ambil test case ke-2 dan jadikan semuanya 1 - ini harus menjadi 16, bukan 9.

Kirill L.

Sial, saya berpikir tentang pengujian dengan semua nol tetapi tidak dengan semua (tidak pernah disebutkan dalam tantangan ...). Saya akan mencoba untuk membuat sesuatu.

etene

@ KirillL. omong-omong, kamu cepat! Saya masih mengerjakan jawaban saya ketika Anda memposting jawaban Anda dan sedikit kecewa (dan bangga!) Ketika saya melihat pendekatan kami serupa ... tingkat di sini mengesankan.

etene

1

Golf beberapa byte lagi dengan menyingkirkan duplikasi find. Sekarang kode kita tidak identik lagi, saya sarankan kita setidaknya memperbaiki kesalahan yang jelas dari satu sama lain - dalam kasus Anda byte tambahan berasal dari menggunakan tuple, ("1"*i,)bukan daftar.

Kirill L.

Terima kasih, ya tuple yang tidak berguna itu cukup bodoh di pihak saya. Dan ekstra findjuga, itu pintar kamu.

etene

2

Ruby `-n` , 63 byte

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

Cobalah online!

Versi Ruby dari jawaban Python saya . Golfier sebagai program lengkap. Atau, lambda anonim:

Ruby , 70 68 byte

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

Cobalah online!

Kirill L.
sumber

1

Perl 6 , 61 60 58 byte

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

Cobalah online!

nwellnhof
sumber

1

Python 2 , 138 128 byte

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

Cobalah online!

Diselamatkan

-10 byte berkat ovs

TFeld
sumber

1

Clojure, 193 byte

#(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, segalanya meningkat: o

Kurang golf:

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

NikoNyrh
sumber

Kotak terbesar

Jawaban:

Jelly , 18 byte

Bagaimana?

Haskell , 113 121 118 117 byte

Penjelasan / Tidak Diundang

Haskell , 99 97 byte

K (ngn / k) , 33 28 byte

J , 33 27 byte

Penjelasan:

APL (Dyalog Unicode) , 35 34 32 byte

Retina , 143 byte

JavaScript, 92 byte

APL (Dyalog Classic) , 21 20 byte

Python 2 , 117 109 byte

Python 2 , 116 115 117 109 byte

Ruby `-n` , 63 byte

Ruby , 70 68 byte

Perl 6 , 61 60 58 byte

Python 2 , 138 128 byte

Clojure, 193 byte

Kotak terbesar

Jawaban:

Jelly , 18 byte

Bagaimana?

Haskell , 113 121 118 117 byte

Penjelasan / Tidak Diundang

Haskell , 99 97 byte

K (ngn / k) , 33 28 byte

J , 33 27 byte

Penjelasan:

APL (Dyalog Unicode) , 35 34 32 byte

Retina , 143 byte

JavaScript, 92 byte

APL (Dyalog Classic) , 21 20 byte

Python 2 , 117 109 byte

Python 2 , 116 115 117 109 byte

Ruby -n , 63 byte

Ruby , 70 68 byte

Perl 6 , 61 60 58 byte

Python 2 , 138 128 byte

Clojure, 193 byte

Ruby `-n` , 63 byte