Antecedentes
Considere una cadena (cerrada) de barras, cada una de las cuales tiene una longitud entera. ¿Cuántos poliominoos distintos sin agujeros puede formar con una cadena dada? O, en otras palabras, ¿cuántos polígonos diferentes que no se cruzan entre sí con lados alineados por eje puede formar con una cadena dada?
Veamos un ejemplo. Considere una cadena particular que consta de 8 barras de longitud 1 y 2, que podemos representar como [1, 1, 2, 2, 1, 1, 2, 2]
. Hasta rotaciones y traslaciones, solo hay 8 posibles poliominós (contamos diferentes reflexiones):
Esta primera barra es azul oscuro, y luego atravesamos el polígono en sentido antihorario .
El sentido de rotación no afecta el resultado en el ejemplo anterior. Pero consideremos otra cadena [3, 1, 1, 1, 2, 1, 1]
, que produce los siguientes 3 poliominós:
Tenga en cuenta que no incluimos un reflejo del último poliomino, porque requeriría un recorrido en sentido horario.
Si tuviéramos una cadena más flexible de la misma longitud, en [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
realidad podríamos formar ambas reflexiones entre algunas otras poloninoas, con un total de 9:
El reto
Dada una descripción de una cadena, como una matriz o similar, determine el número de poliominoes distintos que puede formar (hasta rotaciones y traslaciones) usando las barras en orden mientras recorre el perímetro en sentido antihorario.
Escriba un programa completo e incluya comandos para compilar (si corresponde) y ejecute su código desde la línea de comandos. Incluya también un enlace a un compilador / intérprete gratuito para su idioma.
Su programa debe leer la entrada de STDIN. La primera línea contendrá un número entero M . Las siguientes líneas M serán casos de prueba, cada una de las cuales será una lista de longitudes de varilla separadas por espacios. Su programa debe imprimir líneas M en STDOUT, cada una de las cuales consiste en un único número entero: el número de poliominós distintos que se pueden formar.
Solo debes usar un solo hilo.
Su programa no debe usar más de 1 GB de memoria en cualquier momento. (Este no es un límite completamente estricto, pero monitorearé el uso de memoria de su ejecutable y eliminaré cualquier proceso que use constantemente más de 1 GB o aumente significativamente por encima de él).
Para evitar cantidades excesivas de cálculo previo, su código no debe tener más de 20,000 bytes y no debe leer ningún archivo.
Tampoco debe optimizar hacia los casos de prueba específicos elegidos (por ejemplo, codificando sus resultados). Si sospecho que sí, me reservo el derecho de generar nuevos conjuntos de puntos de referencia. Los conjuntos de prueba son aleatorios, por lo que el rendimiento de su programa en esos debe ser representativo de su rendimiento en la entrada arbitraria. La única suposición que se le permite hacer es que la suma de las longitudes de las barras es uniforme.
Puntuación
He proporcionado conjuntos de referencia para cadenas de N = 10, 11, ..., 20 barras. Cada conjunto de prueba contiene 50 cadenas aleatorias con longitudes entre 1 y 4 inclusive.
Su puntaje principal es la N más grande para la cual su programa completa el conjunto de pruebas completo en 5 minutos (en mi máquina, en Windows 8). El desempate será el tiempo real empleado por su programa en ese conjunto de prueba.
Si alguien supera el conjunto de prueba más grande, seguiré agregando los más grandes.
Casos de prueba
Puede usar los siguientes casos de prueba para verificar la corrección de su implementación.
Input Output
1 1 0
1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1 1 1 9
1 1 1 1 1 1 1 1 1 1 1 1 36
1 1 1 1 1 1 1 1 1 1 1 1 1 1 157
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 758
1 1 2 2 1 1 2 2 8
1 1 2 2 1 1 2 2 1 1 23
1 1 2 2 1 1 2 2 1 1 2 2 69
1 2 1 2 1 2 1 2 3
1 2 1 2 1 2 1 2 1 2 1 2 37
1 2 3 2 1 2 3 2 5
1 2 3 2 1 2 3 2 1 2 3 2 23
3 1 1 1 2 1 1 3
1 2 3 4 5 6 7 1
1 2 3 4 5 6 7 8 3
1 2 3 4 5 6 7 8 9 10 11 5
2 1 5 3 3 2 3 3 4
4 1 6 5 6 3 1 4 2
3 5 3 5 1 4 1 1 3 5
1 4 3 2 2 5 5 4 6 4
4 1 3 2 1 2 3 3 1 4 18
1 1 1 1 1 2 3 3 2 1 24
3 1 4 1 2 2 1 1 2 4 1 2 107
2 4 2 4 2 2 3 4 2 4 2 3 114
Encontrará un archivo de entrada con estos aquí .
Tabla de clasificación
User Language Max N Time taken (MM:SS:mmm)
1. feersum C++ 11 19 3:07:430
2. Sp3000 Python 3 18 2:30:181
fuente
Respuestas:
C ++ 11
Actualizaciones: se agregó la primera línea
c
que comienza temprano si la distancia está demasiado lejos del origen (que era el propósito de la variablerlen
, pero olvidé escribirla en la primera versión). Lo cambié para usar mucho menos memoria, pero a costa del tiempo. Ahora resuelve N = 20 en poco menos de 5 minutos para mí.Compilar con
fuente
#define
s thoPython 3 (con PyPy ) - N = 18
Corre con
./pypy <filename>
.Esta es la implementación de referencia que escribí cuando discutí la pregunta con Martin. No se hizo teniendo en cuenta la velocidad y es bastante hacky, pero debería proporcionar una buena base para comenzar.
N = 18 toma aproximadamente 2.5 minutos en mi modesta computadora portátil.
Algoritmo
Las rotaciones se comprueban convirtiendo cada forma en una serie de
F
hacia adelante,A
hacia la izquierda yC
hacia la derecha en cada punto de la red en el límite de la forma. A esto le llamo una cadena de ángulo . Dos formas son rotacionalmente idénticas si sus cadenas angulares son permutaciones cíclicas. En lugar de verificar siempre esto comparando dos cadenas de ángulos directamente, cuando encontramos una nueva forma, la convertimos a una forma canónica antes de almacenarla. Cuando tenemos un nuevo candidato, convertimos a la forma canónica y verificamos si ya tenemos esto (explotando el hash, en lugar de iterar a través de todo el conjunto).La cuerda angular también se usa para verificar que la forma se forme en sentido antihorario, asegurándose de que el número de
A
s exceda el número deC
s en 4.La auto-intersección se verifica ingenuamente almacenando cada punto de la red en el límite de la forma y viendo si un punto se visita dos veces.
El algoritmo central es simple: coloca la primera barra a la derecha y luego prueba todas las posibilidades para las barras restantes. Si las barras alcanzan un punto que está demasiado lejos del origen (es decir, la suma de las longitudes de barra restantes es menor que la distancia de Manhattan del punto desde el origen), entonces dejamos de buscar ese subárbol prematuramente.
Actualizaciones (las últimas primero)
fuente