37. Bundeswettbewerb

Material zu den Aufgaben der 2. Runde

Hier steht das Material für die 2. Runde des 37. BwInf zum Download bereit (letzte Änderung: 30. März 2019). Einige Fragen zu den Aufgaben sind bereits im Community-Forum des Portals Einstieg Informatik beantwortet, ein wiederholter Blick dorthin lohnt sich also. Wertvolle Anregungen geben aber auch die Tipps und Beispiellösungen der Vorjahre. Wichtig sind zudem die Beschreibungen von Inhalt und Struktur der einzureichenden ZIP-Archivdatei mit den Aufgabenlösungen.

Das Material steht zusammen mit den Aufgaben auch in einem Git-Repository auf git.bwinf.de zur Verfügung. Wenn Git installiert ist, kann man das Repository mit dem folgenden Kommandozeilenbefehl auf den eigenen Rechner klonen:

git clone https://git.bwinf.de/bwinf/bwinf37-runde2.git

WICHTIG: Aus aktuellem Anlass sei nochmals darauf hingewiesen, dass vor Einsendeschluss keine Lösungsideen oder Lösungen mit Programmen veröffentlicht werden dürfen. Stellt daher bitte sicher, dass ein eigenes Software-Repository für den Wettbewerb (z.B. bei einem Git-Hoster wie GitLab oder GitHub) nicht öffentlich einsehbar ist.

Vorlagen

Im Folgenden findet ihr drei Vorlagen (letzte Änderung: 18. Dezember 2018), die ihr für eure Dokumentation der Aufgabenbearbeitungen verwenden könnt (aber nicht müsst).

Eine kurze Anleitung, wie man mit LaTeX Texte schreibt, haben wir für euch hier bereitgestellt: LaTeX-Kurzanleitung.

Alle Vorlagen befinden sich auch in einem Git-Repository unter https://git.bwinf.de/bwinf/vorlagen.

Aufgabe 1: Lisa rennt

Zu dieser Aufgabe gibt es fünf zu verarbeitende Textdateien mit Beispieldaten (letzte Änderung: 30. März 2019):

Dabei enthält in jeder Datei

  • die erste Zeile die Anzahl p der Polygone, 
  • jede der folgenden p Zeilen für das jeweilige Polygon die Information „nx1y1x2y2 ... xnyn“ über die Anzahl n seiner Ecken (mindestens drei Ecken) und die ganzzahligen xi- und yi-Koordinaten (xi, yi) seiner n Ecken (die Zahlen sind durch einzelne Leerzeichen voneinander getrennt),
  • die letzte Zeile die ganzzahligen x- und y-Koordinaten von Lisas Haus (getrennt durch ein Leerzeichen).

Dokumentation der Ergebnisse:

Alle fünf Beispiele sollten bearbeitet und klar dokumentiert werden, d.h. die Beispiele sollten im PDF der Dokumentation der Aufgabe enthalten sein.

Das dokumentierte Ergebnis einer Routenberechnung sollte zumindest die folgenden Angaben umfassen (weitere Angaben sind gerne möglich):

  • (späteste) Startzeit (Uhrzeit auf Sekunden genau) für Lisa an ihrem Haus
  • (beste) Zielzeit (Uhrzeit auf Sekunden genau) für Lisas Treffen auf den Bus an der Landstraße,
  • (positive) y-Koordinate (auf Meter genau) von Lisas Treffen auf den Bus,
  • Dauer (in Minuten, auf Sekunden genau) und Länge (auf Meter genau) von Lisas Route,
  • x- und y-Koordinaten (auf Meter genau) aller Eckpunkte der berechneten Route von Lisas Haus bis zur Landstraße (einschließlich der Nennung der ID des jeweiligen Hindernispolygons),
  • Visualisierung der berechneten Route von Lisas Haus bis zur Landstraße zusammen mit allen Hindernissen (z.B. mittels SVG, etwa eine halbe DIN-A4-Seite, ggf. aus Gründen der visuellen Übersichtlichkeit ohne einer Benennung der Eckpunkte und Polygone).

Die Polygone werden am besten in der Reihenfolge benannt, in der sie in der Eingabedatei enthalten sind, d.h. das erste Polygon in der Eingabedatei erhält als Namen die ID "P1", das zweite Polygon die ID "P2" usw. Lisas Haus mit der ID "L" ist kein Polygon, sondern nur durch ein einzelnes x- und y-Koordinatenpaar bestimmt.

Berechnete Zahlen können als Festkommazahlen (mit wenigen Nachkommastellen) ausgegeben werden.

