Twoim zadaniem jest wdrożenie strategii Tetris zrównoważonej pod względem wyniku w stosunku do wielkości kodu.
W tej wersji gry tetromino są obracane i upuszczane z góry do siatki 20 rzędów i 10 kolumn. Podczas opadania nie można ich obracać ani przesuwać w poziomie. Jak zwykle, upuszczony element zatrzymuje się, gdy osiągnie dno siatki lub gdy dalszy ruch w dół spowodowałby kolizję z już zajętym kwadratem.
Gdy nlinie poziome zostaną całkowicie wypełnione, zapadają się jednocześnie, siatka jest uzupełniana npustymi liniami u góry, a wynik jest zwiększany o 2 n -1 punktów. Dla n= 1,2,3,4 to odpowiednio 1,3,7,15 punktów. Po zniknięciu linii niektóre bloki mogą nadal unosić się w powietrzu (nie ma „ reakcji łańcuchowej grawitacji ”).
Jeśli nie ma miejsca na pojawienie się bieżącego elementu w żądanym miejscu, siatka jest czyszczona, bieżący element jest ignorowany, a gra jest kontynuowana z następnym kawałkiem jako bieżącym. Nie ma za to kary.
Powinieneś przeczytać strumień rodzajów elementów i zdecydować, jak je obrócić i gdzie je upuścić. Patrząc w przyszłość na następny kawałek (tylko jeden) jest dozwolony: możesz spojrzeć na kawałek i+1przed odpowiedzią i, ale musisz zdecydować o losie iprzed spojrzeniem i+2. Żadne spojrzenie w przyszłość nie jest dostępne poza ostatnim fragmentem danych wejściowych.
Typy Tetromino i ich rotacje są kodowane zgodnie z następującą tabelą:
type 0 1 2 3 4 5 6
O I Z J L S T
┌────┬────┬────┬────┬────┬────┬────┐
rotation 0 │## │# │## │ # │# │ ## │### │
│## │# │ ## │ # │# │## │ # │
│ │# │ │## │## │ │ │
│ │# │ │ │ │ │ │
├────┼────┼────┼────┼────┼────┼────┤
1 │## │####│ # │### │ # │# │# │
│## │ │## │ # │### │## │## │
│ │ │# │ │ │ # │# │
│ │ │ │ │ │ │ │
├────┼────┼────┼────┼────┼────┼────┤
2 │## │# │## │## │## │ ## │ # │
│## │# │ ## │# │ # │## │### │
│ │# │ │# │ # │ │ │
│ │# │ │ │ │ │ │
├────┼────┼────┼────┼────┼────┼────┤
3 │## │####│ # │# │### │# │ # │
│## │ │## │### │# │## │## │
│ │ │# │ │ │ # │ # │
│ │ │ │ │ │ │ │
└────┴────┴────┴────┴────┴────┴────┘
Dane wejściowe są binarne - sekwencja bajtów, której reszta po podzieleniu przez 7 powinna być interpretowana jako OIZJLSTtetromino. Wystąpią one z mniej więcej takim samym prawdopodobieństwem (z tym wyjątkiem, że kilka pierwszych typów może pojawić się nieco częściej, ponieważ 256 nie jest wielokrotnością liczby 7, ale powinno to być nieistotne). Dane wejściowe mogą pochodzić ze standardowego wejścia lub z pliku o nazwie „i” lub zostać przekazane jako argument. Możesz odczytać wszystkie dane naraz, pod warunkiem przestrzegania ograniczenia wybiegania w przyszłość.
Dane wyjściowe są również binarne - sekwencja bajtów o tej samej długości co dane wejściowe. Może to być standardowe wyjście lub plik o nazwie „o” lub wynik funkcji. Każdy bajt koduje r*16 + x, gdzie rjest pożądany obrót i xjest indeksem 0 kolumny, w której powinien znajdować się skrajnie lewy kwadrat obróconego tetromina. Te ri xmuszą być ważne, tj. 0 ≤ r ≤ 3I 0 ≤ x ≤ 10-w, gdzie wjest szerokość odpowiedniego elementu.
Twój program musi być deterministyczny - biorąc pod uwagę to samo wejście, musi wytwarzać dokładnie to samo wyjście. Używanie PRNG jest w porządku, pod warunkiem, że jest stałe.
Całkowity wynik to wynik z gry minus rozmiar kodu w bajtach. Proszę użyć następującego pliku (64 kB pseudolosowego szumu) jako danych wejściowych: https://gist.github.com/ngn/857bf2c99bfafc649b8eaa1e489e75e4/raw/880f29bd790638aa17f51229c105e726bce60235/i
Poniższy skrypt python2 / python3 odczytuje pliki „i” i „o” z bieżącego katalogu, odtwarza grę i drukuje wynik (pamiętaj, aby odjąć rozmiar kodu od wyniku):
a = [0] * 23 # grid (1square=1bit, 1row=1int, LSB is left, 3 empty rows on top)
# O I Z J L S T tetrominoes
t = [[[3,3],[1,1,1,1],[3,6], [2,2,3],[1,1,3],[6,3], [7,2] ],
[[3,3],[15], [2,3,1],[7,4], [4,7], [1,3,2],[1,3,1]],
[[3,3],[1,1,1,1],[3,6], [3,1,1],[3,2,2],[6,3], [2,7] ],
[[3,3],[15], [2,3,1],[1,7], [7,1], [1,3,2],[2,3,2]]]
tw = [[2,1,3,2,2,3,3],[2,4,2,3,3,2,2],[2,1,3,2,2,3,3],[2,4,2,3,3,2,2]] # widths
th = [[2,4,2,3,3,2,2],[2,1,3,2,2,3,3],[2,4,2,3,3,2,2],[2,1,3,2,2,3,3]] # heights
score = 0
for p, rx in zip(bytearray(open('i', 'rb').read()),
bytearray(open('o', 'rb').read())):
p %= 7; r = rx >> 4; x = rx & 15 # p:piece type, r:rotation, x:offset
b = [u << x for u in t[r][p]] # as a bit-matrix (list of ints)
bw = tw[r][p]; bh = th[r][p] # width and height
y = 0 # drop it
while y <= 23 - bh and all((a[y + i] & b[i]) == 0 for i in range(bh)):
y += 1
y -= 1
if y < 3: # no room?
a = [0] * len(a) # clear the grid and carry on
else:
for i in range(bh): # add the piece to the grid
a[y + i] |= b[i]
n = 0
for i in reversed(range(bh)): # collapse full lines
if a[y + i] == (1 << 10) - 1:
n += 1; del a[y + i]; a = [0] + a
score += (1 << n) - 1
print(score)
Podobnie działa znacznie szybszy program C, ale z pewnością działa tylko w systemie Linux:
#include<stdio.h>
#include<fcntl.h>
#include<sys/mman.h>
#include<sys/stat.h>
#define F(i,n,b...)for(i=0;i<n;i++){b;}
typedef int I;typedef char C;
I a[23],t[]={
51,4369,99,802,785,54,39,51,15,306,71,116,561,305,
51,4369,99,275,547,54,114,51,15,306,113,23,561,562};
C*th="2423322213223324233222132233";
I main(){
struct stat h;stat("i",&h);I i,j,k,l=h.st_size,z=0;
C*mi=mmap(0,l,1,1,open("i",0,0),0),*mo=mmap(0,l,1,1,open("o",0,0),0);
F(k,l,
I p=(mi[k]&255)%7,r=3&mo[k]>>4,q=r*7+p,x=mo[k]&15,y=0,h=th[q]-'0',b[4];
F(i,h,b[i]=(t[q]>>(4*i)&15)<<x)
while(y<=23-h){I u=0;F(i,h,u|=a[y+i]&b[i])if(u)break;y++;}
if(--y<3){F(i,23,a[i]=0)continue;}
F(i,h,a[y+i]|=b[i])
I n=0;F(i,23,n+=a[i]==1023)
if(n){j=23;F(i,20,a[j]=a[22-i];j-=a[j]!=1023)F(i,j,a[i]=0);z+=(1<<n)-1;})
printf("%d\n",z);return 0;}
Najwyższy łączny wynik wygrywa. Standardowe luki są zabronione.
Odpowiedzi:
C, wynik: 4136 (4290–154 bajtów)
Chodzi o to, że bloki S, Z, O, używam ustalonych lokalizacji i rotacji:
Reszta - J, L, T - są upakowane w pierwszych trzech kolumnach z pewną cykliczną rotacją.
Wersja bez golfa:
źródło