# Principled Programming / Tim Teitelbaum / Chapter 4.
from rational import Rational
import math
    
# 1. Divide and Conquer.
# 2. Sequential Refinement.
# 2.1. Example 1.
# 2.2. Example 2.
# 2.3. Example 3.
# 2.4. Example 4.
# 2.7. Example 5.
# 2.8. Generalization.
# 2.8.1. From Locations to Arbitrary Conditions.
# 2.8.2. Loosening the Coupling.
# 2.8.3. Weakening and Strengthening in Practice.
# 2.8.3.1 Example 1
# 2.8.3.2 Example 2
# 2.8.3.3 Example 3
# 2.8.3.4 Example 4
# 2.8.3.5 Example 5
# 2.8.4. Conjunctive Normal Form.
# 2.8.5. Implicit Preconditions.
# 2.8.6. Problem Reduction.
# 3. Case Analysis.
# 3.1 Examples.
# 3.1.1. Absolute value

def e4_3_1_1_1() -> None:
        """# Demonstrate absolute value using explicit if-else."""
    # SETUP
        x: int = 1
        y: int = 0
    # Let y be |x|.
        if x >= 0: y = x
        else: y = -x
    # OUTPUT
        print("absolute value of", x, " is", y)
    # SETUP
        x = -1
    # Let y be |x|.
        if x >= 0: y = x
        else: y = -x
    # OUTPUT
        print("absolute value of", x, " is", y)
            
# 3.1.2. Case Analysis subsumed in a procedure

def e4_3_1_2_1() -> None:
        """Demonstrate absolute value using a library procedure."""
    # SETUP
        x: int = 1
        y: int = 0
    # Let y be |x|.
        y = abs(x)
    # OUTPUT
        print("absolute value of", x, " is ", y)
    # SETUP
        x = -1
    # Let y be |x|.
        y = abs(x)
    # OUTPUT
        print("absolute value of", x, " is ", y)
            
# 3.1.3. Case Analysis subsumed in an operator

def e4_3_1_3_1() -> None:
        """Demonstrate one way to do modular increment."""
    # SETUP
        N: int = 3
        k: int = 0
        print("Increment:", k, "mod:", N, end='')
    # Increment k mod N.
        if k == N - 1: k = 0
        else: k += 1
    # OUTPUT
        print(" is:", k)
    # SETUP
        k = 1
        print("Increment:", k, "mod:", N, end='')
    # Increment k mod N.
        if k == N - 1: k = 0
        else: k += 1
    # OUTPUT
        print(" is:", k)
    # SETUP
        k = 2
        print("Increment:", k, "mod:", N, end='')
    # Increment k mod N.
        if k == N - 1: k = 0
        else: k += 1
    # OUTPUT
        print(" is:", k)
            
def e4_3_1_3_2() -> None:
        """Demonstrate one way to do modular decrement"""
    # SETUP
        N: int = 3
        k: int = 0
        print("Decrement:", k, "mod:", N, end='')
    # Decrement k mod N.
        if k == 0: k = N - 1
        else: k -= 1
    # OUTPUT
        print(" is:", k)
    # SETUP
        k = 1
        print("Decrement:", k, "mod:", N, end='')
    # Decrement k mod N.
        if k == 0: k = N - 1
        else: k -= 1
    # OUTPUT
        print(" is:", k)
    # SETUP
        k = 2
        print("Decrement:", k, "mod:", N, end='')
    # Decrement k mod N.
        if k == 0: k = N-1
        else: k -= 1
    # OUTPUT
        print(" is:", k)
            
def e4_3_1_3_3() -> None:
        """Demonstrate another way to do modular increment"""
    # SETUP
        N: int = 3
        k: int = 0
        print("Increment:", k, "mod:", N, end='')
    # Increment k mod N.
        k = (k + 1) % N
    # OUTPUT
        print(" is:", k)
    # SETUP
        k = 1
        print("Increment:", k, "mod:", N, end='')
    # Increment k mod N.
        k = (k + 1) % N
    # OUTPUT
        print(" is:", k)
    # SETUP
        k = 2
        print("Increment:", k, "mod:", N, end='')
    # Increment k mod N.
        k = (k + 1) % N
    # OUTPUT
        print(" is:", k)
            
