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

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

# ## Exam recitation
# 
# We went over various questions from previous exams

# ###### Takeaways:
# - The exam is easy, all you have to do is write down the correct answers
# - When in doubt, bet on 42

# #### Code for printing several outputs in one cell (not part of the recitation):

# In[ ]:


from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"


# ## 2019AA1: Linked Lists

# A doubly linked list is similar to a linked list, the difference being that:
# - Each node has a next field (pointing forward) and a prev field (pointing backwards)
# - The list contains a head field (pointing to the first node) and a tail field (pointing to the last field)

# In[ ]:


class Node():

    def __init__(self, val):
        self.value = val
        self.next = None
        self.prev = None

class DLList():
    def __init__(self, lst=None):
        self.head = None
        self.tail = None
        self.len = 0
        if lst != None:
            for item in lst:
                self.insert(item)
                
    def __len__(self):
        return self.len
    
    def __repr__(self):
        n = len(self)
        s = "["
        node = self.head
        for i in range(n):
            s += str(node.value)+", "
            node = node.next
        if len(s) > 1:
            s = s[:-2] + "]"
        else:
            s += "]"
        return s
        


# Implement the insert method. The input is $val$ and $first$ a boolean parameter. If $first==True$ insert at head, else insert at tail.
# 
# Runtime and memory usage should be $O(1)$.
# 
# The idea is that there are three cases:
# - If the list is empty the head and tail should be the new node
# - Otherwise, if $first == True$ we should place the new node at the front of the list and change existing head
# - Finally, if $first == False$ we should do the same for the tail
# 

# In[ ]:


class Node():

    def __init__(self, val):
        self.value = val
        self.next = None
        self.prev = None

class DLList():
    def __init__(self, lst=None):
        self.head = None
        self.tail = None
        self.len = 0
        if lst != None:
            for item in lst:
                self.insert(item)
                
    def __len__(self):
        return self.len
    
    def __repr__(self):
        n = len(self)
        s = "["
        node = self.head
        for i in range(n):
            s += str(node.value)+", "
            node = node.next
        if len(s) > 1:
            s = s[:-2] + "]"
        else:
            s += "]"
        return s
    
    def insert(self, val, first=False):
        node = Node(val)
        if len(self) == 0:
            self.head = self.tail = node
        elif first:
            tmp = self.head
            self.head = node
            self.head.next = tmp
            tmp.prev = self.head
        else:
            tmp = self.tail
            self.tail = node
            self.tail.prev = tmp
            tmp.next = self.tail
        self.len += 1
            
        


# Implement the rotate method. Given $0 \leq k < n$, the $i$th node of the list will change place and become the $(i+k)~\%~n$ node.
# 
# Runtime should be $O(\textrm{min}(k, n-k))$, memory usage should be $O(\log n)$ and the method should work in place.
# 

# In[ ]:


class Node():

    def __init__(self, val):
        self.value = val
        self.next = None
        self.prev = None

class DLList():
    def __init__(self, lst=None):
        self.head = None
        self.tail = None
        self.len = 0
        if lst != None:
            for item in lst:
                self.insert(item)
                
    def __len__(self):
        return self.len
    
    def __repr__(self):
        n = len(self)
        s = "["
        node = self.head
        for i in range(n):
            s += str(node.value)+", "
            node = node.next
        if len(s) > 1:
            s = s[:-2] + "]"
        else:
            s += "]"
        return s
    
    def insert(self, val, first=False):
        node = Node(val)
        if len(self) == 0:
            self.head = self.tail = node
        elif first:
            tmp = self.head
            self.head = node
            self.head.next = tmp
            tmp.prev = self.head
        else:
            tmp = self.tail
            self.tail = node
            self.tail.prev = tmp
            tmp.next = self.tail
        self.len += 1
            
    def rotate(self, k):
        fwd = True
        shift = k
        if k > len(self) - k:
            shift = len(self) - k
            fwd = False
        self.head.prev = self.tail
        self.tail.next = self.head
        node = self.head
        for i in range(shift):
            if fwd:
                node = node.prev
            else:
                node = node.next
        self.head = node
        self.tail = node.prev
        self.head.prev = None
        self.tail.next = None


# ### Testing

# In[ ]:


L = DLList([i for i in range(10)])
print(L)
L.rotate(2)
print(L)


# ## 2018AA5: Rotating trees
# 
# Given two BSTs $T,S$ we say that $T$ and $S$ are equivalent if they are the same up to a sequence of switching between left and right sons of some of the nodes in the trees. 
# 
# The following trees are equivalent:
# 
# ![title](equiv1.png)
# 
# But they are not equivalent to this tree:
# 
# ![title](equiv2.png)
# 
# Implement $equiv(r1, r2)$ which gets two root nodes $r1, r2$ and return $True$ iff they represent roots of equivalent trees. The function should be recursive.
# 
# The idea is:
# - Two leaves are equivalent if their key and value are equivalent
# - Two trees are equivalent if:
#     - Their roots agree on their keys and values
#     - Their left sons $L1, L2$ and right sons $R1,R2$ are equivalent, or $L1, R2$ and $L2, R1$ are equivlanet

