Elementos de una matriz con algún vecino menor

Las matrices pueden representarse mediante tablas cuyos índices son pares de números naturales. Su tipo se define por

Por ejemplo, la matriz

se define por

Los vecinos de un elemento son los que están a un paso en la misma fila, columna o diagonal. Por ejemplo, en la matriz anterior, el 1 tiene 8 vecinos (el 9, 4, 6, 8, 7, 4, 2 y 5) pero el 9 sólo tiene 3 vecinos (el 4, 8 y 1).

Definir la función

tal que (algunoMenor p) es la lista de los elementos de p que tienen algún vecino menor que él. Por ejemplo,

pues sólo el 1 y el 3 no tienen ningún vecino menor en la matriz.

Soluciones

El código se encuentra en GitHub.

La elaboración de las soluciones se describe en el siguiente vídeo

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Operaciones binarias con matrices

Entre dos matrices de la misma dimensión se pueden aplicar distintas operaciones binarias entre los elementos en la misma posición. Por ejemplo, si a y b son las matrices

entonces a+b y a-b son, respectivamente

Definir la función

tal que (opMatriz f p q) es la matriz obtenida aplicando la operación f entre los elementos de p y q de la misma posición. Por ejemplo,

Soluciones

Codificación matricial

El procedimiento de codificación matricial se puede entender siguiendo la codificación del mensaje "todoparanada" como se muestra a continuación:

  • Se calcula la longitud L del mensaje. En el ejemplo es L es 12.
  • Se calcula el menor entero positivo N cuyo cuadrado es mayor o igual que L. En el ejemplo N es 4.
  • Se extiende el mensaje con N²-L asteriscos. En el ejemplo, el mensaje extendido es "todoparanada****"
  • Con el mensaje extendido se forma una matriz cuadrada NxN. En el ejemplo la matriz es

  • Se rota 90º la matriz del mensaje extendido. En el ejemplo, la matriz rotada es

  • Se calculan los elementos de la matriz rotada. En el ejemplo, los elementos son "*npt*aap*drd*aao"
  • El mensaje codificado se obtiene eliminando los asteriscos de los elementos de la matriz rotada. En el ejemplo, "nptaapdrdaao".

Definir la función

tal que (codificado cs) es el mensaje obtenido aplicando la codificación matricial al mensaje cs. Por ejemplo,

Nota: Este ejercicio está basado en el problema Secret Message de Kattis.

Soluciones

Número de islas rectangulares de una matriz

En este problema se consideran matrices cuyos elementos son 0 y 1. Los valores 1 aparecen en forma de islas rectangulares separadas por 0 de forma que como máximo las islas son diagonalmente adyacentes. Por ejemplo,

Definir la función

tal que (numeroDeIslas p) es el número de islas de la matriz p. Por ejemplo,

Soluciones

Máximos locales de una matriz

Un elemento de una matriz es un máximo local si es mayor que todos sus vecinos. Por ejemplo, en la matriz

los máximos locales son 8 (en la posición (1,4)), 2 (en la posición (2,2)) y 7 (en la posición (4,3)).

Definimos el tipo de las matrices, mediante

y el ejemplo anterior por

Definir la función

tal que (maximosLocales p) es la lista de las posiciones en las que hay un máximo local, con el valor correspondiente. Por ejemplo,

Soluciones