Tetris Tangrams

13

Wprowadzenie

Tangramy to klasyczna łamigłówka polegająca na układaniu / dopasowywaniu bloków do różnych kształtów. Od chińskiego 七巧板 - dosłownie oznacza „siedem desek umiejętności”. Weźmy ten pomysł i wykorzystajmy siedem kawałków Tetrominos do wypełnienia siatki.

Wyzwanie

Napisz funkcję lub program, który pobiera tablicę współrzędnych siatki jako dane wejściowe i wysyła wypełnioną siatkę 10 na 20 wypełnioną elementami Tetris, z wyjątkiem określonych współrzędnych.

Zoptymalizuj swój wynik, starając się utrzymać jednolity rozkład elementów.

Kryteria

Użyj tej pastebin współrzędnych, aby wykonać swoje zadanie. Istnieje pięć zestawów współrzędnych. Zmodyfikuj format zapisu współrzędnych, ale nie wartości.

Zestaw danych nr 2 nie może zostać rozwiązany - w tym przypadku po prostu wyślij siatkę z wypełnionymi komórkami wejściowymi (tzn. XTam, gdzie są otwory).

Wejście

Współrzędne siatki reprezentują „otwory” w siatce. Są to komórki, które nie mogą zawierać żadnej części Tetromino.

Współrzędne siatki:

(0,0), (1,0), (2,0), ... (9,0)
(0,1), (1,1), (2,1), ... (9,1)
.
.
.
(0,19), (1,19), (2,19), ... (9,19)
  • Użyj wybranego przez siebie stylu tablicy języka programowania, aby wprowadzić współrzędne.

  • Reprezentuj otwory w siatce za pomocą Xlub innego ASCII do wydruku .

Wynik

Używając standardowego rozmiaru siatki Tetris o szerokości 10 komórek i wysokości 20 komórek , wydrukuj siatkę roztworu tylko wtedy, gdy siatkę można całkowicie i idealnie wypełnić za pomocą elementów Tetromino.

Kawałki zbudowane z liter I, O, L, J, T, Z, Sw następujący sposób:

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

Przykład

Przykład rozwiązania wyjściowego bez współrzędnych wejściowych:

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

Z następującą dystrybucją:

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

Notatki

Współrzędne reprezentują pojedynczą Xi Ypozycję na siatce. Siatka jest oparta na 0, co oznacza, że ​​współrzędna (0,0)powinna być albo górną lewą, albo lewą dolną komórką, wybór autora.

Cegły mogą:

  • być wybrane według uznania autora.
  • być obracany według uznania autora.
  • być umieszczone na siatce w dowolnym miejscu według uznania autora (aka: brak grawitacji Tetris)

Cegły nie mogą:

  • być umieszczone poza granicami siatki.
  • nachodzą na istniejącą cegłę lub dziurę w siatce.
  • być niestandardowym kawałkiem Tetris tetromino.

Punktacja

Twój wynik jest w formacie:

(1000 - [bajty w kodzie]) * (M / 10 + 1)

Gdzie M jest mnożnikiem dla rozkładu elementów używanych w zestawach rozwiązań.

Najwyższy wynik Ides of March wygrywa.

Aby obliczyć M, dodaj najniższą indywidualną wartość rozkładu tetromino dla każdego zestawu, a następnie weź średnią zaokrągloną w dół, aby obliczyć M.

Na przykład:

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

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

Więc użyłbyś 4jako swojej wartości M.

Uwaga: Jeśli zestaw nie ma rozwiązania, nie uwzględniaj go przy obliczaniu M, ponieważ nie miałby on rozkładu tetromino.

