public class LoopExercises {
    
    
    /** = the product of 2..10 */
    public static int E1a() {
        int x= 2;
        int k= 2;
        // inv: P1: 2 ² k ² 10  and  x is the product of 2..k
        while (k != 10) {
            x= x * (k+1);
            k= k+1;
        }
        // x is the product of 2..10
        return x;
    }
    
    /** = the product of 2..10 */
    public static int E1b() {
        int x= 1;
        int k= 2;
        // inv: P2: 2 ² k ² 11  and  x is the product of 2..(k Ð 1)
        while (k != 11) {
            x= x * k;
            k= k+1;
        }
        // x is the product of 2..10
        return x;
    }
    
    /** = the product of 2..10 */
    public static int E1c() {
        int x= 10;
        int k= 10;
        // inv: P3: 2 ² k ² 10  and  x is the product of k..10
        while (k != 2) {
            x= x * (k-1);
            k= k-1;
        }
        // x is the product of 2..10
        return x;
    }
    
    /** = the product of 2..10 */
    public static int E1d() {
        int x= 1;
        int k= 10;
        // inv: P4: 1 ² k ² 10  and  x is the product of (k + 1)..10
        while (k != 1) {
            x= x * k;
            k= k-1;
        }
        // x is the product of 2..10
        return x;
    }
    
    /** = "n is divisible by an integer in first..last
         Precondition: first <= last */
    public static boolean E2a(int n, int first, int last) {
        boolean b= false;
        int k= first-1;
        // inv: P1: b = "n is divisible by an integer in first..k"..10
        while (k != last) {
            if (n % (k+1) == 0 ) {
                b= true;
            }
            k= k+1;
        }
        // R: b = "n is divisible by an integer in first..last"
        return b;
    } 
    
    /** = "n is divisible by an integer in first..last
         Precondition: first <= last */
    public static boolean E2b(int n, int first, int last) {
        boolean b= false;
        int k= first;
        // inv: P2: b = "n is divisible by an integer in first..(k Ð 1)"
        while (k <= last) {
            if (n % k == 0 ) {
                b= true;
            }
            k= k+1;
        }
        // R: b = "n is divisible by an integer in first..last"
        return b;
    } 

    /** = "n is divisible by an integer in first..last
         Precondition: first <= last */
    public static boolean E2c(int n, int first, int last) {
        boolean b= false;
        int k= last+1;
        // inv: P3: b = "n is divisible by an integer in k..last"
        while (k != first) {
            if (n % (k-1) == 0 ) {
                b= true;
            }
            k= k-1;
        }
        // R: b = "n is divisible by an integer in first..last"
        return b;
    } 
    
    /** = "n is divisible by an integer in first..last
         Precondition: first <= last */
    public static boolean E2d(int n, int first, int last) {
        boolean b= false;
        int k= last;
        // inv: P4: b = "n is divisible by an integer in k+1..last"
        while (first <= k) {
            if (n % k == 0 ) {
                b= true;
            }
            k= k-1;
        }
        // R: b = "n is divisible by an integer in first..last"
        return b;
    } 
    
    /** = the largest power of 2 that is at most n
          Precondition: n > 0*/
    public static int E3(int n) {
        int k= 0;
        int b= 1;
        // invariant: P: 1 ² 2**k ² n  and  b = 2**k
        while ( 2*b <= n  ) {
            k= k+1;
            b= 2*b;
        }
        
        // R: 1 ² 2**k ² n < 2**(k+1)
        return k;
    }
    
    
   /** = the quotient q when x (³ 0) is divided by y (> 0) */
    public static int E4a(int x, int y) {
        int q= 0;
        int r= x;
        // invariant P: x = y * q + r*  and  0 ² r
        while (r >= y) {
            q= q + 1;
            r= r - y;
        }
        
        // R: x = y * q + r      where 0 ² r < y
        return q;
    }
    
    /** = the remainder r when x (³ 0) is divided by y (> 0) */
    public static int E4b(int x, int y) {
        int q= 0;
        int r= x;
        // invariant P: x = y * q + r*  and  0 ² r
        while (r >= y) {
            q= q + 1;
            r= r - y;
        }
        
        // R: x = y * q + r      where 0 ² r < y
        return r;
    }
    
