1 ! Copyright (c) 2008 Aaron Schaefer, Slava Pestov.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: arrays ascii assocs hashtables io.encodings.ascii io.files kernel math
4 math.parser namespaces make sequences sequences.private sorting
5 splitting grouping strings sets accessors project-euler.common ;
8 ! http://projecteuler.net/index.php?section=problems&id=59
13 ! Each character on a computer is assigned a unique code and the preferred
14 ! standard is ASCII (American Standard Code for Information Interchange). For
15 ! example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107.
17 ! A modern encryption method is to take a text file, convert the bytes to
18 ! ASCII, then XOR each byte with a given value, taken from a secret key. The
19 ! advantage with the XOR function is that using the same encryption key on the
20 ! cipher text, restores the plain text; for example, 65 XOR 42 = 107, then 107
23 ! For unbreakable encryption, the key is the same length as the plain text
24 ! message, and the key is made up of random bytes. The user would keep the
25 ! encrypted message and the encryption key in different locations, and without
26 ! both "halves", it is impossible to decrypt the message.
28 ! Unfortunately, this method is impractical for most users, so the modified
29 ! method is to use a password as a key. If the password is shorter than the
30 ! message, which is likely, the key is repeated cyclically throughout the
31 ! message. The balance for this method is using a sufficiently long password
32 ! key for security, but short enough to be memorable.
34 ! Your task has been made easy, as the encryption key consists of three lower
35 ! case characters. Using cipher1.txt (right click and 'Save Link/Target
36 ! As...'), a file containing the encrypted ASCII codes, and the knowledge that
37 ! the plain text must contain common English words, decrypt the message and
38 ! find the sum of the ASCII values in the original text.
44 ! Assume that the space character will be the most common, so XOR the input
45 ! text with a space character then group the text into three "columns" since
46 ! that's how long our key is. Then do frequency analysis on each column to
47 ! find out what the most likely candidate is for the key.
49 ! NOTE: This technique would probably not work well in all cases, but luckily
50 ! it did for this particular problem.
54 : source-059 ( -- seq )
55 "resource:extra/project-euler/059/cipher1.txt"
56 ascii file-contents [ blank? ] trim-tail "," split
57 [ string>number ] map ;
59 TUPLE: rollover seq n ;
61 C: <rollover> rollover
63 M: rollover length n>> ;
65 M: rollover nth-unsafe seq>> [ length mod ] keep nth-unsafe ;
67 INSTANCE: rollover immutable-sequence
69 : decrypt ( seq key -- seq )
70 over length <rollover> swap [ bitxor ] 2map ;
72 : frequency-analysis ( seq -- seq )
74 [ 2dup [ = ] curry count 2array , ] each
75 ] { } make nip ; inline
77 : most-frequent ( seq -- elt )
78 frequency-analysis sort-values keys peek ;
80 : crack-key ( seq key-length -- key )
81 [ " " decrypt ] dip group but-last-slice
82 flip [ most-frequent ] map ;
86 : euler059 ( -- answer )
87 source-059 dup 3 crack-key decrypt sum ;
89 ! [ euler059 ] 100 ave-time
90 ! 8 ms ave run time - 1.4 SD (100 trials)