El Tangram es un rompecabezas de disección hecho de siete formas: cinco triángulos de diferentes tamaños, un paralelogramo y un cuadrado. Dada una forma, el objetivo es recrear la forma usando todas las piezas y sin superponerse. Obviamente, hay infinitas maneras de organizar este conjunto de piezas en el plano. Un subconjunto interesante son los
Tangramas de cuadrícula
Podemos dibujar el cuadrado de Tangram "estándar" en un cuadrado más grande que está subdividido por una cuadrícula en 16 cuadrados más pequeños. Los tangramas de cuadrícula son solo formas formadas por las piezas de tangram, de modo que todos los vértices de las piezas están en los puntos de la cuadrícula.
Estos son los tipos de rompecabezas de Tangram que queremos considerar en este desafío, ya que probablemente sean más fáciles de manejar que los más generales.
Como nota al margen: los matemáticos chinos Chuan-Chin Hsiung y Fu Traing Wang demostraron en 1942 que solo hay 13 tangramas convexos. Primero mostraron que el problema puede reducirse a tangramas de cuadrícula y luego usaron algunos argumentos combinatorios y geométricos. Estos son todos esos 13:
Reto
Dado un tangram de cuadrícula solucionable, envíe una disección del tangram de cuadrícula en las siete piezas de tangram.
IO
Se da un tangram como una imagen en blanco y negro (la forma es en negro, el fondo en blanco), con ambos lados múltiplos de 50px. La cuadrícula tiene un ancho de exactamente 50px. Las líneas de la cuadrícula son paralelas a los lados de la imagen.
EDITAR: La imagen puede aceptarse como entrada y devolverse como salida en cualquier formato de imagen ráster conveniente como PNG, TIFF, PBM, etc., pero es aceptable una representación como una matriz binaria 2D o cadena o matriz.
La salida debería tener nuevamente el mismo tamaño y debería tener nuevamente la misma forma, pero con cada pieza de un color diferente, o alternativamente con líneas blancas que separen todas las piezas. Vale la pena señalar que el cuadrángulo no rectangular se puede voltear.
Los píxeles en el borde de las piezas no tienen que coincidir exactamente con el de la forma, también si hay efectos de alias u otra pelusa, esto todavía está bien.
Ejemplo de entrada y salida:
Ejemplos:
Soluciones posibles:
Respuestas:
BBC BASIC,
570 514490 bytes ASCIIDescargue el intérprete en http://www.bbcbasic.co.uk/bbcwin/download.html
435 bytes tokenizados
El programa completo muestra una entrada
L.bmp
en la pantalla, luego la modifica para encontrar una solución.Explicación
Tenga en cuenta que en BBC basic una distancia de 1 píxel = 2 unidades, por lo que la cuadrícula de 50x50 píxeles se convierte en una cuadrícula de 100x100.
Usamos una función recursiva para colocar los 2 triángulos grandes, triángulo mediano, cuadrado y paralelogramo en la forma. La forma anterior de la lista se dibuja antes de realizar la siguiente llamada recursiva. Si una llamada recursiva regresa sin encontrar una solución, la forma anterior se sobreescribe en negro y se intenta una nueva posición de la forma anterior.
Una vez que se dibujan estas cinco formas, colocar los dos triángulos pequeños es solo una formalidad. Sin embargo, es necesario dibujar uno de ellos para distinguirlos si comparten una ventaja común. Solo coloreamos uno de los dos triángulos pequeños. El otro queda en negro natural.
Se intenta colocar cada forma en diferentes coordenadas x, y y en 4 rotaciones diferentes. Para probar si hay espacio libre para dibujar una forma, usamos la plantilla a continuación, con ángulos de 45 grados. Las rotaciones se realizan alrededor de los
*
8 píxeles probados y están en 2 semicírculos de radio de 9 y 81 unidades y caen en líneas radiantes en múltiplos impares de 22.5 grados a los ejes x e y.Para un triángulo grande, los 8 espacios deben estar libres. Para otras formas, solo algunas de las celdas deben estar claras para que se aplique una máscara.
Una vez que se establece que una forma se ajustará, debe dibujarse. Si es un triángulo con el que se traza
PLOT 85
, si es un paralelogramo, el número es 32 más alto (tenga en cuenta que paraPLOT
fines consideramos un cuadrado como un paralelogramo especial). En cualquier caso, se deben dar 3 vértices consecutivos. El segundo vértice es el origen de la forma (marcada*
en la tabla anterior) excepto en el caso del triángulo grande, donde (antes de la rotación) es-1,-1.
Los otros 2 vértices pueden tener coordenadas x e y de las-1,0 or 1
cuales se extraen de la base 3 números codificados, luego escalados por 99 y rotados según sea necesario mediante transformación conc
ys
.Código sin golf
Salida
Este es un montaje de las soluciones encontradas por el programa para los casos de prueba. El uso de 99 en lugar de 100 por razones de golf deja algunos pequeños espacios negros. Como las formas se vuelven a dibujar durante las búsquedas, puede tardar unos segundos en ejecutarse en algunos casos, y es bastante fascinante de ver.
fuente