Skip to content

Instantly share code, notes, and snippets.

@rodrigogiraoserrao
Created August 6, 2020 16:13
Show Gist options
  • Save rodrigogiraoserrao/8845dc6a7191bc66cb9d2733e44261d5 to your computer and use it in GitHub Desktop.
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)
: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