Вступление

Tangrams - классическая загадка, вовлекающая расположение / подгонку блоков в различные формы. От китайского 七巧板 - буквально означает «семь досок мастерства». Давайте возьмем эту идею и используем семь фигур Тетромино, чтобы заполнить сетку.

Вызов

Напишите функцию или программу, которая принимает массив координат сетки в качестве входных данных и выводит заполненную сетку 10 на 20, заполненную кусочками тетриса, за исключением указанных координат.

Оптимизируйте свой счет, пытаясь сохранить равномерное распределение фигур.

критерии

Используйте этот набор координат для выполнения вашей задачи. Есть пять наборов координат. Не стесняйтесь изменять формат, в котором записаны координаты, но не значения.

Набор данных № 2 не может быть решен - в этом случае просто выведите сетку с заполненными входными ячейками (т. XЕ. Там, где находятся отверстия).

вход

Координаты сетки представляют собой «дыры» в сетке. Это клетки, которые не могут содержать какую-либо часть тетромино.

Координаты сетки:

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

• Используйте стиль массива вашего языка программирования для ввода координат.

• Представьте отверстия в сетке с помощью ASCIIX или другой печатной формы .

Выход

Используя стандартную сетку Tetris размером 10 ячеек и высотой 20 ячеек , напечатайте сетку раствора тогда и только тогда, когда сетка может быть заполнена полностью и идеально, используя кусочки тетромино.

Кусочки построенных с буквами I, O, L, J, T, Z, Sследующим образом :

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

пример

Пример выходного решения без входных координат:

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

С распределением следующим образом:

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

Примечания

Координаты представляют собой единое целое Xи Yположение на сетке. Сетка основана на 0, что означает, что координата (0,0)должна быть либо верхней левой, либо нижней левой ячейкой, по выбору автора.

Кирпичи могут:

• быть выбранным по усмотрению автора.
• вращаться так, как считает автор.
• размещаться на сетке в любом месте по усмотрению автора (иначе: нет гравитации тетриса)

Кирпичи не могут:

• размещаться за пределами сетки.
• перекрыть существующий кирпич или отверстие в сетке.
• быть нестандартной тетрис тетромино.

счет

Ваша оценка в формате:

(1000 - [байтов в коде]) * (M / 10 + 1)

Где M - множитель для распределения частей, используемых в ваших наборах решений.

Самый высокий балл по мартовским идам побеждает.

Чтобы вычислить M, добавьте наименьшее индивидуальное значение распределения тетромино для каждого набора, а затем возьмите среднее значение, округленное в меньшую сторону, чтобы вычислить M.

Например:

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

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

Таким образом, вы должны использовать в 4качестве значения М.

Примечание. Если у множества нет решения, не учитывайте это множество при вычислении M, так как оно не имеет распределения тетромино.

Python 3 , 819 байт, M = 0, счет = 181

Это программа грубой силы DFS. Он строит массив NumPy и вставляет все введенные отверстия. Затем он берет самую левую незаполненную плитку в верхнем ряду, в которой она есть, и помещает тетромино. Рекурсивно, теперь мы делаем это снова - когда мы не можем либо найти решение, либо возвращаемся назад и пробуем другой фрагмент при первой же возможности.

Значение M равно 0, поскольку он пытается использовать элементы в определенном порядке и почти всегда находит решение без последнего в списке. Я пытался использовать произвольно упорядоченный список каждый цикл, чтобы сделать более равномерное распределение, но я получил только M 2, что не стоило байтов, необходимых для импорта random.shuffle .

Я не могу прокомментировать приведенный ниже код, так как во время игры в гольф я давно забыл, чем он занимается. Общая идея:

• Импорт продукта numy и itertools, с 1-буквенными названиями
• Переименуйте некоторые встроенные функции в однобуквенные функции и определите лямбду для сохранения байтов
• Создайте массив возможных тетромино в виде n-ny-массивов, включая все вращения
• В рекурсивной функции:
  • Найдите нужную позицию незаполненной плитки и прокрутите список фигур
  • Для каждой части циклически перебирайте ее переводы (двигая вверх и вниз)
  • Если что-то не работает (кусок сходит с доски, попадает в другой кусок, попадает в дыру и т. Д.), Попробуйте следующий перевод или весь следующий фрагмент
  • Если это работает, отлично. Попробуйте, затем рекурсивно вызовите функцию.
  • Если этот путь не сработал, он вернет «а», поэтому мы просто попробуем еще раз. Если это сработало, оно возвращает доску, и мы передаем ее наверх.
• Наконец, программа. Мы строим доску 10x20 как массив из 1 единиц.
• Вход имеет вид (x1, y1); (x2, y2); ... Мы ставим 9 для каждого отверстия в нем, затем получаем результат запуска функции на нем.
• Затем оператор print отображает либо успешный результат, либо пустую оригинальную доску построчно, заменяя соответствующие буквы или символы числами.

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

Попробуйте онлайн!

Образец теста:

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