CzarMatt
źródło
4
Poprawianie pytań po ich opublikowaniu jest na ogół trudne, ponieważ jeśli zmiany są znaczne, unieważnią pracę osób, które już rozpoczęły pracę nad problemem (lub, co gorsza, nawet opublikowały wynik). Polecam zamieszczanie pomysłów na wyzwania w piaskownicy . To miejsce, w którym można poprosić o opinię i dopracować specyfikację, zanim zacznie ona obowiązywać. To powiedziawszy, po szybkim przejrzeniu nie widziałem żadnych rażących problemów z twoim wyzwaniem.
Martin Ender,
@ MartinBüttner Należy zauważyć, dziękuję za opinie.
CzarMatt
2
Idy marca = 15 marca. Musiałem to sprawdzić.
Level River St
Wprowadziłem kilka drobnych zmian, aby załadować opis zadania, ponieważ w przeciwnym razie nie można zrozumieć, o co jesteśmy proszeni przy pierwszym czytaniu. Myślę, że poprawą byłoby stwierdzenie, których przypadków wejściowych nie można rozwiązać, aby działały one jako przypadki testowe oprócz zestawu danych oceniania.
Peter Taylor,
@PeterTaylor Do przyjęcia, dodałem, którego zestawu rozwiązań nie można rozwiązać. Dziękujemy za opinię.
CzarMatt

Odpowiedzi:

2

Python 3 , 819 bajtów, M = 0, wynik = 181

To jest program DFS z brutalną siłą. Buduje tablicę numpy i wstawia wszystkie wprowadzone otwory. Następnie bierze lewy, niewypełniony kafelek w najwyższym rzędzie, który ma jeden, i umieszcza tetromino. Rekurencyjnie, teraz robimy to ponownie - kiedy nie możemy albo znaleźć rozwiązania, albo wycofujemy się i wypróbowujemy kolejny kawałek przy pierwszej okazji.

Ma M 0, ponieważ próbuje użyć elementów w określonej kolejności i prawie zawsze znajduje rozwiązanie bez ostatniego na liście. Próbowałem użyć losowo uporządkowanej listy w każdym cyklu, aby uzyskać bardziej równomierny rozkład, ale dostałem tylko M wynoszące 2, co nie było warte bajtów wymaganych do importowania random.shuffle .

Nie mogę skomentować poniższego kodu, ponieważ podczas gry w golfa od dawna zapomniałem, jak wiele z tego robi. Ogólny pomysł:

  • Zaimportuj produkt numpy i itertools z 1-literowymi nazwami
  • Zmień nazwę niektórych wbudowanych funkcji na funkcje 1-literowe i zdefiniuj lambda, aby zapisać bajty
  • Zbuduj tablicę możliwych tetrominos jako tablice numeryczne i wszystkie rotacje włącznie
  • W funkcji rekurencyjnej:
    • Uzyskaj pożądaną pozycję niewypełnionego kafelka i przeglądaj listę elementów
    • Dla każdego utworu przewijaj jego tłumaczenia (przesuwając go w górę i w dół)
    • Jeśli coś nie działa (kawałek zjeżdża z planszy, uderza w inny kawałek, uderza w dziurę itp.), Spróbuj następnego tłumaczenia lub następnego całego
    • Jeśli to działa, świetnie. Spróbuj, a następnie wywołaj funkcję rekurencyjnie.
    • Jeśli ta ścieżka nie zadziała, zwróci „a”, więc spróbujmy jeszcze raz. Jeśli zadziałało, zwraca tablicę, a my przekazujemy ją dalej.
  • Wreszcie program. Budujemy tablicę 10x20 jako tablicę liczb 1.
  • Dane wejściowe mają postać (x1, y1); (x2, y2); ... Umieszczamy 9 dla każdego otworu w nim, a następnie otrzymujemy wynik uruchomienia funkcji na nim.
  • Instrukcja print wyświetla następnie pomyślny wynik lub pustą, oryginalną tablicę linia po linii, zastępując cyfry odpowiednimi literami lub symbolami.
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)))

Wypróbuj online!

Test próbny:

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
źródło
1
O rany - to jest niesamowite. Dzięki za wspaniały napisanie i miłej pracy!
CzarMatt