Find the submatrix with the smallest mean

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

• It would also be interesting to have a challenge with not necessarily contiguous rows and columns Commented Feb 4, 2017 at 14:18
• No, go ahead yourself :-) Commented Feb 4, 2017 at 14:50
• Do you mean integers in the mathematical or data type sense, i.e., can we take a matrix of integral floats? Commented Feb 4, 2017 at 18:15
• Mathematical sense. Is it one thing I've learned here, it is that you can make assumptions about data types in various languages... Commented Feb 4, 2017 at 20:06
• Sweet, that saves a byte. Thanks for clarifying. Commented Feb 4, 2017 at 20:38

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

• Oh, >_< of course :D Commented Feb 4, 2017 at 12:34
• I would be interested in an ungolfed version of jelly, since it has so many useful functions. Commented Feb 4, 2017 at 16:42
• +3\⁺€F÷9Ṃ saves a couple of bytes. Commented Feb 4, 2017 at 17:36
• @Dennis Wow, is that really processing +3\ first and the duplicate as +3\€? Did not expect that to happen Commented Feb 4, 2017 at 17:47
• The parser is essentially stack-based; \ pops 3 and + and pushes the quicklink +3\, ⁺ pops the the quicklink and pushes two copies, then € pops the topmost copy and pushes a mapping version. Commented Feb 4, 2017 at 17:51

Octave, 30 bytes

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


Try it online!

Octave, 38 bytes

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


MATL, 13 9 bytes

3thYCYmX<


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]


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

• Very very slick! Commented Feb 4, 2017 at 20:18

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
3  \         For each overlapping 2d array of height 3
9%~             Divide by 9
[:    ,                Flatten it
<./@                 Reduce by minimum

• I like how the [] look like they’re matched, but they’re really not.
– lynn
Commented Feb 5, 2017 at 0:12
• @Lynn Wait a second, that's not right. J is supposed to distract viewers with multiple unbalanced brackets. Should have used a [ or | :) Commented Feb 5, 2017 at 0:22

Python 2, 938180 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.

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

• I like the filtering sublists idea. Useful if that sublist size depended on a computed value. Commented Feb 4, 2017 at 12:32

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]

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!

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


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!

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.

JavaScript (ES6), 10798 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 ]
]));

• I'm somewhat interested in your so-called naïve approach, since the best I could do with a reasonably pure approach was 113 bytes: (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
Commented Feb 6, 2017 at 21:27
• @Neil I think it was something close to 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, although I think my first attempt was actually larger than that. Commented Feb 6, 2017 at 21:36
• Nice, although I was able to shave off a 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
Commented Feb 6, 2017 at 23:53
• @Neil Cool. This allows to save one more byte with 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 Commented Feb 7, 2017 at 0:12

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
)ø        # transpose matrix
˜      # flatten the matrix to a list
9/    # divide each by 9
W   # get the minimum


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


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

• -1 byte: ÷9/↧♭≑≊(/+♭)◫3_3 Commented Nov 15, 2023 at 6:10
• @alephalpha Thanks! Commented Nov 15, 2023 at 7:27

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!

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


K (ngn/k), 2120 17 bytes

Port of @miles' J solution

-3 thanks to @Bubbler

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


Try it online!

• "Sum of 3-windows in 2D" can be done with 2(+3+/':)/, and "divide by 9" can be done with 1%9% (works fine when the answer is zero). Commented Nov 20, 2023 at 6:08

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