Die Community zu .NET und Classic VB.
Menü

ActiveVB-Wettbewerb 3: Ein Bär sucht Obst

 von 

Willkommen 

Es ist wieder so weit: ActiveVB veranstaltet den dritten Wettbewerb, der den Auftakt zu einer ganzen Reihe an Wettbewerben darstellt.

Motivation  

Herr Mustermann hat heute einen anstrengenden Tag vor sich - bei all dem Stress, den sein Job als Informatiker im Moment mit sich bringt, hatte er die Verpflichtungen des Alltags einfach aus dem Auge verloren.
Die Konsequenzen sind verheerend: Das Geburtstagspaket für seine Tanten liegt schon viel zu lange zuhause herum, die Tiefkühltruhe ist leer und Freddy der Kanarienvogel hungert. Ach ja, und der Minivan in der Auffahrt hat seine letzte Wartung ungefähr in der Steinzeit erlebt.

Naja, irgendwann muss es ja erledigt werden, denkt er sich also widerwillig und ist schon fast an der Haustür, da beginnt ihn eine Frage zu beschäftigen: Wie soll er am besten fahren? Bei den dutzenden Supermärkten in der Gegend, den Post-Annahmestellen und den wie Pilzen aus dem Boden sprießenden Zoohandlungen ist es doch quasi vorprogrammiert, einen Umweg zu nehmen.
Froh über die neu gewonnene Ausrede für einen Aufschub murmelte er noch eben ein Benzin ist kostbar! und wandte sich schnell wieder in Richtung Arbeitszimmer. Stift, Papier und eine Stadtkarte, damit sollte sich die beste Route doch sicher finden lassen.

Zuerst würde er kurz einen Abstecher zur Tankstelle machen müssen, um wenigstens einmal den Reifendruck zu prüfen, solange die Räder noch kalt sind. Dann schnell zur Post und das leidige Päckchen loswerden, bevor die absurd kurzen Öffnungszeiten ihm einen Strich durch die Rechnung machen, in die Tierhandlung und zuletzt die empfindlichen Gefrierwaren. Das klingt wie ein Plan, dachte Herr Mustermann sich und markierte die entsprechenden Stationen auf seiner Karte:


Abbildung 1: Das Schlachtfeld

Aber welche Tankstelle soll er nun als erste anfahren? Und dann zu welchem Postamt?
Was hier noch mit dem bloßen Auge zu lösen geht, wird bei mehr Stationen umso komplizierter. Wie kann man also die optimale Route effizient berechnen?

Aufgabenstellung  

Probleme wie das oben geschilderte treten häufig auf - natürlich bei jeder Art von komplizierter Logistik, aber auch im Alltag, und sei es, dass ein Bär auf der Wiese ein paar Sorten von Fallobst genießen will (um auch mal den mysteriösen Arbeitstitel des Wettbewerbs zu erklären). Generell einfach immer, wenn man aus einer Menge verschiedener Leistungen eine möglichst gute Auswahl getroffen werden soll. Wir formulieren das Problem folgendermaßen:

Beschreibung

Gegeben sei eine Menge von Stationen (Punkte in der Ebene), wobei jede Station einem bestimmten Stations- Typen angehört. Weiterhin ist eine Reihenfolge von Typen als Liste (Typ Nr. 1, Typ Nr. n) gegeben. Ein gültiger Weg besteht darin, zuerst zu einer beliebige Station von Typ 1, dann zu einer von Typ 2 usw. bis schließlich zu einer von Typ n zu fahren. Gesucht ist der kürzeste Weg , der Stationen aller angegebenen Typen in der richtigen Reihenfolge mindestens einmal besucht.

Auf einen Stadtplan verzichten wir natürlich, die Stationen können einfach mit geraden Linien verbunden werden. Es gibt keine weiteren Annahmen über die Reihenfolge oder die Stationen selbst (z.B. dass es sich um einen Rundweg handeln müsste), außer dass es zu jedem Typen auch mindestens eine Station gibt.

Implementierung des Wettbewerbs

Um die Leistungsfähigkeit der Lösungen objektiv zu bewerten, werden wir die Einsendungen diesmal mithilfe eines Programmes automatisiert mit den verschiedensten Eingaben auf Herz und Nieren prüfen. Dafür muss das zu entwickelnde Programm zumindest eine gemeinsame formale Schnittstelle erfüllen, über die wir es ansprechen können.