# In[ ]:


class Tree_node():
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.left = None
        self.right = None

    def __repr__(self):
        return "(" + str(self.key) + ":" + str(self.val) + ")"

    def __eq__(self,other):
        if other==None:
            return False
        if self.key==other.key and self.val==other.val:
            return True
        else:
            return False    
        
class Binary_search_tree():

    def __init__(self):
        self.root = None


    def __repr__(self): #no need to understand the implementation of this one
        out = ""
        for row in printree(self.root): #need printree.py file
            out = out + row + "\n"
        return out


    def lookup(self, key):
        ''' return node with key, uses recursion '''

        def lookup_rec(node, key):
            if node == None:
                return None
            elif key == node.key:
                return node
            elif key < node.key:
                return lookup_rec(node.left, key)
            else:
                return lookup_rec(node.right, key)

        return lookup_rec(self.root, key)



    def insert(self, key, val):
        ''' insert node with key,val into tree, uses recursion '''

        def insert_rec(node, key, val):
            if key == node.key:
                node.val = val     # update the val for this key
            elif key < node.key:
                if node.left == None:
                    node.left = Tree_node(key, val)
                else:
                    insert_rec(node.left, key, val)
            else: #key > node.key:
                if node.right == None:
                    node.right = Tree_node(key, val)
                else:
                    insert_rec(node.right, key, val)
            return
        
        if self.root == None: #empty tree
            self.root = Tree_node(key, val)
        else:
            insert_rec(self.root, key, val)

def equiv(node1, node2):
    if node1 == node2 == None:
        return True
    if node1 == None or node2 == None or node1 != node2:
        return False
    no_switch = equiv(node1.left, node2.left) and equiv(node1.right, node2.right)
    switch = equiv(node1.left, node2.right) and equiv(node1.right, node2.left)
    return switch or no_switch


# ### Testing

# In[ ]:


T1 = Binary_search_tree()
T1.insert(1,1)
T1.root.left = Tree_node(2,2)
T1.root.right = Tree_node(3,3)
T1.root.left.left = Tree_node(4,4)

T2 = Binary_search_tree()
T2.insert(1,1)
T2.root.left = Tree_node(3,3)
T2.root.right = Tree_node(2,2)
T2.root.right.left = Tree_node(4,4)

T3 = Binary_search_tree()
T3.insert(1,1)
T3.root.left = Tree_node(3,3)
T3.root.right = Tree_node(2,2)
T3.root.left.left = Tree_node(4,4)

equiv(T1.root,T2.root)
equiv(T1.root,T3.root)
#k = Tree_node(1,1)
#p = Tree_node(1,1)
#k == p


# Can memoization help? Not really, since subtrees can be disjoint, we will never reach a tree we've already examined.

# Next, given two roots of $T1,T2$ determine if there exists a non-empty subtree of $T1$ equivalent to a subtree of $T2$.
# 
# The idea
# - If the two roots are equivalent (and not empty) we are done
# - If one of the roots is $None$, we are done
# - Otherwise:
#     - There may be a subtree of $T2$ equivalent to $T1$
#     - Or a subtree of $T1$ equivalent to $T2$

# In[ ]:


def subequiv(node1, node2):
    if equiv(node1, node2) and node1 != None:
        return True
    if node1 == None or node2 == None:
        return False
    t1_stays = subequiv(node1, node2.left) or subequiv(node1, node2.right)
    t2_stays = subequiv(node1.left, node2) or subequiv(node1.right, node2)
    return t1_stays or t2_stays


# In[ ]:


subequiv(T1.root,T2.root)
T4 = Binary_search_tree()
T4.insert(100,100)
T4.root.left = T2.root
subequiv(T4.root, T2.root)

# Since they share leaves
subequiv(T2.root, T3.root)


# ## 2018BB5: Hashing
# 
# For each of the following hash functions for tuples give 2 tuples of integers of length $\geq 3$ (same length for both tuples) that collide.

# Possible solutions:
# 
# - Since $hash1$ is dependant on values and parities we can simply mix lists while maintaining parity of positions, e.g.: $$(3, 2, 5), (5, 2, 3)$$
# - For $hash2$ if the tuples have length $3$ then $hash2(t) = t[0] + 2t[1]+4t[2]$. We can take any $t1$ and place all the weight of $t2$ on the first entry, e.g.: $$(1,1,1), (7,0,0)$$
# - For $hash3$, each entry is mapped to its integer value when represented in binary (e.g. - $5 \to 101$). We can get the value of $4 \to 100$ by summing 10 entries of $2 \to 10$, so a possible solution is (note that this is not proper python code):
# $$(2 \text{ for i in } range(10)),(4, 0 \text{ for i in } range(9))$$

