Hallo und herzlich willkommen zum ersten Programmierwettbewerb in der Entwickler-Ecke seit langem!

Da das Programmieren zu einem Programmierer-Forum genauso dazugehört, wie die Fragen zu verschiedensten Themen aus dem Bereich der Entwicklung von Software, möchten wir hier allen Interessenten einmal die Möglichkeit geben, ihre Kreativität unter Beweis zu stellen.

Die Aufgaben werden hierbei jedoch bewusst nicht in 5 Minuten lösbar sein, da das zugrundeliegende Thema etwas umfangreicherer Natur ist, aber trotzdem sehr spannend für die meisten sein dürfte. Eine Anregung zu diesem Thema erhielten die Initiatoren BenBE und Martok dabei von einem Posting was Luckie bereits vor längerer Zeit auf seiner Homepage veröffentlicht hat, in dem es um die simulierte Evolution von Computer-Programmen ging.
Dabei waren drei Dinge bemerkenswert:

1. Es gibt eine Möglichkeit Computer-Programme sich selbstständig optimieren zu lassen!
   
2. Dabei entstehen Programme, die effizienter als Menschengeschriebene Programme sind!
   
3. Die Programme sind völlig unverständlich
   

Und wenn das ein Buchautor hinbekommt, so sollte es doch auch für einen Programmierer mit guten Grundkenntnissen eine lösbare Aufgabe darstellen, solch ein Programm zu entwickeln.

Um jedoch für alle die gleichen Chancen zu gewähren und die Evolution der Programme möglichst einfach gestalten zu können, haben wir uns eine Variante einer Turing-Maschine als Austragungsort ausgesucht, die mit wenigen Befehlen (nämlich genau 9 Stück). Ihr habt es erraten: Als Programmiersprache nutzen wir eine Variante von BRAINFUCK

Die Aufgaben:

1. Schreibe ein BF-Programm, was "Hello world!" auf dem Bildschirm ausgibt. Optimiere dieses so weit es geht. Alle Optimierungsschritte sollten erkennbar sein!
   
   
2. Schreibe ein BF-Programm, was zwei Zahlen einliest, diese Potenziert UND dezimal auf dem Bildschirm ausgibt.
   
   
3. Schreibe ein Programm, was für eine beliebige (Text-)Eingabe ein BF-Programm angibt, was genau diese Eingabe als Ausgabe liefert. Das ausgegebene BF-Programm soll dabei automatisch von einem Programm der Evolution unterworfen werden, um dieses soweit es geht zu optimieren. Das ausgegebene Programm muss den untenstehenden Anforderungen genügen.
   
   
4. Dokumentiere alle geschriebenen Programme
   

Die Anforderungen:

• Die fertigen BF-Programme müssen auf dem von Martok im DF vorgestellten BF-Interpreter lauffähig sein und fehlerfrei laufen.
  
  
• Der Arbeitsspeicher des BF-Interpreters ist dabei auf maximal 8193 Speicherzellen begrenzt.
  
  
• Die Maximallaufzeit für ein Programm darf maximal 16*n^2+65536 Takte betragen, wobei n die Anzahl auszugebender Zeichen angibt.
  

Die Regeln:

1. Alle Programme müssen selbstgeschrieben, oder von selbst geschriebenen Programmen selbst geschrieben sein.
   
   
2. Fehler in Martoks BF-Interpreter sind zu melden, damit diese behoben werden können.
   
   
3. Die Nutzung von Fremd-Sources ist in der Dokumentation anzugeben.
   
   
4. Die eingesendete Lösung muss alle BF- und Delphi-Sources beinhalten, sowie die geschriebene Dokumentation.
   
   
5. Abgabe der Programme ist der 01.09.2007 00:00:00 UTC.
   
   
6. Von jedem User wird lediglich eine Lösung bewertet. Welche das bei Mehrfacheinsendungen ist, muss vor Abgabeschluss schriftlich (PN\Email) vorliegen. Bei Nichtvorliegen losen wir zufällig eine aus.
   

Die Bewertung:

• Die Initiatoren werden Referenz-Lösungen für die BF-Programme schreiben, die vor Beginn der Bwertung im DF veröffentlicht werden). Die Größe und Ausführungszeit dieser Programme wird reziprok ins Verhältnis gesetzt zu den eingesendeten Lösungen. Ein gleichschnelles und gleichgroßes Programm erhält 100 Punkte, ein halb so großes Programm 200.
  
  
• Die Punktzahlen für Größe und Ausführungsgeschwindigkeit werden für jede Teillösung multipliziert.
  
  
• Die Punktzahlen der Einzellösungen werden zur Gesamtpunktzahl multipliziert.
  
  
• Auf die Dokumentation gibt es eine Maximal-Punktzahl von 5 Punkten, für Lesbarkeit, Umfang, Detailreichtum, Verständlichkeit und weitere Faktoren. Diese wird mit den Punkten der Programmlösungen multipliziert.
  

