#!/usr/bin/env python
# coding: utf-8

# <h1><center>cs1001.py , Tel Aviv University, Fall 2017-2018</center></h1>
# <img src="http://www.pngall.com/wp-content/uploads/2016/05/Python-Logo-PNG-Image-180x180.png" width=50/>

# # Recitation 4

# We talked about comlexity. First we had an intuitive intro through an exercise and then we formally defined the notion of $O$ and solved some theoretical exercises.
# 
# #### Takeaways:
# 
# <ol>
#   <li>The time complexity bound implies how that the running time changes as a function of the input size.</li>
#   <li>Two solutions that have the same time complexity bound may differ in their running time (one can be more efficient than the other).</li>
#   <li>The Big O notation "hides" additive and multiplicative constants</li>
#   <li>Two solutions that have the same time complexity bound may differ in their running time (one can be more efficient than the other).</li>
#    <li>To analyze nested loops that are dependent, use a sum ($\sum$), with the boundaries of the external loop as the limits and the number of iterations for the inner loop in the sum itself.</li>
# </ol>

# ## Exercise: Given an natural number $p$, how many right triangles exist with integer sized sides whose perimeter is $p$?

# ### Model:
# 
# How many triplets (a,b,c) are there such that:
# 
# <ol>
# <li>$a^2 + b^2 = c^2$</li>
#   <li>$a + b + c = p$</li>
#   <li>$a,b,c > 0$ are all integers</li>
# </ol>
# 
# ### In order to avoid counting a triplet twice or more, we require:
# 
# <ol>
# <li>$0 < a < b < c$</li>
# </ol>
# 
# ### Note:
# 
# <ol>
# <li>$a \neq b$ and $b \neq c$</li>
# <li>The condition $b < c$ is redundant (since we require that $a,b,c > 0$ and $a^2 + b^2 = c^2$)</li>
# </ol>

# When computing code complexity, we
# <ol>
#     <li>define the entire content of the innermost loop as an “atomic operation” which takes constant time.</li>
#     <li>describe the complexity as a function of $p$ (i.e., use $p$ as the “problem size” or “input size”). 
#         Note, however, that the formal definition of “problem size” for a numeric input is the size it takes to represent the input, i.e. $n = \log(p)$. 
#         Working with $p$ here is easier and more intuitive.</li>
# </ol>

# # Trivial solution (v1):

# In[3]:


def number_of_integer_right_triangles_v1(p):
    cnt = 0
    for a in range(1,p):
        for b in range(1,p):
            for c in range(1,p):
                if a + b + c == p and a < b and a*a + b*b == c*c:
                    cnt += 1
    return cnt


# ### Analysis:
# 
# $(p-1)^3$ iterations.
# 
# The complexity is $O(p^3)$ (cubic complexity)

# # Second version (v2):

# Once we set $a,b$ and $p$, $c$ is already defined!

# In[4]:


def number_of_integer_right_triangles_v2(p):
    cnt = 0
    for a in range(1,p):
        for b in range(1,p):
            c = p - a - b
            if a < b and a*a + b*b == c*c:
                cnt += 1
    return cnt


# ### Analysis:
# 
# $(p-1)^2$ iterations.
# 
# The complexity is $O(p^2)$ (squared complexity)

# # Third version (v3):

# We require $a<b$, so just start $b$'s loop from $a+1$

# In[5]:


def number_of_integer_right_triangles_v3(p):
    cnt = 0
    for a in range(1,p):
        for b in range(a+1,p):
            c = p - a - b
            if a*a + b*b == c*c:
                cnt += 1
    return cnt


# ### Analysis:
# 
# The loop are now dependent, so the number of iterations is: $\sum_{a = 1}^{p-1} (p - (a+1)) = \frac{(p-1)(p-2)}{2}$
# 
# The complexity is again $O(p^2)$ (squared complexity)

# # Fourth version (v4):

# $a = p-b-c < p-2a \implies 3a < p$. Thus: $a < p/3$, that is, the maximal possible value of $a$ is $p//3$ (we add $1$ in order to include $p//3$ in the range).
# 
# $b = p-a-c < p-a-b  \implies 2b < (p-a)$. Thus: $b < (p-a)/2$, that is, the maximal possible value of $b$ is $(p-a)//2$ (we add 1 in order to include (p-a)//2 in the range).

