Skip to content

Instantly share code, notes, and snippets.

@rodrigogiraoserrao
Created August 6, 2020 16:19
Show Gist options
  • Save rodrigogiraoserrao/7f09c6314c3c6bdfab34e4594c728fc6 to your computer and use it in GitHub Desktop.
Save rodrigogiraoserrao/7f09c6314c3c6bdfab34e4594c728fc6 to your computer and use it in GitHub Desktop.
RGS's array-oriented solution to Problem 9, Phase 2 of 2020 APL competition (see https://mathspp.com/blog/2020-apl-competition for my thoughts on it)
⍝ PROBLEM 9.1, array-oriented solution, faster for the 3 examples provided.
Weights ← {
(⎕IO ⎕ML ⎕WX) ← 0 1 3
⍝ Reads the mobile data from the file ⍵ and returns its weights.
⍝ Monadic function expecting a character vector and returning an integer vector.
⍝ Returns the weights ordered from left to right, top to bottom.
⍝ How it works:
⍝ We will build a square coefficient matrix where each variable is the weight of a left (┌) or right (┐) corner.
⍝ Let's say n is the number of leafs in the mobile; then n is also the number of pivots and by the lengths of the arms
⍝ we can already write n equations that relate corresponding left and right corners.
⍝ An extra (n-1) equations can be written by finding corners which are on top of pivots
⍝ and realizing the weights of those parent corners are the same as the total weight of the two children corners.
⍝ These (2n-1) equations give all the restrictions we need in terms of weight relationships; we then add
⍝ an arbitrary equation that sets the weight of the whole mobile to 1 and then we rescale it with the GCD operation.
⍝ Throughout the algorithm we implicitly order corners and pivots from left to right, top to bottom.
m ← Mobiles.OpenToMatrix ⍵
L ← (⍸m∊⊢) ⍝ locate specifc characters in the mobile character matrix
lpiv ← L'┴'
n ← ≢lpiv ⋄ N ← 2×n ⋄ n_ ← n-1
⍝ Each 2-integer scalar gives weight ratios for a pivot.
w ← (↓⌽↑ lpiv-L'┌') + (lpiv-L'┐')
⍝ First n equations using arm lengths.
mat ← (∊w)@(↓⍉↑ ((⍳n)\⍨n⍴2) (⍳N)) ⊢ 0⍴⍨n N
⍝ We want to find parent corners (pc) whose children (ch) are pivots.
pc ← L'┌┐' ⋄ ch ← (⍸m~⍤∊⊢)' │┌─┐' ⍝ don't assume children are uppercase letters.
p2c ← ⊃⌽ ↓⍉↑⍸ <\ ∊∘(⊂¯1 0) ×pc∘.-ch ⍝ m[ch[p2c]] shows what is below m[pc]
⍝ Find which pivot is below each corner
pivs ← lpiv ⍳ ch[p2c]
ap ← ~ pivs = ≢lpiv
pivs ← ap/pivs ⍝ filter out corners above leafs.
⍝ Map each children pivot to its two branched children corner indices (chi) and build the (n-1) equations
chi ← (1∘+,⊢) 2×pivs
vs ← (¯1⍴⍨2×n_),n_⍴1
mat2 ← vs@(↓⍉↑ (r,r,r←⍳n_) (chi,⍸ap)) ⊢ 0⍴⍨n_ N
(~ap) / (⊢÷∨/) (N↑1) (⊣⌹⍪) mat⍪mat2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment