Created
August 6, 2020 16:13
-
-
Save rodrigogiraoserrao/8845dc6a7191bc66cb9d2733e44261d5 to your computer and use it in GitHub Desktop.
RGS's recursive solution to Problem 9, Phase 2 of 2020 APL competition (see https://mathspp.com/blog/2020-apl-competition for my thoughts on it)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
:Namespace Mobiles | |
⍝ This namespace defines a set of helper functions for the recursive solution of the last problem. | |
(⎕IO ⎕ML ⎕WX) ← 0 1 3 | |
⍝ Monadic function to take a path to a mobile.txt file and return a character matrix. | |
OpenToMatrix ← {↑⊃⎕nget ⍵ 1} | |
Parse ← { | |
(⎕IO ⎕ML ⎕WX) ← 0 1 3 | |
⍝ Monadic function to parse (recursively) a mobile in matrix form. | |
⍝ Parses the mobile to a data structured similar to the brainf*ck tape in https://dfns.dyalog.com/n_bf.htm | |
⍺ ← ⊃⍸⍵∊'┴│' ⍝ find the first point to start parsing | |
'┌┐│'∊⍨⍺⌷⍵: (⍺+1 0)∇⍵ ⍝ parse down | |
~'┴'∊⍨c←⍺⌷⍵: c ⍝ reached a leaf | |
w ← ⍵ | |
_P ← { ⍝ lateral crawler to traverse the mobile arms | |
ctr ← 0 ⋄ aa ← ⍺⍺ | |
ctr ,⍥⊂ {ctr+←1 ⋄ ⍵+aa}⍣{'┌┐'∊⍨⍺⌷w} ⍵ | |
} | |
(cl al) ← 0 ¯1_P ⍺ | |
(cr ar) ← 0 1_P ⍺ | |
gcd ← cl ∨ cr ⋄ cl ÷← gcd ⋄ cr ÷← gcd | |
(al∇⍵) (cl) (cr) (ar∇⍵) | |
} | |
SplitWeight ← { | |
(⎕IO ⎕ML ⎕WX) ← 0 1 3 | |
⍝ Dyadic function to recursively assign weight ⍺ to each tree leaf in ⍵. | |
1=≢⍵: ⊂⍵ ⍺ | |
(l lw rw r) ← ⍵ | |
s ← ⍺÷lw+rw | |
(l ∇⍨ s×rw), (r ∇⍨ s×lw) | |
} | |
:EndNamespace | |
⍝ PROBLEM 9.1, recursive solution, no ⌹ nor coefficient matrix. | |
WeightsRec ← { | |
(⎕IO ⎕ML ⎕WX) ← 0 1 3 | |
⍝ Returns the weights with the labels ordered by ⍋. | |
p ← Mobiles.Parse Mobiles.OpenToMatrix ⍵ | |
splits ← 1 Mobiles.SplitWeight p | |
(⊢÷∨/) ⊃ ↓⍉⌽↑ splits[⍋splits] | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment