Temukan submatrix dengan mean terkecil

21

Anda diberi matriks bilangan bulat n-by-m , dengan n, m> 3 . Tugas Anda adalah menemukan 3-oleh-3 sub-matriks yang memiliki rata-rata terendah, dan menampilkan nilai ini.

Aturan dan klarifikasi:

  • Bilangan bulat akan menjadi non-negatif
  • Input dan format output opsional
  • Keluaran harus akurat hingga minimal 2 desimal (jika bukan bilangan bulat)
  • Kiriman harus terdiri dari baris dan kolom berturut-turut

Kasus uji:

35    1    6   26   19   24
 3   32    7   21   23   25
31    9    2   22   27   20
 8   28   33   17   10   15
30    5   34   12   14   16
 4   36   29   13   18   11 

Minimum mean: 14

100    65     2    93
  3    11    31    89
 93    15    95    65
 77    96    72    34

Minimum mean: 46.111

1   1   1   1   1   1   1   1
1   1   1   1   1   1   1   1
1   1   1   1   1   1   1   1
1   1   1   1   1   1   1   1

Minimum mean: 1

4   0   0   5   4
4   5   8   4   1
1   4   9   3   1
0   0   1   3   9
0   3   2   4   8
4   9   5   9   6
1   8   7   2   7
2   1   3   7   9

Minimum mean: 2.2222

Ini adalah sehingga kode terpendek dalam setiap bahasa menang. Saya mendorong orang untuk mengirim jawaban dalam bahasa yang sudah digunakan, meskipun itu tidak lebih pendek dari yang pertama.

Stewie Griffin
sumber
Juga akan menarik untuk memiliki tantangan dengan baris dan kolom yang tidak berdekatan
Luis Mendo
Tidak, silakan sendiri :-)
Luis Mendo
Apakah maksud Anda bilangan bulat dalam pengertian tipe matematika atau data, yaitu, bisakah kita mengambil matriks pelampung integral?
Dennis
Pengertian matematika. Apakah ini satu hal yang saya pelajari di sini, adalah bahwa Anda dapat membuat asumsi tentang tipe data dalam berbagai bahasa ...
Stewie Griffin
Manis, itu menghemat satu byte. Terima kasih telah mengklarifikasi.
Dennis

Jawaban:

11

Jelly , 11 9 byte

+3\⁺€F÷9Ṃ

Disimpan 2 byte berkat @ Dennis .

Cobalah online!

Penjelasan

+3\⁺€F÷9Ṃ  Main link. Input: 2d matrix
+3\        Reduce overlapping sublists of size 3 by addition
   ⁺€      Repeat previous except over each row
     F     Flatten
      ÷9   Divide by 9
        Ṃ  Minimum
mil
sumber
1
Oh,> _ <tentu saja: D
Jonathan Allan
Saya akan tertarik dengan versi jelly yang tidak diserap, karena ia memiliki banyak fungsi yang berguna.
J Atkin
1
+3\⁺€F÷9Ṃmenghemat beberapa byte.
Dennis
@ Dennis Wow, apakah itu benar-benar memproses +3\terlebih dahulu dan duplikatnya +3\€? Tidak menyangka itu akan terjadi
mil
1
Parser pada dasarnya berbasis stack; \muncul 3dan +dan mendorong quicklink +3\, muncul quicklink dan mendorong dua salinan, lalu muncul salinan paling atas dan mendorong versi pemetaan.
Dennis
8

Oktaf, 38 byte

@(M)min(conv2(M,ones(3)/9,'valid')(:))
Rainer P.
sumber
8

MATL , 13 9 byte

3thYCYmX<

Port of @ rahnema1 menjawab .

Cobalah online!

Bagaimana itu bekerja

Pertimbangkan input

[100 65  2 93;
   3 11 31 89;
  93 15 95 65;
  77 96 72 34]

sebagai contoh.

3th   % Push [3 3]
      % STACK: [3 3]
YC    % Input matrix implicitly. Convert 3x3 sliding blocks into columns
      % STACK: [100   3  65  11;
                  3  93  11  15;
                 93  77  15  96;
                 65  11   2  31;
                 11  15  31  95;
                 15  96  95  72;
                  2  31  93  89;
                 31  95  89  65;
                 95  72  65  34]
Ym    % Mean of each column
      % STACK: [46.1111 54.7778 51.7778 56.4444]
X<    % Minimum of vector. Display implicitly
      % STACK: [46.1111]
Luis Mendo
sumber
7

Mathematica, 37 35 byte

Terima kasih @MartinEnder untuk 2 byte!

