{"id":5316,"date":"2018-09-28T13:50:57","date_gmt":"2018-09-28T13:50:57","guid":{"rendered":"https:\/\/www.dyalog.com\/blog\/?p=5316"},"modified":"2018-09-29T08:13:53","modified_gmt":"2018-09-29T08:13:53","slug":"2018-apl-problem-solving-competition-phase-i-problems-sample-solutions","status":"publish","type":"post","link":"https:\/\/www.dyalog.com\/blog\/2018\/09\/2018-apl-problem-solving-competition-phase-i-problems-sample-solutions\/","title":{"rendered":"2018 APL Problem Solving Competition: Phase I Problems Sample Solutions"},"content":{"rendered":"

The following are my attempts at the Phase I problems<\/a> of the 2018 APL Problem Solving Competition. There are not necessarily “right answers” as personal style and taste come into play. More explanation of the code is provided here than common practice. All solutions pass all the tests specified in the official problem description.<\/p>\n

The solutions for problems 1 and 3 are due to Brian Becker, judge and supremo of the competition. They are better than the ones I had originally.<\/p>\n

1. Oh Say Can You See?<\/strong><\/p>\n

Given a vector or scalar of skyscraper heights, compute the number of skyscrapers which can be seen from the left. A skyscraper hides one further to the right of equal or lesser height.<\/p>\n

   visible \u2190 {\u2262\u222a\u2308\\\u2375}<\/code><\/pre>\n
Proceeding from left to right, each new maximum obscures subsequent equal or lesser values. The answer is the number of unique maxima. A tacit equivalent is \u2262\u2218\u222a\u2218(\u2308\\)<\/code>.<\/p>\n
2. Number Splitting<\/strong><\/p>\n
Split a non-negative real number into the integer and fractional parts.<\/p>\n
   split \u2190 0 1\u2218\u22a4<\/code><\/pre>\n
The function \u237a\u22a4\u2375<\/code> encodes the number \u2375<\/code> in the number system specified by numeric vector \u237a<\/code> (the bases). For example, 24 60 60\u22a4sec<\/code> expresses sec<\/code> in hours, minutes, and seconds. Such expression obtains by repeated application of the process, starting from the right of \u237a<\/code>: the next “digit” is the remainder of the number on division by a base, and the quotient of the division feeds into the division by the next base. Therefore, 0 1\u22a4\u2375<\/code> divides \u2375<\/code> by 1<\/code>; the remainder of that division is the requisite fractional part and the quotient the integer part. That integer part is further divided by the next base, 0<\/code>. In APL, remaindering by 0<\/code> is defined to be the identity function.<\/p>\n
You can have a good argue about the philosophy (theology?) of division by 0<\/code>, but the APL definition in the context of \u237a\u22a4\u2375<\/code> gives practically useful results: A 0<\/code> in \u237a<\/code> essentially says, whatever is left. For example, 0 24 60 60\u22a4sec<\/code> expresses sec<\/code> as days\/hours\/minutes\/seconds.<\/p>\n
3. Rolling Along<\/strong><\/p>\n
Given an integer vector or scalar representing a set of dice, produce a histogram of the possible totals that can be rolled.<\/p>\n
   roll \u2190 {{\u237a('*'\u2374\u2368\u2262\u2375)}\u2338,+\/\u00a8\u2373\u2375}\r\n\r\n   roll 5 3 4\r\n3  *\r\n4  ***\r\n5  ******\r\n6  *********\r\n7  ***********\r\n8  ***********\r\n9  *********\r\n10 ******\r\n11 ***\r\n12 *<\/code><\/pre>\n
\u2373\u2375<\/code> produces all possible rolls for the set of dice (the cartesian product of \u2373\u00a8\u2375<\/code>) whence further application of +\/\u00a8<\/code> and then ,<\/code> produce a vector of all possible totals. With the vector of possible totals in hand, the required unique totals and corresponding histogram of the number of occurrences obtain readily with the key<\/em> operator \u2338<\/code>. (And rather messy without<\/em> the key<\/em> operator.) For each unique total, the operand function {\u237a('*'\u2374\u2368\u2262\u2375)}<\/code> produces that total and a vector of *<\/code> with the required number of repetitions.<\/p>\n
The problem statement does not require it, but it would be nice if the totals are listed in increasing order. At first, I’d thought that the totals would need to be explicitly sorted to make that happen, but on further reflection realized that the unique elements of ,+\/\u00a8\u2373\u2375<\/code> (when produced by taking the first occurrence) are guaranteed to be sorted.<\/p>\n
4. What’s Your Sign?<\/strong><\/p>\n
Find the Chinese zodiac sign for a given year.<\/p>\n
   zodiac_zh \u2190 {(1+12|\u2375+0>\u2375) \u2283 ' '(\u2260\u2286\u22a2)' Monkey Rooster Dog Pig Rat Ox Tiger Rabbit Dragon Snake Horse Goat'}<\/code><\/pre>\n
Since the zodiac signs are assigned in cycles of 12, the phrase 12|<\/code> plays a key role in the solution. The residue<\/em> (remainder) function |<\/code> is inherently and necessarily 0-origin; the 1+<\/code> accounts for the 1-origin indexing required by the competition. Adding 0>\u2375<\/code> overcomes the inconvenient fact that there is no year 0.<\/p>\n
Essentials of the computation are brought into sharper relief if each zodiac sign is denoted by a single character:<\/p>\n
   zzh \u2190 {(1+12|\u2375+0>\u2375)\u2283'\u7334\u96de\u72d7\u8c6c\u9f20\u725b\u864e\u5154\u9f8d\u86c7\u99ac\u7f8a'}<\/code><\/pre>\n
The Chinese Unicode characters were found using https:\/\/translate.google.com<\/a> and then copied and pasted into the Dyalog APL session.<\/p>\n
5. What’s Your Sign? Revisited<\/strong><\/p>\n
Find the Western zodiac sign for a given month and day.<\/p>\n
   zodiac_en\u2190{\r\n     d\u219012 2\u2374 1 20  2 19  3 21  4 20  5 21  6 21  7 23  8 23  9 23  10 23  11 22  12 22\r\n     s\u219013\u2374' '(\u2260\u2286\u22a2)' Capricorn Aquarius Pisces Aries Taurus Gemini Cancer Leo Virgo Libra Scorpio Sagittarius'\r\n     (1+d\u2378\u2375)\u2283s\r\n   }<\/code><\/pre>\n
For working with irregular-sized non-overlapping intervals, the pre-eminent function is \u2378<\/code>, interval index<\/em>. As with the Chinese zodiac, essentials of the computation are brought into sharper relief if each zodiac sign is denoted by a single character:<\/p>\n
   zen\u2190{\r\n     d\u219012 2\u2374 1 20  2 19  3 21  4 20  5 21  6 21  7 23  8 23  9 23  10 23  11 22  12 22\r\n     (1+d\u2378\u2375)\u228313\u2374'\u2651\u2652\u2653\u2648\u2649\u264a\u264b\u264c\u264d\u264e\u264f\u2650'\r\n   }<\/code><\/pre>\n
The single-character signs, Unicode U+2648 to U+2653, were found by Google search and then confirmed by https:\/\/www.visibone.com\/htmlref\/char\/cer09800.htm<\/a>. It is possible that the single-character signs do not display correctly in your browser; the line of code can be expressed alternatively as (1+d\u2378\u2375)\u228313\u2374\u2395ucs 9800+12|8+\u237312<\/code>.<\/p>\n
6. What\u2019s Your Angle?<\/strong><\/p>\n
Check that angle brackets are balanced and not nested.<\/p>\n
   balanced \u2190 {(\u2227\/c\u220a0 1)\u22270=\u2283\u233dc\u2190+\\1 \u00af1 0['<>'\u2373\u2375]}<\/code><\/pre>\n
In APL, functions take array arguments, and so too indexing<\/em> takes array arguments, including the indices (the “subscripts”). This fact is exploited to transform the argument string into a vector c<\/code> of 1<\/code> and \u00af1<\/code> and 0<\/code>, according to whether a character is <<\/code> or ><\/code> or “other”. For the angles to be balanced, the plus scan (the partial sums) of c<\/code> must be a 0-1<\/code> vector whose last element is 0<\/code>.<\/p>\n
The closely related problem where the brackets can be nested (e.g. where the brackets are parentheses), can be solved by checking that c<\/code> is non-negative, that is, \u2227\/(\u00d7c)\u220a0 1<\/code> (and the last element is 0<\/code>).<\/p>\n
7. Unconditionally Shifty<\/strong><\/p>\n
Shift a boolean vector \u2375<\/code> by \u237a<\/code>, where positive means a right shift and negative means a left shift.<\/p>\n
   shift \u2190 {(\u2262\u2375)\u2374(-\u237a)\u233d\u2375,(|\u237a)\u23740}<\/code><\/pre>\n
The problem solution is facilitated by the rotate<\/em> function \u237a\u233d\u2375<\/code>, where a negative \u237a<\/code> means rotate right and positive means rotate left. Other alternative unguarded code can use \u2191<\/code> or \u2193<\/code> (take<\/em> or drop<\/em>) where a negative \u237a<\/code> means take (drop) from the right and positive means from the left.<\/p>\n
8. Making a Good Argument<\/strong><\/p>\n
Check whether a numeric left argument to \u237a\u2349\u2375<\/code> is valid.<\/p>\n
   dta \u2190 {0::0 \u22c4 1\u22a3\u237a\u2349\u2375}<\/code><\/pre>\n
This is probably the shortest possible solution: Return 1<\/code> if \u237a\u2349\u2375<\/code> executes successfully, otherwise the error is trapped and a 0<\/code> is returned. A longer but more insightful solution is as follows:<\/p>\n
   dt \u2190 {((\u2262\u237a)=\u2262\u2374\u2375) \u2227 \u2227\/\u237a\u220a\u2368\u2373(\u2262\u2374\u2375)\u230a(\u00d7\u2262\u237a)\u2308\u2308\u2308\/\u237a}<\/code><\/pre>\n
The first part of the conjunction checks that the length of \u237a<\/code> is the same as the rank of \u2375<\/code>. (Many APL authors would write \u2374\u2374\u2375<\/code>; I prefer \u2262\u2374\u2375<\/code> because the result is a scalar.) The second part checks the following properties on \u237a<\/code>:<\/p>\n