blog/posts/dyalog-apl-competition-2020-phase-2.org

---
title: "Dyalog APL Problem Solving Competition 2020 — Phase II"
subtitle: "Annotated Solutions"
date: 2020-08-02
tags: programming, apl
toc: true
---

* Introduction

After [[./dyalog-apl-competition-2020-phase-1.html][Phase I]], here are my solutions to Phase II problems. The full
code is included in the post, but everything is also available [[https://github.com/dlozeve/apl-competition-2020][on
GitHub]].

A PDF of the problems descriptions is available on [[https://www.dyalogaplcompetition.com/][the competition
website]], or directly from [[https://github.com/dlozeve/apl-competition-2020/blob/master/Contest2020/2020%20APL%20Problem%20Solving%20Competition%20Phase%20II%20Problems.pdf][my GitHub repo]].

The submission guidelines gave a template where everything is defined
in a ~Contest2020.Problems~ Namespace. I kept the default values for
~⎕IO~ and ~⎕ML~ because the problems were not particularly easier with
~⎕IO←0~.

#+begin_src default
  :Namespace Contest2020

	  :Namespace Problems
		  (⎕IO ⎕ML ⎕WX)←1 1 3
#+end_src

* Problem 1 -- Take a Dive

#+begin_src default
  ∇ score←dd DiveScore scores
    :If 7=≢scores
	    scores←scores[¯2↓2↓⍋scores]
    :ElseIf 5=≢scores
	    scores←scores[¯1↓1↓⍋scores]
    :Else
	    scores←scores
    :EndIf
    score←2(⍎⍕)dd×+/scores
  ∇
#+end_src

This is a very straightforward implementation of the algorithm
describe in the problem description. I decided to switch explicitly on
the size of the input vector because I feel it is more natural. For
the cases with 5 or 7 judges, we use Drop (~↓~) to remove the lowest
and highest scores.

At the end, we sum up the scores with ~+/~ and multiply them by
~dd~. The last operation, ~2(⍎⍕)~, is a train using [[https://help.dyalog.com/18.0/index.htm#Language/Primitive%20Functions/Format%20Dyadic.htm][Format (Dyadic)]] to
round to 2 decimal places, and [[https://help.dyalog.com/18.0/index.htm#Language/Primitive%20Functions/Execute.htm][Execute]] to get actual numbers and not
strings.

* Problem 2 -- Another Step in the Proper Direction

#+begin_src default
  ∇ steps←{p}Steps fromTo;segments;width
    width←|-/fromTo
    :If 0=⎕NC'p' ⍝ No left argument: same as Problem 5 of Phase I
	    segments←0,⍳width
    :ElseIf p<0 ⍝ -⌊p is the number of equally-sized steps to take
	    segments←(-⌊p){0,⍵×⍺÷⍨⍳⍺}width
    :ElseIf p>0 ⍝ p is the step size
	    segments←p{⍵⌊⍺×0,⍳⌈⍵÷⍺}width
    :ElseIf p=0 ⍝ As if we took zero step
	    segments←0
    :EndIf
    ⍝ Take into account the start point and the direction.
    steps←fromTo{(⊃⍺)+(-×-/⍺)×⍵}segments
  ∇
#+end_src

This is an extension to [[./dyalog-apl-competition-2020-phase-1.html#stepping-in-the-proper-direction][Problem 5 of Phase I]]. In each case, we compute
the "segments", i.e., the steps starting from 0. In a last step,
common to all cases, we add the correct starting point and correct the
direction if need be.

To compute equally-sized steps, we first divide the segment $[0, 1]$
in ~p~ equal segments with ~(⍳p)÷p~. This subdivision can then be
multiplied by the width to obtain the required segments.

When ~p~ is the step size, we just divide the width by the step size
(rounded to the next largest integer) to get the required number of
segments. If the last segment is too large, we "crop" it to the width
with Minimum (~⌊~).

* Problem 3 -- Past Tasks Blast

#+begin_src default
  ∇ urls←PastTasks url;r;paths
    r←HttpCommand.Get url
    paths←('[a-zA-Z0-9_/]+\.pdf'⎕S'&')r.Data
    urls←('https://www.dyalog.com/'∘,)¨paths
  ∇
#+end_src

I decided to use ~HttpCommand~ for this task, since it is simply one
~]load HttpCommand~ away and should be platform-independent.

Parsing XML is not something I consider "fun" in the best of cases,
and I feel like APL is not the best language to do this kind of
thing. Given how simple the task is, I just decided to find the
relevant bits with a regular expression using [[https://help.dyalog.com/18.0/index.htm#Language/System%20Functions/r.htm][Replace and Search]]
(~⎕S~).

After finding all the strings vaguely resembling a PDF file name (only
alphanumeric characters and underscores, with a =.pdf= extension), I
just concatenate them to the base URL of the Dyalog domain.

* Problem 4 -- Bioinformatics

The first task can be solved by decomposing it into several functions.

#+begin_src default
  ⍝ Test if a DNA string is a reverse palindrome.
  isrevp←{⍵≡⌽'TAGC'['ATCG'⍳⍵]}
#+end_src

First, we compute the complement of a DNA string (using simple
indexing) and test if its Reverse (~⌽~) is equal to the original
string.

#+begin_src default
  ⍝ Generate all subarrays (position, length) pairs, for 4 ≤ length ≤ 12.
  subarrays←{⊃,/(⍳⍵),¨¨3↓¨⍳¨12⌊1+⍵-⍳⍵}
#+end_src

We first compute all the possible lengths for each starting point. For
instance, the last element cannot have any (position, length) pair
associated to it, because there is no three element following it. So
we crop the possible lengths to $[3, 12]$. For instance for an array
of size 10:

#+begin_src default
        {3↓¨⍳¨12⌊1+⍵-⍳⍵}10
┌──────────────┬───────────┬─────────┬───────┬─────┬───┬─┬┬┬┐
│4 5 6 7 8 9 10│4 5 6 7 8 9│4 5 6 7 8│4 5 6 7│4 5 6│4 5│4││││
└──────────────┴───────────┴─────────┴───────┴─────┴───┴─┴┴┴┘
#+end_src

Then, we just add the corresponding starting position to each length
(1 for the first block, 2 for the second, and so on). Finally, we
flatten everything.

#+begin_src default
  ∇ r←revp dna;positions
    positions←subarrays⍴dna
    ⍝ Filter subarrays which are reverse palindromes.
    r←↑({isrevp dna[¯1+⍵[1]+⍳⍵[2]]}¨positions)/positions
  ∇
#+end_src

For each possible (position, length) pair, we get the corresponding
DNA substring with ~dna[¯1+⍵[1]+⍳⍵[2]]~ (adding ~¯1~ is necessary
because ~⎕IO←1~). We test if this substring is a reverse palindrome
using ~isrevp~ above. [[https://help.dyalog.com/18.0/index.htm#Language/Primitive%20Functions/Replicate.htm][Replicate]] (~/~) then selects only the (position,
length) pairs for which the substring is a reverse palindrome.

The second task is just about counting the number of subsets modulo
1,000,000. So we just need to compute $2^n \mod 1000000$ for any
positive integer $n\leq1000$.

#+begin_src default
  sset←{((1E6|2∘×)⍣⍵)1}
#+end_src

Since we cannot just compute $2^n$ directly and take the remainder, we
use modular arithmetic to stay mod 1,000,000 during the whole
computation. The dfn ~(1E6|2∘×)~ doubles its argument mod
1,000,000. So we just apply this function $n$ times using the [[https://help.dyalog.com/18.0/index.htm#Language/Primitive%20Operators/Power%20Operator.htm][Power]]
operator (~⍣~), with an initial value of 1.

* Problem 5 -- Future and Present Value

First solution: ~((1+⊢)⊥⊣)~ computes the total return for a vector of
amounts ~⍺~ and a vector of rates ~⍵~. It is applied to every prefix
subarray of amounts and rates to get all intermediate values. However,
this has quadratic complexity.

#+begin_src default
  rr←(,\⊣)((1+⊢)⊥⊣)¨(,\⊢)
#+end_src

Second solution: We want to be able to use the recurrence relation
(~recur~) and scan through the vectors of amounts and rates,
accumulating the total value at every time step. However, APL
evaluation is right-associative, so a simple [[https://help.dyalog.com/18.0/index.htm#Language/Primitive%20Operators/Scan.htm][Scan]]
(~recur\amounts,¨values~) would not give the correct result, since
~recur~ is not associative and we need to evaluate it
left-to-right. (In any case, in this case, Scan would have quadratic
complexity, so would not bring any benefit over the previous
solution.)  What we need is something akin to Haskell's ~scanl~
function, which would evaluate left to right in $O(n)$
time[fn:apl-scan]. This is what we do here, accumulating values from
left to right. (This is inspired from [[https://dfns.dyalog.com/c_ascan.htm][~dfns.ascan~]], although heavily
simplified.)

[fn:apl-scan] There is an interesting [[https://stackoverflow.com/a/25100675/8864368][StackOverflow answer]] explaining
the behaviour of Scan, and compares it to Haskell's ~scanl~ function.


#+begin_src default
  rr←{recur←{⍵[1]+⍺×1+⍵[2]} ⋄ 1↓⌽⊃{(⊂(⊃⍵)recur⍺),⍵}/⌽⍺,¨⍵}
#+end_src

For the second task, there is an explicit formula for cashflow
calculations, so we can just apply it.

#+begin_src default
  pv←{+/⍺÷×\1+⍵}
#+end_src

* Problem 6 -- Merge

#+begin_src default
  ∇ text←templateFile Merge jsonFile;template;ns
    template←⊃⎕NGET templateFile 1
    ns←⎕JSON⊃⎕NGET jsonFile
    ⍝ We use a simple regex search and replace on the
    ⍝ template.
    text←↑('@[a-zA-Z]*@'⎕R{ns getval ¯1↓1↓⍵.Match})template
  ∇
#+end_src

We first read the template and the JSON values from their files. The
[[https://help.dyalog.com/18.0/index.htm#Language/System%20Functions/nget.htm][~⎕NGET~]] function read simple text files, and [[https://help.dyalog.com/18.0/index.htm#Language/System%20Functions/json.htm][~⎕JSON~]] extracts the
key-value pairs as a namespace.

Assuming all variable names contain only letters, we match the regex
~@[a-zA-Z]*@~ to match variable names enclosed between ~@~
symbols. The function ~getval~ then returns the appropriate value, and
we can replace the variable name in the template.

#+begin_src default
  ∇ val←ns getval var
    :If ''≡var ⍝ literal '@'
	    val←'@'
    :ElseIf (⊂var)∊ns.⎕NL ¯2
	    val←⍕ns⍎var
    :Else
	    val←'???'
    :EndIf
  ∇
#+end_src

This function takes the namespace matching the variable names to their
respective values, and the name of the variable.
- If the variable name is empty, we matched the string ~@@~, which
  corresponds to a literal ~@~.
- If the variable name is present in the namespace, we query the
  namespace to get the required value.
- Otherwise, we have an unknown variable, so we replace it with ~???~.

* Problem 7 -- UPC

#+begin_src default
  CheckDigit←{10|-⍵+.×11⍴3 1}
#+end_src

The check digit satisfies the equation
\[ 3 x_{1}+x_{2}+3 x_{3}+x_{4}+3 x_{5}+x_{6}+3 x_{7}+x_{8}+3 x_{9}+x_{10}+3 x_{11}+x_{12} \equiv 0 \bmod 10, \]
therefore,
\[ x_{12} \equiv -(3 x_{1}+x_{2}+3 x_{3}+x_{4}+3 x_{5}+x_{6}+3 x_{7}+x_{8}+3 x_{9}+x_{10}+3 x_{11}) \bmod 10. \]

Translated to APL, we just take the dot product between the first 11
digits of the barcode with ~11⍴3 1~, negate it, and take the remainder
by 10.

#+begin_src default
  ⍝ Left and right representations of digits. Decoding
  ⍝ the binary representation from decimal is more
  ⍝ compact than writing everything explicitly.
  lrepr←⍉(7⍴2)⊤13 25 19 61 35 49 47 59 55 11
  rrepr←~¨lrepr
#+end_src

For the second task, the first thing we need to do is save the
representation of digits. To save space, I did not encode the binary
representation explicitly, instead using a decimal representation that
I then decode in base 2. The right representation is just the
bitwise negation.

#+begin_src default
  ∇ bits←WriteUPC digits;left;right
    :If (11=≢digits)∧∧/digits∊0,⍳9
	    left←,lrepr[1+6↑digits;]
	    right←,rrepr[1+6↓digits,CheckDigit digits;]
	    bits←1 0 1,left,0 1 0 1 0,right,1 0 1
    :Else
	    bits←¯1
    :EndIf
  ∇
#+end_src

First of all, if the vector ~digits~ does not have exactly 11
elements, all between 0 and 9, it is an error and we return ~¯1~.

Then, we take the first 6 digits and encode them with ~lrepr~, and the
last 5 digits plus the check digit encoded with ~rrepr~. In each case,
adding 1 is necessary because ~⎕IO←1~. We return the final bit array
with the required beginning, middle, and end guard patterns.

#+begin_src default
  ∇ digits←ReadUPC bits
    :If 95≠⍴bits ⍝ incorrect number of bits
	    digits←¯1
    :Else
	    ⍝ Test if the barcode was scanned right-to-left.
	    :If 0=2|+/bits[3+⍳7]
		    bits←⌽bits
	    :EndIf
	    digits←({¯1+lrepr⍳⍵}¨(7/⍳6)⊆42↑3↓bits),{¯1+rrepr⍳⍵}¨(7/⍳6)⊆¯42↑¯3↓bits
	    :If ~∧/digits∊0,⍳9 ⍝ incorrect parity
		    digits←¯1
	    :ElseIf (⊃⌽digits)≠CheckDigit ¯1↓digits ⍝ incorrect check digit
		    digits←¯1
	    :EndIf
    :EndIf
  ∇
#+end_src

- If we don't have the correct number of bits, we return ~¯1~.
- We test the first digit for its parity, to determine if its actually
  a left representation. If it's not, we reverse the bit array.
- Then, we take the bit array representing the right digits
  (~¯42↑¯3↓bits~), separate the different digits using [[https://help.dyalog.com/18.0/index.htm#Language/Primitive%20Functions/Partition.htm][Partition]]
  (~⊆~), and look up each of them in the ~rrepr~ vector using [[https://help.dyalog.com/18.0/index.htm#Language/Primitive%20Functions/Index%20Of.htm][Index Of]]
  (~⍳~). We do the same for the left digits.
- Final checks for the range of the digits (i.e., if the
  representations could not be found in the ~lrepr~ and ~rrepr~
  vectors), and for the check digit.

* Problem 8 -- Balancing the Scales

#+begin_src default
  ∇ parts←Balance nums;subsets;partitions
    ⍝ This is a brute force solution, running in
    ⍝ exponential time. We generate all the possible
    ⍝ partitions, filter out those which are not
    ⍝ balanced, and return the first matching one. There
    ⍝ are more advanced approach running in
    ⍝ pseudo-polynomial time (based on dynamic
    ⍝ programming, see the "Partition problem" Wikipedia
    ⍝ page), but they are not warranted here, as the
    ⍝ input size remains fairly small.

    ⍝ Generate all partitions of a vector of a given
    ⍝ size, as binary mask vectors.
    subsets←{1↓2⊥⍣¯1⍳2*⍵}
    ⍝ Keep only the subsets whose sum is exactly
    ⍝ (+/nums)÷2.
    partitions←nums{((2÷⍨+/⍺)=⍺+.×⍵)/⍵}subsets⍴nums
    :If 0=≢,partitions
	    ⍝ If no partition satisfy the above
	    ⍝ criterion, we return ⍬.
	    parts←⍬
    :Else
	    ⍝ Otherwise, we return the first possible
	    ⍝ partition.
	    parts←nums{((⊂,(⊂~))⊃↓⍉⍵)/¨2⍴⊂⍺}partitions
    :EndIf
  ∇
#+end_src

* Problem 9 -- Upwardly Mobile

This is the only problem that I didn't complete. It required parsing
the files containing the graphical representations of the trees, which
was needlessly complex and, quite frankly, hard and boring with a
language like APL.

However, the next part is interesting: once we have a matrix of
coefficients representing the relationships between the weights, we
can solve the system of equations. [[https://help.dyalog.com/18.0/index.htm#Language/Primitive%20Functions/Matrix%20Divide.htm][Matrix Divide]] (~⌹~) will find one
solution to the system. Since the system is overdetermined, we fix
~A=1~ to find one possible solution. Since we want integer weights,
the solution we find is smaller than the one we want, and may contain
fractional weights. So we multiply everything by the [[https://help.dyalog.com/18.0/index.htm#Language/Primitive%20Functions/And%20Lowest%20Common%20Multiple.htm][Lowest Common
Multiple]] (~∧~) to get the smallest integer weights.

#+begin_src default
  ∇ weights←Weights filename;mobile;branches;mat
    ⍝ Put your code and comments below here

    ⍝ Parse the mobile input file.
    mobile←↑⊃⎕NGET filename 1
    branches←⍸mobile∊'┌┴┐'
    ⍝ TODO: Build the matrix of coefficients mat.

    ⍝ Solve the system of equations (arbitrarily setting
    ⍝ the first variable at 1 because the system is
    ⍝ overdetermined), then multiply the coefficients by
    ⍝ their least common multiple to get the smallest
    ⍝ integer weights.
    weights←((1∘,)×(∧/÷))mat[;1]⌹1↓[2]mat
  ∇
#+end_src

#+begin_src default
	  :EndNamespace
  :EndNamespace
#+end_src