Der Preis:

Als Preis winkten dem Gewinner eine Verewigung im Museum der Entwickler-Ecke.
Geld- und\oder Sachpreise können wir leider nicht bereitstellen.

Viel Spaß und Erfolg beim Coden wünschen euch
BenBE und Martok


Moderiert von Klabautermann: Topic aus Algorithmen, Optimierung und Assembler verschoben am So 29.04.2007 um 17:35

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Schöne Idee, aber auf Grund von Brainfuck enthalte ich mich. Darauf hab ich nun wirklich keine Lust.

Ich weiss nicht, ob man mit einem Ev.Alg. ein Programm sinnvoll optimieren lassen kann, wenn die Antwort nur korrekt (= richtige Ausgabe) oder falsch ist... Der Raum der Lösungen (mit korrekter Ausgabe) ist extram dünnbesetzt. Man kann sich fragen, in wiefern hier (kleine) Mutationen, Kreuzungen usw. Sinn machen. Von Hand zu optimieren ist vermutlich effizienter.
Schade, dass die Aufgaben nur sehr wenig mit Delphi zu tun haben. Die Idee und das Thema wären aber super.

Das Entwickler-Ecke Team möchte an dieser Stelle darauf hinweisen, dass es sich um keinen offiziellen Entwickler-Ecken Wettbewerb handelt.

Da wir solche Userinitiativen begrüßen und unterstützen markieren wir das Thema als Wichtig.

Da der hier versprochene Preis zwar angefragt aber niemals zugesagt wurde, machen wir eine Erwähnung des Gewinners im Museum von der Resonanz des Wettbewerbes abhängig.

Den Teilnehmern wünschen wir viel Erfolg.

Euer Entwickler-Ecke Team

Ich werde aufgrund von Brainfuck wohl auch nicht mitmachen. Wenn es Delphi gewesen wäre hätte ich vllt mitgemacht. Die Idee ist aber gut.

Hi,

Martok und ich haben selber vor der Umsetzung dieses Wettbwerbs ein wenig rumexperimentiert und sind dabei bereits auf recht gute Methoden gekommen, wie man eine solche Evolution realisieren kann. Man darf dazu allerdings nicht Schwarz-Weiß-Denken nutzen, sondern muss sich ein wenig am Beispiel der Natur orientieren.

Auch sind alle Aufgaben (außer die 1.) bewusst so gestellt, dass sie automatisiert gelöst werden können, wenn man eine Idee zur Realisierung findet. Für 3. ist explizit keine Kenntnis für Brainfuck notwendig (haben es ausprobiert und haben bisher relativ brauchbare Möglichkeiten gefunden).

Die Sprachwahl für diesen Wettbewerb wäre sicherlich mit Delphi besser an dieses Forum angelehnt, macht aber die Entwicklung der zugrundeliegenden Algorithmen um einiges komplizierter. Die Wahl von Brainfuck für die zu bewertenden Programme hat daher 2 Gründe:
1. Vereinfachung der Evolutionsprogramme, da man sich nicht um die Programmsyntax kümmern muss
2. Vereinfachung der Bewertung, da alle Programme aus einfachen, objektiv vergleichbaren Befehlen bestehen.

Da wir selber einige Startschwierigkeiten mit unseren Ansätzen hatten, haben wir bewusst sehr viel Zeit gegeben. Wir hoffen, dass es nicht allein an der etwas ungewöhnlichen Programmiersprache scheitern sollte.

P.S.: Eure Optimierungsprogramme dürfen sehr wohl in Delphi (oder auch jeder anderen gewünschten Programmiersprache) geschrieben sein.

MfG,
BenBE.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

hi!

ich würd mal sagen brainfuck is f***ed!
aba trotzdem, ich bin dabei!
nur 2 fragen:

zu 2. das programm soll wahrscheinlich auch der evolution unterworfen werden und optimiert sein

zu 3. ich versteh nicht so ganz was ich da machen soll. könnte mir das jemand bitte genauer erklären.
Thx!

dein Programm bekommt die Eingabe "Hello World" zum Beispiel, dann soll es ein BF Programm erzeugen, welches genau dieses als Ausgabe hat. (und das mit evolutionärer Optimierung)

