Freitag, 6. Februar 2015

(Gute) Idee für einen Mystery Cache und wie man sie nicht umsetzt...

Neulich hatten wir eine Idee für einen neuen Mystery Cache von uns. Also eigentlich ist die Idee fremdinspiriert, weil es so eine Aufgabe auch bei der Qualifikation zur letzten deutschen Geocaching-Meisterschaft gab.

Die Aufgabe ist eigentlich ganz einfach: gegeben wird ein Morse-Code ohne Leerzeichen zwischen den Buchstaben. Das macht das Dekodieren deutlich schwieriger, weil man nicht weiß, wo ein Buchstabe aufhört und der nächste anfängt.

So könnte z.B. selbst ein sehr kurzer Code wie
.-
entweder A heißen (das ist .-) oder ET (das ist . -, also mit Leerzeichen zwischen . und -). Und je länger das Wort, desto schwieriger wird es.

Außerdem muss man sich bei der Auswahl des Morsecode natürlich sicher sein, dass bei der Dekodierung wirklich nur ein sinnvolles Wort raus kommt, wenn die Lösung eindeutig sein soll.

Für diese Prüfung hatten wir folgendes Python-Skript (für Python 3), welches einen beliebigen Morsecode - welcher nur aus den Buchstaben A bis Z bestehen darf - in alle prinzipiell möglichen Zeichenfolgen dekodiert:

ALPHABET = {
".-": "A",
"-...": "B",
"-.-.": "C",
"-..": "D",
".": "E",
"..-.": "F",
"--.": "G",
"....": "H",
"..": "I",
".---": "J",
"-.-": "K",
".-..": "L",
"--": "M",
"-.": "N",
"---": "O",
".--.": "P",
"--.-": "Q",
".-.": "R",
"...": "S",
"-": "T",
"..-": "U",
"...-": "V",
".--": "W",
"-..-": "X",
"-.--": "Y",
"--..": "Z"
}
     
     
def consume(code, suffixes=None):
    if not code:
        yield ()
    else:
        if suffixes is None:
            suffixes = {}
  
        for morse, letter  in ALPHABET.items():
            if code.startswith(morse):
                suffix = code[len(morse):]
                try:
                    remainder = suffixes[suffix]
                except KeyError:
                    remainder = set(consume(suffix, suffixes))
                    suffixes[suffix] = remainder
     
                for sub in remainder:
                    yield (letter,) + sub
     
def main():
    code = ".--.---...-.-." #POSTEN
     
    for message in set(consume(code)):
        print("".join(message))
     
     
if __name__ == "__main__":
    main()

Das Skript arbeitet ziemlich effizient und entsprechend schnell.
Es gibt übrigens auch eine Webseite, die etwas ähnliches online bereitstellt: Link

Wir hatten das Wort POSTEN für das Rätsel verwendet. Dafür gibt es dann 3963 mögliche Dekodierungen, die das Skript alle ausgibt.

Und wie man so eine Cache _nicht_ umsetzt, haben wir dann auch direkt live demonstriert. Beim Durchsehen der Liste war POSTEN in der Tat das einzige sinnvolle, deutsche Wort. ATEMTIER wäre zwar auch möglich und deutsch, ist aber kein sinnvolles Wort. Also wurde das Listing so geschrieben, zum Review eingereicht und auch veröffentlicht.

Nach ein paar Logs kam dann aber nach weniger als 24h später eine Info, das AKZENTE auch möglich ist. Gegencheck: stimmt. Und das ist auch deutsch und ein sinnvolles Wort. Nur hatten wir dieses Wort bei der Prüfung übersehen... Na ja, und weil der Cache eindeutig lösbar sein sollte und wir auch keine Verrenkungen und weiteren Einschränkungen im Listung machen wollten ist der Cache dann direkt ins Archiv gewandert... Doof, aber so war's halt.

