HackThisSite Programming Challenge 1 Algorithm (Unscrambling)

Recently hackthissite.org was recommended to me — it’s really fun to play around with, even if I think some of the challenges are not that realistic any more.

I thought it would be just as much fun to post some of my solutions to the programming challenges here. If not absolutely neccessary for understanding the underlying algorithm, I won’t post any information about how to use the programs, because the purpose of these posts shall be to understand it, not to use it in order to solve the HTS challenges.

My solution for challenge 1 (Unscrambling) is based on the observation that if the unscrambled string are unique, a string containing the sorted characters of the string to be unscrambled also is unique.

The noobishest solution I can think of would be to iterate over the wordlist for every string to be unscrambled and check if all the characters from the string to be unscrambled also are present in the original string (and the length is equal, of course).

In order to do this more efficiently (My algorithm is $\mathcal{O}(n)$ indexing and theoretically $\mathcal{O}(log\ n)$ lookup), we can save the character-sorted representations in an associative data structure. After sorting this data structure, we can use binary lookup in order to find the unscrambled version of a word.

In order to lookup, we just need to calculate the character-sorted version of the string to be unscrambled and return it.

Here is my implementation in Ruby:

data = Hash.new # Key = sorted chars of string
#Read the wordlist and sort the characters
File.open('wordlist.txt').each do |line|
 line.strip!
 sorted = line.chars.sort.join
 data [sorted] = line
end
#Read the words to descramble
#Output a comma-separated list of the scrambled words
File.open('words.txt').each do |line|
 line.strip!
 print data[line.chars.sort.join]+","
end
#Print a final newline to make copynpaste faster
print "\n"

The script prints an extra comma at the end of the line you need to paste at the HTS site, but that shouldn’t be a problem.

I found the ruby implementation of the character-sorting from this Stackoverflow post.