Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

#05: "Game of Life", K.d.C., 20.04.2008

Werbeanzeige

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

1

20.03.2008, 16:22

#05: "Game of Life", K.d.C., 20.04.2008

#05: "Game of Life"
Typ: Kürze des Codes
Deadline: 20.04.2008
Abgabe: contest@spieleprogrammierer.de

Bitte beachten:
- Ablauf und Regeln

Das Game of Life ist eine Simulation primitiven "Lebens" innerhalb einer 2D-Welt. Die Welt ist in unserem Fall quadratisch und besteht aus NxN Feldern (N liegt garantiert zwischen 1 und 256). Ein Feld kann entweder eine lebendige Zelle beinhalten oder leer sein. Die Simulation ist "rundenbasiert": in jeder Iteration wird die nächste Generation der Zellen berechnet. Dabei wird anhand folgender Regeln entschieden, was mit jedem Feld geschieht:
  • Hat ein leeres Feld genau 3 Zellen als Nachbarn, so entsteht auf diesem Feld eine neue Zelle.
  • Hat eine Zelle weniger als 2 Zellen als Nachbarn, so stirbt sie an Vereinsamung, und das Feld wird leer.
  • Hat eine Zelle mehr als 3 Nachbarzellen, so stirbt sie an Überbevölkerung, und das Feld wird leer.
  • Ansonsten bleibt das Feld unverändert.
Jedes Feld in der Spielwelt hat genau 8 Nachbarfelder: links oben, oben, rechts oben, links, rechts, links unten, unten und rechts unten. Das gilt auch für die Felder am Rand. Alles, was das Spielfeld auf der einen Seite verlässt, kommt auf der anderen Seite wieder herein. Man kann sich die 2D-Welt also so vorstellen, als sei sie über einen Torus (Donut) gespannt. Bei einer 1x1-Welt hat das einzige existierende Feld sich selbst 8x als Nachbar. Ist auf dem Feld eine Zelle, so stirbt sie an Überbevölkerung durch sich selbst (klingt komisch, ist aber so).

Eure Aufgabe ist es, eine Funktion zu programmieren, die für eine gegebene Spielwelt die nächste Generation berechnet - also die oben genannten Regeln für jedes Feld anwendet. Die Funktion erhält als Parameter die Größe der Welt world_size (= N, nicht N²), ein Eingabe- und ein Ausgabe-Array. Die nächste Generation der Spielwelt muss in dieses Ausgabe-Array geschrieben werden. Ein- und Ausgabespeicherbereich überlappen sich nicht.

C-/C++-Quelltext

 
1

void my_game_of_life(int world_size, const bool* p_world_in, bool* p_world_out);

Die Felder sind zeilenweise von oben nach unten und innerhalb der Zeilen von links nach rechts in den Arrays angeordnet. true steht für eine lebendige Zelle, false für ein leeres Feld. Wenn die aktuelle Spielwelt also wie folgt aussieht, ...

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12

8x8-Spielwelt
O = Zelle
. = leeres Feld

O....O..
.O...OO.
O...O.O.
.O.....O
OO..OO..
...O....
.OO...OO
O....OOO


... dann enthält das Eingabe-Array folgende Werte:

C-/C++-Quelltext

 
1

true, false, false, false, false, true, false, false, false, true, false, false, false, true, true, false, true, ...

Bitte beachten:
  • Bei diesem Wettbewerb kommt es nicht auf die Geschwindigkeit an, sondern auf die Anzahl der benötigten Token! Einen Token-Counter findet ihr hier.
  • Die Benutzung der Standardbibliothek ist verboten!
  • Weiterhin ist es nicht erlaubt, über die Grenzen der Arrays hinweg zu lesen bzw. zu schreiben (könnte zu Abstürzen führen).
  • Code, dessen Verhalten undefiniert ist, wird disqualifiziert. Passt also auf, dass ihr nicht zu viel kürzt!
