[QUIZ#6] World of Codecraft

Quiz #6
World of Codecraft

Regeln
Die Regeln und der Ablauf der Quizrunde können in der entsprechenden Ankündigung eingesehen werden. Bitte lest sie euch aufmerksam durch, da sie alle wichtigen Informationen enthält. Lösungsansätze können und dürfen auch schon vorab untereinander ausgetauscht und diskutiert werden, allerdings nicht öffentlich im Forum. Verwendet stattdessen bitte private Nachrichten oder schaut im Chat vorbei.

Abgabe
Die Abgabe erfolgt wie immer im Abgabeforum. Abgabefrist ist Sonntag, der 9. November 2008 um ca. 22 Uhr.

Das Problem
Du bist Beta-Tester des neuen, revolutionären MMORPG "World of Codecraft". Darin übernimmt der Spieler die Rolle eines Programmierers, der Programmieraufträge erfüllen muss, um seine Eigenschaftswerte zu verbessern. Der Programmierer besitzt die Eigenschaftswerte "Programmierung" und "Teamfähigkeit". Beide können ganzzahlige, positive Werte annehmen. Anfänglich besitzt man in beiden den Wert 1. Damit der Programmierer einen Auftrag annehmen kann, muss er in "Programmierung" oder in "Teamfähigkeit" eine bestimmte Mindestpunktzahl besitzen. Für die Erfüllung eines Auftrags bekommt der Programmierer Erfahrungspunkte. Diese kann er frei auf seine beiden Eigenschaftswerte verteilen.

Du hast dir nun bereits einige interessante Aufträge herausgesucht, von denen die Punkteanforderungen und die Erfahrungspunkte bekannt sind. Jetzt willst du herausfinden, wie viele dieser Aufträge du bei geschickter Wahl der Reihenfolge und Verteilung der Erfahrungspunkte höchstens erfüllen kannst. Da du im echten Leben auch ein Programmierer bist, schreibst du dir dafür natürlich ein Programm.

Die Eingabe besteht aus den Beschreibungen der ausgesuchten Aufträge. Jeder Auftrag wird durch zwei Zeilen spezifiziert. Die erste Zeile enthält den Titel (Benennung) des Auftrags. In der zweiten Zeile stehen durch Leerzeichen getrennt: die nötigen Punkte in "Programmierung", die nötigen Punkte in "Teamfähigkeit" und die Erfahrungspunkte, die man bei Erfüllung erhält. Das Ende der Eingabe wird durch eine Leerzeile markiert.

Als Ausgabe wird die maximale Anzahl der erfüllbaren Aufträge erwartet.

Erweiterung
Es sollen zusätzlich noch die Titel der auszuführenden Aufträge in der richtigen Reihenfolge und die zu wählende Punkteverteilung ausgegeben werden. Es bleibt euch überlassen, ob ihr alle möglichen (können sehr viele werden) oder nur die erstbeste Lösung ausgebt.

Beispiele
Eingabe:
Code:
Taschenrechner
1 1 1
Tabellenkalkulation
2 2 2
Ausgabe:
Code:
2
Ausgabe (erweitert):
Code:
1. Nehme "Taschenrechner" an, verteile 1 PR, 0 TF.
2. Nehme "Tabellenkalkulation" an, verteile 1 PR, 1 TF.
Hinweis 1: Es ist egal, ob man den einen Punkt aus "Taschenrechner" für PR (Programmierung) oder TF (Teamfähigkeit) verwendet. In beiden Fällen kann "Tabellenkalkulation" angenommen werden (da man ja die Punktegrenze in PR oder die in TF (oder beide) erfüllen muss).
Hinweis 2: Die Punkteverteilung von "Tabellenkalkulation" ist hier natürlich irrelevant und wurde willkürlich gewählt.

Eingabe:
Code:
A
1 1 2
B
3 1 1
C
1 3 1
D
10 20 5
E
3 3 1
Ausgabe:
Code:
4
Ausgabe (erweitert):
Code:
1. Nehme "A" an, verteile 2 PR, 0 TF.
2. Nehme "B" an, verteile 0 PR, 1 TF.
3. Nehme "C" an, verteile 0 PR, 1 TF.
2. Nehme "E" an, verteile 1 PR, 0 TF.


Eingabe:
Code:
A
603 614 19
B
710 669 2
C
65 985 21
D
577 610 1
E
751 624 12
F
786 826 16
G
358 817 2
H
339 494 19
I
257 937 5
J
35 268 6
K
1 1 14
L
58 357 1
M
681 607 5
N
640 559 2
O
370 744 15
P
310 452 20
Q
1 1 16
R
194 737 16
S
1 1 9
T
664 744 1
U
617 51 15
V
748 990 15
W
135 253 20
X
705 814 15
Y
371 491 13
Z
1 1 13
a
552 794 8
b
148 477 8
c
145 564 22
d
1 1 21
e
780 106 10
f
35 747 13
g
1 1 6
h
628 414 16
i
175 402 17
j
278 117 13
k
2 990 19
l
609 385 13
m
271 94 9
n
437 728 4
o
424 841 8
p
652 76 7
q
771 179 13
r
616 948 2
s
688 975 8
t
749 378 11
u
694 180 2
Ausgabe:
Code:
16
Ausgabe (erweitert): Keine Ahnung, dazu müsste ich die Erweiterung erst mal selber implementieren ;-)

