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

Prefijo con suma acotada

Definir la función

tal que (prefijoAcotado x ys) es el mayor prefijo de ys cuya suma es menor que x. Por ejemplo,

Soluciones

Ordenación por una fila

Las matrices se pueden representar por listas de lista. Por ejemplo, la matriz

se puede representar por

Definir la función

tal que (ordenaPorFila xss k) es la matriz obtenida ordenando xs por los elementos de la fila k. Por ejemplo,

Soluciones

Ordenación por una columna

Las matrices se pueden representar por listas de lista. Por ejemplo, la matriz

se puede representar por

Definir la función

tal que (ordenaPor xss k) es la matriz obtenida ordenando xs por los elementos de la columna k. Por ejemplo,

Soluciones

Problema del dominó

Las fichas del dominó se pueden representar por pares de números enteros. El problema del dominó consiste en colocar todas las fichas de una lista dada de forma que el segundo número de cada ficha coincida con el primero de la siguiente.

Definir, mediante búsqueda en espacio de estados, la función

tal que (domino fs) es la lista de las soluciones del problema del dominó correspondiente a las fichas fs. Por ejemplo,

Nota: Las librerías necesarias se encuentran en la página de códigos.

Soluciones