# In[6]:


def number_of_integer_right_triangles_v4(p):
    cnt = 0
    for a in range(1,p//3 + 1):
        for b in range(a+1,(p-a)//2 + 1):
            c = p - a - b
            if a*a + b*b == c*c:
                cnt += 1
    return cnt


# ### Analysis:
# 
# The number of iterations is: $\sum_{a = 1}^{p/3} (\lfloor\frac{p-a}{2}\rfloor + 1 - (a+1))$
# 
# The complexity is again $O(p^2)$ (squared complexity)

# # Fifth version (v5):

# $a+b+c=p \implies c = p-a-b$. 
# 
# Substitute $c$ with $p-a-b$ in $a^2+b^2=c^2$ and isolate $b$ to get $b = \frac{p^2-2ap}{2(p-a)}$.
# 
# We don't even need to calculate c here!

# In[7]:


def number_of_integer_right_triangles_v5(p):
    cnt = 0
    for a in range(1,p//3 + 1):
        b = (p**2 - 2*a*p) / (2*(p-a))
        if b == int(b) and a < b:
            cnt += 1
    return cnt


# ### Analysis:
# 
# $\frac{p}{3}$ iterations.
# 
# The complexity is $O(p)$ (linear complexity)

# # Experiment:
# 
# For the input $p=240$: the runtimes rank: $v_1, v_2, v_3, v_4, v_5$.
# 
# Once we double the input to $p=480$, the increase in runtime for $v_1$ is quadric (i.e. the runtimes is $2^3 = 8$ times slower), for $v_2,v_3,v_4$ its squared (i.e. the runtimes are $2^2=4$ times slower), and for $v_5$ its doubled.

# In[9]:


import time

def elapsed(expression,number=1):
    ''' computes elapsed time for executing code
    number of times (default is 1 time). expression should
    be a string representing a Python expression. '''
    t1=time.clock()
    for i in range(number):
        x = eval(expression)
    t2=time.clock()
    return t2-t1


print("v1, p = 240 took",elapsed("number_of_integer_right_triangles_v1(240)"), "secs")
print("v2, p = 240 took",elapsed("number_of_integer_right_triangles_v2(240)"), "secs")
print("v3, p = 240 took",elapsed("number_of_integer_right_triangles_v3(240)"), "secs")
print("v4, p = 240 took",elapsed("number_of_integer_right_triangles_v4(240)"), "secs")
print("v5, p = 240 took",elapsed("number_of_integer_right_triangles_v5(240)"), "secs")
print("")
print("v1, p = 480 took",elapsed("number_of_integer_right_triangles_v1(480)"), "secs")
print("v2, p = 480 took",elapsed("number_of_integer_right_triangles_v2(480)"), "secs")
print("v3, p = 480 took",elapsed("number_of_integer_right_triangles_v3(480)"), "secs")
print("v4, p = 480 took",elapsed("number_of_integer_right_triangles_v4(480)"), "secs")
print("v5, p = 480 took",elapsed("number_of_integer_right_triangles_v5(480)"), "secs")


# # Big O notation
# 
# Given two functions $f(n)$ and $g(n)$,
# 
# $f(n) = O(g(n))$ 
#  If and only if there exist $c \geq 0 $ and $n_{0}\in \mathbb{R}$ such that
#  $\forall n>n_0$    
#    $|f(n)| \leq c\cdot|g(n)|$ 

# ### Time complexity hierarchy
#   
# Let $n$ denote the size of the input.
# The most common time complexities we encounter are :
# 
# * Constant - $O(1)$
# * Logarithmic - $O(\log(n))$
# * Root/fractional - $O(n^{1/c})$ for $c>1$
# * Linear - $O(n)$
# * Loglinear - $O(n \log(n))$
# * Polynomial - $O(n^{c})$ for $c>1$
# * Exponential - $O(c^{n})$ for $c>1$
# 
# See also this list on [Wikipedia](http://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities).

# ## Prove or Disprove examples
# See some examples [here](http://tau-cs1001-py.wdfiles.com/local--files/recitation-logs-2017a/complexity_prove_or_disprove.pdf)