Find the submatrix with the smallest mean

Question

You're given a n-by-m matrix of integers, where n,m > 3. Your task is to find the 3-by-3 sub-matrix that has the lowest mean, and output this value.

Rules and clarifications:

• The integers will be non-negative
• Optional input and output format
• The output must be accurate up to at least 2 decimal poins (if it's non-integer)
• The submatrices must be made up of consecutive rows and columns

Test cases:

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

This is code-golf so the shortest code in each language wins. I encourage people to post answers in languages that are already used, even if it's not shorter than the first one.

Answer 1

Jelly, 11 9 bytes

+3\⁺€F÷9Ṃ

Saved 2 bytes thanks to @Dennis.

Try it online!

Explanation

+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

Answer 2

Octave, 30 bytes

@(A)min(mean(im2col(A,[3,3])))

Try it online!

Answer 3

Octave, 38 bytes

@(M)min(conv2(M,ones(3)/9,'valid')(:))

Answer 4

MATL, 13 9 bytes

3thYCYmX<

Port of @rahnema1's answer.

Try it online!

How it works

Consider input

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

as an example.

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]

Answer 5

Mathematica, 37 35 bytes

Thanks @MartinEnder for 2 bytes!

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

Explanation

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

Answer 6

J, 21 bytes

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

Try it online!

The proper way to operate on subarrays in J is to use the third (_3) form of cut ;. where x (u;._3) y means to apply verb u on each full subarray of size x of array y. A solution using that requires only 1 more byte but will be much more efficient on larger arrays.

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

Try it online!

Explanation