Viel Spaß!
 

OnlyFoo

Erfahrenes Mitglied
Von mir iwrds diesmal keine Lösung geben...

(Übrigens, wenn man im Browser weiße Schrift hat (weil man ein dunkles Fenster-Schema hat, dann ist die schrift nicht lesbar...)
 

Anhänge

  • screen.jpg
    screen.jpg
    37,1 KB · Aufrufe: 252
Hallo,

hat überhaupt jemand die Absicht, an diesem Quiz teilzunehmen? Wenn nicht, woran liegt es? Ist die Aufgabe zu schwierig oder zu leicht? Ist die Aufgabenstellung unklar? Besteht überhaupt noch Interesse an der Fortführung des Coding Quiz?

Fragende Grüße,
Matthias
 

deepthroat

Erfahrenes Mitglied
Hi.
Hallo,

hat überhaupt jemand die Absicht, an diesem Quiz teilzunehmen? Wenn nicht, woran liegt es? Ist die Aufgabe zu schwierig oder zu leicht? Ist die Aufgabenstellung unklar? Besteht überhaupt noch Interesse an der Fortführung des Coding Quiz?
So wie es aussieht werde ich es wohl diesmal auch wieder nicht schaffen eine Lösung abzugeben.

Das letzte Quiz lag mir irgendwie nicht (grafische Aufgaben mag ich irgendwie nicht).

Die Aufgabenstellung mußte ich irgendwie öfter lesen bevor ich zum Kern durchgedrungen bin und die ganze Verpackung erstmal ausblenden konnte :)

Wenn es meine Zeit zuläßt würde ich auch wieder mal an einem Quiz teilnehmen, nur demnächst muss ich mal schauen.

Gruß
 

Fabsch

Erfahrenes Mitglied
Dieses mal habe ich es zwar gesehen, gelesen und angefangen, aber ich hatte nicht genug Zeit.
Aber ich denke, dass mehr mitmachen würden, wenn die Aufgaben etwas einfacher wären und man diese auch mal schnell als noch nicht so Fortgeschrittener in vielleicht 2-3 Stunden lösen kann (oder auch Aufgaben für Anfänger und für die Fortgeschrittenen dann noch kompliziertere Erweiterungen).
Aber falls es noch ein nächstes Quiz geben wird, werde ich wieder mitmachen, dann habe ich auch wieder mehr Zeit dafür.

MfG
Fabsch
 

Mairhofer

Erfahrenes Mitglied
Hallo,

hat überhaupt jemand die Absicht, an diesem Quiz teilzunehmen? Wenn nicht, woran liegt es? Ist die Aufgabe zu schwierig oder zu leicht? Ist die Aufgabenstellung unklar? Besteht überhaupt noch Interesse an der Fortführung des Coding Quiz?

Fragende Grüße,
Matthias
Auch wenn ich mir nur ansatzweise vorstellen kann was für eine Arbeit in den Vorbereitungen für ein Quiz stecken, so sage ich ehrlich, bis auf das erste Quiz, das sich die Aufgabenstellungen für mich nicht lohnen. Um es mal salopp zu sagen, sind es meistens nur Arrayabgrasungen mit nem kleinen Algo dahinter.
Da ich nur nebenbei programmiere und diese Programmierungen meistens für einen meiner Jobs sind, muss das Quiz schon einen Mehrwert haben, sprich ich brauche es aktuell oder könnte es in Zukunft benötigen, das ich meine andere Aufgabe unterbreche.

