amakukha · August 20, 2020 16:35
diff --git a/APL_Competition_2020_P9.dyalog b/APL_Competition_2020_P9.dyalog
 Weights←{
     ⍝ 2020 APL Problem Solving Competition Phase II
     ⍝ Problem 9, Task 1 - Weights

     ⍝ 1) Read the diagram of a mobile from the file as a vector of lines (M).
     ⍝ 2) Find lines which exactly repeat the preceding lines and contain only
     ⍝    vertical bars (│) and spaces. Such lines don't bring any useful
     ⍝    information. (This filtering step allows to process files which are
     ⍝    very deep without running out of memory. For example, 10K characters
     ⍝    wide, 100K lines deep. Without filtering, such a file would be
     ⍝    represented by a matrix with 1 billion characters!)
     ⍝ 3) Remove the repeating lines and format the rest of the lines into a
     ⍝    character matrix (2D).
     q←~((∧/∊∘'│ ')¨M)∧0,2≡/M←⊃⎕NGET ⍵ 1
     M←⍕↑q/M

     ⍝ Find the distinct weight names to know how many variables are there.
     ⍝ Assumption: all characters other than " ┌─┴┐│" and newline are weights.
     N←∪' ┌─┴┐│'~⍨∊M

     ⍝ Coefficients matrix: specifies the relationships between weights.
     ⍝ It is such a matrix that satisfies (C+.×W)≡(1,(¯1+≢N)⍴0),
     ⍝ where W is the solution vector (numeric values of weights).
     ⍝ We have only one row at this point: to set the first weight as the unit.
     C←(1@1)(1(≢N))⍴0    ⍝ the first weight is provisionally set to be 1

     ⍝ Define recursive function for parsing.
     ⍝ Returns a boolean vector for weights found in the sub-mobile (sub-tree)
     ⍝ Meanwhile, appends the matrix C as it goes (see the next function)
     descent←{                      ⍝ this function parses input vertically
         y←⍺+¯1+⌊/⍸'│'≠(⍺-1)↓M[;⍵]  ⍝ find first non-'│' from here down
         '┴'=M[y;⍵]:y explore ⍵     ⍝ explore new lever if fulcrum is found
         (1@(N⍳M[y;⍵]))(≢N)⍴0       ⍝ otherwise: turn weight name into a vector
     }

     ⍝ Parses a lever and adds the resulting relations between weights into C
     explore←{                      ⍝ this function parses input horizontally
         d←(∊∘'┐┌')M[⍺;]            ⍝ find all lever edges in the current row
         l r←(⍳∘1)¨(⌽(⍵-1)↑d)(⍵↓d)  ⍝ offsets of the left and right edges
         w1←(⍺+1)descent ⍵-l        ⍝ parse left sub-mobile
         w2←(⍺+1)descent ⍵+r        ⍝ parse right sub-mobile
         cfs←(l×w1)-r×w2            ⍝ relationship between weights here (coefs)
         C⍪←cfs÷∨/cfs               ⍝ divide the coefs by GCD and catenate to C
         w1+w2                      ⍝ return all the weights of this sub-mobile
     }

     ⍝ Find the topmost link: it will be the starting point for parsing.
     ⍝ Assumption: there are no empty lines above the mobile.
     x←⌊/M[1;]⍳'┴│'

     ign←1 descent x        ⍝ parse the input to find the matrix C

     ⍝ 1) Obtain a solution by multiplying the inverse of C by vector 1 0 ... 0
     ⍝    (equivalent to just taking the first column of the inverse).
     ⍝ 2) Divide the solution vector by generalized GCD of its values to get
     ⍝    the smallest integer solution.
     ,W÷∨/W←(⌹C)[;1]
 }
	Weights←{
	⍝ 2020 APL Problem Solving Competition Phase II
	⍝ Problem 9, Task 1 - Weights

	⍝ 1) Read the diagram of a mobile from the file as a vector of lines (M).
	⍝ 2) Find lines which exactly repeat the preceding lines and contain only
	⍝ vertical bars (│) and spaces. Such lines don't bring any useful
	⍝ information. (This filtering step allows to process files which are
	⍝ very deep without running out of memory. For example, 10K characters
	⍝ wide, 100K lines deep. Without filtering, such a file would be
	⍝ represented by a matrix with 1 billion characters!)
	⍝ 3) Remove the repeating lines and format the rest of the lines into a
	⍝ character matrix (2D).
	q←~((∧/∊∘'│ ')¨M)∧0,2≡/M←⊃⎕NGET ⍵ 1
	M←⍕↑q/M

	⍝ Find the distinct weight names to know how many variables are there.
	⍝ Assumption: all characters other than " ┌─┴┐│" and newline are weights.
	N←∪' ┌─┴┐│'~⍨∊M

	⍝ Coefficients matrix: specifies the relationships between weights.
	⍝ It is such a matrix that satisfies (C+.×W)≡(1,(¯1+≢N)⍴0),
	⍝ where W is the solution vector (numeric values of weights).
	⍝ We have only one row at this point: to set the first weight as the unit.
	C←(1@1)(1(≢N))⍴0 ⍝ the first weight is provisionally set to be 1

	⍝ Define recursive function for parsing.
	⍝ Returns a boolean vector for weights found in the sub-mobile (sub-tree)
	⍝ Meanwhile, appends the matrix C as it goes (see the next function)
	descent←{ ⍝ this function parses input vertically
	y←⍺+¯1+⌊/⍸'│'≠(⍺-1)↓M[;⍵] ⍝ find first non-'│' from here down
	'┴'=M[y;⍵]:y explore ⍵ ⍝ explore new lever if fulcrum is found
	(1@(N⍳M[y;⍵]))(≢N)⍴0 ⍝ otherwise: turn weight name into a vector
	}

	⍝ Parses a lever and adds the resulting relations between weights into C
	explore←{ ⍝ this function parses input horizontally
	d←(∊∘'┐┌')M[⍺;] ⍝ find all lever edges in the current row
	l r←(⍳∘1)¨(⌽(⍵-1)↑d)(⍵↓d) ⍝ offsets of the left and right edges
	w1←(⍺+1)descent ⍵-l ⍝ parse left sub-mobile
	w2←(⍺+1)descent ⍵+r ⍝ parse right sub-mobile
	cfs←(l×w1)-r×w2 ⍝ relationship between weights here (coefs)
	C⍪←cfs÷∨/cfs ⍝ divide the coefs by GCD and catenate to C
	w1+w2 ⍝ return all the weights of this sub-mobile
	}

	⍝ Find the topmost link: it will be the starting point for parsing.
	⍝ Assumption: there are no empty lines above the mobile.
	x←⌊/M[1;]⍳'┴│'

	ign←1 descent x ⍝ parse the input to find the matrix C

	⍝ 1) Obtain a solution by multiplying the inverse of C by vector 1 0 ... 0
	⍝ (equivalent to just taking the first column of the inverse).
	⍝ 2) Divide the solution vector by generalized GCD of its values to get
	⍝ the smallest integer solution.
	,W÷∨/W←(⌹C)[;1]
	}