APL Problem Solving Competition 2020

My solutions for the 2020 APL Problem Solving Competition:

Developed using Dyalog APL 18.0.

Phase II highlights

Balance problem (P.8) was solved using the Horowitz—Sahni algorithm with O(N×2^N/2) time complexity.
- Two more approaches are used for improved performance in special cases: recursive and brute force.
- I also tried the pseudo-polynomial dynamic programming approach, but it was consistently outperformed by the recursive branch and bound method with greedy heuristic.
Simple exponentiation by squaring: sset←{⍵>1:1e6|(1+2|⍵)×(∇⌊⍵÷2)*2 ⋄ 2} (P.4.2)
Simple solution for the cashflow problem: rr←{AR×+\⍺÷AR←×\1+⍵} (P.5.1)
- It's the fastest and seemed to be the most “array-based”. In a production setting, however, I'd rather go with a recurrent solution instead, which avoids the division operation.

Result

I won the Grand Prize (2500 USD + invitation to Dyalog '20 conference).

My take

Totally recommended!

This was a lot of fun and Dyalog APL is a useful tool to learn.

Advice for future contestants

Use dfns instead of tradfns.
Use dfns.cmpx for profiling.
Use APLcart.info to find idioms.
Always use ]Boxing on -style=max -trains=tree
Study algorithms.

If you want to learn more, you can watch my talk at Dyalog'20 titled "How I Won the APL Problem Solving Competition".