Skip to content

Winning solution for the APL Problem Solving Competition 2020

Notifications You must be signed in to change notification settings

amakukha/apl-contest-2020

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

25 Commits
 
 
 
 
 
 

Repository files navigation

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×2N/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".