Alle fünf Textdateien mit Beispieldaten gibt es auch im SVG-Format für Vektorgrafiken, die in modernen Webbrowsern direkt visualisiert werden können:

Jede SVG-Datei kann wie eine Textdatei bearbeitet werden; so kann die polyline-Zeile mit der ID "R" (polyline ID="R") durch weitere Punkten (points="...") von Lisas Route ergänzt werden, um sie von Lisas Haus bis zur Landstraße, der y-Achse, als Polygonzug z.B. im Webbrowser zu visualisieren.

Aufgabe 2: Dreiecksbeziehungen

Zu dieser Aufgabe gibt es fünf zu verarbeitende Textdateien mit Beispieldaten (letzte Änderung: 18. Januar 2019):

Dabei enthält in jeder Datei

  • die erste Zeile die Anzahl d der Dreiecke,
  • jede der folgenden d Zeilen für das jeweilige Dreieck die Information „3x1y1x2y2 ... x3y3“ über die ganzzahligen xi- und yi-Koordinaten (xi, yi) seiner 3 Ecken (die Zahlen sind durch einzelne Leerzeichen voneinander getrennt).

Dokumentation der Ergebnisse:

Alle fünf Beispiele sollten bearbeitet und klar dokumentiert werden, d.h. die Beispiele sollten im PDF der Dokumentation der Aufgabe enthalten sein.

Das dokumentierte Ergebnis einer berechneten Grundstücksanordnung sollte zumindest die folgenden Angaben umfassen (weitere Angaben sind gerne möglich):

  • Gesamtabstand (auf Meter genau) der am weitesten voneinander entfernten Grundstücke,
  • x- und y-Koordinaten (auf Meter genau) der drei Ecken aller Dreiecksgrundstücke (aufsteigend sortiert nach ihrer Platzierung entlang der x-Achse und benannt nach der ID des jeweiligen Dreiecks),
  • Visualisierung der berechneten Lage der Dreiecke entlang der x-Achse (z.B. mittels SVG, etwa eine halbe DIN-A4-Seite, ggf. aus Gründen der visuellen Übersichtlichkeit ohne einer Benennung der Ecken und Dreiecke).

Die Dreiecke werden am besten in der Reihenfolge benannt, in der sie in der Eingabedatei enthalten sind, d.h. das erste Dreieck in der Eingabedatei erhält als Namen die ID "D1", das zweite Dreieck die ID "D2" usw.

Berechnete Zahlen können als Festkommazahlen (mit wenigen Nachkommastellen) ausgegeben werden.

Alle fünf Textdateien mit Beispieldaten gibt es auch im SVG-Format für Vektorgrafiken, die in modernen Webbrowsern direkt visualisiert werden können:

Jede SVG-Datei kann wie eine Textdatei bearbeitet werden; so können die Ecken der Grundstücksdreiecke mittels polygon-Zeilen (polygonID="D..." points="...") als Punkte der jeweiligen dreieckigen Polygonen dargestellt werden, um eine berechnete Grundstücksanordnung entlang der x-Achse z.B. im Webbrowser zu visualisieren.

Aufgabe 3: Schach dem Wildschwein

ACHTUNG: Es gibt ein wichtiges Update zum Inhalt der Aufgabe 3, Variante A; bitte unbedingt beachten und die aktuelle Aufgabenstellung herunterladen (Änderungen in Fettdruck auf Seite 6).

Außerdem gibt es nun zu dieser Aufgabe fünf zu verarbeitende Textdateien mit Beispieldaten (letzte Änderung: 18. Januar 2019):

Variante A:

Jede Datei enthält in der ersten Zeile eine Figuren-Anfangsstellung in adoptierter FEN-Notation (Jagdhunde als Springer N, weißer König K als Jäger und schwarzer König k als Wildschwein) und in der zweiten Zeile das Zielfeld. Ein Beispiel für eine konkrete Stellung ist die erste Zeile

N5K/8/5k2/8/8/2N5/8/5N2 w

mit einem Buchstaben w oder b am Zeilenende (nach eine Leerzeichen als Separator), wenn der Jäger (white) bzw. sein Gegner (black) am Zug ist; die zweite Zeile bezeichnet nur das Zielfeld für das Wildschwein mittels eines Buchstaben a bis h für die Spalte direkt gefolgt von einer Ziffer 1 bis 8 für die Zeile, z.B. "h4".

Variante B:

Jede Datei enthält in der ersten Zeile eine Figuren-Anfangsstellung in FEN-Notation und in der zweiten Zeile das Zielfeld. Ein Beispiel für die in der Aufgabe abgebildeten Schach-Stellung ist die erste Zeile

