Дешифровка и ФП(ФП)
Поучаствовал в конкурсе по функциональному программированию. Автор, который ведет интересный и нескучный блог, и уже не первый раз устраивает конкурсы, в качестве призов предлагая свои книги. Я слежу за конкурсами с самого начала, но раньше как-то не хватало времени. В этот раз, впрочем, конкурс был менее всего функциональным, и показался простым и интересным.
Задача простая -- дешифровка текста, зашифрованного самым примитивным методом, которым я баловался еще в школе: XOR с кодовым словом. Задача облегчалась тем, что был известен тип текста -- программа на Хаскеле, чем многие воспользовались, и длина ключа. Если бы длина ключа была бы не известна, но ограничена сверху, то задача была бы куда сложнее. А так -- всего лишь несколько строк. Кроме длины автор любезно сообщил алфавит, чем еще более сократил варианты.
Для декодирования я выбрал простую стратегию -- вместо поиска ключевых слов, как делали некоторые, искал наиболее эффективный способ раскодировать пробелы. Этот метод годится для любого текста на большинстве алфавитных языков, в любом тексте пробел -- самый часто повторяющийся символ. Хаскель -- не исключение. Для определенного ключа можно посчитать метрику, насколько хорошо ключ раскодирует текст, которая в случае пробелов тривиальна -- сколько всего пробелов в раскодированном тексте. Поскольку мы проверяем односимвольное "слово", то подбирать ключ можно не целиком, а посимвольно. То есть вместо полного перебора всех ключей длины N в алфавите из M символов, что требует M^N проверок, достаточно перебрать символы в каждой позиции независимо, что оставляет всего M*N вариантов.
Далее несколько Scala-примеров.
Функция декодирования текста:
def decode(s: Array[Byte], key: String) = s grouped key.length flatMap (_ zip key) map (x => x._1 ^ x._2 toByte) toArray
Функция определения качества ключа, по набору проверочных слов. Чем больше, тем лучше. В моем случае в наборе был только один пробел, но функция универсальна.
def score(s: String, checkList: List[String]) = checkList map (c => (s sliding c.length count (_ == c)) * c.length) sum
Компактная, но неэффективная функция перебора набора ключей и поиска наилучшего. Можно свернуть в более эффективный, но более корявый foldLeft.
def bestKey(keys: List[String]) = keys map (k => (score ( new String(decode(data, k)), checkList), k)) maxBy (_._1)
Генератор ключей на базе образца, перебором в определенной позиции:
val syms = 'A' to 'Z'
def genKeys(base: String, pos: Int) = syms map (s => base.patch(pos, s.toString, 1)) toList
Ну и, наконец, финальный "цикл" по позициям. Было известно, что в ключе ровно пять символов.
val best = (0 to 4).foldLeft("AAAAA")( (best, pos) => bestKey(genKeys(best, pos))._2 )
Все достаточно функционально и кратко, хотя решения других участников часто были короче (на ЛИСПе, преимущественно). Я в них не вчитывался, возможно, там другие принципы использовались. Скала лаконичный, но не самый лаконичный язык. Эх, когда же у меня руки дойдут погрузиться в J как следует!...
В общем, текст я декодировал, получившуюся программу на Хаскеле запустил в вебовском интерпретаторе, код выслал и занял счастливое 13е место. Впрочем, по большому счету там есть места первое -- и остальные, не на скорость же соревнование. В качестве приза получил личный электронный, подписанный автором экземпляр книги "Методы получения, представления и обработки знаний с НЕ-факторами". Давно не читал современной литературы по обработке и представлениям знаний, поэтому прочту с интересом. Когда появится время.
P.S. Что такое ФП(ФП)? Если не догадались, то ищите ответ у _darkus_ :)
Задача простая -- дешифровка текста, зашифрованного самым примитивным методом, которым я баловался еще в школе: XOR с кодовым словом. Задача облегчалась тем, что был известен тип текста -- программа на Хаскеле, чем многие воспользовались, и длина ключа. Если бы длина ключа была бы не известна, но ограничена сверху, то задача была бы куда сложнее. А так -- всего лишь несколько строк. Кроме длины автор любезно сообщил алфавит, чем еще более сократил варианты.
Для декодирования я выбрал простую стратегию -- вместо поиска ключевых слов, как делали некоторые, искал наиболее эффективный способ раскодировать пробелы. Этот метод годится для любого текста на большинстве алфавитных языков, в любом тексте пробел -- самый часто повторяющийся символ. Хаскель -- не исключение. Для определенного ключа можно посчитать метрику, насколько хорошо ключ раскодирует текст, которая в случае пробелов тривиальна -- сколько всего пробелов в раскодированном тексте. Поскольку мы проверяем односимвольное "слово", то подбирать ключ можно не целиком, а посимвольно. То есть вместо полного перебора всех ключей длины N в алфавите из M символов, что требует M^N проверок, достаточно перебрать символы в каждой позиции независимо, что оставляет всего M*N вариантов.
Далее несколько Scala-примеров.
Функция декодирования текста:
def decode(s: Array[Byte], key: String) = s grouped key.length flatMap (_ zip key) map (x => x._1 ^ x._2 toByte) toArray
Функция определения качества ключа, по набору проверочных слов. Чем больше, тем лучше. В моем случае в наборе был только один пробел, но функция универсальна.
def score(s: String, checkList: List[String]) = checkList map (c => (s sliding c.length count (_ == c)) * c.length) sum
Компактная, но неэффективная функция перебора набора ключей и поиска наилучшего. Можно свернуть в более эффективный, но более корявый foldLeft.
def bestKey(keys: List[String]) = keys map (k => (score ( new String(decode(data, k)), checkList), k)) maxBy (_._1)
Генератор ключей на базе образца, перебором в определенной позиции:
val syms = 'A' to 'Z'
def genKeys(base: String, pos: Int) = syms map (s => base.patch(pos, s.toString, 1)) toList
Ну и, наконец, финальный "цикл" по позициям. Было известно, что в ключе ровно пять символов.
val best = (0 to 4).foldLeft("AAAAA")( (best, pos) => bestKey(genKeys(best, pos))._2 )
Все достаточно функционально и кратко, хотя решения других участников часто были короче (на ЛИСПе, преимущественно). Я в них не вчитывался, возможно, там другие принципы использовались. Скала лаконичный, но не самый лаконичный язык. Эх, когда же у меня руки дойдут погрузиться в J как следует!...
В общем, текст я декодировал, получившуюся программу на Хаскеле запустил в вебовском интерпретаторе, код выслал и занял счастливое 13е место. Впрочем, по большому счету там есть места первое -- и остальные, не на скорость же соревнование. В качестве приза получил личный электронный, подписанный автором экземпляр книги "Методы получения, представления и обработки знаний с НЕ-факторами". Давно не читал современной литературы по обработке и представлениям знаний, поэтому прочту с интересом. Когда появится время.
P.S. Что такое ФП(ФП)? Если не догадались, то ищите ответ у _darkus_ :)