#07: "Lateinisches Quadrat", K.d.C., 20.07.2008

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

1

22.06.2008, 15:47

#07: "Lateinisches Quadrat"
Typ: Kürze des Codes
Deadline: 20.07.2008
Abgabe: contest@spieleprogrammierer.de

Bitte beachten:
- Ablauf und Regeln

Aufgabenstellung:
Aus der Wikipedia: Ein lateinisches Quadrat ist ein Quadrat aus n×n Feldern, wobei jedes Feld mit einem von n verschiedenen Symbolen belegt ist, so dass jedes Symbol in jeder Zeile und in jeder Spalte jeweils genau einmal auftritt. Die Zahl n wird Ordnung des lateinischen Quadrats genannt.

Beispiele für lateinische Quadrate:

	Quellcode
1 2 3 4	1 2 3 4 3 2 1 1 2 1 3 4 1 2 2 1 3 2 1 2 3 4 1 1 3 2 4 1 2 3

Diese beiden sind keine lateinischen Quadrate:

	Quellcode
1 2 3 4	1 2 3 4 1 2 3 4 1 3 3 2 5 6 7 8 4 3 2 1 2 3 4 1 1 4 3 2 6 7 8 5

Ihr sollt eine Funktion implementieren, die ein Quadrat von Zahlen erhält (zeilenweise in einem Array abgespeichert) sowie die Seitenlänge. Die Funktion soll entscheiden, ob es ein lateinisches Quadrat ist oder nicht. Die Seitenlänge liegt zwischen 1 und MAX_SQUARE_SIZE (im Testprogramm als Konstante definiert). Die Zahlen im Quadrat unterliegen keiner besonderen Beschränkung. Im Testprogramm liegen sie zwischen 0 und 9999999, aber darauf dürft Ihr euch nicht verlassen.

C-/C++-Quelltext

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

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

bool is_latin_square(const uint* p_numbers,
                     uint size)
{
    // BEGIN COUNT


    // Hier kommt dein Code!

    // true liefern, wenn das Quadrat ein lateinisches Quadrat ist, sonst false.

    return false;

    // END COUNT

}

Wie bei allen "Kürze des Codes"-Aufgaben ist die Verwendung der Standardbibliothek nicht erlaubt.
Derjenige gewinnt, der die kürzeste korrekte Lösung liefert.
Das Testprogramm arbeitet nur mit zufälligen Tests. Bei der endgültigen Bewertung werde ich auch noch einige Spezialfälle testen. Ihr solltet euch also nicht darauf verlassen, dass das Testprogramm alle Fehler aufdeckt.

Paket hier herunterladen

Das Paket besteht aus dem Quelltext der Testumgebung (inklusive Referenzimplementierung), Code::Blocks-Projekt und Token-Counter.

Viel Spaß und viel Erfolg!

David Scherfgens Website | Konzentrationstest Polizei

Zum Seitenanfang

Lord-archimedes

Treue Seele

Beiträge: 234

Wohnort: Hannover

2

22.06.2008, 20:39

lol @david eine echt coole Aufgabe
erst gestern fragte ich mich wann ein neuer contest kommt xD

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

3

22.06.2008, 20:53

Gut

Ich habe noch eine kleine Änderung gemacht.
Die Zahlen liegen im Testprogramm zwar zwischen 0 und 9999999, aber das muss nicht immer so sein.
Also bitte keine Arrays der Größe 10000000 ...

David Scherfgens Website | Konzentrationstest Polizei

Zum Seitenanfang

Gotbread

Alter Hase

Beiträge: 421

Beruf: Student (Etechnik) + Hiwi

4

22.06.2008, 21:27

gibt es schon ergebnisse was die tokenanzahl betrifft ?

bin bei 118

Mfg Goti
www.gotbread.bplaced.net
viele tolle spiele kostenlos, viele hardware-basteleien

"Es ist nicht undicht, es läuft über" - Homer Simpson

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

5

22.06.2008, 22:52

Bin im zweistelligen Bereich!

Aber ich muss noch durch extreme Brute Force-Tests herausfinden, ob meine Bedingung wirklich korrekt ist.

David Scherfgens Website | Konzentrationstest Polizei

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

6

23.06.2008, 00:06

Noch ein kleines Update:
Es gibt jetzt eine neue Konstante MAX_SQUARE_SIZE_SQ, die als MAX_SQUARE_SIZE * MAX_SQUARE_SIZE definiert ist.

David Scherfgens Website | Konzentrationstest Polizei

Zum Seitenanfang

Deviloper

Community-Fossil

Beiträge: 2 872

7

23.06.2008, 14:24

Hey das zählt nicht

Man kommt bestimmt auch ohne aus, und dann ist es blöd wenn du neue Sachen hinzufügst!

Devil Entertainment :: Your education is our inspiration
Der Spieleprogrammierer :: Community Magazin
Merlin - A Legend awakes :: You are a dedicated C++ (DirectX) programmer and you have ability to work in a team? Contact us!
Siedler II.5 RttR :: The old settlers-style is comming back!

Also known as (D)Evil