def e4_3_1_3_4() -> None:
        """Demonstrate another way to do modular decrement."""
    # SETUP
        N: int = 3
        k: int = 0
        print("Decrement:", k, "mod:", N, end='')
    # Decrement k mod N.
        k = (k+N-1)%N
    # OUTPUT
        print(" is:", k)
    # SETUP
        k = 1
        print("Decrement:", k, "mod:", N, end='')
    # Decrement k mod N.
        k = (k + N - 1) % N
    # OUTPUT
        print(" is:", k)
    # SETUP
        k = 2
        print("Decrement:", k, "mod:", N, end='')
    # Decrement k mod N.
        k = (k + N - 1) % N
    # OUTPUT
        print(" is:", k)

# 3.1.4. Case Analysis subsumed in a table lookup
# 3.1.5. Parity

def e4_3_1_5_1() -> None:
        """Confirm treatment of modulus on negative argument."""
    # SETUP
        n: int = -1
        print(n, "is: ", end='')
    # Output whether n is odd or even.
        if (n % 2) == 1: print("odd")
        else: print("even")
    # SETUP
        print(n, "is: ", end='')
    # Output whether n is odd or even.
        if (n % 2) == 0: print("even")
        else: print("odd")
    
# 3.1.6. Roots

def e4_3_1_6_1() -> None:
        """Demonstrate computation of Boolean result."""
    # SETUP
        A: float = 1.0e0
        B: float = 2.0e0
        C: float = 1.0e0
    # Let im be True iff the roots of quadratic Ax2+Bx+C=0 are imaginary.
        im: bool  # Roots are imaginary.
        if B * B - 4 * A * C < 0: im = True
        else: im = False
    # OUTPUT
        print (im)
    # Let im2 be True iff the roots of quadratic Ax2+Bx+C=0 are imaginary.
        im2: bool = (B * B - 4 * A * C) < 0  # Roots are imaginary.
    # OUTPUT
        print (im2)
    # SETUP
        A = 2.0
    # Let im3 be True iff the roots of quadratic Ax2+Bx+C=0 are imaginary.
        im3: bool # Roots are imaginary.
        if B * B - 4 * A * C < 0: im3 = True
        else: im3 = False
    # OUTPUT
        print (im3)
    # Let im4 be True iff the roots of quadratic Ax2+Bx+C=0 are imaginary.
        im4: bool = (B * B - 4 * A * C) < 0 # Roots are imaginary.
    # OUTPUT
        print (im4)

def e4_3_1_6_2() -> None:
    """Compute roots of Ax^2+Bx+C=0 for an unbounded number of <A,B,C> inputs."""
    while True:
        A: float = float(input("Enter A: "))
        B: float = float(input("Enter B: "))
        C: float = float(input("Enter C: "))
        D: float = B * B - 4 * A * C
        root_abs_D = math.sqrt(abs(D))
        if A==0 and B==0 and C == 0:
            print("Trivial true equation. Every x is a root")
        elif A==0 and B==0 and C != 0:
            print("False equation with no variable")
        elif A==0:
            print("Linear. One root: ", -C/B)
        elif D == 0:
            print("Quadratic. One real root: ", -B/(2 * A))
        elif D > 0:
            print("Quadratic. Two real roots")
            print("Root1: ", (-B + root_abs_D)/2)
            print("Root2: ", (-B - root_abs_D)/2)
        else:
            print("Quadratic. Two imaginary roots.")
            print("Root1: ", -B/2, "+",  root_abs_D/2, "i")
            print("Root2: ", -B/2, "-",  root_abs_D/2, "i")

# 3.1.7. Parallel lines

def e4_3_1_7_1() -> None:
        """Are two lines parallel or intersecting."""
    # SETUP
        m1: float = 0.0e0
        m2: float = 2.2250738585072014E-308
        b1: float = 0.0e0
        b2: float = 0.0e0
    # Output whether lines y=m1*x+b1 and y=m2*x+b2 are parallel or intersect.
        if (m1 == m2) and (b1 != b2): print("parallel")
        else: print("intersect")

# 3.2 Generalization
# 4. Iterative Refinement
# 4.1 Iteration in the Real World
# 4.2 Nontermination

def rational_divide(r1: Rational, r2: Rational) -> Rational:
    """Define division on one Rational with another."""
    return Rational(r1.get_numerator() * r2.get_denominator(),
                    r1.get_denominator() * r2.get_numerator())

