Du bist nicht angemeldet.

Werbeanzeige

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 184

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

21

10.02.2013, 12:11

@domin:
In Level 2 können sich die Figuren nicht gegenseitig helfen, da sie durch Mauern komplett voneinander getrennt sind.

domin

1x Contest-Sieger

  • Private Nachricht senden

22

10.02.2013, 12:13

Sorry hab ich übersehen... :S Ich dachte du beschreibst den Fall, dass die Spielsteine sich nicht gegenseitig helfen müssen, aber dies trotzdem können.
Meine Projekte:
LightBulb, TurtleRun

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 184

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

23

10.02.2013, 12:29

Ich habe Level 2 durch einen anderen ersetzt und werde jetzt noch die Contest-Beschreibung anpassen.
Neuer Level 2:

Quellcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
################
#.##############
#.............G#
#.##############
#.#b.......#...#
#.#B...........#
#.#............#
#.#............#
#.#............#
#.#............#
#.#............#
#.#............#
#.#.........#..#
#.###########..#
#R...........rg#
################
10

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 184

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

24

10.02.2013, 16:28

Ich habe so viele Ideen, was man alles anstellen könnte, um das Problem effizient zu lösen.
Leider sind die meisten davon recht tricky umzusetzen ...

Am Ende wird's wahrscheinlich auf etwas relativ Einfaches herauslaufen, das dann aber code-technisch ordentlich optimiert ist.

Zahlen möchte ich jetzt mal nicht nennen, dafür ist es noch zu früh.
Aber auf jeden Fall bin ich deutlich schneller als Helmut, der sicher noch irgendein Fehlerchen in seinem Programm hat ;)

Geheim

Treue Seele

Beiträge: 202

Wohnort: Salzburg

Beruf: Schüler

  • Private Nachricht senden

25

11.02.2013, 12:39

Hallo David,
Das ist ja mal eine schöne Aufgabe ;)
Ich hab allerdings eine Frage zu einem Satz von dir:
"Eure Funktion darf keine statischen Variablen benutzen oder sich auf
sonstige Weise Dinge für einen nachfolgenden Aufruf "merken". "
Es ist wahrscheinlich für die meisten klar was das bedeutet, aber ich bin mir nicht ganz sicher und bevor ich falsch drauf los lege will ich das lieber geklärt haben^^
Heißt das jetzt, dass ich mir von einem Level aufs Nächste nichts "merken" darf, oder dass ich mir innerhalb meiner Funktion zum Beispiel nicht merken darf, wo sich 'R' nur in diesem Level befindet?
Also bedeutet "nachfolgenden Aufruf", der Aufruf meiner Funktion pro Level, oder der Aufruf innerhalb meiner Funktion für meine Lösung?

MfG Geheim!

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 184

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

26

11.02.2013, 13:08

Es ist so gemeint, dass man z.B. Folgendes nicht machen darf:

C-/C++-Quelltext

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int numMovesToSolve(const Level& level)
{
    static bool initialized = false;
    static std::vector<bool> statesVisited;
    
    if (!initialized)
    {
        // Speicher reservieren, aber nur beim ersten Aufruf der Funktion.
        statesVisited.reserve(14 * 14 * 14 * 14 * 14 * 14);
        initialized = true;
    }
    else
    {
        // Der Vektor existiert noch!
        // Juhu, keine teure Speicherreservierung nötig!
    }

    statesVisited.assign(14 * 14 * 14 * 14 * 14 * 14, false);
    
    // Hier kommt der Algorithmus.
}

Innerhalb deiner Funktion darfst du dir selbstverständlich alles merken, was du willst.
Aber wenn deine Funktion das nächste Mal aufgerufen wird, darf sie nichts mehr vom vorherigen Aufruf wissen.

Geheim

Treue Seele

Beiträge: 202

Wohnort: Salzburg

Beruf: Schüler

  • Private Nachricht senden

27

11.02.2013, 17:03

Alles klar, dankeschön ;)

Schrompf

Alter Hase

Beiträge: 1 307

Wohnort: Dresden

Beruf: Softwareentwickler

  • Private Nachricht senden

28

11.02.2013, 19:41

Hab jetzt mit 2h Zeitaufwand eine Lösung gebastelt, die erstmal eine plumpe Breadth First-Suche über alle Zugmöglichkeiten macht. Damit komme ich schonmal auf 17,5ms für die erste Map und auf 370ms für die dritte Map. Allerdings nutzt meine Lösung aktuell noch _BitScanForward und _BitScanReverse, die als Compiler Intrinsics ja verboten sind. Mal schauen, ob ich die bei Gelegenheit clever ersetzen kann.

Ansonsten wäre mein nächster Schritt, vom Zielzustand aus rückwärts der Suche "entgegen zu gehen", um so die letzten und zumeist teuersten Iterationen einzusparen. Aber das wird warten müssen, bis ich wieder etwas Freizeit verantworten kann.
Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 184

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

29

11.02.2013, 19:44

Die Zeiten klingen gut, was für einen Prozessor hast du denn?
Und rückwärts suchen wird wohl nicht möglich sein. Eine Figur könnte theoretisch von überall gekommen sein, nicht nur von der nächsten Mauer.

BlueCobold

Community-Fossil

Beiträge: 10 870

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

30

11.02.2013, 19:50

Ich dachte das hätten wir schon geklärt :P
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Werbeanzeige