HackThisSite: Programming Challenge 1 – Algorithmus (Unscrambling)

Kürzlich wurde mir hackthissite.org empfohlen — es macht wirklich Spaß, damit herumzuspielen, auch wenn ich denke, dass einige der Challenges nicht mehr allzu realistisch sind.

Ich dachte, es wäre genauso viel Spaß, einige meiner Lösungen zu den Programming Challenges hier zu veröffentlichen. Wenn es für das Verständnis des zugrunde liegenden Algorithmus nicht absolut notwendig ist, werde ich keine Informationen darüber posten, wie man die Programme verwendet, da der Zweck dieser Beiträge darin bestehen soll, sie zu verstehen, nicht sie zu verwenden, um die HTS-Challenges zu lösen.

Meine Lösung für Challenge 1 (Unscrambling) basiert auf der Beobachtung, dass wenn die unscrambled Strings eindeutig sind, auch ein String, der die sortierten Zeichen des zu unscramblenden Strings enthält, eindeutig ist.

Die anfänglichste Lösung, die mir einfällt, wäre, für jeden zu unscramblenden String über die Wortliste zu iterieren und zu prüfen, ob alle Zeichen des zu unscramblenden Strings auch im Original-String vorhanden sind (und die Länge natürlich gleich ist).

Um dies effizienter zu machen (mein Algorithmus hat $\mathcal{O}(n)$-Indizierung und theoretisch $\mathcal{O}(log\ n)$-Lookup), können wir die zeichensortierten Repräsentationen in einer assoziativen Datenstruktur speichern. Nach dem Sortieren dieser Datenstruktur können wir binäre Suche verwenden, um die unscrambled Version eines Wortes zu finden.

Für den Lookup müssen wir nur die zeichensortierte Version des zu unscramblenden Strings berechnen und zurückgeben.

Hier ist meine Implementierung in Ruby:

data = Hash.new # Schlüssel = sortierte Zeichen des Strings
#Wortliste einlesen und Zeichen sortieren
File.open('wordlist.txt').each do |line|
 line.strip!
 sorted = line.chars.sort.join
 data [sorted] = line
end
#Zu entschlüsselnde Wörter einlesen
#Kommagetrennte Liste der entschlüsselten Wörter ausgeben
File.open('words.txt').each do |line|
 line.strip!
 print data[line.chars.sort.join]+","
end
#Abschließenden Zeilenumbruch ausgeben, um Copy-Paste zu beschleunigen
print "\n"

Das Skript gibt ein zusätzliches Komma am Ende der Zeile aus, die man auf der HTS-Seite einfügen muss, aber das sollte kein Problem sein.

Die Ruby-Implementierung der Zeichensortierung stammt aus diesem StackOverflow-Beitrag.