def e4_4_2_1() -> None:
        """Demonstrate termination of repeated halving on finite number systems,
        and nontermination of repeated halving on infinite number systems.
        """

    # SETUP
        h: int = 10
        print("Repeated halving of the integer: ", h)
    # REPEATED INTEGER DIVISION BY 2
        while h != 0: h = h // 2;
    # OUTPUT
        print(h)
    # SETUP
        h2: float = 10.0
        print("Repeated halving of the float: ", h2)
    # REPEATED FLOATING DIVISION BY 2
        while h2 != 0: h2 = h2 / 2;
    # OUTPUT
        print(h2)
    # SETUP
        zero: Rational = Rational(0,1)
        two:  Rational = Rational(2,1)
        h3:   Rational = Rational(10, 1)
        print("Repeated halving of the rational: ", h3)
    # REPEATED RATIONAL DIVISION BY 2
        while h3 != zero:
            print(h3)
            h3 = rational_divide(h3, two)
    # OUTPUT
        print(h3)

# 4.3 Finding Loop Invariants
# 4.4 Generalization
# 4.5 Integer Division

def e4_4_5_1() -> None:
        """# Integer Division."""
    # SETUP
        x: int = 10
        y: int = 3
    # Given int x≥0 and int y>0, set int q to x/y, and int r to x%y.
    # OUTPUT VARIABLES ON EACH ITERATION
        r: int = x; q: int = 0
        while r >= y:
            r = r - y; q += 1
            print("x: ", x, "y: ", y, "q: ", q, "r: ", r)
        print("---")
    # SETUP
        x = 10; y = 5
    # Given int x≥0 and int y>0, set int q to x/y, and int r to x%y.
    # OUTPUT VARIABLES ON EACH ITERATION
        r = x; q = 0
        while r >= y:
            r = r - y; q += 1
            print("x: ", x, "y: ", y, "q: ", q, "r: ", r)
        print("---")

# 4.7 Euclid's Algorithm
            
def gcd(x: int, y: int) -> int:
    """# Given x>0 and y>0, return the greatest common divisor of x and y."""
    while x != y:
        if x > y: x = x - y
        else:     y = y - x
    return x

def e4_7_1() -> None:
    print("gcd of: ", 24, "and: ",  9, "is: ", gcd(24,9))
    print("gcd of: ", 24, "and: ", 24, "is: ", gcd(24,24))
    print("gcd of: ", 3,  "and: ",  7, "is: ", gcd(3,7))
    print("gcd of: ", 6,  "and: ", 35, "is: ", gcd(6,35))

# 4.8 Coolatz Conjecture

def e4_8_1() -> None:
    """Given input n>0, output Coolatz Conjecture sequence."""
    n: int = int(input("Enter integer for Collatz Conjecture test: "))
    while n != 1:
        if (n % 2) == 0: n = n // 2
        else: n = 3 * n + 1
        print(n)
    print("done")

    n: int = int(input("Enter integer for Collatz Conjecture test: "))
    print(n)

def e4_8_2() -> None:
            """ Test Coolatz Conjecture on all integers between 1 and an input integer.
    # Output max value of all sequences tested."""
        # Setup
            hi: int = 1
            n: int = int(input("Enter range of ints for Coolatz Conjecture test: "))
        # if CC holds for all j from 1 through n, output a say-so and max int reached. */
            for k in range(1, n+1):
                # Confirm that CC holds for k. */
                   j: int = k
                   while j != 1:
                      if (j % 2) == 0: j = j // 2
                      else:
                          j = 3 * j + 1; hi = max(hi, j)
            print("Coolatz Conjecture holds up through:", n)
            print("Max integer reached: ", hi)

# 5. Recursive Refinement

def e4_5_1() -> None:
    """Count down from 5, and say “BLASTOFF” at 0."""
    countdown(5)
def countdown(n: int) -> None:
    """Count down from n, and say "BLASTOFF" at zero."""
    if n == 0: print("BLASTOFF")
    else:
        print(n)
        countdown(n-1)
            
# Output the sum of 1 through 100. MULTIPLE SOLUTIONS