Und hier ist das Problem. Beim 1. Quiz (das mit den Präsidentennamen) konnte man die Lösungen theoretisch 1:1 übernehmen in eine echte Anwendung. Bei den anderen Quizthemen finde ich einfach keine für mich nutzbare Realanwendung.

Ich hoffe, das wird jetzt nicht falsch verstanden. Ich finde die Idee hinter dem Quiz gut. Habe gerne bei ner Tasse Kaffee entspannt und die Umsetzungen in anderen Programmiersprachen gelesen.
Nur die Themen die mich gerade beschäftigen oder beschäftigen werden, passen nicht in ein Quiz oder sind in mehreren Sprachen umsetzbar, daher auch keine Vorschläge von mir.
Als Beispiel kann ich nennen, das ich in der letzten Zeit unter anderem einen FeedParser geschrieben habe, in Zukunft steht etwas mit RTF an. Wie ich das einschätze, Aufgaben die nicht in ein paar Tagen sauber oder in Sprachen wie Bash zu lösen sind.
Oder anderes Beispiel wäre das arbeiten via PHP CLI (ohne Webkrams) wo ich mit sehr spezifischen Daten umgehe. Als Quizvorschlag würde dann rauskommen, nachdem man es für die Allgemeinheit umgestrickt und für mehrere Sprachen geöffnet hat, lese eine Datei ein, ordne die Zeilen nach Muster XYZ und schreibe die Daten wieder.

Nun gut, ich dachte ich schreib mal meine Meinung, vielleicht motiviert es andere auch ihre persönlichen Beweggründe zu nennen oder es entwickelt sich eine Diskussion. Hoffe es fühlt sich keiner durch meine Ehrlichkeit auf den Schlips getreten.

Schönen Abend noch
Gruss
Andreas
 

Thomas Darimont

Erfahrenes Mitglied
Hallo,

ich habe mich auch mit der (interessanten) Aufgabe beschäftigt aber am Wochenende nicht die Zeit gefunden das weiter zu verfolgen.
Wollte das ganze über einen Constraint-Solver lösen. Ein Prototyp mit Excel hat schon ein kleinem Rahmen funktioniert ;-)

Das habe ich dann ungefähr so aufgezogen.

Für n mögliche Projekte hat man 0 < t <= n mögliche "TimeSlots" an denen die
Projekte durchgeführt werden können. Für das Beispiel habe ich mich mal auf eine
Ressource beschränkt (und die Aufgabenstellung ein wenig vereinfacht).

Code:
Project	RSkill  Skill		T0	T1	T2		
A	3	4		0	1	0		1
B	4	5		0	0	1		1
C	1	3		1	0	0		1
	Skills:		1*	4	8	13

				1	1	1
Hier verlangt Projekt A einen Skill von 3 (Required Skill) und bringt 4 Skill-Punkte.
*) Wir starten hier mit einem Skill Punkt.

Für jedes Projekt führen wir nun eine binäre "TimeSlot" Variable ein die sagt ob ein
Projekt in diesem TimeSlot ausgeführt werden kann. Dabei legt man für T0...TN Spalten die Constraints fest dass die Summe in einer Splate sowie in einer Zeile nur 1 oder 0 sein kann.
Das heißt wir können in einem Time-Slot nur ein Projekt durchführen.

In der Skills-Zeile sieht man dann zu jedem Zeitpunkt wie viel Skill-Punkte man insgesamt erlangt hat. Diesen Wert (genauer gesagt, der letzte Skill-Wert in der Spalte T2) gilt es unter Beachtung der genannten Constraints zu maximieren.
Dabei sind die TimeSlot Variablen (T0-T2) unsere binären (also nur 1 oder 0) Veränderlichen.

Damit der Solver keine Projekte wählt für die nicht genügend Skills vorliegen müssen wir die Wahl von Projekten mit einem höheren RSkill Level als unser dezeitiges Skilllevel bestrafen.

Bei 3-4 Projekten kommt der Excel Solver noch gut damit klar. Jedoch läuft er
ab 5 Projekten nach einer ersten Lösung nicht mehr weiter. Bei ILP (Integer Linear Programming, also nur ganzzahlige Werte) Problemen ist der Excel Solver nicht so dolle...

Na ja, vielleicht schaff ich doch noch diese Woche was kleines nachzuliefern.

Also Coding Quiz unbedingt weiter führen, aber man sollte bei schwierigeren Aufgaben ein wenig mehr Zeit einräumen (vielleicht eine Woche). Weiterhin sollte man vielleicht mehrere (verschiedene) Aufgaben stellen und dann eine auswählen lassen. Probleme gibts ja genug ;-)