[:<./@,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

Answer 7

Python 2, 93 81 80 79 bytes

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

Try it online!

How it works

f is a recursive function that takes a list of tuples (or any other indexable 2D iterable that represents a matrix M) and recursively computes the minimum of the mean of the 3×3 submatrix in the upper left corner and f applied recursively to M without its first row and M without its first column.

f(M) does the following.

• If M has less than three rows, M[2:] is an empty list, which f returns.

  Note that, since n > 3 in the first run, the initial cannot cannot return an empty list.

• If M has three rows or more, M[2:] is non-empty and thus truthy, so the code to the right of and gets executed, returning the minimum of the three following values.

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

  M[:3] yields the first three rows of M, zip(*...) transposes rows and columns (yielding a list of tuples), sum(...,()) concatenates all tuples (this works because + is concatenation), and sum(...)/9 computes the mean of the resulting list of nine integers.

  f(M[1:])
  

  recursively applies f to M with its first row removed.

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

  transposes rows and columns, removes the first row of the result (so the first column of M, and recursively applies f to the result.

Note that the previously removed layer in a recursive call will always be a row, so testing if M has enough rows will always be sufficient..

Finally, one may expect that some recursive calls returning [] would be a problem. However, in Python 2, whenever n is a number and A is an iterable, the comparison n < A returns True, so computing the minimum of one or more numbers and one or more iterables will always return the lowest number.

Answer 8

Jelly, 18 bytes

Missed the trick, as used by miles in their answer, of using an n-wise cumulative reduce of addition - the whole first line can be replaced with +3\ for 11.

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

Try it online!

Traverses all contiguous sublists, filters to keep only those of length 3 and sums (which vectorises) then repeats for each resulting list, to get the sums of all 3 by 3 sub-matrices and finally flattens those into one list, takes the minimum and divides by 9 (the number of elements making this minimal sum).

Answer 9

Pyth, 19 bytes

chSsMsMs.:R3C.:R3Q9

A program that takes input of a list of lists and prints the result.

Test suite

How it works

[Explanation coming later]

Answer 10

Haskell, 87 bytes

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

Try it online!

Answer 11

Uiua, 14 bytes

÷9/↧♭⍥(/+⍉◫3)2

Try it!

÷9/↧♭⍥(/+⍉◫3)2    input: a matrix of shape RxC
      ⍥(      )2    repeat twice:
             ◫3      windows of 3; shape (R-2)x3xC
           ⍉        transpose (rotate axes once); shape 3xCx(R-2)
         /+          sum over the length-3 axis; shape Cx(R-2)
             ◫3      windows of 3; shape (C-2)x3x(R-2)
           ⍉        transpose (rotate axes once); shape 3x(R-2)x(C-2)
         /+          sum over the length-3 axis; shape (R-2)x(C-2)
÷9/↧♭               minimum of all elements divided by 9

Uiua, 14 bytes

÷9/↧♭/+/+◫-2△.

Try it!

÷9/↧♭/+/+◫-2△.    input: a matrix of shape RxC
           -2△     subtract 2 from the shape; [R-2, C-2]
          ◫   .    2D windows of that size; gives 3x3x(R-2)x(C-2) array
      /+/+          sum over the first two axes
÷9/↧♭              minimum of all elements divided by 9

Answer 12

Python 3, 111 103 bytes

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

Try it online!

Answer 13

Python 2, 96 bytes

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.

Test cases at Repl.it

An unnamed function taking a list of lists, a - the rows of the matrix.

The helper function h zips through three adjacent slices, and maps the sum function across the transpose, zip(*s), of each. This results in summing all height three slices of single columns.

The unnamed function calls the helper function, transposes and calls the helper function again on the result, then finds the minimum of each and the minimum of the result, which it then divides by 9. to yield the average.

Answer 14

JavaScript (ES6), 107 98 96 bytes

A function that computes the sums of triplets over the rows and then calls itself to do the same thing over the columns, keeping track of the minimum value 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 is a bit verbose for that kind of stuff and lacks a native zip() method. It took me quite a lot of time to save just a dozen bytes over a more naive approach. (Yet, a shorter method probably exists.)

Non-recursive version, 103 bytes

Saved 2 bytes with the help of 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

Test cases

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

console.log(f([
  [ 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 ]
]));

console.log(f([
  [ 100, 65,  2, 93 ],
  [   3, 11, 31, 89 ],
  [  93, 15, 95, 65 ],
  [  77, 96, 72, 34 ]
]));

console.log(f([
  [ 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 ]
]));

console.log(f([
  [ 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 ]
]));

Answer 15

05AB1E, 21 16 bytes

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

Try it online!

Explanation

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

Answer 16

Nekomata, 10 bytes

2ᵑ{q3Lµ}aṁ

Attempt This Online!

2ᵑ{q3Lµ}aṁ
2ᵑ{    }        Apply the following function twice
   q                Choose a contiguous subsequence
    3L              of length 3
      µ             Take its mean
        aṁ      Minimum of all possible results

Answer 17

Uiua, 17 16 bytes

÷9/↧♭≡≡(/+♭)◫3_3

Try it!

-1 thanks to alephalpha

÷9/↧♭≡≡(/+♭)◫3_3
            ◫3_3  # 3x3 windows
     ≡≡(   )      # map function to each matrix in 4D array
          ♭       # deshape
        /+        # sum
    ♭             # deshape
  /↧              # minimum
÷9                # divide by 9

Answer 18

R, 78 bytes

\(m,l=nrow(m))min(mapply(\(x,y)mean(m[x-0:2,y-0:2]),3:l,y=rep(3:ncol(m),l-2)))

Try it online!

Answer 19

Vyxal, 10 bytes

2(3lvṁ∩)fg

Try it Online!

2(     )   # Twice
  3l       # Take sliding windows of length 3
    vṁ     # Take the mean of each window
      ∩    # Transpose
        fg # Flatten and take the minimum

Answer 20

K (ngn/k), 21 20 17 bytes

Port of @miles' J solution

-3 thanks to @Bubbler

1%9%&//2(+3+/':)/

Try it online!

Answer 21

Scala, 142 bytes

Golfed version. Try it online!

M=>if(M.size<3||M(0).size<3)Double.MaxValue else List((0 to 2).flatMap(i=>(0 to 2).map(j=>M(i)(j))).sum/9.0,f(M.tail),f(M.transpose.tail)).min

Ungolfed version. Try it online!

object Main {

  def f(M: List[List[Int]]): Double = {
    if (M.length < 3 || M.head.length < 3) Double.MaxValue
    else {
      val minSubMatrix = (0 until 3).flatMap(i => (0 until 3).map(j => M(i)(j))).sum / 9.0
      List(minSubMatrix, f(M.tail), f(M.transpose.tail)).min
    }
  }

  def main(args: Array[String]): Unit = {
    val M = List(List(100, 65, 2, 93), List(3, 11, 31, 89), List(93, 15, 95, 65), List(77, 96, 72, 34))
    println(f(M))
  }
}