Übrigens lohnt es sich, eine Visualisierung einzubauen, denn das Game of Life ist sehr interessant zu beobachten. Es gibt eine Vielzahl von "Lebewesen", die je nach Spielregeln entstehen können.


(Link)

(Link)

(Link)

(Quelle: Wikipedia-Artikel)

Viel Spaß und frohe Ostern!

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

//////////////////////////////////////////////////////////////////////////

// spieleprogrammierer.de-Programmier-Contest #05                       //

// ******************************************************************** //

// Titel: ...... "Game of Life"                                         //

// Typ: ........ Kürze des Codes                                        //

// Deadline: ... 20.04.2008                                             //

// Abgabe: ..... contest@spieleprogrammierer.de                         //

// ******************************************************************** //

//                                                                      //

// Aufgabenstellung siehe:                                              //

// https://www.spieleprogrammierer.de/phpBB2/viewtopic.php?t=9284        //

//                                                                      //

//////////////////////////////////////////////////////////////////////////


#include <iostream>
#include <cstdlib>

//////////////////////////////////////////////////////////////////////////


// maximale Größe der Welt (Breite und Höhe)

const int MAX_WORLD_SIZE = 256;

// Anzahl der durchzuführenden Tests

const int NUM_TESTS = 500;

//////////////////////////////////////////////////////////////////////////


// >>> DEINE FUNKTION - BITTE IMPLEMENTIEREN! <<<

// >>> BENUTZUNG DER STANDARDBIBLIOTHEK IST VERBOTEN! <<<

void my_game_of_life(int world_size, const bool* p_world_in, bool* p_world_out)
{
    // Alle Token zwischen "BEGIN COUNT" und "END COUNT" werden vom Token-Counter gezählt

    // (Download unter http://www.scherfgen-software.net/misc/tokencounter.zip).


    // BEGIN COUNT


    // Dies sind 5 Token:

    int x = 42;

    // END COUNT

}

//////////////////////////////////////////////////////////////////////////


// Referenzlösung (304 Token)

void correct_game_of_life(int world_size, const bool* p_world_in, bool* p_world_out)
{
    struct Helper
    {
        static int coords_to_index(int x, int y, int world_size)
        {
            // Was auf der einen Seite raus geht, kommt auf der anderen Seite wieder rein.

            while(x < 0) x += world_size;
            while(x >= world_size) x -= world_size;
            while(y < 0) y += world_size;
            while(y >= world_size) y -= world_size;

            // Index für die korrigierten Koordinaten bestimmen

            return y * world_size + x;
        }
    };

    for(int x = 0; x < world_size; ++x)
    {
        for(int y = 0; y < world_size; ++y)
        {
            // Nachbarn dieses Felds zählen

            const unsigned int num_neighbors = p_world_in[Helper::coords_to_index(x - 1, y - 1, world_size)] +
                                               p_world_in[Helper::coords_to_index(x, y - 1, world_size)] +
                                               p_world_in[Helper::coords_to_index(x + 1, y - 1, world_size)] +
                                               p_world_in[Helper::coords_to_index(x - 1, y, world_size)] +
                                               p_world_in[Helper::coords_to_index(x + 1, y, world_size)] +
                                               p_world_in[Helper::coords_to_index(x - 1, y + 1, world_size)] +
                                               p_world_in[Helper::coords_to_index(x, y + 1, world_size)] +
                                               p_world_in[Helper::coords_to_index(x + 1, y + 1, world_size)];

            // Index für aktuelles Feld bestimmen

            const unsigned int index = Helper::coords_to_index(x, y, world_size);

            if(num_neighbors == 3)
            {
                // Zelle wird geboren

                p_world_out[index] = true;
            }
            else if(num_neighbors < 2 || num_neighbors > 3)
            {
                // Zelle stirbt an Vereinsamung bzw. Überbevölkerung

                p_world_out[index] = false;
            }
            else
            {
                // Es passiert nichts.

                p_world_out[index] = p_world_in[index];
            }
        }
    }
}

