{"id":1735,"date":"2015-01-26T10:44:54","date_gmt":"2015-01-26T10:44:54","guid":{"rendered":"http:\/\/www.dyalog.com\/blog\/?p=1735"},"modified":"2015-01-26T10:46:22","modified_gmt":"2015-01-26T10:46:22","slug":"solving-the-2014-apl-problem-solving-competition-cryptography-problem-2","status":"publish","type":"post","link":"https:\/\/www.dyalog.com\/blog\/2015\/01\/solving-the-2014-apl-problem-solving-competition-cryptography-problem-2\/","title":{"rendered":"Solving the 2014 APL Problem Solving Competition \u2013 Cryptography Problem 2"},"content":{"rendered":"<p>This post is the continuation of the series where we examine some of the problems selected for the 2014 <a href=\"http:\/\/www.dyalogaplcompetition.com\/\" target=\"_blank\">APL Problem Solving Competition<\/a>. In this post we&#8217;ll continue looking at the cryptography problems from <a href=\"http:\/\/www.dyalog.com\/uploads\/files\/student_competition\/2014_problems_phase2.pdf\" target=\"_blank\">Phase II<\/a> that we started looking at in a <a title=\"Solving the 2014 APL Problem Solving Competition \u2013 Cryptography Problem 1\" href=\"http:\/\/www.dyalog.com\/blog\/2015\/01\/solving-the-2014-apl-problem-solving-competition-cryptography-problem-1\/\" target=\"_blank\">previous blog post<\/a>.<\/p>\n<h2>Cryptography Problem 2 \u2013 Book Cipher Variation<\/h2>\n<p><strong><em>Task 1 \u2013 Let&#8217;s Get Normal<\/em><\/strong><\/p>\n<p>The first task is to normalise some text by weeding out non-alphabetic characters, collapsing consecutive spaces and converting to upper case. It&#8217;s possible to do this all by hand with APL, but it&#8217;s much easier to use the <code class=\"language-apl\">\u2395R<\/code> operator to search for and replace <a href=\"http:\/\/en.wikipedia.org\/wiki\/Regular_expression\" target=\"_blank\">regular expressions<\/a>.<\/p>\n<p>Taking the transformations in turn, here&#8217;s how to convert non-alphabetic characters in message <code class=\"language-apl\">\u2375<\/code> to spaces:<\/p>\n<pre><code class=\"language-apl\">('[^[:alpha:]]'\u2395R' ')\u2375<\/code><\/pre>\n<p>Here&#8217;s how to convert multiple consecutive spaces to a single space:<\/p>\n<pre><code class=\"language-apl\">(' +'\u2395R' ')\u2375<\/code><\/pre>\n<p>And here&#8217;s how to convert every alphabetic character to upper case:<\/p>\n<pre><code class=\"language-apl\">('.'\u2395R'\\u&amp;')\u2375<\/code><\/pre>\n<p>We can combine the first two of these, by converting any sequence of one or more non-alphabetic characters to a single space, giving the following implementation:<\/p>\n<pre><code class=\"language-apl\">Normalise\u2190{\r\n    text\u2190\u2395SE.UnicodeFile.ReadText \u2375\r\n    ('[^[:alpha:]]+' '.'\u2395R' ' '\\u&amp;'\u2360'Mode' 'D')text\r\n}<\/code><\/pre>\n<p>The <em>option<\/em> <code class=\"language-apl\">'Mode' 'D'<\/code> tells <code class=\"language-apl\">\u2395R<\/code> to operate in Document mode, which processes the whole file at once instead of line by line, as we are not interested in preserving the original line breaks. Here it is in action:<\/p>\n<pre><code class=\"language-apl\">      70\u2191bor\u2190Normalise'\/home\/jay\/Desktop\/BillOfRights.txt'\r\nTHE PREAMBLE TO THE BILL OF RIGHTS CONGRESS OF THE UNITED STATES BEGUN<\/code><\/pre>\n<p><strong><em>Task 2 \u2013 Encryption<\/em><\/strong><\/p>\n<p>In this cipher there are lots of different ways of encoding each character of the message, and we are free to pick any of them. In order to try to &#8220;minimise the number of duplicated pairs in the result&#8221;, we simply pick randomly whenever we have a free choice. The function <code class=\"language-apl\">pickone<\/code> helps with this. Given a boolean vector, it first uses <code class=\"language-apl\">{\u2375\/\u2373\u2374\u2375}<\/code> to get a vector of the indices of all the 1 bits, and then uses <code class=\"language-apl\">{\u2375[?\u2262\u2375]}<\/code> to choose one of these indices at random.<\/p>\n<p>In this coding of <code class=\"language-apl\">BookEncrypt<\/code>, the anonymous inner dfn encodes a single character of the message into a (word offset) pair. These pairs are joined together with <code class=\"language-apl\">\u2283,\/<\/code>, a common pattern for catenating strings. The Disclose is required because, in Dyalog, reduction always <em>reduces<\/em> the rank of its argument, so <code class=\"language-apl\">,\/<\/code> on a vector of strings returns a <em>scalar<\/em>: the enclose of the catenated strings.<\/p>\n<pre><code class=\"language-apl\">BookEncrypt\u2190{\r\n    pickone\u2190{\u2375[?\u2262\u2375]}\u2218{\u2375\/\u2373\u2374\u2375}\r\n    b\u2190' ',\u237a                     \u235d b has a space wherever a word starts in the key.\r\n    s\u2190{\u2375\/\u2373\u2374\u2375}b=' '              \u235d Get the indices of all the word starts.\r\n    \u2283,\/{\r\n         p\u2190pickone b=\u2375          \u235d Choose a random occurrence of letter \u2375\r\n         p-\u2190s                   \u235d and get its offset within each word.\r\n         w\u2190pickone{(0&lt;\u2375)\u2227\u2375\u226420}p \u235d Choose a word with a reasonable offset\r\n         w(p[w])                \u235d and return the (word offset) pair.\r\n    }\u00a8\u2375                         \u235d ... for each letter in the message.\r\n}<\/code><\/pre>\n<p>Here it is in action:<\/p>\n<pre><code class=\"language-apl\">      \u22a2cipher\u2190bor BookEncrypt 'MYSECRETMESSAGE'\r\n480 11 523 11 440 6 115 5 78 16 579 18 696 20 330 16 544 4 658 17 400 9 661 11\r\n      246 18 186 4 482 13<\/code><\/pre>\n<p><strong><em>Task 3 \u2013 Decryption<\/em><\/strong><\/p>\n<p>Decryption is simpler then encryption, because there is no need to make random choices. All we have to do is:<\/p>\n<ul>\n<li>Find the index of the start of each word in the key, as before.<\/li>\n<li>Split the input into pairs of numbers.<\/li>\n<li>For each pair, find the character in the key at the specified offset from the start of the specified word.<\/li>\n<\/ul>\n<p>There are various ways to split the input into pairs of numbers. Here, we do it with the Rank operator (<code class=\"language-apl\">\u2364<\/code>). Encrypting an N-character message gives a vector of 2\u00d7N numbers. To split it into pairs we first reshape it into a matrix with N rows and 2 columns; and then use <code class=\"language-apl\">f\u23641<\/code> to apply <code class=\"language-apl\">f<\/code> to the rank-1 subarrays of this matrix, which are its row vectors.<\/p>\n<p>Here&#8217;s the code:<\/p>\n<pre><code class=\"language-apl\">BookDecrypt\u2190{\r\n    b\u2190' ',\u00af1\u2193\u237a                  \u235d b has a space wherever a word starts in the key.\r\n    s\u2190{\u2375\/\u2373\u2374\u2375}b=' '              \u235d Get the indices of all the word starts.\r\n    {\r\n        (w o)\u2190\u2375                 \u235d Get word number and offset\r\n        b[s[w]+o]               \u235d and find the character at that position\r\n    }\u23641\u22a2(0.5\u00d7\u2262\u2375)2\u2374\u2375             \u235d ... for each pair of numbers in the input.\r\n}<\/code><\/pre>\n<p>And here it is in action:<\/p>\n<pre><code class=\"language-apl\">      bor BookDecrypt cipher\r\nMYSECRETMESSAGE<\/code><\/pre>\n<p>To be continued&#8230;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>This post is the continuation of the series where we examine some of the problems selected for the 2014 APL Problem Solving Competition. In this post we&#8217;ll continue looking at the cryptography problems from Phase II that we started looking &hellip; <a href=\"https:\/\/www.dyalog.com\/blog\/2015\/01\/solving-the-2014-apl-problem-solving-competition-cryptography-problem-2\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":15,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13,8,22],"tags":[],"class_list":["post-1735","post","type-post","status-publish","format-standard","hentry","category-algorithms","category-apl-language","category-student-competition"],"_links":{"self":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/1735","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/users\/15"}],"replies":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/comments?post=1735"}],"version-history":[{"count":35,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/1735\/revisions"}],"predecessor-version":[{"id":1885,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/1735\/revisions\/1885"}],"wp:attachment":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/media?parent=1735"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/categories?post=1735"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/tags?post=1735"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}