Home
Allgemeines Vorträge Workshops Demos Praxis Dr. Tux Service Presse
Tux
> Service
> Keysigning
> LPI-Prüfungen
> Wettbewerb
> RoboSumo
> Verpflegung
> Tagungsnetz
Sponsoren
Organisatoren
Sitemap
Impressum
Sponsoren:   

weitere Sponsoren


Tagungsfahrdienst

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:
  1. Mario Goppold Dauer: 0h:58m:36s
  2. 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.
pi pi
Die Chemnitzer Linux-Tage sind ein Projekt des IN-Chemnitz e.V. | Impressum | Datenschutzerklärung