Min@BlockMap[Mean@*Mean,#,{3,3},1]&

Penjelasan

Min@BlockMap[Mean@*Mean,#,{3,3},1]&
    BlockMap[                    ]&  (* BlockMap function *)
                        #            (* Divide the input *)
                          {3,3}      (* Into 3x3 matrices *)
                                1    (* With offset 1 *)
             Mean@*Mean              (* And apply the Mean function twice to
                                        each submatrix *)
Min                                  (* Find the minimum value *)
JungHwan Min
sumber
Sangat sangat apik!
Greg Martin
5

Python 2 , 93 81 80 79 byte

f=lambda M:M[2:]and min(sum(sum(zip(*M[:3])[:3],()))/9,f(M[1:]),f(zip(*M)[1:]))

Cobalah online!

Bagaimana itu bekerja

f adalah fungsi rekursif yang mengambil daftar tupel (atau iterable 2D lainnya yang dapat diindeks yang mewakili matriks M ) dan secara rekursif menghitung minimum rata-rata submatrix 3 × 3 di sudut kiri atas dan f diterapkan secara rekursif ke M tanpa baris pertama dan M tanpa kolom pertama.

f(M) melakukan hal berikut.

  • Jika M memiliki kurang dari tiga baris, M[2:]adalah daftar kosong, yang mengembalikan f .

    Perhatikan bahwa, sejak n> 3 pada putaran pertama, inisial tidak dapat mengembalikan daftar kosong.

  • Jika M memiliki tiga baris atau lebih, M[2:]tidak kosong dan dengan demikian benar, maka kode di sebelah kanan anddijalankan, mengembalikan minimum dari tiga nilai berikut.

    min(sum(sum(zip(*M[:3])[:3],()))/9

    M[:3]menghasilkan tiga baris pertama M , zip(*...)mentransposisi baris dan kolom (menghasilkan daftar tupel), sum(...,())menggabungkan semua tupel (ini bekerja karena +merupakan penyatuan), dan sum(...)/9menghitung rata-rata dari daftar yang dihasilkan dari sembilan bilangan bulat.

    f(M[1:])

    secara rekursif berlaku f ke M dengan baris pertama dihapus.

    f(zip(*M)[1:])

    mentransposisi baris dan kolom, menghilangkan baris pertama dari hasil (jadi kolom pertama dari M , dan secara f berlaku untuk hasil.

Perhatikan bahwa lapisan yang sebelumnya dihapus dalam panggilan rekursif akan selalu menjadi baris, jadi menguji apakah M memiliki cukup baris akan selalu mencukupi ..

Akhirnya, orang mungkin berharap bahwa beberapa panggilan rekursif yang kembali []akan menjadi masalah. Namun, dalam Python 2 , setiap kali n adalah angka dan A adalah iterable, perbandingan n < Amengembalikan True , sehingga menghitung minimum satu atau lebih angka dan satu atau lebih iterables akan selalu mengembalikan angka terendah.

Dennis
sumber
3

J , 21 byte

[:<./@,9%~3+/\3+/\"1]

Cobalah online!

Cara yang tepat untuk beroperasi pada subarrays di J adalah dengan menggunakan ketiga ( _3) bentuk dipotong ;.di mana x (u;._3) ysarana untuk menerapkan kata kerja upada setiap subarray penuh ukuran xarray y. Solusi menggunakan yang hanya membutuhkan 1 byte lebih tetapi akan jauh lebih efisien pada array yang lebih besar.

[:<./@,9%~3 3+/@,;._3]

Cobalah online!

Penjelasan

[:<./@,9%~3+/\3+/\"1]  Input: 2d array M
                    ]  Identity. Get M
                  "1   For each row
              3  \       For each overlapping sublist of size 3
               +/          Reduce by addition
          3  \         For each overlapping 2d array of height 3
           +/            Reduce by addition
       9%~             Divide by 9
[:    ,                Flatten it
  <./@                 Reduce by minimum
mil
sumber
1
Saya suka bagaimana []penampilan mereka cocok, tetapi sebenarnya tidak.
Lynn
1
@ Lynn Tunggu sebentar, itu tidak benar. J seharusnya mengalihkan perhatian pemirsa dengan beberapa tanda kurung yang tidak seimbang. Seharusnya menggunakan a [atau |:)
mil
2

Jelly , 18 byte

Melewatkan trik, seperti yang digunakan oleh mil dalam jawaban mereka , menggunakan pengurangan kumulatif n-bijaksana penambahan - seluruh baris pertama dapat diganti dengan +3\untuk 11.

ẆµL=3µÐfS€
ÇÇ€FṂ÷9

Cobalah online!

Melintasi semua daftar yang bersebelahan, memfilter agar hanya yang panjangnya 3 dan jumlah (vektorisasi) yang kemudian diulang untuk setiap daftar hasil, untuk mendapatkan jumlah semua 3 oleh 3 sub-matriks dan akhirnya meratakannya menjadi satu daftar, mengambil minimum dan membaginya dengan 9 (jumlah elemen yang membuat jumlah minimal ini).

Jonathan Allan
sumber
Saya suka gagasan penyaringan daftar. Berguna jika ukuran sublist tergantung pada nilai yang dihitung.
mil
2

Pyth, 19 byte

chSsMsMs.:R3C.:R3Q9

Program yang mengambil input dari daftar daftar dan mencetak hasilnya.

Suite uji

Bagaimana itu bekerja

[Penjelasan datang nanti]

TheBikingViking
sumber
1

Python 3 , 111 103 byte

lambda m,r=range:min(sum(sum(m[y+i][x:x+3])for i in r(3))/9for x in r(len(m[0])-3)for y in r(len(m)-3))

Cobalah online!

ovs
sumber
1

Python 2, 96 byte

h=lambda a:[map(sum,zip(*s))for s in zip(a,a[1:],a[2:])]
lambda a:min(map(min,h(zip(*h(a)))))/9.

Uji kasus di Repl.it

Fungsi yang tidak disebutkan namanya mengambil daftar daftar, a- baris matriks.

Fungsi helper hritsleting melalui tiga irisan yang berdekatan, dan memetakan fungsi penjumlahan melintasi transpose, zip(*s)masing-masing. Ini menghasilkan penjumlahan semua tinggi, tiga irisan kolom tunggal.

Fungsi yang tidak disebutkan namanya memanggil fungsi helper, mentranspos dan memanggil fungsi helper lagi pada hasilnya, kemudian menemukan minimum masing-masing dan minimum hasil, yang kemudian dibagi dengan 9. untuk menghasilkan rata-rata.

Jonathan Allan
sumber
1

JavaScript (ES6), 107 98 96 byte

Fungsi yang menghitung jumlah kembar tiga di atas baris dan kemudian memanggil dirinya sendiri untuk melakukan hal yang sama di atas kolom, melacak nilai minimum M .

f=m=>m.map((r,y)=>r.map((v,x)=>M=(z[x<<9|y]=v+=r[x+1]+r[x+2])<M?v:M),z=[M=1/0])&&m[1]?f([z]):M/9

JS sedikit verbose untuk hal-hal semacam itu dan tidak memiliki zip()metode asli . Butuh cukup banyak waktu untuk menghemat hanya selusin byte melalui pendekatan yang lebih naif. (Namun, metode yang lebih pendek mungkin ada.)

Versi non-rekursif, 103 byte

Disimpan 2 byte dengan bantuan Neil

m=>m.map((r,y)=>y>1?r.map((v,x)=>[..."12345678"].map(i=>v+=m[y-i%3][x+i/3|0])&&(M=v<M?v:M)):M=1/0)&&M/9

Uji kasus

Arnauld
sumber
Saya agak tertarik pada apa yang disebut pendekatan naif Anda, karena yang terbaik yang bisa saya lakukan dengan pendekatan yang cukup murni adalah 113 byte:(a,b=a.map(g=a=>a.slice(2).map((e,i)=>a[i]+a[i+1]+e)))=>eval(`Math.min(${b[0].map((_,i)=>g(b.map(a=>a[i])))})`)/9
Neil
@Neil Saya pikir itu adalah sesuatu yang dekat m=>m.map((r,y)=>r.map((v,x)=>[..."12345678"].map(i=>v+=(m[y+i/3|0]||[])[x+i%3])&&(M=v<M?v:M)),M=1/0)&&M/9, meskipun saya pikir upaya pertama saya sebenarnya lebih besar dari itu.
Arnauld
Bagus, meskipun saya bisa mencukur habis byte: m=>m.map((r,y)=>y>1&&r.map((v,x)=>[..."12345678"].map(i=>v+=m[y-i%3][x+i/3|0])&&(M=v<M?v:M)),M=1/0)&&M/9.
Neil
@Neil Cool. Ini memungkinkan Anda untuk menyimpan satu byte lagi denganm=>m.map((r,y)=>y>1?r.map((v,x)=>[..."12345678"].map(i=>v+=m[y-i%3][x+i/3|0])&&(M=v<M?v:M)):M=1/0)&&M/9
Arnauld
1

05AB1E , 21 16 byte

2FvyŒ3ùO})ø}˜9/W

Cobalah online!

Penjelasan

2F         }       # 2 times do:
  v     }          # for each row in the matrix
   yŒ3ù            # get all sublists of size 3
       O           # reduce by addition
         )ø        # transpose matrix
            ˜      # flatten the matrix to a list
             9/    # divide each by 9
               W   # get the minimum
Emigna
sumber
1

Haskell , 87 byte

import Data.List
t(a:b:c:d)=a+b+c:t(b:c:d);t _=[]
s=(/9).minimum.(t=<<).transpose.map t

Cobalah online!

Roman Czyborra
sumber