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

Posiciones de máximos locales

Los vectores se definen usando tablas como sigue:

Un elemento de un vector es un máximo local si no tiene ningún elemento adyacente mayor o igual que él.

Definir la función

tal que (posMaxVec p) devuelve las posiciones del vector p en las que p tiene un máximo local. Por ejemplo,

Soluciones

Máxima suma en una matriz

Las matrices puede representarse mediante tablas cuyos índices son pares de números naturales:

Definir la función

tal que (maximaSuma p) es el máximo de las sumas de las listas de elementos de la matriz p tales que cada elemento pertenece sólo a una fila y a una columna. Por ejemplo,

ya que las selecciones, y sus sumas, de la matriz

son

Hay dos selecciones con máxima suma: [2,8,7] y [3,8,6].

Soluciones

Relleno de matrices

Dada una matriz cuyos elementos son 0 ó 1, su relleno es la matriz obtenida haciendo iguales a 1 los elementos de las filas y de las columna que contienen algún uno. Por ejemplo, el relleno de la matriz de la izquierda es la de la derecha:

Las matrices se pueden representar mediante tablas cuyos índices son pares de enteros

por ejemplo, la matriz de la izquierda de la figura anterior se define por

Definir la función

tal que (relleno p) es el relleno de la matriz p. Por ejemplo,

Soluciones

Referencias

Basado en Matrix Fill-In del blog Programming Praxis.

Ampliación de una matriz sumando sus filas

Representamos las matrices mediante el tipo de dato

Por ejemplo,

representa la matriz

Definir la función

tal que (ampliada p) es la matriz obtenida al añadir una nueva fila a p cuyo elemento i-ésimo es la suma de la columna i-ésima de p. Por ejemplo,

En Haskell,

Soluciones