# In[ ]:


hash1 = lambda t : sum([(-1)**i * t[i] for i in range(len(t))])

hash2 = lambda t : sum([2**i * t[i] for i in range(len(t))]) 

hash3 = lambda t : sum(int(bin(t[i])[2:]) for i in range(len(t))) 


# In[ ]:


hash1((3,2,5))
hash1((5,2,3))


# In[ ]:


hash2((1,1,1))
hash2((7,0,0))


# In[ ]:


hash3([2 for i in range(10)])
hash3([4] + [0 for i in range(9)])


# Given a list $L$ of $n$ tuples of length $2$ we say that $L$ is symmetric if $(a,b) \in L \implies (b,a) \in L$.
# 
# Implement $issym$ which gets $L$ as input and returns $True$ iff $L$ is symmetric. The function should run in time $O(n)$ on average.
# 
# The idea: we create a set from $L$ and then simply iterate over $L$ and check if each opposite member is in the set.

# In[ ]:


def issym(L):
    n = len(L)
    s = set(L)
    for i in range(n):
        (a,b) = L[i]
        if (b,a) not in s:
            return False
    return True

issym([(1,2), (2,1), (3,3)])

issym([(1,2), (2,1), (3,3), (4,3)])


# ## 2017AA2: Profit
# 
# Given $n$ and a list of integers $values$ of length $n$, we we will think of a landlord that has an apartment of size $n$ square meters. The landlord can divide his apartment into smaller subapartments and an apartment of size $k \leq n$ will yield a rent of $value[k-1]$ dollars.
# 
# E.g., for $n = 4, values=[1,5,8,9]$ we can have:
# - One apartment of size $4$ renting at $9$ dollars
# - Two apartments of size $1$ and one of size $2$ renting at $1+1+5=7$ dollars
# - And so on...
# 
# Our goal is to find a partition which maximizes the landlords profit. Our solution needs to be recursive and **use no loops**.
# 
# The idea:
# - If we don't have any space, or we don't have any partitions available, we make 0 dollars
# - If we have 1 meter, we make $value[0]$
# - Otherwise, say the length of $len(value)$ is $i$:
#     - If we can make an apartment of size $i$, i.e. $i \leq size$ then we profit $value[i-1]$ and we need to split $size - i$ meters
#     - Otherwise, we can shorten the length of $len(value)$ to $i-1$ and we still need to split $size$
# - We compute both of the above and take the max between them

# In[ ]:


def profit(value, size):
    n = len(value)
    return profit_rec(value, n, size)

def profit_rec(value, i, size):
    if size == 0 or i == 0:
        return 0
    if size == 1:
        return value[0]
    
    with_last = 0
    if i <= size:
        with_last = profit_rec(value, i, size - i)+value[i-1]
        
    without_last = profit_rec(value, i - 1, size)
    return max(with_last, without_last)

profit([1, 5, 8, 9], 4)
profit([2, 3, 7, 8, 9], 5)
    


# ## 2017AB2: Jump
# 
# Given a list $lst$ of $n$ integers where $lst[0]=0$ we want to get to $lst[n-1]$ by jumping to the right (i.e. - advancing in the list). 
# 
# We init a counter $cnt=0$ and if we add $lst[i]$ to the counter for every index $i$ we visit.
# 
# Implement $jump$ which gets a list as described above and returns the minimal total penalty.
# 
# The idea: We must visit $lst[-1]$ and we should visit any index $i$ s.t. $lst[i] < 0$.

# In[ ]:


def jump(lst):
    # Note the range!
    return lst[-1] + sum(lst[i] for i in range(len(lst)-1) if lst[i] < 0)

jump([0,4,5,1,2,-3,-5])

jump([0,4,5,1,2,-3,2])


# Jump limited - we now get a parameter $max\_jump$ and we can now advance only $1 \leq i \leq max\_jump$ steps in each move.
# 
# Implement $jump\_rec$ without splicing.

# In[ ]:


def jump_lim(lst, max_jump):
    return jump_rec(lst, max_jump, 0)

def jump_rec(lst, max_jump, ind):
    if ind == len(lst) - 1:
        return lst[ind]
    cnt = float("inf")
    for j in range(1, max_jump + 1):
        if ind+j < len(lst):
            res = jump_rec(lst, max_jump, ind+j) + lst[ind]
        if res < cnt:
            cnt = res
    return cnt
        
jump_lim([0,4,5,1,2,-3,2], 100)
jump_lim([0, 2, 2, 0, 4], 3)


# Add memoization:

# In[ ]:


