Am Freitag, den 19. Oktober habe ich wieder am Catalysts Coding Contest, dem, nach eigenen Angaben härtesten Programmierwettbewerb Österreichs, teilgenommen. Zum ersten Mal war ich beim Herbsttermin in Wien dabei. Der Wettbewerb fand dieses Mal in der Volkshalle im Rathaus statt.
Wie man auch der offizielle Presseaussendung entnehmen kann, ging es dieses Mal um das “Lippenlesen”. Genauer gesagt war verlangt vom Computer bereits erkannte Bewegungen den Buchstaben zuzuordnen.
Bei mir hat es leider nur für das Level 2 gereicht, aber da ich mit dem Studium noch nicht begonnen habe, ist das nicht so schlimm. Genau genommen bin ich auf Platz 101 von 126 gelandet, wie der folgende Screenshot beweist:
Ich möchte im Folgenden kurz die Aufgabenstellungen und meine Lösung erläutern:
Level 1
Hier wurde eine Trainingsdatei mit den Buchstaben und den zugehörigen Bewegungen bereitgestellt:
126 a I U v o b I I i i c I ( i c d I ( i c e I U i c f I I i u g I ( i c h S S i ...Am Anfang steht die Anzahl der Buchstaben und dahinter stehen Buchstaben mit den zugehörigen vier Zeichen, die die Bewegung darstellen. In diesem Beispiel gibt es 26 Buchstaben des Alphabetes und ein “a” bedeutet als Bewegung “I U v o”, “b” bedeutet “I I i i”, usw…
Hier musste man also zuerst die Übersetzungen einlesen, was ich mit folgendem Code erledigt habe:
1$data = CCCHelper::stringToArray("26 a I U v o b I I i i c I ( i c d I ( i c e I U i c f I I i u g I ( i c h S S i c i I U v o j S S i c k I ( i c l D H v o m I I i i n I ( i c o - C i o p I I i i q o - i i r I ( i c s I ( i c t S S i c u - C i c v I I i u w o - i i x S S i c y I ( i c z I ( i c");
2
3$dict = Array();
4
5for($i = 1; $i < ($data[0]*5); $i = $i+5){
6 $dict[$data[$i]] = $data[$i+1] . " " . $data[$i+2] . " " . $data[$i+3] . " " . $data[$i+4];
7}Zum Aufspalten der Buchstaben habe ich eine kleine, selbst geschriebene, Hilfsklasse namens CCCHelper verwendet, in der die folgende Funktion definiert ist:
1public static function stringToArray($input){
2 return explode(" ", $input);
3}Dadurch erhielt ich eine Auflistung der Buchstaben:
1Array
2(
3 [a] => I U v o
4 [b] => I I i i
5 [c] => I ( i c
6 [d] => I ( i c
7 [e] => I U i c
8 [f] => I I i u
9 [g] => I ( i c
10 [h] => S S i c
11 [i] => I U v o
12 [j] => S S i c
13 [k] => I ( i c
14 [l] => D H v o
15 [m] => I I i i
16 [n] => I ( i c
17 [o] => - C i o
18 [p] => I I i i
19 [q] => o - i i
20 [r] => I ( i c
21 [s] => I ( i c
22 [t] => S S i c
23 [u] => - C i c
24 [v] => I I i u
25 [w] => o - i i
26 [x] => S S i c
27 [y] => I ( i c
28 [z] => I ( i c
29)Wie man hier sieht, kommt die gleiche Abfolge bei mehreren Buchstaben vor.
Nun ging um die Erkennung der Buchstaben in mehreren Beispielen.
121 - C i o I ( i c - C i o o - i i S S i c I ...Auch hier wurde an erster Stelle wieder die Anzahl der Buchstaben angegeben und dahinter befinden sich in Vierer-Gruppen die erkannten Bewegungen. “- C i o” bedeutet zum Beispiel ein “o”.
1$speech = CCCHelper::stringToArray("21 - C i o I ( i c - C i o o - i i S S i c I ( i c I ( i c I I i u o - i i S S i c I I i u I ( i c I U i c I ( i c - C i c o - i i S S i c - C i o I ( i c S S i c S S i c");
2
3for($i = 1; $i < ($speech[0]*4)+1; $i=$i+4){
4 $res[] = array_keys($dict, $speech[$i] . " " . $speech[$i+1] . " " . $speech[$i+2] . " " . $speech[$i+3]);
5}Dieser Code sucht bei jeder Vierer-Gruppe nach Vorkommen in den Übersetzungen und schreibt diese in ein Array. Dieses sieht dann so auch:
1Array
2(
3 [0] => Array
4 (
5 [0] => o
6 )
7
8 [1] => Array
9 (
10 [0] => c
11 [1] => d
12 [2] => g
13 [3] => k
14 [4] => n
15 [5] => r
16 [6] => s
17 [7] => y
18 [8] => z
19 )
20
21 [2] => Array
22 (
23 [0] => o
24 )
25
26 ...
27
28 [20] => Array
29 (
30 [0] => h
31 [1] => j
32 [2] => t
33 [3] => x
34 )
35
36)Verlangt war diese Buchstaben so auszugeben, dass zuerst die Anzahl der möglichen Übersetzungen und dann die Buchstaben für jede Bewegung angegeben werden. Bei einem Buchstaben, der zum Beispiel entweder “a” oder “i” ist, wird “2 a i” ausgegeben. Diese müssen auch aufsteigend sortiert sein.
1foreach($res as $char){
2 echo count($char) . " ";
3 sort($char);
4 foreach($char as $item){
5 echo $item . " ";
6 }
7}Durch diesen Code habe ich bei jedem Eintrag die Anzahl und die möglichen Buchstaben ausgeben lassen, was zu folgendem Ergebnis führte:
11 o 9 c d g k n r s y z 1 o 2 q w 4 h j t x 9 c d g k n r s y z ...Level 2
Bei Level 2, das ich leider nicht mehr fertigstellen konnte, was wohl an der schon zunehmenden Erschöpfung lag, mussten aus diesen Buchstaben alle möglichen Kombinationen aus einer ~18000 Wörter langen Wörterbuchdatei ausgegeben werden.
Wer sich selbst an den Beispielen versuchen will, der kann dies hier tun. Catalysts hat auch eine Infografik des Wettbewerbs veröffentlicht:
Ich freue mich schon wieder auf den nächsten Wettbewerb und hoffe, dass ich wieder dabei sein kann!