Flippind Matrix

Introducción

He de admitir que llegar a la solución final me llevó más tiempo de análisis, que de código. El problema Flipping Matrix, enuncia lo siguiente:

Sean inventó un juego que involucra una matriz donde cada celda de la matriz contiene un número entero. Puede invertir cualquiera de sus filas o columnas cualquier número de veces. El objetivo del juego es maximizar la suma de los elementos en la submatriz ubicada en el cuadrante superior izquierdo de la matriz.
Dadas las configuraciones iniciales de las matrices, ayude a Sean a invertir las filas y columnas de cada matriz de la mejor manera posible para que la suma de los elementos en el cuadrante superior izquierdo de la matriz sea máxima.

Básicamente, el problema consiste en encontrar el valor máximo de cada submatriz. Esta submatriz está delimitada por un de tamaño “nxn” y los números posibles son aquellos que se encuentran en las posiciones inversas de esa submatriz, tanto en filas como en columnas.

Solución Inicial

La solución propuesta utiliza solo dos bucles para recorrer todas las filas y columnas dentro del cuadrado morado y una función que identifica el número máximo entre las cuatro posiciones posibles para cada submatriz. La función compara el valor del cuadrado superior izquierdo, superior derecho, inferior izquierdo e inferior derecho y devuelve el valor máximo de los cuatro.

def flippingMatrix(matrix):
    n = len(matrix)//2
    max_total = 0
    for i in range(n):
        for j in range(n):
            top_left = matrix[i][j]
            top_right = matrix[i][n*2-1-j]
            bottom_left = matrix[n*2-1-i][j]
            bottom_right = matrix[n*2-1-i][n*2-1-j]
            max_val = max(top_left, top_right, bottom_left, bottom_right)
            max_total += max_val
    return max_total

El código proporcionado implementa una función llamada flippingMatrix que toma una matriz cuadrada de números y devuelve el valor máximo que se puede obtener al hacer "flip" de los valores de una submatriz de 2x2 en la matriz original. El "flip" significa cambiar los valores de la submatriz con sus correspondientes simétricos en la matriz. A continuación, explico línea a línea al algoritmo:

1. n = len(matrix)//2 - Calcula la mitad de la longitud de la matriz y la asigna a la variable n. Esto se utiliza más adelante para delimitar la submatriz 2x2 que se utiliza para hacer el "flip".
2. max_total = 0 - Inicializa la variable max_total a cero. Esta variable se utiliza para almacenar la suma del valor máximo de cada submatriz 2x2 que se considera.
3. for i in range(n): - Comienza un bucle que se ejecuta n veces. Este bucle itera sobre las filas de la submatriz 2x2.
4. for j in range(n): - Dentro del bucle anterior, comienza otro bucle que se ejecuta n veces. Este bucle itera sobre las columnas de la submatriz 2x2.
5. top_left = matrix[i][j] - Calcula el valor del elemento en la esquina superior izquierda de la submatriz 2x2 y lo asigna a la variable top_left.
6. top_right = matrix[i][n*2-1-j] - Calcula el valor del elemento en la esquina superior derecha de la submatriz 2x2 y lo asigna a la variable top_right.
7. bottom_left = matrix[n*2-1-i][j] - Calcula el valor del elemento en la esquina inferior izquierda de la submatriz 2x2 y lo asigna a la variable bottom_left.
8. bottom_right = matrix[n*2-1-i][n*2-1-j] - Calcula el valor del elemento en la esquina inferior derecha de la submatriz 2x2 y lo asigna a la variable bottom_right.
9. max_val = max(top_left, top_right, bottom_left, bottom_right) - Calcula el valor máximo entre los cuatro valores de la submatriz 2x2 y lo asigna a la variable max_val.
10. max_total += max_val - Añade el valor máximo de la submatriz 2x2 a la variable max_total.
11. return max_total - Devuelve el valor total máximo obtenido al hacer "flip" de los valores de una submatriz de 2x2 en la matriz original.

Conclusiones

En resumen, el código implementa una solución eficiente para el problema de “flip” de una matriz 2D y utiliza la función
max para obtener el valor máximo de una submatriz de 2x2 en cada iteración del bucle anidado.

Recomendación

En mi arículo explico como optimizar la solución 1.

Y en mi GitHub podrás descargar el código y las pruebas, además de ver soluciones a otros problemas.