def jump_lim(lst, max_jump):
    d = {}
    return jump_rec_mem(lst, max_jump, 0, d)

def jump_rec_mem(lst, max_jump, ind, d):
    if ind == len(lst) - 1:
        return lst[ind]
    if ind in d:
        return d[ind]
    
    cnt = float("inf")
    for j in range(1, max_jump + 1):
        if ind+j < len(lst):
            res = jump_rec_mem(lst, max_jump, ind+j, d) + lst[ind]
        if res < cnt:
            cnt = res
    d[ind] = cnt
    return cnt
        
jump_lim([0,4,5,1,2,-3,2], 100)
jump_lim([0, 2, 2, 0, 4], 3)


# ## 2017BA4b: Rotated strings
# 
# We say that two strings of lengthh $n$, $s,t$ are rotated if there exists and $0 \leq i \leq n$ such that:
# $$s == t[i:n] + t[0:i]$$
# 
# I.e., $introtocs$ is a rotation of $tocsintro$ and of $rotocsint$ but not of $introcsto$.
# 
# Implement $is_rot$ which gets two strings and return $True$ iff they are rotated.
# 
# The function should work in $O(n)$ and is allowed a small chance of error.
# 
# Use $fingerprint, fingerprint\_text$ we've seen when discussing KR.

# In[ ]:


def is_rot(s, t):
    n = len(s)
    if n != len(t):
        return False
    fp = fingerprint(s)
    t = t+t
    fp_list = substring_fingerprints(t, n)
    for i in range(n):
        if fp == fp_list[i]:
            return True
    return False

def fingerprint(string,  basis=2**16, r=2**32-3):
    """ used to computes karp-rabin fingerprint of the pattern
        and of the first substring in the text
        employs Horner method (modulo r) """
    s = 0
    for ch in string:
        s = (s*basis + ord(ch)) % r # Horner
    return s

def substring_fingerprints(string, m,  basis=2**16, r=2**32-3):
    """ return a list of all fingerprints of size m windows in string """
    fp_list = []
    b_power = pow(basis, m-1, r)

    # compute first fingerprint
    fp_list.append(fingerprint(string[0:m], basis, r))

    # compute f_list[s], based on f_list[s-1]
    for s in range(1,len(string)-m+1): # O(n-m-1), each iteration O(1)
        next_fingerprint = \
                ((fp_list[s-1] - ord(string[s-1])*b_power) * basis \
                              + ord(string[s+m-1])) % r
        fp_list.append(next_fingerprint)

    return fp_list

is_rot("introtocs", "introtocs")

is_rot("introtocs", "tocsintro")

is_rot("introtocs", "introtosc")



# ## 2019AB2: Matching strings
# Given a list of strings $strlst$ and a string $word$ we say we can construct $word$ from $strlst$ if we can pick at most 1 char from each string in the list that yield $word$.
# 
# For example, we can construct "Raz" from $["abc", "FOR", "buzz"]$ and also from $["abc", "FOR", "aaa", "buzz", "hello"]$ but not from $["az", "FOR", "jkl"]$
# 
# Implement the recursive $construct\_rec$. The idea is that we maintain an index $j$ s.t. we need to construct $word[j:]$ from the list of strings.
# - If $j==len(word)$ we are done.
# - Otherwise, we go over the list, for each string we check if it contains $word[j]$ and if so we recurse on $j+1$ and ommit that string from the list
# - If we exit the loop without success, we return $False$

# In[ ]:


def construct(str_list, word):
    if len(str_list) < len(word):
        return False
    return construct_rec(str_list, word, 0)

def construct_rec(str_list, word, j):
    if j == len(word):
        return True
    for i in range(len(str_list)):
        if word[j] in str_list[i]:
            if construct_rec(str_list[:i]+str_list[i+1:], word, j+1):
                return True
    return False
            
construct(["abc", "FOR", "buzz"], "Raz")    
construct(["az", "FOR", "jkl"], "Raz")    
construct(["az", "FOR", "hello","a"], "Raz")


# Now we need to solve a variant where the order of the strings we take must agree with the order of characters in $word$.
# 
# E.g., now we can no longer construct "Raz" from $["abc", "FOR", "buzz"]$ but we can from $["FOR", "abc", "jkl", "buzz"]$.
# 
# The new solution should run in time $O(n)$ where $n$ is the length fo the string list.
# 
# The idea: we can now be greedy. Whenever we can take a certain string we should, because we will not be able to take it from characters later on.

# In[ ]:


def construct_order(str_list, word):
    i = 0
    j = 0
    while i < len(word) and j < len(str_list):
        if word[i] in str_list[j]:
            i += 1
        j += 1
        
        if i == len(word):
            return True
        
    return False
        
            
construct_order(["abc", "FOR", "buzz"], "Raz")    
construct_order(["FOR", "abc", "buzz"], "Raz")