Potong latar belakang yang mengganggu itu!

13

Bukankah ini mengganggu ketika Anda mengambil foto, tetapi latar belakangnya mengurangi substansi gambar yang sebenarnya? Saya akan mengatakan begitu. Saya perlu tahu berapa banyak yang harus saya potong agar saya dapat mengatasi masalah ini! Tapi - seperti biasa - saya cukup malas, jadi saya butuh seseorang untuk melakukan ini untuk saya ...

Tugas & Aturan

Diberikan matriks biner yang mewakili gambar, output dimensi (lebar dan tinggi) dari sub-matriks terkecil yang berisi semua 1 s dalam matriks asli. Sebuah sub-matriks adalah sebuah blok dari entri yang berdekatan dari matriks asli. Secara ekivalen, ini adalah matriks baru yang dibentuk dengan tumpang tindih subset dari baris yang berdekatan dan subset dari kolom yang berdekatan dari aslinya.

  • Dimungkinkan untuk mengambil lebar dan tinggi matriks sebagai input juga.
  • Input dijamin mengandung setidaknya satu 1 .
  • Anda dapat mengambil input dan memberikan output melalui metode standar apa pun , sambil memperhatikan bahwa celah ini dilarang secara default. Ini adalah , jadi cobalah untuk menyelesaikan tugas dalam byte paling sedikit yang dapat Anda kelola dalam bahasa pilihan Anda.

Contoh

[000000010100011011001010000000][101001101101010](5,3)

Uji kasus

Masukan | Keluaran

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

[[0,0,0,0,0], [0,1,0,1,0], [0,0,1,0,0]]
-> (3,2) atau (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) atau (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) atau (3,5)
Tuan Xcoder
sumber
1
Ini terasa sangat akrab; apakah itu di Sandbox sebentar?
Shaggy
8
Ini memang sangat dekat dengan pertanyaan terkait tetapi saya pikir itu dapat dianggap sebagai subset yang cukup jauh karena menghasilkan matriks tidak mutlak diperlukan untuk menghitung lebar dan tinggi sebenarnya. Misalnya, salah satu algoritma yang mungkin adalah menghitung jumlah minimal nol marginal untuk setiap baris dan kolom dan mengurangi yang dari dimensi asli.
Tn. Xcoder

Jawaban:

5

APL (Dyalog Unicode) , 10 byte SBCS

Fungsi awalan diam-diam anonim.

(1+⌈/-⌊/)⍸

Cobalah online!

 indeks 1s.

(... ) terapkan fungsi tersembunyi berikut untuk itu:

⌊/ minimum ( koordinat y terendah dan koordinat x terendah )

⌈/- minus maksimum yang (ini memberi kami kisaran)

1+ satu plus itu (termasuk)

Adm
sumber
5

Oktaf , 57 56 45 byte

Ini finddia angkat berat: Ini findsadalah baris dan kolom yang berisi entri bukan-nol. Maka kita hanya perlu menemukan perbedaan antara maksimum dan minimum (plus satu) untuk masing-masing secara terpisah.

Terima kasih @beaker dan @AndrasDeak untuk -1 byte, dan @LuisMendo untuk -11 byte!

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

Cobalah online!

cacat
sumber
3

Python 2 , 92 86 byte

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)

Cobalah online!

Chas Brown
sumber
3

Jelly , 7 byte

S,§t€0Ẉ

Cobalah online!

Bagaimana itu bekerja

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
sumber
3

Python 2 ,  63  55 byte

-8 dengan bantuan dari Vincent (gunakan matriks input sebagai array Numpy)

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

Fungsi yang tidak disebutkan namanya menerima 2-d Numpy array of integer (in {0,1}) yang mengembalikan daftar integer [width,height],.

Cobalah online!


Versi Non-Numpy dalam 63 byte (menerima daftar daftar bilangan bulat di {0,1} ):

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

Cobalah online!

Bagaimana?

Mengingat matriks, a, formasing-masing ( v) dari transpos, zip(*a)dana itu sendiri kita menemukan ketinggian yang diperlukan (mengingat transpose ini adalah lebar).

Pemetaan maxdi seluruh vmenghasilkan daftar nol dan yang, mewakili jika setiap baris vberisi yang ada. Representasi string dari daftar ini ditemukan menggunakan backticks ( `...`), ini memberikan string dengan leading [, lalu nol dan yang dibatasi oleh , (koma + spasi). Kami mengiris string ini mulai dari indeks satu di langkah tiga menggunakan [1::3]kami mendapatkan string hanya nol dan yang, yang memungkinkan kami untuk menggunakan fungsi string stripuntuk menghapus nol luar ( strip('0')).

Sebagai contoh:

      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
sumber
57 byte menggunakan array numpy.
Vincent
Jika kita mengambil input sebagai tipe non-built-in, bukankah kita harus menghitung semacam pernyataan impor untuk memungkinkan kita melakukannya? (Mungkin saja kita harus memberi judul posting sebagai "Python 2 dengan numpy" - Saya tidak sepenuhnya yakin) ... jika Anda punya waktu, bisakah Anda bertanya di ruang obrolan byte kesembilan belas?
Jonathan Allan
1
... juga 55 byte, kan?
Jonathan Allan
1
Saya tidak bisa menemukan jawaban yang jelas di PPCG Meta , jadi saya tidak yakin tentang ini. Dan ya, 55 byte memang :)
Vincent
1
Saya hanya bertanya. Menurut pos ini , impor tidak harus dimasukkan.
Vincent
1

Retina 0.8.2 , 83 byte

+`^0+¶|¶0+$

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

Cobalah online! Penjelasan:

+`^0+¶|¶0+$

Hapus baris nol di depan dan di belakang.

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

Hapus semua 0pada baris di atas yang terakhir. Hapus semua 1keduanya, tetapi ubah digit di bawahnya pada baris berikutnya menjadi 1dalam kasus itu. Ini bitwise atau baris bersama.

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

Hitung jumlah baris sebagai jumlah baris baru ditambah 1 dan jumlah kolom sebagai jumlah digit antara 1 dan terakhir.

Neil
sumber
1

J , 31 byte

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

Cobalah online!

Penjelasan:

                            ^:_ - 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
sumber
1

q / kdb +, 16 byte

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

Mathematica, 34 byte

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

Fungsi murni. Mengambil daftar integer yang bersarang sebagai input, dan mengembalikan daftar dua integer (tinggi diikuti oleh lebar) sebagai output. Karakter Unicode adalah U + F3C7 untuk \[Transpose].

LegionMammal978
sumber
1

R , 48 46 byte

function(m)1+diff(apply(which(m>0,T),2,range))

Cobalah online!

-2 byte disimpan oleh Giuseppe.

Kirill L.
sumber
1

05AB1E , 11 9 byte

ζ‚Oε0Û0Üg

-2 byte terima kasih kepada @ Mr.Xcoder .

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

ζ            # 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
sumber
1
ζ‚Oε0Û0Ügmenghemat 2 byte.
Tn. Xcoder
@ Mr.Xcoder Ah, tentu saja. Saya sudah tidak terlalu senang dengan swap itu. Tidak percaya saya tidak berpikir tentang melakukan pasangan pertama dan daripada jumlah ..>.>
Kevin Cruijssen
0

Haskell , 76 byte

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

Cobalah online!

Laikoni
sumber
0

Japt, 16 15 byte

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

Cobalah atau jalankan semua test case


Penjelasan

[   ]               :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
Shaggy
sumber
0

Ruby , 60 byte

->m{[m,m.transpose].map{|x|x.map(&:max).join[/1.*/]=~/0*$/}}

Cobalah online!

GB
sumber