Das Feedback der anderen Cacher aus der Region auf das Rätsel war übrigens durchaus positiv, die hatten wohl Spaß beim Lösen. Also wer die Idee für einen eigenen Mystery übernehmen will - nur zu :-)

Wie oben bereits erwähnt, kann man die Schwierigkeit steigern, in dem man das Wort (=den Morsecode) länger macht. Schwieriger wird es auch, wenn man die Zahlen 0 bis 9 oder das Buckel-S (ß) als möglichen Zeichen dazu nimmt. Diese bestehen nämlich aus fünf Morsecode-Symbolen (also . und -), wodurch es deutlich mehr mögliche Dekodierungen gibt.

Bei der Steigerung der Schwierigkeit sollte man aber wenn behutsam vorgehen. Denn: wenn das Wort zu lang wird, macht auch das manuelle Dekodieren keinen Spaß mehr. Und wer sich mal so richtig unbeliebt bei seinen Mitcachern machen will, der nimmt als Wort z.B. RASTERTUNNELELEKTRONENMIKROSKOP. Das ist dann aber eher so eine D8 bis D9 Schwierigkeit...

Und wer die Idee übernimmt: Macht nicht den gleiche Fehler wie wir - prüft die Liste der möglichen Dekodierungen sorgfältig. Was bei längeren Worten ziemlich (zeit-) aufwendig sein kann. Oder mal lässt die möglichen Dekodierungen direkt noch vom Computer gegen ein Wörterbuch prüfen. Was auch ein bisschen zusätzliche Programmierung voraussetzt.

Grundsätzlich finden wir diese Mystery-Idee auch nach wie vor gut. Nur haben das ganze halt ein bisschen in den Sand gesetzt. Na ja, der erste größere Fehler im 67. Mystery ist immer noch eine gute Erfolgsrate ;-)


Update 11.2.2015: in dem Python-Listing aus dem Originalpost war die Morsesequenz für R falsch, wodurch nicht alle möglichen Dekodierungen gefunden wurden. Ist jetzt korrigiert und jetzt ist auch das Wort AKZENTE in der Ergebnisliste.

Kommentare:

  1. Aber AKZENTE kommt bei eurem Script gar nicht vor:

    root@eib:~# python3 ./code.py3 |egrep "AKZENTE|POSTEN"
    POSTEN

    AntwortenLöschen
    Antworten
    1. Ist aber dummerweise der gleiche Code ohne Leerzeichen
      .--.---...-.-. #Posten
      .--.---...-.-. #AKZENTE

      Löschen
  2. RASTERTUNNELELEKTRONENMIKROSKOP wäre .-..-...-..-.-..--.-...-....-...-.--.-.----..-.--..-.-.-.---...-.----.--. => das sind so circa 1000000000 Wörter.
    Mein Rechner mit 4GB RAM hat jedenfalls mit "MemoryError" aufgegeben....
    Wenn da mal eine Difficulty von 9 reicht. *lol*

    AntwortenLöschen
  3. Ich hatte Dein Rätsel auch schon gelöst und fand es schade, dass der Cache so schnell archiviert wurde.

    Die Lösung "Akzente" hatte ich auch gefunden, man hätte sie aber ausschließen können, indem man nur Worte in der Grundform zulässt - und Akzente ist eben nicht Grundform, sondern Plural.

    Und da der Cache ja archiviert ist:

    Meine erste Idee war übrigens auch, den Morsecode rekursiv zu parsen. Dann hatte ich aber eine Idee, die noch viel einfacher war, nämlich der umgekehrte Ansatz: Ich habe mir mit aspell eine Liste aller dort im Wörterbuch enthaltenen Wörter erzeugt, letztendlich "aspell dump master | aspell expand", und die dann mit einem kleinen Programm ohne Blanks Morse-codiert und dann gegen den vorgegebenen Morse-Code verglichen.

    Noch einfacher und noch effizienter...

    AntwortenLöschen