introduction

Les tangrams sont un puzzle classique qui consiste à disposer / ajuster des blocs en différentes formes. Du chinois meaning - signifiant littéralement "sept conseils de compétence". Prenons cette idée et utilisons les sept pièces Tetrominos pour remplir une grille.

Défi

Écrivez une fonction ou un programme qui prend en entrée un tableau de coordonnées de grille et génère une grille de 10 x 20 remplie de pièces Tetris, sauf dans les coordonnées spécifiées.

Optimisez votre score en essayant de garder la distribution des pièces uniforme.

Critères

Utilisez cette corbeille de coordonnées pour accomplir votre tâche. Il existe cinq ensembles de coordonnées. N'hésitez pas à modifier le format dans lequel les coordonnées sont écrites, mais pas les valeurs.

L'ensemble de données n ° 2 ne peut pas être résolu - dans ce cas, il suffit de sortir la grille avec des cellules d'entrée remplies (c'est-à-dire Xoù se trouvent les trous).

Contribution

Les coordonnées de la grille représentent des «trous» dans la grille. Ce sont des cellules qui ne peuvent contenir aucune partie d'un tétromino.

Coordonnées de la grille:

(0,0), (1,0), (2,0), ... (9,0)
(0,1), (1,1), (2,1), ... (9,1)
.
.
.
(0,19), (1,19), (2,19), ... (9,19)

• Utilisez le style de choix de votre langage de programmation pour saisir les coordonnées.

• Représentez les trous dans la grille avec un Xou un autre ASCII imprimable .

Production

En utilisant une taille de grille Tetris standard de 10 cellules de large par 20 cellules de haut , imprimez une grille de solution si et seulement si la grille peut être remplie complètement et parfaitement en utilisant des pièces Tetromino.

Pièces construites avec des lettres I, O, L, J, T, Z, Scomme suit:

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

Exemple

Exemple de solution de sortie sans coordonnées d'entrée:

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

Avec répartition comme suit:

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

Remarques

Les coordonnées représentent un seul Xet une Yposition sur la grille. La grille est basée sur 0, ce qui signifie que les coordonnées (0,0)doivent être en haut à gauche ou en bas à gauche, au choix de l'auteur.

Les briques peuvent:

• être sélectionné à la discrétion de l'auteur.
• être tourné comme l'auteur le juge bon.
• être placé sur la grille n'importe où à la discrétion de l'auteur (aka: pas de gravité Tetris)

Les briques ne peuvent pas:

• être placé en dehors des limites de la grille.
• chevaucher une brique ou un trou existant dans la grille.
• être une pièce non standard Tetris tetromino.

Notation

Votre score est au format:

(1000 - [octets dans le code]) * (M / 10 + 1)

Où M est un multiplicateur pour la distribution des pièces utilisées dans vos ensembles de solutions.

Le score le plus élevé des Ides de mars l'emporte.

Pour calculer M, ajoutez la valeur de distribution tétromino individuelle la plus faible pour chaque ensemble, puis prenez la moyenne arrondie vers le bas pour calculer M.

Par exemple:

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

6 + 4 + 5 + 4 + 4 = 21/5 = 4,6

Vous utiliserez donc 4comme valeur M.

Remarque: Si un ensemble n'a pas de solution, ne tenez pas compte de cet ensemble dans le calcul de M, car il n'aurait pas de distribution tétromino.

Python 3 , 819 octets, M = 0, score = 181

Il s'agit d'un programme DFS à force brute. Il construit un tableau numpy et insère tous les trous entrés. Il prend ensuite la tuile non remplie la plus à gauche sur la ligne la plus haute qui en a une, et place un tétromino. Récursivement, nous le faisons à nouveau - lorsque nous ne pouvons pas, nous avons trouvé une solution, ou nous revenons en arrière et essayons un autre morceau à la première occasion.

Celui-ci a un M de 0, car il essaie d'utiliser les pièces dans un ordre déterminé et trouve presque toujours une solution sans la dernière de la liste. J'ai essayé d'utiliser une liste ordonnée au hasard à chaque cycle pour faire une distribution plus uniforme, mais je n'ai obtenu qu'un M de 2, ce qui ne valait pas les octets requis pour importer random.shuffle .

Je ne peux pas commenter le code ci-dessous, car dans mon golf, j'ai oublié depuis longtemps ce qu'il fait. L'idée générale:

• Importer des produits numpy et itertools, avec des noms à 1 lettre
• Renommez certaines fonctions intégrées en fonctions à 1 lettre et définissez un lambda pour enregistrer les octets
• Construisez la gamme de tétrominos possibles sous forme de tableaux nd numpy, toutes les rotations incluses
• Dans la fonction récursive:
  • Obtenez la position de la tuile non remplie souhaitée et parcourez la liste des pièces
  • Pour chaque morceau, parcourez-en les traductions (en le déplaçant de haut en bas)
  • Si quelque chose ne fonctionne pas (le morceau sort du plateau, frappe un autre morceau, frappe un trou, etc.), essayez la traduction suivante ou la prochaine pièce entière
  • Si cela fonctionne, tant mieux. Essayez-le, puis appelez récursivement la fonction.
  • Si ce chemin n'a pas fonctionné, il renverra «a», nous essayons donc à nouveau. Si cela a fonctionné, il retourne le tableau et nous le faisons passer le long de la ligne.
• Enfin, le programme. Nous construisons la carte 10x20 comme un tableau numpy de 1.
• L'entrée est de la forme (x1, y1); (x2, y2); ... Nous mettons un 9 pour chaque trou, puis obtenons le résultat de l'exécution de la fonction dessus.
• L'instruction d'impression affiche alors soit le résultat positif, soit le tableau original vide ligne par ligne, en substituant les lettres ou symboles appropriés aux chiffres.

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)))

Essayez-le en ligne!

Échantillon test:

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