{"id":2094,"date":"2015-04-07T08:29:37","date_gmt":"2015-04-07T08:29:37","guid":{"rendered":"http:\/\/www.dyalog.com\/blog\/?p=2094"},"modified":"2015-04-07T08:34:55","modified_gmt":"2015-04-07T08:34:55","slug":"solving-the-2014-apl-problem-solving-competition-how-tweet-it-is","status":"publish","type":"post","link":"https:\/\/www.dyalog.com\/blog\/2015\/04\/solving-the-2014-apl-problem-solving-competition-how-tweet-it-is\/","title":{"rendered":"Solving the 2014 APL Problem Solving Competition \u2013 How Tweet It Is"},"content":{"rendered":"

This post is the continuation of the series where we examine some of the problems selected for the 2014 APL Problem Solving Competition<\/a>.<\/p>\n

The problems presented in Phase 1<\/a> of the competition were selected because they could be solved succinctly, generally in a single line of APL code. This makes them well suited for experimentation on TryAPL.org<\/a>.<\/p>\n

Problem 2 of Phase 1, entitled “How tweet it is” reads<\/h4>\n

“Twitter messages have a 140 character limit – what if the limit was even shorter? One way to shorten the message yet retain most readability is to remove interior vowels from its words. Write a dfn which takes a character vector and removes the interior vowels from each word.”<\/p>\n

Test cases:\r\n      {your_solution} 'if you can read this, it worked!'\r\nif yu cn rd ths, it wrkd!\r\n      {your_solution} 'APL is REALLY cool'\r\nAPL is RLLY cl\r\n      {your_solution} '' \u235d an empty vector argument should return an empty vector\r\n\r\n      {your_solution} 'a' \u235d your solution should work with a single character message\r\na\r\n<\/code><\/pre>\n
We’ll examine a couple of approaches to this problem \u2013 one that’s more “traditional APL” code, and another that makes use of a really helpful Dyalog feature.<\/p>\n
This problem could be restated as\u00a0“find and remove the vowels that aren’t at the beginning or end of a word”. To start with, we need to determine where the words are and where the vowels are. A word is a contiguous set of letters; multiple words are separated by spaces or punctuation. For simplicity’s sake, we’ll ignore contractions and possessives.<\/p>\n
The “Traditional APL”\u00a0Approach<\/h4>\n
This approach employs a technique that is not commonly found outside of APL and its brethren \u2013 using a Boolean vector to determine which elements to remove or keep. First, let’s find where all the vowels are:<\/p>\n
      string\u2190'If you can read this, it worked!'\r\n      vowels\u2190{\u2375\u220a'aeiouAEIOU'}\r\n      vowels string\r\n1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0<\/code><\/pre>\n
To help illustrate what’s happening, I’ll write a little operator called “show” to compactly display the string, the Boolean vector, and the elements that would be selected by applying the Boolean to the string.<\/p>\n
      show\u2190{\u2375\u236a\u2375{\u2191(1 0\u2355 \u2375)(\u2375\\\u2375\/\u237a)}\u237a\u237a \u2375}\r\n      vowels show string\r\nIf you can read this, it worked!\r\n10001100100011000010001000100100\r\nI   ou  a   ea    i   i   o  e\r\n<\/code><\/pre>\n
Next we want to remove vowels that aren’t at either end of a word. First, find where the words are by finding where the letters are. \u00a0There are several ways to do this; the most obvious may be to use a character vector constant:<\/p>\n
      letters\u2190{\u2375\u220a'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'}<\/code><\/pre>\n
Long character constants\u00a0seem a bit awkward to me. \u00a0So, another technique uses the Unicode Conversion system function to return the 26 characters starting at the code points for\u00a0each of ‘a’ and ‘A’:<\/p>\n
      letters\u2190{\u2375\u220a\u2395UCS (\u237326)\u2218.+\u00af1+\u2395UCS'aA'}<\/code><\/pre>\n
Yet another way might be to use the code point values directly and do numerical operations:<\/p>\n
      letters\u2190{{((\u2375\u226565)\u2227\u2375\u226490)\u2228(\u2375\u226597)\u2227\u2375\u2264122}\u2395UCS \u2375}<\/code><\/pre>\n
Which technique you choose is largely a matter of taste and style. All three return the same result and have comparable performance. My personal preference is the second one – it has fewer characters for me to mistype \ud83d\ude42<\/p>\n
      letters show string\r\nIf you can read this, it worked!\r\n11011101110111101111001101111110\r\nIf you can read this  it worked \r\n<\/code><\/pre>\n
So now let’s\u00a0mark the interior letters of the words. This employs a technique known as shift and compare<\/em> that I learned in the early 1980s when I was privileged to work with Bob Smith<\/a>. Among Bob’s many contributions to the APL world was a book on Boolean Functions and Techniques<\/a>. To mark the interior letters,\u00a0we’ll do both a right and left shift:<\/p>\n
      interior\u2190{\u2375\u2227(\u00af1\u21930,\u2375)\u22271\u2193\u2375,0}\r\n      {interior letters \u2375} show string\r\nIf you can read this, it worked!\r\n00001000100011000110000000111100\r\n    o   a   ea   hi       orke  \r\n<\/code><\/pre>\n
The last step is to find interior vowels and negate:<\/p>\n
      {(vowels \u2375)\u2227interior letters \u2375} show string\r\nIf you can read this, it worked!\r\n00001000100011000010000000100100\r\n    o   a   ea    i       o  e  \r\n\r\n      {(vowels \u2375)\u2372interior letters \u2375} show string\r\nIf you can read this, it worked!\r\n11110111011100111101111111011011\r\nIf y u c n r  d th s, it w rk d!\r\n<\/code><\/pre>\n
Putting it all together…<\/p>\n
      tweet\u2190{\u2375\/\u2368~(\u2375\u220a'aeiouAEIOU')\u2227{(1\u2193\u2375,0)\u2227\u00af1\u21930,\u2375}\u2375\u220a\u2395UCS(\u237326)\u2218.+\u00af1+\u2395UCS'aA'}\r\n      tweet string\r\nIf yu cn rd ths, it wrkd!\r\n<\/code><\/pre>\n
The Other Technique – Using Regular Expressions<\/h4>\n
In version 13.0, Dyalog introduced the system functions \u2395S<\/code> and \u2395R<\/code> as interfaces to the PCRE (Perl Compatible Regular Expression) library. Like APL, regular expressions may seem a bit alien at first, but\u00a0in the years since their incorporation into Dyalog, I’ve grown to appreciate their power and flexibility – they can frequently accomplish complex string manipulations more succinctly than their APL equivalents thus furthering Dyalog’s power as a tool of thought, notation and execution.<\/p>\n
      tweet\u2190{('\\B[AEIOU]\\B' \u2395R '' \u2360 1) \u2375}\r\n      tweet string\r\nIf yu cn rd ths, it wrkd!\r\n<\/code><\/pre>\n
The expression above replaces any vowel (\u2360 1<\/code>means case-insensitive) that is not at the beginning or end of a word with the empty vector, effectively removing the interior vowels. A blog post is not enough space to give an adequate overview of regular expressions. But I hope the expression above piques your interest and encourages you to experiment with \u2395S<\/code> and \u2395R<\/code> on TryAPL.org<\/a> or with a Dyalog system of your own.<\/p>\n","protected":false},"excerpt":{"rendered":"
This post is the continuation of the series where we examine some of the problems selected for the 2014 APL Problem Solving Competition. The problems presented in Phase 1 of the competition were selected because they could be solved succinctly, … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":10,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[22],"tags":[],"class_list":["post-2094","post","type-post","status-publish","format-standard","hentry","category-student-competition"],"_links":{"self":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/2094","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\/10"}],"replies":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/comments?post=2094"}],"version-history":[{"count":22,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/2094\/revisions"}],"predecessor-version":[{"id":2384,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/2094\/revisions\/2384"}],"wp:attachment":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/media?parent=2094"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/categories?post=2094"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/tags?post=2094"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}