 |
Lösungen Programmierwettbewerb Chemnitzer Linux-Tag 2004
Lösungen Programmierwettbewerb Chemnitzer Linux-Tag 2004
Einleitung
Es werden drei Aufgaben gestellt. Der Teilnehmer kann die Aufgaben in
einer der folgenden Scriptsprachen lösen.
- Bash #!/bin/bash
(incl. sed, awk, grep, wc, find, du etc.)
- Perl #!/usr/bin/perl
- Python #!/usr/bin/python2
- Ruby #!/usr/bin/ruby
- tcl #!/usr/bin/tclsh
Folgende Editoren sind installiert:
- vim
- emacs
- xemacs
- joe
Der Teilnehmer logt sich mit Benutzernamen und Passwort ein. In seinem
Home-Verzeichnis befindet sich unterhalb dem Verzeichnis "aufgaben"
pro Aufgabe ein Verzeichnis.
In einem Aufgaben-Verzeichnis stehen drei Unterverzeichnisse:
- aufgabe/ (Aufgabenstellung (readonly))
- loesung/ (Hier muss das Programm mit dem Namen "loesung" erstellt werden)
- ergebnis/ (Ergebnis: Aufgabe richtig oder falsch)
Gewonnen hat, wer alle Aufgaben am schnellsten gelöst hat.
Die Aufgaben müssen in der folgenden Reihenfolge gelöst werden:
1. gleiche-dateien
2. lexikalische-sortierung
3. pnm-diff
Es ist jeweils *eine* Datei mit dem Namen "loesung" zu erstellen
(Nicht loesung.sh, loesung.pl ...). Das Script wird beim Test *ohne*
Argumente aufgerufen.
Eine Aufgabe wird abgegeben indem man mit "touch fertig" (Im
Verzeichnis "loesung") eine leere Datei erstellt. Innerhalb der
nächsten fünf Sekunden wird das Programm des Teilnehmers getestet und
das Ergebnis in dem Verzeichnis "ergebnis" erstellt. Wurde die Aufgabe
gelöst, kann die nächste Aufgabe begonnen werden. Wer welche Aufgaben
schon gelöst hat ist auf der Leinwand des Beamers zu sehen.
Falls die Lösung nicht stimmt kann beliebig oft die Aufgabe erneut
abgeben weren, in dem die leere Datei "fertig" erneut erstellt wird.
Die Ergebnisse der Aufgaben können eingesehen, aber nicht für die
Lösung verwendet werden.
Internetzugang oder Kommunikation per Email, talk, IRC ... ist nicht erlaubt.
Erste Aufgabe: Gleiche Dateien
In dem Verzeichnis "data" und allen Unterverzeichnissen sind die
Dateien zu finden, die exakt den gleichen Inhalt haben.
In dem Verzeichnis "data" und dessen Unterverzeichnissen befinden sich
nur Verzeichnisse oder normale Dateien. Keine Links, oder
Block/Character-Devices. Es sind maximal vier Unterverzeichnisse
vorhanden.
Die Datei- und Verzeichnissname bestehen aus exakt drei Ziffern
(100-999).
Eine Gruppen von gleichen ist zu sortieren und leerzeichengetrennt in
eine Zeile zu schreiben. Der Aufruf von "./loesung" soll die Zeilen
der Gruppen sortiert in die Datei "gleiche.out" schreiben.
> ./loesung
> diff gleiche_soll.out gleiche.out # Test ob Lösung richtig
Einzelne Dateien, die mit keinen anderen identisch sind, sind zu
ignorieren.
Zur Kontrolle kann das Ergebnis in "gleiche_soll.out" angeschaut
werden. Das ist die Liste, die dabei entstehen soll.
Lösungen:
- Mario Goppold Dauer: 0h:58m:36s
- Alexander Franz Dauer: 1h:09m:13s
Zweite Aufgabe: Lexikalische Sortierung
Sortiere die Datei "worte.txt", nach folgenden Regeln:
- Die Sortierung ist entsprechend dem Alphabet ohne Beachtung der
Groß/Kleinschreibung
aa
BB
cc
- Bei identischen Worten (abgesehen von Groß/Kleinschreibung) kommen
kleingeschriebene zuerst.
bb
BB
bbb
BBB
- Zahlen in Worten werden wie ein Zeichen
behandelt. Es sind nur positive Zahlen bis 65536 möglich.
Zahlen kommen vor Buchstaben.
Beispiel:
1000
a1b
a2b
a10b
- "Ä" wird wie "A" behandelt, entsprechend bei
"Ö" und "Ü" und äöü
- ß wird wie "ss" behandelt.
- Es kommen nur die Zeichen 0-9 a-z A-Z äöü ÄÖÜ ß vor.
- Kommen Worte in worte.txt mehrfach vor, so sollen sie auch
in sortiert.txt mehrfach vorkommen.
Der Aufruf "./loesung" soll die Datei "worte.txt" einlesen und eine
Datei "sortiert.txt" erstellen, die "sortiert_soll.txt" entspricht.
Bei Unklarheiten bitte sortiert_soll.txt ansehen.
Lösungen:
Es war ein spannendes Kopf-an-Kopf Rennen: Franz Alexander hat nur 79
Sekunden später abgegeben!
Dritte Aufgabe: PNM-Diff
Es sind zwei schwarz/weiße PBM Bild Dateien gegeben:
bild1.pbm bild2.pbm
Erstelle die Differenz der beiden Bilder als "diff.ppm"
Die schwarz/weiß Bilder sind gleich groß und es ist pro Pixel ein Bit
gespeichert (schwarz/weiß). Das Ergebnis diff.ppm besteht jedes Pixel
aus drei Byte (RGB).
- Wenn Bild1 an einem Pixel schwarz ist, und Bild2 weiß, soll
"\xff\x00x\00" in diff.ppm sein.
- Wenn Bild1 weiß und Bild2 schwarz, dann "\x00\x00\xff".
- Wenn ein Pixel in beiden Dateien gleich ist, dann
soll im Ergebnis \x00\x00\x00 stehen wenn in den Ausgangsdateien
das Pixel wahr (1) ist, ansonsten \xff\xff\xff.
Das gewünschte Ergebnis steht in diff_soll.ppm und kann mit z.B. mit
dem Befehl "display" angesehen werden.
Hinweis zum Datei-Format:
In der Aufgabe werden zwei Formate verwendet.
PBM: Portable Bitmap
Die Augangsdateien sind schwarz/weiß (Ein Bit pro Pixel). Die Datei
fängt mit "P4\n" an. In der nächsten Zeile steht die X- und
Y-Auflösung: "400 100\n". Anschließend kommen die Pixel des Bildes.
Die Anordnung der Pixel im Byte erfährt man aus den Test-Dateien oder
durch ausprobieren.
Falls das Bit gleich eins: schwarz
Falls das Bit gleich null: weiß
PPM: Portable Pixmap
Das Ergebnis ist ein Farbbild mit drei Byte pro Pixel (RGB). Die
erste Zeile ist "P6\n". In der nächsten Zeile steht wieder die
Auflösung des Bildes. Danach kommt die Farbtiefe pro Pixel:
"255\n". Anschließend kommen die Pixel des Bildes.
\x00\x00\x00 == schwarz
\xff\x00\x00 == rot
\x00\x00\xff == blau
\xff\xff\xff == weiß
Für die Aufgabe reicht es, wenn das Programm mit der Auflösung 400x100
umgehen kann. Andere Auflösungen müssen nicht unterstützt
werden. Nähere Informationen zum Dateiformat: Siehe Man-Page von
"pbm" und "ppm".
Schreibe ein Programm "loesung", das bei dem Aufruf
./loesung
die Dateien "bild1.pbm" und "bild2.pbm" einliest und "diff.ppm"
erstellt.
Diese Aufgabe wurde leider nicht mehr gelöst.
Download
Lösungen und Aufgaben als tgz: loesungen.tar.gz
Dankeschön
Ein großes Dankeschön, an alle die die Aufgaben getestet oder
anderweitig geholfen haben: Andreas Heik, Karsten Petersen, Ronald
Schmidt, Andreas Israel, René Liebscher, Stefan Ziegler.
|
|
|
|
