Алгоритм решения HackThisSite Programming Challenge 1 (Unscrambling)

Недавно мне порекомендовали hackthissite.org — это действительно весело, даже если я думаю, что некоторые из заданий уже не так реалистичны.

Я подумал, что было бы так же весело опубликовать некоторые из моих решений задач по программированию здесь. Если не абсолютно необходимо для понимания лежащего в основе алгоритма, я не буду публиковать никакой информации о том, как использовать программы, потому что цель этих постов — понять это, а не использовать для решения заданий HTS.

Моё решение для задания 1 (Unscrambling) основано на наблюдении, что если нерасшифрованные строки уникальны, строка, содержащая отсортированные символы расшифровываемой строки, также уникальна.

Самое нубское решение, которое я могу придумать, — перебрать список слов для каждой расшифровываемой строки и проверить, все ли символы из расшифровываемой строки также присутствуют в исходной строке (и длина равна, конечно).

Чтобы сделать это более эффективно (Мой алгоритм — $\mathcal{O}(n)$ индексация и теоретически $\mathcal{O}(log\ n)$ поиск), мы можем сохранить отсортированные по символам представления в ассоциативной структуре данных. После сортировки этой структуры данных мы можем использовать бинарный поиск для нахождения расшифрованной версии слова.

Для поиска нам нужно просто вычислить отсортированную по символам версию расшифровываемой строки и вернуть её.

Вот моя реализация на Ruby:

unscramble.rb

data = Hash.new # Ключ = отсортированные символы строки
#Чтение списка слов и сортировка символов
File.open('wordlist.txt').each do |line|
 line.strip!
 sorted = line.chars.sort.join
 data [sorted] = line
end
#Чтение слов для расшифровки
#Вывод списка слов через запятую
File.open('words.txt').each do |line|
 line.strip!
 print data[line.chars.sort.join]+","
end
#Вывод последнего символа новой строки для ускорения копирования
print "\n"

data = Hash.new # Ключ = отсортированные символы строки
#Чтение списка слов и сортировка символов
File.open('wordlist.txt').each do |line|
 line.strip!
 sorted = line.chars.sort.join
 data [sorted] = line
end
#Чтение слов для расшифровки
#Вывод списка слов через запятую
File.open('words.txt').each do |line|
 line.strip!
 print data[line.chars.sort.join]+","
end
#Вывод последнего символа новой строки для ускорения копирования
print "\n"

Скрипт выводит лишнюю запятую в конце строки, которую вам нужно вставить на сайт HTS, но это не должно быть проблемой.

Я нашёл ruby-реализацию сортировки символов в этом посте на StackOverflow.