22 lines
1.4 KiB
APL
22 lines
1.4 KiB
APL
|
lcs←{
|
|||
|
|
⎕IO←0
|
|||
|
|
betterof←{⊃(</+/¨⍺ ⍵)⌽⍺ ⍵} ⍝ better of 2 selections
|
|||
|
|
cmbn←{↑,⊃∘.,/(⊂⊂⍬),⍵} ⍝ combine lists
|
|||
|
|
rr←{∧/↑>/1 ¯1↓[1]¨⊂⍵} ⍝ rising rows
|
|||
|
|
hmrr←{∨/(rr ⍵)∧∧/⍵=⌈\⍵} ⍝ has monotonically rising rows
|
|||
|
|
rnbc←{{⍵/⍳⍴⍵}¨↓[0]×⍵} ⍝ row numbers by column
|
|||
|
|
valid←hmrr∘cmbn∘rnbc ⍝ any valid solutions?
|
|||
|
|
a w←(</⊃∘⍴¨⍺ ⍵)⌽⍺ ⍵ ⍝ longest first
|
|||
|
|
matches←a∘.=w
|
|||
|
|
aps←{⍵[;⍒+⌿⍵]}∘{(⍵/2)⊤⍳2*⍵} ⍝ all possible subsequences
|
|||
|
|
swps←{⍵/⍨∧⌿~(~∨⌿⍺)⌿⍵} ⍝ subsequences with possible solns
|
|||
|
|
sstt←matches swps aps⊃⍴w ⍝ subsequences to try
|
|||
|
|
w/⍨{
|
|||
|
|
⍺←0⍴⍨⊃⍴⍵ ⍝ initial selection
|
|||
|
|
(+/⍺)≥+/⍵[;0]:⍺ ⍝ no scope to improve
|
|||
|
|
this←⍺ betterof{⍵×valid ⍵/matches}⍵[;0] ⍝ try to improve
|
|||
|
|
1=1⊃⍴⍵:this ⍝ nothing left to try
|
|||
|
|
this ∇ 1↓[1]⍵ ⍝ keep looking
|
|||
|
|
}sstt
|
|||
|
|
}
|