N5K/8/5k2/8/8/2N5/8/5N2 w

mit einem Buchstaben w oder b am Zeilenende (nach eine Leerzeichen als Separator), wenn Weiß (white) bzw. Schwarz (black) am Zug ist; die zweite Zeile enthält nur das Zielfeld für den schwarzen König mittels eines Buchstaben a bis h für die Spalte direkt gefolgt von einer Ziffer 1 bis 8 für die Zeile, z.B. "h4".

Dokumentation der Ergebnisse:

Alle fünf Beispiele sollten bearbeitet und klar dokumentiert werden, d.h. die Beispiele sollten im PDF der Dokumentation der Aufgabe enthalten sein.

Das dokumentierte Ergebnis einer berechneten Lösung für eine Figuren-Anfangsstellung sollte zumindest die folgenden Angaben umfassen (weitere Angaben sind gerne möglich):

Jede PGN-Datei kann wie eine Textdatei bearbeitet werden; es gibt außerdem PGN-Viewer, um den Spielverlauf z.B. im Webbrowser zu visualisieren (z.B. LT-PGN-VIEWER, pgn4web games viewer oder Apronus PGN Viewer and Editor).

Alle fünf Beispiele können durch die Verwendung der FEN-Notation in der jeweiligen URL in Webbrowsern visualisiert werden:

Zum Beispiel mittels des Lichess Editor wie folgt:

  1. https://lichess.org/editor/5N1k/3N4/8/5N2/8/8/4K3/8_w
  2. https://lichess.org/editor/8/2N5/8/8/k7/3N4/1K2N3/8_w
  3. https://lichess.org/editor/1N6/7K/8/8/5k2/8/NN6/8_w
  4. https://lichess.org/editor/8/1N6/6N1/8/8/8/6N1/1K3k2_w
  5. https://lichess.org/editor/4N3/4k3/8/4N3/8/8/7N/3K4_w

Oder mittels des Jin Chess Diagram Setup:

  1. https://www.jinchess.com/chessboard/?p=5N1k/3N4/8/5N2/8/8/4K3/8 w
  2. https://www.jinchess.com/chessboard/?p=8/2N5/8/8/k7/3N4/1K2N3/8 w
  3. http://www.jinchess.com/chessboard/?p=1N6/7K/8/8/5k2/8/NN6/8 w
  4. https://www.jinchess.com/chessboard/?p=8/1N6/6N1/8/8/8/6N1/1K3k2 w
  5. https://www.jinchess.com/chessboard/?p=4N3/4k3/8/4N3/8/8/7N/3K4 w

Oder auch mittels des SimpleChessBoard:

  1. https://hxim.github.io/simplechessboard/popup/simplechessboard.html?x=5N1k/3N4/8/5N2/8/8/4K3/8 w - - 0 1
  2. https://hxim.github.io/simplechessboard/popup/simplechessboard.html?x=8/2N5/8/8/k7/3N4/1K2N3/8 w - - 0 1
  3. https://hxim.github.io/simplechessboard/popup/simplechessboard.html?x=1N6/7K/8/8/5k2/8/NN6/8 w - - 0 1
  4. https://hxim.github.io/simplechessboard/popup/simplechessboard.html?x=8/1N6/6N1/8/8/8/6N1/1K3k2 w - - 0 1
  5. https://hxim.github.io/simplechessboard/popup/simplechessboard.html?x=4N3/4k3/8/4N3/8/8/7N/3K4 w - - 0 1

Weitere Beispieldaten für mögliche Figuren-Anfangsstellungen lassen sich zum Beispiel mittels des Random-FEN-Generator erstellen.

Hinweis: Viele Schachprogramme und Webseiten akzeptieren den gekürzten FEN-String, wie er in den Beispieldateien enthalten ist; einige benötigen jedoch einen kompletten FEN-String, der am Ende durch die Zeichen " - - 0 1" ergänzt ist:

  1. kompletter FEN-String: 5N1k/3N4/8/5N2/8/8/4K3/8 w - - 0 1
  2. kompletter FEN-String: 8/2N5/8/8/k7/3N4/1K2N3/8 w - - 0 1
  3. kompletter FEN-String: 1N6/7K/8/8/5k2/8/NN6/8 w - - 0 1
  4. kompletter FEN-String: 8/1N6/6N1/8/8/8/6N1/1K3k2 w - - 0 1
  5. kompletter FEN-String: 4N3/4k3/8/4N3/8/8/7N/3K4 w - - 0 1