Created
August 6, 2020 16:19
-
-
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)
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
⍝ 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