Die auf der Karte verfügbaren Stationen liegen in Form einer Textdatei mit folgendem Aufbau vor:

[Typbezeichnung] Name -> (x-Koordinate|y-Koordinate)

Hierbei bestehen Typbezeichnung und Name aus Zahlen, Buchstaben oder Leerzeichen. Leere Bezeichnungen kommen nicht vor. Eine mögliche Eingabe wäre beispielsweise:

[Zuhause] Home Sweet Home -> (10|10)
[Zoohandlung] Tante Ernas Kleintierhof -> (1,1|3,5)
[Supermarkt] Frisch auf den Tisch -> (100|42)
[Zoohandlung] Alles für den Dackel -> (-24,1|-11)

Die Reihenfolge, in der die einzelnen Typen anzulaufen sind, ist in einer weiteren Textdatei der folgendem Art gegeben:

Zuhause -> Zoohandlung -> Supermarkt -> Zuhause

Die Aufgabe besteht darin, ein Programm mit Namen wb3 zu entwickeln, das beide Textdateien und einen Ausgabepfad als Befehlszeilenargument aufnimmt, den kürzesten Weg mit den erhaltenen Vorgaben berechnet und als Ergebnis die Namen der entsprechenden Stationen in die Zieldatei schreibt. Beispiel für den Aufruf:

wb3 reihenfolge.txt stationen.txt kürzesterweg.txt

Als Ergebnis sollte die Datei kürzesterweg.txt eine entsprechende Ausgabe für den kürzesten Weg enthalten:

Home Sweet Home -> Tante Ernas Kleintierhof -> Frisch auf den Tisch -> Home Sweet Home

Über diese Spezifikation hinaus sind Ihrer Kreativität aber keine Grenzen gesetzt - bis hin zu ausgefeilten Benutzeroberflächen und Einspeisung ins Navigationssystem ;)

Ergebnisse  

Mit einiger Verzögerung, für die wir uns an dieser Stelle entschuldigen wollen, wurden am 30. Juli 2011 die Ergebnisse des Wettbewerbs veröffentlicht. Der Name des Gewinners lautet Alfred Ruf, besser bekannt als ActiveVB-Clubmitglied Nautilo, der mit der einzigen Einsendung in VB6 auf 85 Punkte kam. Platz zwei des Treppchens belegt Eckard Ahlers alias Spatzenkanonier mit 83 Punkten für sein VB.NET-Programm, gefolgt von Jonathan Haas mit 73 Punkten für sein C#-Programm.

Eine Übersicht über alle Teilnehmer, ihre Punktzahlen und ihre Projekte enthält die folgende Tabelle:

Name Verwendete SprachePunktzahlDownload
Nautilo Visual Basic 6 85 Projektdateien
Spatzenkanonier Visual Basic .NET 83 Projektdateien
Jonathan C# 73 Projektdateien
Timo Visual Basic .NET 53 Projektdateien
Claus Hoffmann Visual Basic .NET 49 Projektdateien

Tabelle 1

Wir, das Bereichsteam Wettbewerbe, bedanken uns auch im Namen von ActiveVB für die Einsendungen und das Interesse am Wettbewerb und freuen uns schon auf den nächsten Wettbewerb.

Bewertung und Anmeldung  

Das fertige Programm wird von den Juroren Dario Stein, Henrik Ilgen und Robert Closheim mit den folgenden Kriterien und Punktzahlen bewertet:

  • Erfüllung der Aufgabenspezifikationen: 20 Punkte
  • Verständlichkeit des Codes: 20 Punkte
  • Effizienz: 20 Punkte
  • Korrektheit der Lösung: 20 Punkte
  • Kreativität: 20 Punkte
Gewonnen hat, wer die meisten Punkte sammeln kann.

Der Wettbewerb dauerte vom 2. April 2011 bis zum 14. Mai 2011. Alle Einsendungen werden auf der Wettbewerbsseite veröffentlicht, sofern sie zumindest ansatzweise der Aufgabenstellung entsprechen. Einsendungen, die uns nach dem Einsendeschluss erreichen, können bei der Prämierung nicht mehr berücksichtigt werden. Bitte beachten Sie die allgemeinen Hinweise zu den Wettbewerben (akzeptierte Programmiersprachen und ähnliches) auf der Übersichtsseite zu den Wettbewerben.

Das Team von ActiveVB wünscht allen Teilnehmern viel Erfolg und freut sich auf rege Beteiligung.