Tetris Tangrams

13

Introducción

Los tangramas son un rompecabezas clásico que involucra la organización / colocación de bloques en varias formas. Del chino 七巧板 - literalmente significa "siete tableros de habilidad". Tomemos esta idea y usemos los siete Tetrominos piezas de para llenar una cuadrícula.

Desafío

Escriba una función o programa que tome una matriz de coordenadas de cuadrícula como entrada y genere una cuadrícula completa de 10 por 20 llena de piezas de Tetris, excepto en las coordenadas especificadas.

Optimice su puntaje intentando mantener la distribución uniforme de las piezas.

Criterios

Utilice este pastebin de coordenadas para realizar su tarea. Hay cinco conjuntos de coordenadas. Siéntase libre de modificar el formato en el que se escriben las coordenadas, pero no los valores.

El conjunto de datos # 2 no se puede resolver; en este caso, simplemente envíe la cuadrícula con las celdas de entrada rellenadas (es decir, Xdonde están los agujeros).

Entrada

Las coordenadas de la cuadrícula representan 'agujeros' en la cuadrícula. Estas son células que no pueden contener ninguna parte de un Tetromino.

Coordenadas de cuadrícula:

(0,0), (1,0), (2,0), ... (9,0)
(0,1), (1,1), (2,1), ... (9,1)
.
.
.
(0,19), (1,19), (2,19), ... (9,19)
  • Use el estilo de matriz de su lenguaje de programación para ingresar las coordenadas.

  • Representar agujeros en la cuadrícula con un Xu otro ASCII imprimible .

Salida

Usando un tamaño de cuadrícula Tetris estándar de 10 celdas de ancho por 20 celdas de alto , imprima una cuadrícula de solución si y solo si la cuadrícula se puede llenar completa y perfectamente usando piezas de Tetromino.

Piezas construidas con letras I, O, L, J, T, Z, Scomo sigue:

I          
I          L      J
I    OO    L      J     T     ZZ      SS
I    OO    LL    JJ    TTT     ZZ    SS

Ejemplo

Ejemplo de solución de salida sin coordenadas de entrada:

ZZIIIILLLI
JZZTTTLLLI
JJJSTLOOLI
SZZSSLOOLI
SSZZSLLJJI
TSOOSLLJII
TTOOSSLJII
TZOOSSLZII
ZZOOSSZZII
ZJJJJSZLLI
TTTJJOOILI
ITZJJOOILI
IZZTTTLIII
IZOOTZLIII
IJOOZZLLII
LJJJZSSTII
LLLTSSTTTI
LLLTTSSZJI
OOLTSSZZJI
OOIIIIZJJI

Con distribución de la siguiente manera:

I          
I          L      J
I    OO    L      J     T     ZZ      SS
I    OO    LL    JJ    TTT     ZZ    SS

11   6     8     6      6     7      6

Notas

Las coordenadas representan un único Xy una Yposición en la cuadrícula. La cuadrícula está basada en 0, lo que significa que la coordenada (0,0)debe ser la celda superior izquierda o inferior izquierda, a elección del autor.

Los ladrillos pueden:

  • ser seleccionado a discreción del autor.
  • rotar como el autor lo considere conveniente.
  • colocarse en la cuadrícula en cualquier lugar a discreción del autor (también conocido como: sin gravedad de Tetris)

Los ladrillos no pueden:

  • colocarse fuera de los límites de la cuadrícula.
  • solape un ladrillo o agujero existente en la cuadrícula.
  • ser una pieza de Tetris tetromino no estándar.

Puntuación

Tu puntuación está en el formato:

(1000 - [bytes en código]) * (M / 10 + 1)

Donde M es un multiplicador para la distribución de piezas utilizadas en sus conjuntos de soluciones.

El puntaje más alto de los idus de marzo gana.

Para calcular M, agregue el valor de distribución de tetromino individual más bajo para cada conjunto y luego tome el promedio redondeado hacia abajo para calcular M.

Por ejemplo:

Set 1: 5
Set 2: 4
Set 3: 5
Set 4: 6
Set 5: 3

6 + 4 + 5 + 4 + 4 = 21/5 = 4.6

Entonces usarías 4como tu valor M.

Nota: Si un conjunto no tiene solución, no factorice ese conjunto en el cálculo de M, ya que no tendría distribución de tetromino.

CzarMatt
fuente
44
En general, es difícil mejorar las preguntas después de que se publican, porque si los cambios son sustanciales, invalidarán el trabajo de las personas que ya comenzaron a trabajar en el problema (o peor, incluso publicaron el resultado). Recomendaría publicar ideas de desafío en el sandbox . Ese es el lugar para pedir comentarios y pulir las especificaciones antes de que continúe. Dicho esto, después de un rápido vistazo, no vi ningún problema evidente con tu desafío.
Martin Ender
@ MartinBüttner Notable, gracias por los comentarios.
CzarMatt
2
Idus de marzo = 15 de marzo. Tenía que ver eso.
Level River St
He realizado algunos pequeños cambios para cargar la descripción de la tarea, porque de lo contrario es imposible entender lo que se nos pide que hagamos en la primera lectura. Creo que sería una mejora si usted declara cuál de los casos de entrada no se puede resolver, de modo que funcionen como casos de prueba además de un conjunto de datos de puntuación.
Peter Taylor
@PeterTaylor Muy bien, he agregado qué conjunto de soluciones no se puede resolver. Gracias por la respuesta.
CzarMatt

