Datatype

Moderators: jkien, Xilvo

Reageer
Berichten: 3

Datatype

Hoi

Voor het vak programmeren is de opdracht om een spelletje te programmeren dat erg lijkt op Tetris. Het wordt namelijk gespeeld op een 2 dimensionaal bord waarop verschillende blokjes verschijnen. Zoals bij Tetris wordt een volledig gevulde rij ook leeg gemaakt. Daarnaast hebben de blokjes 3 verschillende toestanden, zodat bijvoorbeeld een blokje in toestand 3 eerst naar toestand 2 en vervolgens naar toestand 1 zal moeten gaan voordat het van een rij kan verdwijnen. Een blokje dat zich in een volle rij bevindt zal dus steeds naar een lagere toestand gaan totdat het verdwijnt.

Nu is in de opdracht gegeven dat we zelf een gegevenstype moeten kiezen om het 2 dimensionale spelbord voor te stellen. Daarbij is vereist dat de hoeveelheid geheugen die in beslag wordt genomen door een leeg bord, onafhankelijk moet zijn van de dimensie van het bord. Verder moet er een constante uitvoeringstijd zijn wanneer er naar een positie op het bord gekeken wordt om te kijken of deze positie al dan niet bezet is door een deel van een blokje.

We moeten kiezen uit de gegevenstypes strings, list, tuples, sets en dictionaries. De meest voor de hand liggende is natuurlijk lists, maar ik dacht eerder aan dictionaries aangezien deze hashable zijn en zo een snelle uitvoeringstijd hebben. Ook leek het me dan eenvoudig om een positie op het bord op te slaan met bv de waarde 1 als key in de dictionary als de positie gevuld is en met als value de toestand van het blokje, bv voor positie (2,3) in het 2D array de waarde {1, toestand3} op te slaan.

Ik zou graag weten of dit de juiste keuze is en of er nog andere mogelijkheden zijn.

Vriendelijke groeten en alvast bedankt!

Berichten: 463

Re: Datatype

Voor een gegeven positie (x,y) op het bord moet je direct kunnen zien (= in O(1) tijd) of die positie bezet is.

Een 2 dimensionale array die het veld voorstelt mag in deze opdracht niet: "de hoeveelheid geheugen die in beslag wordt genomen door een leeg bord moet onafhankelijk zijn van de afmetingen van het bord".

Als je in een lijst naar positie (x,y) gaat zoeken, dan kost dat minstens O(log(n)) tijd (voor een geordende lijst) en in het slechtste geval zelfs O(n) tijd (voor een ongeordende lijst), deze optie valt dus af.

Een dictionary, doorgaans geimplementeerd als hashtable, doet dit wel in O(1) tijd (tenzij er veel collisions komen).
De key is dan de bordpositie (x,y), de waarde het ID-nummer van het blok op die positie.
(Als positie (x,y) niet bezet is, dan heeft deze positie geen waarde in de dictionary.)

De toestand van elk blok zou ik opslaan als variabele binnen/in het betreffende blok, en niet in deze dictionary: elk blok bezet immers een aantal bordposities (x,y), terwijl er maar 1 toestand per blok is.

Berichten: 1

Re: Datatype

Beste,
Als de afmetingen van het bord groter zijn krijg je toch ook meer bordposities en dus als gevolg meer keys in je dictionary en stijgt de hoeveelheid geheugen die er dan in beslag wordt genomen toch ook? Of ben ik hier fout?

Berichten: 3

Re: Datatype

Bedankt voor de verduidelijking, maar ik begrijp toch nog niet hoe ik dit juist zou moeten implementeren. Op dit moment gebruik ik volgende stukje code om een bord te initialiseren:

board = {}

for row in range(rows):
for col in range(columns):
board[(row,col)] = 'leeg'


Is het de bedoeling om enkel een positie als key toe te voegen aan de dictionary als de positie 'niet leeg' is? Met andere woorden zoals bij een sparse matrix gedaan wordt?

Berichten: 3

Re: Datatype

Na wat zoeken en prutsen probeer ik het als volgt: het bord sla ik op als een lege dictionary waaraan enkel tuppels worden toegevoegd met posities waarop zich een block bevindt. De dimensie van het bord heb ik ook opgeslagen onder de vorm board['dimensie'] = dimensie waarbij de variabele dimensie een tuppel is met de gegeven dimensies voor het bord. Zo wordt voor een leeg bord van eender welke grootte enkel het key value pair 'dimensie': dimensie opgeslagen.

Is dit een juiste manier van werken?

Berichten: 1

Re: Datatype

mashpotatos schreef: zo 05 apr 2020, 15:24 Na wat zoeken en prutsen probeer ik het als volgt: het bord sla ik op als een lege dictionary waaraan enkel tuppels worden toegevoegd met posities waarop zich een block bevindt. De dimensie van het bord heb ik ook opgeslagen onder de vorm board['dimensie'] = dimensie waarbij de variabele dimensie een tuppel is met de gegeven dimensies voor het bord. Zo wordt voor een leeg bord van eender welke grootte enkel het key value pair 'dimensie': dimensie opgeslagen.

Is dit een juiste manier van werken?
Ik heb ook deze methode gebruik met een key 'dimensie'. Ik snap enkel niet zo goed hoe je de blocks opslaat in de dictionary. Gebruik je als key dan de positie bvb. ('a', 3) en dan als value het block?

Berichten: 463

Re: Datatype

Diede schreef: za 04 apr 2020, 13:28 Beste,
Als de afmetingen van het bord groter zijn krijg je toch ook meer bordposities en dus als gevolg meer keys in je dictionary en stijgt de hoeveelheid geheugen die er dan in beslag wordt genomen toch ook? Of ben ik hier fout?
Zie de opdracht in de beginpost van dit topic:
"... Daarbij is vereist dat de hoeveelheid geheugen die in beslag wordt genomen door een leeg bord, onafhankelijk moet zijn van de dimensie van het bord. ..."

Een lege dictionary is niet afhankelijk van de grootte van het bord, maar heeft voor elk bord dezelfde geheugenomvang.
Als het spel start en er steeds meer geheugenposities komen, zal je deze posities inderdaad wel op moeten slaan, en zal de dictionary dus groter worden (= meer geheugenruimte in beslag nemen).

Berichten: 463

Re: Datatype

mashpotatos schreef: zo 05 apr 2020, 15:24 Na wat zoeken en prutsen probeer ik het als volgt: het bord sla ik op als een lege dictionary waaraan enkel tuppels worden toegevoegd met posities waarop zich een block bevindt. De dimensie van het bord heb ik ook opgeslagen onder de vorm board['dimensie'] = dimensie waarbij de variabele dimensie een tuppel is met de gegeven dimensies voor het bord. Zo wordt voor een leeg bord van eender welke grootte enkel het key value pair 'dimensie': dimensie opgeslagen.

Is dit een juiste manier van werken?
De dimensie van het veld kan je in 2 variabelen opslaan, bv. de variabelen 'breedte' en 'hoogte'.
De dictionary reserveer je voor key:value paren waarvan
key = bordpositie (x,y)
value = blok ID-nummer van het tetrisblok.
Elk tetrisblok beslaat dan 4 entries in de dictionary (want elk blok bestaat uit 4 vierkanten).

Op die manier kan je in de dictionary op basis van de key snel zoeken of een bordpositie bezet is of niet.
Elk blok kan bij beweging snel zijn oude entries wissen uit de dictionary en zijn nieuwe erin opslaan.

Reageer