Tetris in matematika

O matematiki, številih, množicah in računih...
Odgovori
Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Tetris in matematika

Odgovor Napisal/-a Aniviller »

Mene pa zanima, ce obstaja nacin izracuna stevila moznih blokov v tetrisu v odvisnosti od stevila kvadratkov iz katerih jih generiramo. Seveda so vse planarne rotacije ista ploskev. Naredil sem program, ki generira vse bloke poljubnega reda in dobil take stevilke: 1,1,2,7,18,60,196,704,2500,9189.
(opomba: naprej zato nisem generiral, ker bi trajalo cca. 20 ur :oops: )
Prvi so trivialni:

Koda: Izberi vse

1: X
2: XX
3: XXX   XX
          X
Ker se ne spoznam na matematiko diskretnih struktur, prosim ce lahko kdo pove, ce obstaja formula, ki opisuje ta problem. :?

Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Odgovor Napisal/-a Aniviller »

Se nekaj: analogen problem v treh dimenzijah (mogoce kdo pozna igro blockout iz leta 1988 :oops: :lol: ) mi da rezultate: 1,1,2,8,29,166,1023...
(tukaj bi trajalo 30 ur! :o )

Uporabniški avatar
shrink
Prispevkov: 14573
Pridružen: 4.9.2004 18:45

Odgovor Napisal/-a shrink »

Se nekaj: analogen problem v treh dimenzijah (mogoce kdo pozna igro blockout iz leta 1988
Blockout je moja najbolj priljubljena igra! Še posebej arkadna verzija, ki sem jo nekoč pred davnimi leti igral na igralnih avtomatih. Če hočeš igrat' arkadno verzijo, ti priporočam emulator MAME. Seveda si moraš nabavit' še ROM-e za Blockout. 8)

Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Odgovor Napisal/-a Aniviller »

Zato sem se pa spravil programirat 3D verzijo za poljuben N-matematicen eksperiment, in naletel na vprasanje, ki sem ga zastavil. Me veseli, da se kdo pozna stare legende racunalniskih iger! :D

Uporabniški avatar
mriz
Prispevkov: 2036
Pridružen: 13.5.2004 23:52
Kraj: maribor

Odgovor Napisal/-a mriz »

V čem si napisal ta program?

Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Odgovor Napisal/-a Aniviller »

Java. V 2D je verzija ze koncana, v 3D pa dalec od tega. So bli profesionalci, ni kej... :lol:

Uporabniški avatar
mriz
Prispevkov: 2036
Pridružen: 13.5.2004 23:52
Kraj: maribor

Odgovor Napisal/-a mriz »

Eh, škoda. Nam niso dali jave niti za povohat, kakor tudi ne diskretnih struktur :(

Pa vseeno, bi lahko dal kodo na ogled? :D Me zelo zanima kako poteka algoritem..

Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Odgovor Napisal/-a Aniviller »

Saj se da na kratko razlozit:

Vzames komplet ze zgeneriranih blokov nizjega reda (zacnes s piko 1x1x1),
Kopiras celoten blok (boolean array) v drugega, ki ima na vseh 6 straneh dodano eno prazno ploskev in za vse izmed praznih, ki se drzijo polnega naredis nov blok, ki ima na tistem mestu polno. Postopek ponovis z vsemi prejsnjimi bloki, vsem obrezes, kar ni potrebno (v vseh treh dimenzijah dolocis najmanjsi in najvecji index in kopiras v drug array, ki ima manjsi obseg (java ne podpira dinamicnih arrayev v najstrozjem smislu). To so zdaj vse mozne razsiritve za eno kocko. Potem pa tisto, ki traja najdlje. Vsak blok moras obrniti na vseh 24 moznih polozajev in za vsakega preveriti, ce je ze v zbirki ze pregledanih (ta je na zacetku prazna). Ce se ni, ga dodas. Vrtenje sem izvedel s transformacijsko matriko (drugace nikoli ne ves, kdaj imas vse obrnitve!). Ko je to koncano, si zakljucil.

Algoritem sem seveda zacel najprej za 2D, kjer ni bilo potrebne transformacije ampak le 3 vrtenja v isto smer, vse ostalo pa analogno z dimenzijo manj. Oba delujeta, kot sem ze rekel, casovno mogoce je izvesti 2D do 10 in 3D do 7.

Mogoce ti v prihodnjem tednu posljem kar 2D razlicico celga programa (je kar uzitek spilat...) :wink:

Uporabniški avatar
mriz
Prispevkov: 2036
Pridružen: 13.5.2004 23:52
Kraj: maribor

Odgovor Napisal/-a mriz »

v bistvu je bila kratka razlaga res bolj primerna :oops:

pa nebi mogel sam nekako iz tega izpeljat matematičnega pravila, vsaj za 2D?

Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Odgovor Napisal/-a Aniviller »

Poskusal sem ze... Prevec kriterijev. Ti moras za vsak blok, ki mu dolocas ali obstaja upostevati kriterij, ali ima soseda ali ne in ce imajo skupnega. Za to pa nimam kaksnega dobrega znanja iz matematike :cry: Sem pa s poskusanjem in predpostavko prisel do dokaj dobre aproksimacije:

2D: n=e^(0.29*x^1.5)
3D: n=e^(0.256*x^1.7)

(mogoce sta 1.5 in 1.7 sqrt(2) in sqrt(3), ampak ne vem (aproksimacija z excelom :cry: :oops: )

Od tukaj tudi predpostavka da kaj vec ne bo mogoce izracunati (vec kot eksponentna rast!)

:mrgreen:

Ma kdo kaksno idejo za tocnejsi izracun?

qg
Prispevkov: 780
Pridružen: 13.1.2006 20:05

qg

Odgovor Napisal/-a qg »

shrink napisal/-a:
Se nekaj: analogen problem v treh dimenzijah (mogoce kdo pozna igro blockout iz leta 1988
Blockout je moja najbolj priljubljena igra! Še posebej arkadna verzija, ki sem jo nekoč pred davnimi leti igral na igralnih avtomatih. Če hočeš igrat' arkadno verzijo, ti priporočam emulator MAME. Seveda si moraš nabavit' še ROM-e za Blockout. 8)
To je bila tudi moja priljubljena igra. Bil sem definitivno zasvojen in pomagalo je samo, da sem jo zbrisal na vseh meni dostopnih računalnikih.

Odgovori