Bei dieser Challenge (Web 300) ist das eigentliche Ziel sehr schnell klar. Es existiert ein Bild, deren Teile verwürfelt sind, und die von uns innerhalb von zwei Sekunden in die richtige Reihenfolge gebracht werden müssen. Da es sehr schwer werden wird, das Bild innerhalb von zwei Sekunden per Hand zu sortieren und das Ergebnis einzugeben, bleibt uns nur der Weg, eine automatisierte Lösung per Skript zu entwickeln.
Dabei wird es erforderlich sein, jedes der zwölf Quadrate eindeutig zu identifizieren. Zur Umsetzung habe ich mir daher überlegt, aus jedem Quadrat die Farben (Rot – Grün – Blau) von vier Pixeln aus den Eckbereichen zu entnehmen und darüber eine Art “Fingerabdruck” jedes Quadrates zu erhalten – hier vereinfacht dargestellt ;-).
Bei der Umsetzung hat sich jedoch das Problem ergeben, dass – wohlmöglich durch die jeweils erneute JPEG-Umwandlung – die Farben der Pixel sich immer (minimal) unterscheiden. Als Umweg werden wir daher nur festhalten, ob sich viel oder wenig Rot-/Grün-/Blau-Töne in den Pixeln befinden und so eine eindeute Zuordnung der Quadrate realisieren.
Um den Server nicht unnötig mit Anfragen zu beschäftigen, nutzen wir hier zwei Skripte. Ein Bash-Skript zur Kommunikation mit dem Server sowie ein Python-Skript zur Sortierung des Bildes. Somit kann die Sortierung an ein- und demselben Bild wiederholt durchgeführt werden um die korrekte Funktion des Sortieralgorithmus zu testen.
Das Skript zur Kommunikation mit dem Server sieht folgendermaßen aus:
#!/bin/bash echo Fetching image... rm -f cookie curl -c cookie -b cookie http://176.9.193.13/CxliTo3-ra/ curl -c cookie -b cookie http://176.9.193.13/CxliTo3-ra/image.php -o sortme.jpeg SORT=$(./sort.py) echo "SOLUTION: $SORT" echo "Posting..." curl -c cookie -b cookie -G --data-urlencode "order=$SORT" http://176.9.193.13/CxliTo3-ra/s.php -o solution.txt cat solution.txt
Zunächst werden hier die Cookies vom Server geladen und das zu sortierende Bild als “sortme.jpeg” gespeichert (Zeilen 4-6). Dann wird das Sortier-Skript “sort.py” aufgerufen sowie das Ergebnis der Sortierung zu Kontrollzwecken ausgegeben (Zeilen 8-9). Zuletzt wird das Ergebnis an den Server gesendet und die Antwort des Servers ausgegeben (Zeilen 11-13).
Nachdem die Kommunikation realisiert ist, muss nun noch die eigentliche Sortierung folgen. Das entsprechende Python-Skript, welches die Python Image Library verwendet, sieht folgendermaßen aus:
#!/usr/bin/python
import sys
import Image
# load image
im = Image.open("sortme.jpeg")
pix = im.load()
# these are the sorted image fingerprints
sorted = ["101101101101", "101111101001", "000111001001", "000001001010",
"101101100100", "101001111111", "001001000000", "010010010010",
"100100100100", "100111100110", "111010110110", "010010110110"]
res = ""
# loop through fingerprints to find 1st, 2nd, ... part
for i in range(0,12):
pos = 0
# image is 400x300, take every 100x100 part
for y in range(0, 300, 100):
for x in range(0, 400, 100):
fingerprint = ""
# create 4x3 array containing 4 pixel with 3 colors (RGB)
check = pix[x+10,y+10] + pix[x+90,y+10] + pix[x+10,y+90] + pix[x+90,y+90]
# loop though RGB-colors to create fingerprint
# we need this because jpeg-converting seems to make colors differ
for k in check:
if k < 128:
fingerprint = fingerprint + "0"
if k >= 128:
fingerprint = fingerprint + "1"
# DEBUG OUTPUT: to create sorted-array manually
# print(str(x) + ":" + str(y) + " --> " + fingerprint)
# correct part found?
if sorted[i] == fingerprint:
res = res + str(pos) + ":"
break
pos += 1
# output in challenge format
sys.stdout.write(res[0:len(res)-1])
Das Bild wird zunächst geladen (Zeilen 7-8) und anschließend das Fingerprint-Array “sorted” definiert (Zeilen 11-13). Diese Array erhalt man, wenn man das Kommentar der DEBUG-Zeile 36 im Skript sowie die äußere For-Schleife entfernt (Skript) und das Ergebnis sortiert:
0:0 --> 101001111111 100:0 --> 101111101001 200:0 --> 100100100100 300:0 --> 111010110110 0:100 --> 100111100110 100:100 --> 001001000000 200:100 --> 000111001001 300:100 --> 000001001010 0:200 --> 101101101101 100:200 --> 101101100100 200:200 --> 010010110110 300:200 --> 010010010010
Wenn man sich nun überlegt, wie das Bild korrekt aussehen würde und diese Fingerabdrücke einmalig sortiert, erhält man das sorted-Array (Zeilen 11-13). Das Skript iteriert anschließend nur noch über alle Quadrate und versucht die richtige Zuordnung über das sorted-Array zu finden (Zeilen 17-42). Abschließend wird das Ergebnis in der von der Challenge geforderten Form ausgegeben.
Führt man das Bash-Skript nun aus, erhalt man diese Ausgabe:
rup0rt@lambda:~/CScamp2012$ ./web300.sh
Fetching image...
SOLUTION: 8:1:6:7:9:0:5:11:2:4:3:10
Posting...
key : 1e48572e9fb2f0b42c3f59bf8245f034
Die Lösung lautet somit: “1e48572e9fb2f0b42c3f59bf8245f034“.