rodrigogiraoserrao · August 6, 2020 15:32
diff --git a/P4Phase2_2020.dyalog b/P4Phase2_2020.dyalog
 ⍝ PROBLEM 4.1
 revp ← {
    (⎕IO ⎕ML ⎕WX) ← 0 1 3
    ⍝ Find reverse palindromes of lengths between 4 and 12 in a DNA character vector.
    ⍝ Monadic function expecting a character vector.
    ⍝ A substring is a reverse palindrome if the substring is equal to its reverse complement.
    ⍝ The complement of a DNA string changes these pairs: 'A'←→'T', 'C'←→'G'.
    ⍝ Returns a 2 column integer matrix as if ⎕IO←1
    (⊢+⍴∘1 0∘⍴) 4 12 _revp ⍵
 }

 _revp ← {
    (⎕IO ⎕ML ⎕WX) ← 0 1 3
    ⍝ General form of the `revp` function.
    ⍝ Dyadic function expecting length delimiters on the left.
    ⍝ The results of this function are ⎕IO dependant.                     
    ⍺ ← 1, ≢⍵
    (m M) ← ⍺   
    dna ← ⍵
    C ← ((⌷∘'ACTG'⍤1 0)4|2+'ACTG'∘⍳) ⍝ complementing can be seen as (+2) mod 4 if we index wisely.
    and ← C dna
    l ← ≢dna
    s ← ⍳1+l-m         ⍝ the indices at which the possible revps start
    ls ← m+⍳1+M-m      ⍝ admissible lengths for the revps we care about
    r ← ↑,s ∘., ls     ⍝ complete table of possible final results
    is ← ,s ∘.(+∘⍳) ls ⍝ sets of indices for the possible revps
    is ← is /⍨ b←l>⌈/↑is  ⍝ remove sets that have indices too large; we first mix ↑ because the padding 0s won't change the result.
                          ⍝ c.f. https://chat.stackexchange.com/transcript/message/54445629#54445629
    r ← b⌿r               ⍝ remove the corresponding final results 
    r ⌿⍨ ∧/(is ⌷⍤0 1⊢dna) = (is (⌽⌷)⍤0 1⊢and)                  
 }

 ⍝ PROBLEM 4.2     
 sset ← {
    (⎕IO ⎕ML ⎕WX) ← 0 1 3
    ⍝ Compute the number of subsets you can make out of a set with size ⍵ (mod 10*6).
    ⍝ Monadic function expecting an integer.
    ⍝ This number is 2*⍵; to build any subset, for any element in the set either include it or not;
    ⍝ These 2 choices over the ⍵ elements give a total of 2*⍵ subsets.
    ⍝ Returns an integer.
    0=⍵: 1
    1000000 PowerMod 2 ⍵
 }

 PowerMod ← {
    (⎕IO ⎕ML ⎕WX) ← 0 1 3
    ⍝ Computes big powers under a given modulus.
    ⍝ Dyadic function expecting two integers on the right and one integer on the left.
    ⍝ For integers (a b)←⍵ computes a*b mod ⍺.
    ⍝ For that, we decompose b to binary and use repeated squaring.
    ⍝ Returns an integer.
    (base exp) ← ⍵
    0=exp: 1
    m ← ⍺
    bin ← ⌽2∘⊥⍣¯1⊢ exp
    l ← ≢bin
    powers ← l↑ {l≤≢⍵:⍵ ⋄ ⍵,m|2*⍨¯1↑⍵}⍣≡ base ⍝ extend the vector of powers to include all (base*2*k) needed.
    {m|⍺×⍵}/ bin/powers
 }
	⍝ PROBLEM 4.1
	revp ← {
	(⎕IO ⎕ML ⎕WX) ← 0 1 3
	⍝ Find reverse palindromes of lengths between 4 and 12 in a DNA character vector.
	⍝ Monadic function expecting a character vector.
	⍝ A substring is a reverse palindrome if the substring is equal to its reverse complement.
	⍝ The complement of a DNA string changes these pairs: 'A'←→'T', 'C'←→'G'.
	⍝ Returns a 2 column integer matrix as if ⎕IO←1
	(⊢+⍴∘1 0∘⍴) 4 12 _revp ⍵
	}

	_revp ← {
	(⎕IO ⎕ML ⎕WX) ← 0 1 3
	⍝ General form of the `revp` function.
	⍝ Dyadic function expecting length delimiters on the left.
	⍝ The results of this function are ⎕IO dependant.
	⍺ ← 1, ≢⍵
	(m M) ← ⍺
	dna ← ⍵
	C ← ((⌷∘'ACTG'⍤1 0)4\|2+'ACTG'∘⍳) ⍝ complementing can be seen as (+2) mod 4 if we index wisely.
	and ← C dna
	l ← ≢dna
	s ← ⍳1+l-m ⍝ the indices at which the possible revps start
	ls ← m+⍳1+M-m ⍝ admissible lengths for the revps we care about
	r ← ↑,s ∘., ls ⍝ complete table of possible final results
	is ← ,s ∘.(+∘⍳) ls ⍝ sets of indices for the possible revps
	is ← is /⍨ b←l>⌈/↑is ⍝ remove sets that have indices too large; we first mix ↑ because the padding 0s won't change the result.
	⍝ c.f. https://chat.stackexchange.com/transcript/message/54445629#54445629
	r ← b⌿r ⍝ remove the corresponding final results
	r ⌿⍨ ∧/(is ⌷⍤0 1⊢dna) = (is (⌽⌷)⍤0 1⊢and)
	}

	⍝ PROBLEM 4.2
	sset ← {
	(⎕IO ⎕ML ⎕WX) ← 0 1 3
	⍝ Compute the number of subsets you can make out of a set with size ⍵ (mod 10*6).
	⍝ Monadic function expecting an integer.
	⍝ This number is 2*⍵; to build any subset, for any element in the set either include it or not;
	⍝ These 2 choices over the ⍵ elements give a total of 2*⍵ subsets.
	⍝ Returns an integer.
	0=⍵: 1
	1000000 PowerMod 2 ⍵
	}

	PowerMod ← {
	(⎕IO ⎕ML ⎕WX) ← 0 1 3
	⍝ Computes big powers under a given modulus.
	⍝ Dyadic function expecting two integers on the right and one integer on the left.
	⍝ For integers (a b)←⍵ computes a*b mod ⍺.
	⍝ For that, we decompose b to binary and use repeated squaring.
	⍝ Returns an integer.
	(base exp) ← ⍵
	0=exp: 1
	m ← ⍺
	bin ← ⌽2∘⊥⍣¯1⊢ exp
	l ← ≢bin
	powers ← l↑ {l≤≢⍵:⍵ ⋄ ⍵,m\|2⍨¯1↑⍵}⍣≡ base ⍝ extend the vector of powers to include all (base2*k) needed.
	{m\|⍺×⍵}/ bin/powers
	}