//////////////////////////////////////////////////////////////////////////


int main()
{
    std::cout << "Teste ..." << std::endl;

    for(int i = 0; i < NUM_TESTS; ++i)
    {
        // zufällige Weltgröße bestimmen

        const int world_size = 1 + rand() % MAX_WORLD_SIZE;

        bool world_in[MAX_WORLD_SIZE * MAX_WORLD_SIZE];
        bool my_world_out[MAX_WORLD_SIZE * MAX_WORLD_SIZE];
        bool correct_world_out[MAX_WORLD_SIZE * MAX_WORLD_SIZE];

        // Welt zufällig füllen

        for(int i = 0; i < world_size * world_size; ++i) world_in[i] = rand() % 3 == 0;

        // mit beiden Implementierungen die nächste Generation berechnen

        my_game_of_life(world_size, world_in, my_world_out);
        correct_game_of_life(world_size, world_in, correct_world_out);

        // Ergebnisse vergleichen

        for(int j = 0; j < world_size * world_size; ++j)
        {
            if(my_world_out[j] != correct_world_out[j])
            {
                std::cout << "Fehler in Test Nr. " << (i + 1) << "!" << std::endl;
                goto end;
            }
        }
    }

    std::cout << "Die Implementierung scheint korrekt zu sein!" << std::endl;

end:
    return 0;
}
David Scherfgens Website | Konzentrationstest Polizei

drakon

Supermoderator

Beiträge: 6 513

Wohnort: Schweiz

Beruf: Entrepreneur

  • Private Nachricht senden

2

20.03.2008, 16:37

Klingt interessant. Da dürfte Beneroth mitmachen.. - Der hat das nämlich schon mal gemacht. (komplett) :D

Hmm.. Mal schauen, ob es mich überkommt.. ;)
http://www.drakon.ch | Weltweit 31. Bester Solitär Spieler (Standard XP)

Anonymous

unregistriert

3

20.03.2008, 16:49

Ich frage einfach mal wie "Kürze des Codes" definiert wird. Kommt es auf die Zeilen an, oder auf die Zeichen...?
Weil afaik lassen sich Projekte auch compilen, wenn sie komplett in eine Zeile geschrieben wurden. Das ist jetzt der Code von dir, hier auf der Seite lässt sich das schlecht anzeigen, hab es aber nochmal bei nopaste hochgeladen.

Quellcode

 
1

#include <iostream>#include <cstdlib> const int MAX_WORLD_SIZE = 256;const int NUM_TESTS = 500;void my_game_of_life(int world_size, const bool* p_world_in, bool* p_world_out){int x = 42;}void correct_game_of_life(int world_size, const bool* p_world_in, bool* p_world_out){struct Helper{static int coords_to_index(int x, int y, int world_size){while(x < 0) x += world_size;while(x >= world_size) x -= world_size;while(y < 0) y += world_size;while(y >= world_size) y -= world_size;return y * world_size + x;}};for(int x = 0; x < world_size; ++x){for(int y = 0; y < world_size; ++y){const unsigned int num_neighbors = p_world_in[Helper::coords_to_index(x - 1, y - 1, world_size)] +p_world_in[Helper::coords_to_index(x, y - 1, world_size)] +p_world_in[Helper::coords_to_index(x + 1, y - 1, world_size)] +p_world_in[Helper::coords_to_index(x - 1, y, world_size)] +p_world_in[Helper::coords_to_index(x + 1, y, world_size)] +p_world_in[Helper::coords_to_index(x - 1, y + 1, world_size)] +p_world_in[Helper::coords_to_index(x, y + 1, world_size)] +p_world_in[Helper::coords_to_index(x + 1, y + 1, world_size)];const unsigned int index = Helper::coords_to_index(x, y, world_size);if(num_neighbors == 3){p_world_out[index] = true;}else if(num_neighbors < 2 || num_neighbors > 3){p_world_out[index] = false;}else{p_world_out[index] = p_world_in[index];}}}}int main(){std::cout << "Teste ..." << std::endl;for(int i = 0; i < NUM_TESTS; ++i){const int world_size = 1 + rand() % MAX_WORLD_SIZE;bool world_in[MAX_WORLD_SIZE * MAX_WORLD_SIZE];bool my_world_out[MAX_WORLD_SIZE * MAX_WORLD_SIZE];bool correct_world_out[MAX_WORLD_SIZE * MAX_WORLD_SIZE];for(int i = 0; i < world_size * world_size; ++i) world_in[i] = rand() % 3 == 0;my_game_of_life(world_size, world_in, my_world_out);correct_game_of_life(world_size, world_in, correct_world_out);for(int i = 0; i < world_size * world_size; ++i){if(my_world_out[i] < correct_world_out[i]){std::cout << "Fehler in Test Nr. " << (i + 1) << "!" << std::endl;goto end;}}}std::cout << "Die Implementierung scheint korrekt zu sein!" << std::endl;end:return 0;}

