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 – Luis Mendo Feb 4 '17 at 14:18
• No, go ahead yourself :-) – Luis Mendo Feb 4 '17 at 14:50
• Do you mean integers in the mathematical or data type sense, i.e., can we take a matrix of integral floats? – Dennis Feb 4 '17 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... – Stewie Griffin Feb 4 '17 at 20:06
• Sweet, that saves a byte. Thanks for clarifying. – Dennis Feb 4 '17 at 20:38

Octave, 30 bytes

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


Try it online!

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 – Jonathan Allan Feb 4 '17 at 12:34
• I would be interested in an ungolfed version of jelly, since it has so many useful functions. – J Atkin Feb 4 '17 at 16:42
• +3\⁺€F÷9Ṃ saves a couple of bytes. – Dennis Feb 4 '17 at 17:36
• @Dennis Wow, is that really processing +3\ first and the duplicate as +3\€? Did not expect that to happen – miles Feb 4 '17 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. – Dennis Feb 4 '17 at 17:51

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! – Greg Martin Feb 4 '17 at 20:18

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.

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 Feb 5 '17 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 | :) – miles Feb 5 '17 at 0:22

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. – miles Feb 4 '17 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]

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 Feb 6 '17 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. – Arnauld Feb 6 '17 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 Feb 6 '17 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 – Arnauld Feb 7 '17 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


import Data.List