Respuestas:

2

Python 3 , 819 bytes, M = 0, Puntuación = 181

Este es un programa DFS de fuerza bruta. Construye una matriz numpy e inserta todos los agujeros ingresados. Luego toma el mosaico sin llenar más a la izquierda en la fila más alta que tiene uno, y coloca un tetromino. Recurrentemente, ahora lo hacemos de nuevo: cuando no podemos, encontramos una solución o retrocedemos y probamos otra pieza a la primera oportunidad.

Esto tiene una M de 0, ya que trata de usar piezas en un orden determinado, y casi siempre encuentra una solución sin la última en la lista. Intenté usar una lista ordenada aleatoriamente cada ciclo para hacer una distribución más uniforme, pero solo obtuve una M de 2, que no valía los bytes necesarios para importar random.shuffle .

No puedo comentar el código a continuación, ya que en mi golf hace mucho que olvidé lo que hace. La idea general:

  • Importe productos numpy e itertools, con nombres de 1 letra
  • Cambie el nombre de algunas incorporaciones para que sean funciones de 1 letra y defina una lambda para guardar bytes
  • Construya el conjunto de posibles tetrominos como nd-arrays, todas las rotaciones incluidas
  • En la función recursiva:
    • Obtenga la posición deseada del mosaico sin llenar y recorra la lista de piezas
    • Para cada pieza, recorra las traducciones de ella (moviéndola hacia arriba y hacia abajo)
    • Si algo no funciona (la pieza se sale del tablero, golpea otra pieza, golpea un agujero, etc.), intente la siguiente traducción o la siguiente pieza completa
    • Si funciona, genial. Pruébelo, luego llame recursivamente a la función.
    • Si esa ruta no funcionó, devolverá 'a', por lo que solo volveremos a intentarlo. Si funcionó, devuelve el tablero y lo pasamos por la línea.
  • Por último, el programa. Construimos la placa de 10x20 como una matriz de 1's.
  • La entrada tiene la forma (x1, y1); (x2, y2); ... Ponemos un 9 para cada hoyo en él, luego obtenemos el resultado de ejecutar la función en él.
  • La declaración impresa muestra el resultado exitoso o el tablero vacío original, línea por línea, sustituyendo los números por letras o símbolos apropiados.
import numpy as n
from itertools import product as e
m,s=range,len
p=[n.rot90(a,k)for a,r in[([[2,2]]*2,1),([[3]*3,[1,3,1]],4),([[0]*4],2),([[1,1,6],[6]*3],4),([[7,1,1],[7]*3],4),([[4,4,1],[1,4,4]],2),([[1,5,5],[5,5,1]],2)]for k in m(r)]
o=lambda a:e(m(s(a)),m(s(a[0])))
def t(l,d=0):
	g=list(zip(*n.where(l==1)))[0]
	for a in p:
		for u,v in o(a):
			w,x=l.copy(),0
			for r,c in o(a):
				if a[r,c]!=1:
					i,j=g[0]+r-u,g[1]+c-v
					if any([i<0,i>19,j<0,j>9])or l[i,j]!=1:
						x=1
						break
					w[i,j]=a[r,c]
			if x==0:
				if len(w[w==1]):
					f=t(w,d+1)
					if type(f)==str:continue
					return f
				return w
	return'a'
b=n.ones((20,10))
b[list(zip(*[eval(k)[::-1]for k in input().split(';')]))]=9
a=t(b)
for r in(a,b)[type(a)==str]:
	print(''.join(map(dict(zip([0,2,3,4,5,6,7,9,1],'IOTZSLJX-')).get,r)))

Pruébalo en línea!

Prueba de muestra:

In: (1,1);(8,1);(4,4);(5,8);(4,11);(5,15);(1,18);(8,18)
Out: 
IIIIOOOOLL
TXOOOOOOXL
TTOOOOOOTL
TOOIOOOOTT
TOOIXOOTTI
TTTITOOTTI
TTTITTTTII
OOTTTTTTII
OOTTTXOOII
TTTTOOOOII
TTTTOOOOII
TTTTXTOOII
ITTTTTTTII
ITTTTTTTII
IITTTLLTTI
IITOOXLTTI
IITOOTLTTI
IITTLTTTTI
IXTLLTJTXI
ILLLLLJJJI
Vedvart1
fuente
1
Oh mi - esto es asombroso. ¡Gracias por la maravillosa redacción y buen trabajo!
CzarMatt