Encuentra la submatriz con la media más pequeña

21

Te dan una matriz de enteros n-por-m , donde n, m> 3 . Su tarea es encontrar la submatriz de 3 por 3 que tenga la media más baja y generar este valor.

Reglas y aclaraciones:

  • Los enteros serán no negativos.
  • Formato opcional de entrada y salida
  • La salida debe ser precisa hasta al menos 2 puntos decimales (si no es entero)
  • Las submatrices deben estar formadas por filas y columnas consecutivas

Casos de prueba:

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

Este es el por lo que gana el código más corto en cada idioma. Animo a las personas a publicar respuestas en idiomas que ya se utilizan, incluso si no es más corto que el primero.

Stewie Griffin
fuente
También sería interesante tener un desafío con filas y columnas no necesariamente contiguas
Luis Mendo
No, adelante tú mismo :-)
Luis Mendo
¿Te refieres a enteros en el sentido matemático o del tipo de datos, es decir, podemos tomar una matriz de flotadores integrales?
Dennis
Sentido matemático. Es una cosa que he aprendido aquí, es que puedes hacer suposiciones sobre los tipos de datos en varios idiomas ...
Stewie Griffin
Dulce, eso ahorra un byte. Gracias por aclararlo.
Dennis

Respuestas:

11

Jalea , 11 9 bytes

+3\⁺€F÷9Ṃ

Guardado 2 bytes gracias a @ Dennis .

Pruébalo en línea!

Explicación

+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
millas
fuente
1
Oh,> _ <por supuesto: D
Jonathan Allan
Me interesaría una versión sin gel de gelatina, ya que tiene muchas funciones útiles.
J Atkin
1
+3\⁺€F÷9ṂGuarda un par de bytes.
Dennis
@ Dennis Wow, ¿eso es realmente el procesamiento +3\primero y el duplicado como +3\€? No esperaba que eso sucediera
millas del
1
El analizador está esencialmente basado en pila; \aparece 3y +empuja el enlace rápido +3\, abre el enlace rápido y empuja dos copias, luego abre la copia superior y empuja una versión de mapeo.
Dennis
8

Octava, 38 bytes

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

MATL , 13 9 bytes

3thYCYmX<

La respuesta del puerto de @ rahnema1 .

Pruébalo en línea!

Cómo funciona

Considerar entrada

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

como ejemplo.

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

Mathematica, 37 35 bytes

¡Gracias @MartinEnder por 2 bytes!

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

Explicación

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
fuente
Muy muy hábil!
Greg Martin
5

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

Pruébalo en línea!

Cómo funciona

f es una función recursiva que toma una lista de tuplas (o cualquier otra iterable 2D indexable que represente una matriz M ) y calcula recursivamente el mínimo de la media de la submatriz 3 × 3 en la esquina superior izquierda yf aplica recursivamente a M sin su primera fila y M sin su primera columna.

f(M) hace lo siguiente

  • Si M tiene menos de tres filas, M[2:]es una lista vacía, que devuelve f .

    Tenga en cuenta que, dado que n> 3 en la primera ejecución, la inicial no puede devolver una lista vacía.

  • Si M tiene tres filas o más, M[2:]no está vacío y, por lo tanto, es verdadero, entonces el código a la derecha de andse ejecuta, devolviendo el mínimo de los tres valores siguientes.

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

    M[:3]produce las primeras tres filas de M , zip(*...)transpone filas y columnas (produciendo una lista de tuplas), sum(...,())concatena todas las tuplas (esto funciona porque +es concatenación) y sum(...)/9calcula la media de la lista resultante de nueve enteros.

    f(M[1:])

    aplica recursivamente f a M con su primera fila eliminada.

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

    transpone filas y columnas, elimina la primera fila del resultado (por lo tanto, la primera columna de M y aplica recursivamente f al resultado).

Tenga en cuenta que la capa eliminada previamente en una llamada recursiva siempre será una fila, por lo que probar si M tiene suficientes filas siempre será suficiente.

Finalmente, uno puede esperar que algunas llamadas recursivas que regresen []sean un problema. Sin embargo, en Python 2 , cuando n es un número y A es un iterable, la comparación n < Adevuelve True , por lo que calcular el mínimo de uno o más números y uno o más iterables siempre devolverá el número más bajo.

Dennis
fuente
3

J , 21 bytes

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

Pruébalo en línea!

La forma correcta de operar en subconjuntos en J es usar la tercera forma ( _3) de corte ;.donde x (u;._3) ysignifica aplicar el verbo uen cada subconjunto completo del tamaño xde la matriz y. Una solución que usa solo requiere 1 byte más pero será mucho más eficiente en matrices más grandes.

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

Pruébalo en línea!

Explicación

[:<./@,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
millas
fuente
1
Me gusta cómo []se combinan, pero realmente no lo son.
Lynn
1
@ Lynn Espera un segundo, eso no está bien. Se supone que J distrae a los espectadores con múltiples paréntesis desequilibrados. Debería haber usado un [o |:)
millas
2

Jalea , 18 bytes

Se perdió el truco, como lo utilizan millas en su respuesta , de usar una reducción acumulativa de suma n-sabia: toda la primera línea se puede reemplazar +3\por 11.

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

Pruébalo en línea!

Atraviesa todas las sublistas contiguas, filtra para mantener solo las de longitud 3 y sumas (que vectoriza) luego repite para cada lista resultante, para obtener las sumas de todas las submatrices 3 por 3 y finalmente las aplana en una lista, toma el mínimo y se divide por 9 (el número de elementos que hacen esta suma mínima).

Jonathan Allan
fuente
Me gusta la idea de filtrado de sublistas. Útil si el tamaño de esa sublista dependía de un valor calculado.
millas
2

Pyth, 19 bytes

chSsMsMs.:R3C.:R3Q9

Un programa que toma la entrada de una lista de listas e imprime el resultado.

Banco de pruebas

Cómo funciona

[Explicación más tarde]

TheBikingViking
fuente
1

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.

Casos de prueba en Repl.it

Una función sin nombre que toma una lista de listas, a- las filas de la matriz.

La función auxiliar se hdesplaza a través de tres sectores adyacentes y asigna la función de suma a través de la transposición zip(*s), de cada uno. Esto da como resultado la suma de todas las alturas en tres sectores de columnas individuales.

La función sin nombre llama a la función auxiliar, transpone y vuelve a llamar a la función auxiliar en el resultado, luego encuentra el mínimo de cada uno y el mínimo del resultado, que luego divide 9.para obtener el promedio.

Jonathan Allan
fuente
1

JavaScript (ES6), 107 98 96 bytes

Una función que calcula las sumas de tripletes sobre las filas y luego se llama a sí misma para hacer lo mismo sobre las columnas, haciendo un seguimiento del valor mínimo 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 es un poco detallado para ese tipo de cosas y carece de un zip()método nativo . Me llevó bastante tiempo guardar solo una docena de bytes en un enfoque más ingenuo. (Sin embargo, probablemente exista un método más corto).

Versión no recursiva, 103 bytes.

Guardado 2 bytes con la ayuda de 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

Casos de prueba

Arnauld
fuente
Estoy algo interesado en su supuesto enfoque ingenuo, ya que lo mejor que pude hacer con un enfoque razonablemente puro fue 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
@Neil Creo que fue algo cercano 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, aunque creo que mi primer intento fue en realidad más grande que eso.
Arnauld
Agradable, a pesar de que fue capaz de afeitar de un 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. Esto permite guardar un byte más conm=>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 bytes

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

Pruébalo en línea!

Explicación

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
fuente