Este desafío hará que cuente pseudo- polyforms en el mosaico cuadrado desaire .
Creo que esta secuencia aún no existe en el OEIS , por lo que este desafío existe para calcular tantos términos como sea posible para esta secuencia.
Actualización: esto ahora está en el OEIS como A309159 : Número de polyforms generalizadas en el mosaico cuadrado de desaire con n celdas.
Definiciones
El mosaico cuadrado es un mosaico semirregular del plano que consiste en triángulos y cuadrados equiláteros.
Una pseudo-poliforma en el mosaico cuadrado es una figura plana construida uniendo estos triángulos y cuadrados a lo largo de sus lados compartidos, de forma análoga a un poliomino. Aquí hay un ejemplo de una pseudo-poliforma de seis y ocho celdas:
Ejemplos
Para n = 1
hay dos pseudo-polyforms de 1 celda, a saber, el cuadrado y el triángulo:
Para n = 2
hay dos pseudo-polyforms de 2 celdas, a saber, un cuadrado con un triángulo y dos triángulos.
Para n = 3
hay cuatro pseudo-polyforms de 3 celdas.
Desafío
El objetivo de este desafío es calcular tantos términos como sea posible en esta secuencia, que comienza 2, 2, 4, ...
y donde el enésimo término es el número de pseudopolipos de n celdas hasta la rotación y la reflexión.
Ejecute su código durante el tiempo que desee. El ganador de este desafío será el usuario que publique la mayor cantidad de términos de la secuencia, junto con su código. Si dos usuarios publican el mismo número de términos, gana el que publique su último término más temprano.
(Una vez que haya suficientes términos conocidos para demostrar que esta secuencia aún no existe en el OEIS, crearé una entrada en el OEIS y enumeraré al contribuyente como coautor si así lo desea).
fuente
Respuestas:
Haskell
Ahora que no solo los comentarios documentan que Peter Taylor fue el primero en dar suficientes términos para buscar en OEIS, puedo dar mis resultados.
Anteriormente conté poliominoes hexagonales . Excepto por algunas optimizaciones, lo que estoy haciendo aquí es muy similar.
Los elementos del mosaico se representan así: puede ir en una línea casi recta de izquierda a derecha (en la primera imagen), alternando entre cuadrados y rectángulos. Hay líneas paralelas casi paralelas que se mueven en direcciones opuestas. Juntos, extrañan algunos triángulos. Hay líneas paralelas casi rectas similares de abajo hacia arriba, que contienen los triángulos que faltan. Ahora ignore el meneo y use un sistema de coordenadas cartesianas, pero solo use números impares para las coordenadas de los cuadrados. Luego, los triángulos obtienen pares de coordenadas con una coordenada par y otra impar. Los pares con ambas coordenadas incluso no representan elementos del mosaico.
(También podría usar números pares para las coordenadas de los cuadrados. Creo que decidí de esta manera porque pensé en la reflexión antes de la rotación).
Guarde el programa en un archivo con un nombre
cgp.hs
y compíleloghc -O2 -o cgp cgp.hs
. Toma un argumento de línea de comando numérico y calcula el número de poliominós de ese tamaño, o ninguno, en cuyo caso calcula los valores hasta que se detiene.Pruébalo en línea!
fuente
2, 2, 4, 10, 28, 79, 235, 720, 2254, 7146, 22927, 74137, 241461, 790838, 2603210, 8604861, 28549166, 95027832
Voy a poner una estaca en el suelo antes de que Christian Sievers publique una respuesta para n = 18. Esto es lo más lejos que puedo llegar con el código actual y 16 GB de RAM. Ya he tenido que sacrificar algo de velocidad para reducir el uso de memoria, y voy a tener que hacerlo aún más. Tengo algunas ideas ...
Este fragmento es el SVG del primer comentario.
El código es C #. Lo ejecuté con .Net Core 2.2.6 en Linux.
fuente