mfg

F34r0fTh3D4rk hat folgendes geschrieben:

dein Programm bekommt die Eingabe "Hello World"...

damit ist mein delphi proggi gemeint und nicht das BF, das wird ja dann erst erzeugt, oder?

F34r0fTh3D4rk hat folgendes geschrieben:

(und das mit evolutionärer Optimierung)

also echzeit evolution

andras hat folgendes geschrieben:

hi! ich würd mal sagen brainfuck is f***ed! aba trotzdem, ich bin dabei! nur 2 fragen: zu 2. das programm soll wahrscheinlich auch der evolution unterworfen werden und optimiert sein

Wie das BF-Programm von 2. erstellt wird\wurde ist jedem selbst überlassen, solange der Weg dokumentiert ist, was zur Lösungsfindung genutzt wurde.

andras hat folgendes geschrieben:

zu 3. ich versteh nicht so ganz was ich da machen soll. könnte mir das jemand bitte genauer erklären. Thx!

Wie gerade bereits geschrieben: Du hast ein Delphi-Programm, welches für einen gegebenen Eingabe-String ein BF-Programm schreibt, was diesen String als Ausgabe liefer. Anschließend optimiert dein Delphi-Programm durch Evolution das erzeugte BF-Programm.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

@BenBe
Diese "Simulierte-Evolutions"-Sache klingt ja sehr interessant. Wo kann man sich denn über so etwas informieren?(Hab das von Luckie schon gelesen). Ich habe davon bisher noch nie etwas gehört.

Christian V. hat folgendes geschrieben:

Ich habe davon bisher noch nie etwas gehört.

Hi,

weißt Du, was das witzige daran ist??? Wir Initiatoren haben außer unserer Phantasie, dem Biologie-Unterricht und etwas kreativität sowie dem Post von Luckie keine detailiertere Beschreibung zum Thema selber. Ich habe Luckie einmal bzgl. des im Artikel erwähnten Buches angeschrieben; dieses handelt aber nicht von simulierter Evolution, sondern der Arbeitsweise von Computern - ist daher also für das Verständnis an dieser Stelle nicht wichtig.

Allgemein könnte Dir aber das Stichwort "Evolutionäre Algorithmen" weiterhelfen. Zu diesem Thema gibt es einiges ...

Ein gewisser Reiz an diesem Wettbewerb soll ja auch sein, einfach mal durch Probieren, Überlegen und Raten eine brauchbare Lösung zu finden

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Nun, dann werde ich mich in drei Wochen vielleicht einfach mal daran versuchen. Dann habe ich nämlich neun Wochen Ferien.

Hallo
klingt ja sehr spannend, werde sicher selber auch versuchen was ich damit machen kann.
ich habe noch eine frage zu aufgabe 1: soll das Programm auch mit Evolution optimiert werden wie die anderen?
super idee!!!!
lg

_Digger hat folgendes geschrieben:

Hallo klingt ja sehr spannend, werde sicher selber auch versuchen was ich damit machen kann. ich habe noch eine frage zu aufgabe 1: soll das Programm auch mit Evolution optimiert werden wie die anderen? super idee!!!! lg

Die erste Aufgabe sollte mit Hand gelöst werden. Wenn Du das mit Evolution machen willst, gerne, solang Du jeden Evolutionsschritt erklären kannst

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

hi
danke für die antwort
ich hätte da aber noch eine frage zu aufgabe 1: wie soll es jetzt genau heißen?
"Hello World" "Hello world" "hello world" "HELLO WORLD"??
lg

Steht in der Aufgabenstellung wörtlich drin ... Vielleicht hilft Dir das???

Der auszugebende Text ist das Zeug zwischen den ""

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

danke, ich wollte nur ganz sicher sein, man weiß ja nie...

Wieviele haben nun eigentlich mitgemacht?

PS @Benny: Ich gebs zu, ich hatte ja gesagt, dass ich evtl. mitmache, wenn ich Zeit habe... aber letzteres fehlte leider .

Es hat leider keine Einsendungen gegeben.

Leider war auch unsere Lösung nicht allzu perfekt, hat aber in einem gewissen Rahmen eine leicht optimalere Version des eingegebenen Algorithmus geliefert.

Somit wäre eigentlich jede halbwegs funktionierende Lösung besser als unsere gewesen *G*

Das Framework (unsere Lösung ...) stellen wir aber gern bereit (auf Anfrage), brauch nur ggf. ein wenig, da ich ATM keinen Zugriff auf die zugehörigen Files habe.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.