extra/project-euler/059/059.factor

   1 ! Copyright (c) 2008 Aaron Schaefer, Slava Pestov.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: accessors arrays ascii assocs grouping io.encodings.ascii
   4 io.files kernel make math math.parser project-euler.common
   5 sequences sequences.private sets sorting splitting ;
   6 IN: project-euler.059
   7
   8 ! http://projecteuler.net/index.php?section=problems&id=59
   9
  10 ! DESCRIPTION
  11 ! -----------
  12
  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.
  16
  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
  21 ! XOR 42 = 65.
  22
  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.
  27
  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.
  33
  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.
  39
  40
  41 ! SOLUTION
  42 ! --------
  43
  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.
  48
  49 ! NOTE: This technique would probably not work well in all cases, but luckily
  50 ! it did for this particular problem.
  51
  52 <PRIVATE
  53
  54 : source-059 ( -- seq )
  55     "resource:extra/project-euler/059/cipher1.txt"
  56     ascii file-contents [ blank? ] trim-tail "," split
  57     [ string>number ] map ;
  58
  59 TUPLE: rollover seq n ;
  60
  61 C: <rollover> rollover
  62
  63 M: rollover length n>> ;
  64
  65 M: rollover nth-unsafe seq>> [ length mod ] keep nth-unsafe ;
  66
  67 INSTANCE: rollover immutable-sequence
  68
  69 : decrypt ( seq key -- seq )
  70     over length <rollover> swap [ bitxor ] 2map ;
  71
  72 : frequency-analysis ( seq -- seq )
  73     dup members [
  74         [ 2dup [ = ] curry count 2array , ] each
  75     ] { } make nip ; inline
  76
  77 : most-frequent ( seq -- elt )
  78     frequency-analysis sort-values keys last ;
  79
  80 : crack-key ( seq key-length -- key )
  81     [ " " decrypt ] dip group but-last-slice
  82     flip [ most-frequent ] map ;
  83
  84 PRIVATE>
  85
  86 : euler059 ( -- answer )
  87     source-059 dup 3 crack-key decrypt sum ;
  88
  89 ! [ euler059 ] 100 ave-time
  90 ! 8 ms ave run time - 1.4 SD (100 trials)
  91
  92 SOLUTION: euler059