    /** = greatest common divisor of x and y.
          Precondition: x > 0 and y > 0 */
    public static int E5(int x, int y) {
        int b= x;
        int c= y;
        // invariant P: b gcd c = x gcd y
        while (b != c) {
            if (b > c) b= b - c;
            else c= c - b;
        }
        // R: b = x gcd y
        return b;
    }
    
    
    /** = s but with vowels removed */
    public static String E6(String s) {
        int k= 0;
        // invariant P: s[0..(k Ð 1)] contains no vowels
        while (k != s.length()) {
              char c= s.charAt(k);
              if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
                c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U') {
                s= s.substring(0,k) + s.substring(k+1);
              } else {
                k= k+1;
              }
 
        }
        // R: s[0..(s.length() Ð 1)] contains no vowels
        return s;
    }
    
    /** = "DNA sequences s1 and s2 are complements of each other" */
    public static boolean E7(String s1, String s2) {
        if (s1.length() != s2.length())
            return false;
        boolean b= true;
        int k= 0;
        // inv: b = "s1[0..k-1] and s2[0..s1.k-1] are complements"
        while (b && k != s1.length()) {
            char c1= s1.charAt(k);
            char c2= s2.charAt(k);
            if (c1 =='A' && c2 !='T') b= false;
            if (c1 =='T' && c2 !='A') b= false;
            if (c1 =='C' && c2 !='G') b= false;
            if (c1 =='G' && c2 !='C') b= false;
            
            k= k + 1;
        }
        // b = "s1[0..s1.length()-1] and s2[0..s1.length()-1] are complements"
        return b;
    }
    
    /** = "=  the complement of DNA sequences s" */
    public static String E8(String s) {
        int k= 0;
        String t= "";
        // inv: t[0..k-1] is the complement of s[0..k-1]
        while (k != s.length()) {
            char c= s.charAt(k);
            if (c =='A') t= t + 'T';
            if (c =='T') t= t + 'A';
            if (c =='C') t= t + 'G';
            if (c =='G') t= t + 'C';
            
            k= k + 1;
        }
        // t[0..t.length()-1] is the complement of s[0..s.length()-1]
        return t;
    }
    
    
    
    
    
    
    
    /** = true iff s is a palidrome */
    public static boolean e22(String s) {
        // initilization
        int k = 0;
        int h = s.length() -  1; 
        
        // invariant: s[0..k-1] is the reverse of s[h..s.length()-1]
        while(k < s.length() && s.charAt(k) == s.charAt(h)) {    
            k = k + 1;
            h = s.length() - 1 - k;
        }
        
        // postcondition: s[0..s.length()-1] is the reverse of s[s.length()-1 .. 0]
        return k == s.length();    
    }
    /** = true iff every character in s is part of a duplicated pair */
    public static boolean e23(String s) {
        
        // precondition: s.length() must be even to have a pair
        if (s.length() % 2 != 0)
            return false;
        
        // initialization
        int k = 0;
        
        // invariant: every character from 0..k is part of a duplicated pair
        while (k < s.length()) {
            if (k % 2 != 0 && s.charAt(k) != s.charAt(k-1))
                return false;
            
            k = k + 1;
        }
        
        // postcondition: every character from 0..s.length()-1 is part of a duplicated pair
        return true;
    }
    
    /** = true iff every character who's position in s is a power of 2 is a digit */
    public static boolean e24(String s) {
        
        // initialization
        int k=1;
        boolean b = true;
        
        // invariant: b = true iff s[c] is a digit for any c = power of two from 0..k
        while (k < s.length()) {
            b = b && Character.isDigit(s.charAt(k));
            k = 2 * k;
        }
        
        // postcondition: true iff s[c] is a digit for any c = power of two from 0..k where s.length() - 1 < k < 2*(s.length() -1)
        return b;
    }
    
    /** = true iff every character in s is identical to every character in t */
    public static boolean e25(String s, String t) {
        // precondition: s and t have the same length
        if (s.length() != t.length())
            return false;
        
        // invariant: each character of the strings s and t from 0..k-1 are identical
        for (int k=0; k<s.length(); k++) {
            if (s.charAt(k) != t.charAt(k))
                return false;
        }
        
        // postcondition: each character of the strings s and t from 0..s.length()-1 are identical
        return true;
    }
    
    public static String e26(String s) {
        
        // initialization
        int k = 0;
        int j = 0;
        String t = "";
        
        // invariant: each character in s from j..k-1 is part of a twin in string t
        while (k < s.length()) {
            
            // initialization
            String toAdd = "";
            j = k;
            
            // invariant: each character in toAdd from j..k is the same
            while (k < s.length() && s.charAt(k) == s.charAt(j)) {
                toAdd = toAdd + s.charAt(k);
                k = k + 1;
            }
            
            // postcondition: toAdd is a run of the same character
            // from the hint, if the length of this run is odd, then we need to add one more copy of the character
            if (toAdd.length() % 2 != 0) {
                toAdd = toAdd + toAdd.charAt(0);
            }
            
            t = t + toAdd;
        }
        
        // postcondition: each character in s from 0..s.length()-1 is part of a twin in string t
        return t;  
    }
}