def e4_5_2() -> None:
    """
    Output the sum of 1 through 100. Solution 1
    (Formula. No iteration.)
    """

    n: int = 100

    print(n*(n+1)//2)

def e4_5_3() -> None:
    """
    Output the sum of 1 through 100. Solution 2
    (Recursion.)
    """

    print(sum(100))
def sum(n: int) -> int:
    """Return the sum of 0 through n."""
    if n == 0: return 0
    else:
        # return Chapter4.sum(n - 1) + n.
            sum_of_1_through_n_minus_1 = sum(n - 1)
            print(sum_of_1_through_n_minus_1, "plus: ", n, "is: :")
            return sum_of_1_through_n_minus_1 + n

def e4_5_4() -> None:
    """
    Output the sum of 1 through 100. Solution 1
    (Forward iteration. Same sequence of additions as Recursion.)
    """

    n: int = 100

    sum: int = 0
    print(sum)
    for k in range(1, n+1):
        print("plus: ", k, "is: :", sum + k)
        sum = sum + k
    print(sum)

def e4_5_5() -> None:
    """
    Output the sum of 1 through 100. Solution 4
    (Recursion, with accumulation)
    """
    
    print(sum2(100))

# Return the sum of n down through 0.
def sum2(n: int) -> int:
    print(0)
    return sumAux(n,0)
# Return the sum of n down through 0, and acc.
def sumAux(n: int, acc: int) -> int:
    if n == 0: return acc
    else:
        print("plus: ", n, "is: ", n+acc)
        return sumAux(n - 1, n + acc)

def e4_5_6() -> None:
    """
    Output the sum of 1 through 100. Solution 5
    (Iteration backwards. Same sequence of additions as "Recursion, with accumulation")
    """

    n: int = 100

    sum: int = n
    print(sum)
    for k in range(n - 1, 0, -1):
        sum = k + sum
        print("plus: ", k, "is: :", sum)
    print(sum)

# 6. Library of Patterns
# 7. Choosing a Refinement
# 8. Extended Example
        
#Uncomment a line to run the test.

# Section 1. Divide and Conquer.

# Section 2. Sequential Refinement.
# Section 2.1. Example 1.
# Section 2.2. Example 2.
# Section 2.3. Example 3.
# Section 2.4. Example 4.
# Section 2.7. Example 5.
# Section 2.8. Generalization.
# Section 2.8.1. From Locations to Arbitrary Conditions.
# Section 2.8.2. Loosening the Coupling.
# Section 2.8.3. Weakening and Strengthening in Practice.
# Section 2.8.3.1 Example 1
# Section 2.8.3.2 Example 2
# Section 2.8.3.3 Example 3
# Section 2.8.3.4 Example 4
# Section 2.8.3.5 Example 5
# Section 2.8.4. Conjunctive Normal Form.
# Section 2.8.5. Implicit Preconditions.
# Section 2.8.6. Problem Reduction.

# Section 3. Case Analysis.
# Section 3.1 Examples.
# Section 3.1.1. Absolute value
#e4_3_1_1_1()
# Section 3.1.2. Case Analysis subsumed in a procedure
#e4_3_1_2_1()
# Section 3.1.3. Case Analysis subsumed in an operator
#e4_3_1_3_1()
#e4_3_1_3_2()
#e4_3_1_3_3()
#e4_3_1_3_4()
# Section 3.1.4. Case Analysis subsumed in a table lookup
# Section 3.1.5. Parity
#e4_3_1_5_1()
# Section 3.1.6. Roots
#e4_3_1_6_1()
#e4_3_1_6_2()
# Section 3.1.7. Parallel lines
#e4_3_1_7_1()
# Section 3.2 Generalization

# Section 4. Iterative Refinement
# Section 4.1 Iteration in the Real World
# Section 4.2 Nontermination
#e4_4_2_1()
#4.3 Finding Loop Invariants
# Section 4.4 Generalization
# Section 4.5 Integer Division
#e4_5_1()
# Section 4.7 Euclid's Algorithm
#e4_7_1()
# Section 4.8 Coolatz Conjecture
#e4_8_1()
#e4_8_2()

# Section 5. Recursive Refinement
#e4_5_1()
#e4_5_2()
#4_5_3()
#e4_5_4()
#e4_5_5()
#e4_5_6()

# Section 6. Library of Patterns
# Section 7. Choosing a Refinement
# Section 8. Extended Example