ead9bd0ff20e

Problem 59
[view raw] [browse files]
author Steve Losh <steve@stevelosh.com>
date Thu, 02 Mar 2017 22:12:19 +0000
parents 1138be746556
children e8225b1bc2b6
branches/tags (none)
files src/euler.lisp

Changes

--- a/src/euler.lisp	Thu Mar 02 18:04:08 2017 +0000
+++ b/src/euler.lisp	Thu Mar 02 22:12:19 2017 +0000
@@ -10,6 +10,18 @@
           :initially (funcall ,f ,value)
           :then (funcall ,f ,var))))))
 
+(defmacro-driver (FOR var IN-LOOPING list)
+  (let ((kwd (if generate 'generate 'for)))
+    (with-gensyms (l remaining)
+      `(progn
+         (with ,l = ,list)
+         (,kwd (,var . ,remaining)
+          :next (if-first-time
+                  ,l
+                  (if (null ,remaining)
+                    ,l
+                    ,remaining)))))))
+
 
 (defmacro-driver (FOR var IN-DIGITS-OF integer &optional RADIX (radix 10))
   "Iterate `var` through the digits of `integer` in base `radix`, low-order first."
@@ -1743,7 +1755,64 @@
       (for ratio = (/ primes count))
       (finding size :such-that (< ratio 1/10)))))
 
-
+(defun problem-59 ()
+  ;; Each character on a computer is assigned a unique code and the preferred
+  ;; standard is ASCII (American Standard Code for Information Interchange).
+  ;; For example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107.
+  ;;
+  ;; A modern encryption method is to take a text file, convert the bytes to
+  ;; ASCII, then XOR each byte with a given value, taken from a secret key. The
+  ;; advantage with the XOR function is that using the same encryption key on
+  ;; the cipher text, restores the plain text; for example, 65 XOR 42 = 107,
+  ;; then 107 XOR 42 = 65.
+  ;;
+  ;; For unbreakable encryption, the key is the same length as the plain text
+  ;; message, and the key is made up of random bytes. The user would keep the
+  ;; encrypted message and the encryption key in different locations, and
+  ;; without both "halves", it is impossible to decrypt the message.
+  ;;
+  ;; Unfortunately, this method is impractical for most users, so the modified
+  ;; method is to use a password as a key. If the password is shorter than the
+  ;; message, which is likely, the key is repeated cyclically throughout the
+  ;; message. The balance for this method is using a sufficiently long password
+  ;; key for security, but short enough to be memorable.
+  ;;
+  ;; Your task has been made easy, as the encryption key consists of three lower
+  ;; case characters. Using cipher.txt (right click and 'Save Link/Target
+  ;; As...'), a file containing the encrypted ASCII codes, and the knowledge
+  ;; that the plain text must contain common English words, decrypt the message
+  ;; and find the sum of the ASCII values in the original text.
+  (let* ((data (-<> "data/59-cipher.txt"
+                 read-file-into-string
+                 (substitute #\space #\, <>)
+                 read-all-from-string))
+         (raw-words (-<> "/usr/share/dict/words"
+                      read-file-into-string
+                      (cl-strings:split <> #\newline)
+                      (mapcar #'string-downcase <>)))
+         (words (make-hash-set :test 'equal :initial-contents raw-words)))
+    (labels
+        ((stringify (codes)
+           (map 'string #'code-char codes))
+         (apply-cipher (key)
+           (iterate (for number :in data)
+                    (for k :in-looping key)
+                    (collect (logxor number k))))
+         (score-keyword (keyword)
+           (-<> (apply-cipher (coerce keyword 'list))
+             (stringify <>)
+             (string-downcase <>)
+             (cl-strings:split <>)
+             (remove-if-not (curry #'hset-contains-p words) <>)
+             length))
+         (answer (keyword)
+           (sum (apply-cipher (coerce keyword 'list)))))
+      (answer
+        (iterate (for-nested ((a :from (char-code #\a) :to (char-code #\z))
+                              (b :from (char-code #\a) :to (char-code #\z))
+                              (c :from (char-code #\a) :to (char-code #\z))))
+                 (for keyword = (list a b c))
+                 (finding keyword :maximizing (score-keyword keyword)))))))
 
 
 
@@ -1874,6 +1943,7 @@
 (test p56 (is (= 972 (problem-56))))
 (test p57 (is (= 153 (problem-57))))
 (test p58 (is (= 26241 (problem-58))))
+(test p59 (is (= 107359 (problem-59))))
 
 (test p74 (is (= 402 (problem-74))))
 (test p145 (is (= 608720 (problem-145))))