http://rafb.net/p/rD2rbg63.html
Dies ist jetzt einfach nur der Vorgegebene Code von dir David.

EDIT: Hätte ich doch einfach mal kurz in die Regeln geschaut -_-
...die Anzahl der Token wird gezählt -.-
find den Code wie oben trotzdem schön :D

mfg Timma

David_pb

Community-Fossil

Beiträge: 3 886

Beruf: 3D Graphics Programmer

  • Private Nachricht senden

4

20.03.2008, 16:51

Die Anzahl der Token ist ausschlaggebend. Kurze Variablennamen und weglassen von Zeilenumbrüchen bringen also nichts.

Siehe auch: https://www.spieleprogrammierer.de/phpBB2/viewtopic.php?t=8826
@D13_Dreinig

rklaffehn

Treue Seele

Beiträge: 267

Wohnort: Braunschweig

  • Private Nachricht senden

5

20.03.2008, 17:37

Der Ergebnisvergleich sollte vieleicht besser auf != testen und nicht auf <.

Denn: false < true aber eben nicht umgekehrt. :)
God is real... unless declared integer.
http://www.boincstats.com/signature/user_967277_banner.gif

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

6

20.03.2008, 17:43

Aah, danke!
Das war aus einer Search & Replace-Aktion entstanden!

Bitte alle den Fehler im Test korrigieren.
Es muss so heißen:

C-/C++-Quelltext

 
1

if(my_world_out[i] != correct_world_out[i])
David Scherfgens Website | Konzentrationstest Polizei

TrommlBomml

Community-Fossil

Beiträge: 2 117

Wohnort: Berlin

Beruf: Software-Entwickler

  • Private Nachricht senden

7

20.03.2008, 18:27

ist das verweden der fkt. sqrt / sqr erlaubt?

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

8

20.03.2008, 18:32

Zitat von »"TrommlBomml"«

ist das verweden der fkt. sqrt / sqr erlaubt?

Nein, da das Verwenden der Standardbibliothek nicht erlaubt ist (steht in der Aufgabenbeschreibung). Ich bin mir ziemlich sicher, dass du diese Funktion überhaupt nicht brauchst. world_size ist nicht die Anzahl der Felder, sondern N. Die Welt hat N² Felder.
David Scherfgens Website | Konzentrationstest Polizei

TrommlBomml

Community-Fossil

Beiträge: 2 117

Wohnort: Berlin

Beruf: Software-Entwickler

  • Private Nachricht senden

9

20.03.2008, 18:34

ah danke, das wr mein denkfehler! dann natürlich schwachsinn!

Toa

Alter Hase

Beiträge: 944

Beruf: Research associate

  • Private Nachricht senden

10

20.03.2008, 18:39

Puhh, da trau ich mich vielleicht ran. Aber bitte nicht auslachen wenn mein Code net so super wird :( , weil die werden ja veröffentlicht.

Werbeanzeige

Zur Zeit ist neben dir 1 Benutzer in diesem Thema unterwegs:

1 Besucher