Gruß Tom
 

zeja

Erfahrenes Mitglied
Ja meine Lösung ist auch nicht so doll... hatte keine Zeit nochmal in mein KI-Buch nach dem Algorithmus für Planungsprobleme zu suchen den wir damals verwendet hatten. Insgesamt fand ich diese Aufgabe auch zu aufwändig um sie in so kurzer Zeit zu lösen.

Aber solche Quizze (wie ist denn die Mehrzahl? ;)) sind eine schöne Abwechslung zum sonstigen Arbeitsalltag und erinnern mich ein wenig an die Uniaufgaben.

Einige Aufgaben passen aber auch nur zu bestimmten Programmiersprachen. Vielleicht besteht in dieser Richtung auch Interesse. Gibts schließlich Aufgaben, welche sich nur mit Reflektierenden, dynamischen oder logischen Sprachen lösen lassen.

Insgesamt kommt mir hier aber auch die Diskussion und das Interesse an anderen Lösungen zu kurz. Mir kommt es doch mehr nach einem Wettbewerb vor, bei dem sich jeder irgendwo mit seinen Kenntnissen/Lösungen profilieren will. So ist es aber ja eigentlich nicht gedacht.

Ich gestehe aber, dass ich trotz Interesse momentan auch keine Zeit habe mehr zur Diskussion beizutragen :-/
 
Hallo liebe Quiz-Teilnehmer (und solche die es werden wollen)!

Danke für eure Antworten und Meinungen. Ich habe aus ihnen den Schluss gezogen, dass das Coding Quiz hier auf tutorials.de doch noch eine Zukunft hat. Das Aufgaben-Niveau war wohl die letzten beiden Male etwas zu hoch für die angepeilten 1-2 Stunden Bearbeitungszeit. Ich hoffe dass die heutige Aufgabe wieder etwas moderater ausfällt.

Und hier ist das Problem. Beim 1. Quiz (das mit den Präsidentennamen) konnte man die Lösungen theoretisch 1:1 übernehmen in eine echte Anwendung. Bei den anderen Quizthemen finde ich einfach keine für mich nutzbare Realanwendung.
Das heißt dann schlicht, dass du nicht in die unmittelbare Zielgruppe des Quiz fällst. Das bedeutet natürlich nicht, dass du deswegen nicht mehr teilnehmen sollst :) Wenn wieder mal eine Aufgabe kommt, die dir zusagt, dann bist du natürlich herzlich eingeladen, eine Lösung zu präsentieren. Dass das eher selten als öfter der Fall sein wird, ist natürlich klar.

Nun gut, ich dachte ich schreib mal meine Meinung, vielleicht motiviert es andere auch ihre persönlichen Beweggründe zu nennen oder es entwickelt sich eine Diskussion. Hoffe es fühlt sich keiner durch meine Ehrlichkeit auf den Schlips getreten.
Keineswegs. Danke für deine ehrliche Meinung!

Einige Aufgaben passen aber auch nur zu bestimmten Programmiersprachen. Vielleicht besteht in dieser Richtung auch Interesse. Gibts schließlich Aufgaben, welche sich nur mit Reflektierenden, dynamischen oder logischen Sprachen lösen lassen.
Das halte ich für ein Gerücht - sofern die Sprache turing-vollständig ist und das Problem turing-berechenbar, lässt sich das Problem auch mit der Sprache lösen. Aber manche Probleme lassen sich mit bestimmten Paradigmen eleganter lösen, das stimmt.

Insgesamt kommt mir hier aber auch die Diskussion und das Interesse an anderen Lösungen zu kurz. Mir kommt es doch mehr nach einem Wettbewerb vor, bei dem sich jeder irgendwo mit seinen Kenntnissen/Lösungen profilieren will. So ist es aber ja eigentlich nicht gedacht.
Da muss ich dir zustimmen, im selben Atemzug aber auch eingestehen, dass mir momentan selber die Zeit für die Diskussion fehlt (welche ja eigentlich im Mittelpunkt stehen sollte).

Ich werde mich dann mal zur Beratung mit mir selbst über die heutige Aufgabe zurückziehen. Stay tuned :)

Grüße,
Matthias
 
Hallo,

heute gibt es leider doch kein Coding Quiz, da mir keine passende Aufgabe einfallen wollte. Eventuell startet morgen eine neue Runde, die dann bis Montag läuft, aber ich will nichts versprechen.

Grüße,
Matthias