Euler : Problem 59

Posted by YpsilonTAKAI On 2011年7月3日日曜日 0 コメント
PE 59

XORで暗号化された暗号を解く問題。

コードは長いけどたいしたことやってない。

キーは3文字だと分っているので、暗号文を3文字ずつで分解して、1番目 2番目 3番目だけからなるリストを作る。
それぞれのリストは同じ文字でエンコードされているので、元の文章の文字の出現頻度と同じ頻度になっているはず。
リストに含まれる数を出現頻度順に並べると先頭が最頻の文字。
さて、英語の文章の最頻文字は「e」、かというとそうではなくて「スペース」です。スペースでデコードしたものを出してみると、それらしきものが現われました。

文章をデコードする関数も作って調べてみると当り。



;;
;; Problem 59 : 2011/6/22
;;"Elapsed time: 37.556729 msecs"

(defn group-same
"Split into same value group
ex. (2 3 1 3 1 3 3) -> [(1 1) (2) (3 3 3 3)]"
([col] (group-same (sort col) []))
([col res]
(if (empty? col)
res
(let [[head tail] (split-with #(= (first col) %) col)]
(recur tail (conj res head ))))))

(defn transpose-grid
"Transpose grid.
[[1 2]
[3 4]] ->
[[1 3]
[2 4]]"
[grid]
(apply map list grid))


(defn sort-by-count [num-list]
"Sort num. set letf according to the count of the number.
ex. [2 2 3 7 7 8] -> (7 2 8 3) : 7 and 2 are two occurense."
(map first
(sort (fn [a b]
(if (= (count a) (count b))
(> (first a) (first b))
(> (count a) (count b))))
(group-same num-list))))


;;;

(def *pe59-file-name* "http://projecteuler.net/project/cipher1.txt")

(use '[clojure.contrib.io :only (slurp*)])
(use '[clojure.contrib.str-utils :only (re-split chomp)])

(defn get-num-seq [file-name]
(let [file-data (slurp* file-name)]
(map #(Integer/valueOf %) (re-split #"," (chomp file-data)))))

(defn encdec-char [key val]
(if (neg? val)
0
(bit-xor key val)))

(let [most-frequent-char \space]
(reduce str
(map #(char (encdec-char % (int most-frequent-char)))
(map first
(map sort-by-count
(transpose-grid
(partition 3 3 (repeat -1)
(get-num-seq *pe59-file-name*))))))))
;;


デコード関数

;;
(defn pe59 [key]
(let [[k1 k2 k3] (map int (seq key))]
(map #(+ (encdec-char k1 (first %))
(encdec-char k2 (second %))
(encdec-char k3 (last %)))
(partition 3 3 (repeat -1) (get-num-seq *pe59-file-name*)))))
;;

0 コメント:

コメントを投稿