# Naive approach
from sys import maxsize 
V = 4

def travellingSalesmanProblem(graph, s):  
    
    vertices = []                                          # store all verteces, but source vertex 
    for i in range(V): 
        if i != s: 
            vertices.append(i)  
    
    min_pathweight = maxsize                               # store min weight Hamiltonian Cycle
  
    while True:
         
        current_pathweight = 0                             # store current Path weight(cost)  
        
        k = s                                              # compute current path weight 
        for i in range(len(vertices)): 
            current_pathweight += graph[k][vertices[i]] 
            k = vertices[i] 
        current_pathweight += graph[k][s]  
        
        min_pathweight = min(min_pathweight, current_pathweight)       # update minimum 
  
        if not next_permutation(vertices): 
            break
  
    return min_pathweight 
  

def next_permutation(L): 
  
    n = len(L) 
  
    i = n - 2
    while i >= 0 and L[i] >= L[i + 1]: 
        i -= 1
  
    if i == -1: 
        return False
  
    j = i + 1
    while j < n and L[j] > L[i]: 
        j += 1
    j -= 1
  
    L[i], L[j] = L[j], L[i] 
  
    left = i + 1
    right = n - 1
  
    while left < right: 
        L[left], L[right] = L[right], L[left] 
        left += 1
        right -= 1
  
    return True
  
# Driver Code 
if __name__ == "__main__": 
  
    # matrix representation of graph 
    graph = [[0, 10, 15, 20], [10, 0, 35, 25],  
             [15, 35, 0, 30], [20, 25, 30, 0]] 
    s = 0
    print(travellingSalesmanProblem(graph, s)) 

# Dynamic approach: https://towardsdatascience.com/solving-tsp-using-dynamic-programming-2c77da86610d
def DP_TSP(distances_array):
    n = len(distances_array)
    all_points_set = set(range(n))

    # memo keys: tuple(sorted_points_in_path, last_point_in_path)
    # memo values: tuple(cost_thus_far, next_to_last_point_in_path)
    memo = {(tuple([i]), i): tuple([0, None]) for i in range(n)}
    queue = [(tuple([i]), i) for i in range(n)]

    while queue:
        prev_visited, prev_last_point = queue.pop(0)
        prev_dist, _ = memo[(prev_visited, prev_last_point)]

        to_visit = all_points_set.difference(set(prev_visited))
        for new_last_point in to_visit:
            new_visited = tuple(sorted(list(prev_visited) + [new_last_point]))
            new_dist = prev_dist + distances_array[prev_last_point][new_last_point]

            if (new_visited, new_last_point) not in memo:
                memo[(new_visited, new_last_point)] = (new_dist, prev_last_point)
                queue += [(new_visited, new_last_point)]
            else:
                if new_dist < memo[(new_visited, new_last_point)][0]:
                    memo[(new_visited, new_last_point)] = (new_dist, prev_last_point)

    optimal_path, optimal_cost = retrace_optimal_path(memo, n)

    return optimal_path, optimal_cost

def retrace_optimal_path(memo: dict, n: int) -> [[int], float]:
    points_to_retrace = tuple(range(n))

    full_path_memo = dict((k, v) for k, v in memo.items() if k[0] == points_to_retrace)
    path_key = min(full_path_memo.keys(), key=lambda x: full_path_memo[x][0])

    last_point = path_key[1]
    optimal_cost, next_to_last_point = memo[path_key]

    optimal_path = [last_point]
    points_to_retrace = tuple(sorted(set(points_to_retrace).difference({last_point})))

    while next_to_last_point is not None:
        last_point = next_to_last_point
        path_key = (points_to_retrace, last_point)
        _, next_to_last_point = memo[path_key]

        optimal_path = [last_point] + optimal_path
        points_to_retrace = tuple(sorted(set(points_to_retrace).difference({last_point})))

    return optimal_path, optimal_cost

import numpy as np

n = 5
X = np.random.rand(n, 2)
distances_array = np.array([[np.linalg.norm(X[i] - X[j])
                                 for i in range(n)]
                                for j in range(n)])
DP_TSP(distances_array)

# a naive recursive implementation; time c. O(2^n), space c. O(1)
def knapsack(W, wt, val, n):  
    
    if n == 0 or W == 0:                                                    # base case 
        return 0  
          
    if wt[n-1] > W:                                                         # if weight of the nth item > W, exclude nth item
        return knapsack(W, wt, val, n-1) 
  
    # return the maximum of two cases: 
    # (1) nth item included, (2) not included 
    else: 
        return max( val[n-1] + knapsack( W-wt[n-1], wt, val, n-1),  knapsack(W, wt, val, n-1))

val = [60, 100, 120]
wt = [10, 20, 30] 
W = 50
length_val = len(val) 
print(knapsack(W, wt, val, length_val))

# DP solution (memoization?)
# O(N*W) time and space
def knapSack(W, weights, values, n): 
    DP = [[0 for x in range(W + 1)] for x in range(n + 1)] 
  
    # Build table DP[][] in bottom up manner 
    for i in range(n + 1): 
        for w in range(W + 1): 
            if i == 0 or w == 0: 
                DP[i][w] = 0
            elif weights[i-1] <= w: 
                DP[i][w] = max(values[i-1] + DP[i-1][w - weights[i-1]],  DP[i-1][w]) 
            else: 
                DP[i][w] = DP[i-1][w] 
  
    return DP[n][W] 
  
values = [60, 100, 120] 
weights = [10, 20, 30] 
W = 50
print(knapSack(W, weights, values, len(values)))

# Recursion + memoization solution  
# returns max value to fit in knapsack of capacity W
# O(N*W) time and space  
def knapsack(weights, values, W, length):     
  
    # base conditions 
    if length == 0 or W == 0: 
        return 0
    if DP[length][W] != -1: 
        return DP[length][W] 
  
    # choice diagram code 
    if wt[length - 1] <= W: 
        DP[length][W] = max( values[length-1] + knapsack( weights, values, W - wt[length-1], length-1),
                            knapsack(weights, values, W, length - 1)) 
        return DP[length][W] 
    elif wt[length - 1] > W: 
        DP[length][W] = knapsack(weights, values, W, length-1) 
        return DP[length][W]
    

values = [60, 100, 120] 
weights = [10, 20, 30] 
W = 50
length = len(val) 
  
# initialize the matrix with -1 at first 
DP = [[-1 for i in range(W + 1)] for j in range(length + 1)]

print(knapsack(weights, values, W, length)) 

# recursive, non-optimized
def rec_coin(target, coins):
    '''
    Target: change amount
    Coins: list of coin values
    '''    
    
    min_coins = target                                    # default to target value
    if target in coins:                                   # base case - check if we have a single coin match
        return 1
    
    else:       
        for i in [c for c in coins if c <= target]:       # for each coin value <= target
            num_coins = 1 + rec_coin(target-i,coins)      # recursive call
            
            if num_coins < min_coins:                     # reset min if we have new min
                min_coins = num_coins
                
    return min_coins

rec_coin(63,[1,5,10,25])

# using memoization or caching
def rec_coin_dynam(target, coins, known_results):
    '''
    Target: change amount
    Coins: list of coin values
    Known_results: previous results    
    '''
        
    min_coins = target                                      # default to target value
    
    if target in coins:                                     # base case 1 - check if we have a single coin match
        known_results[target] = 1
        return 1    
    elif known_results[target] > 0:                         # base case 2 - if this value was already calculated before
        return known_results[target]
    
    else:        
        for i in [c for c in coins if c <= target]:            
            num_coins = 1 + rec_coin_dynam(target-i, coins, known_results)
                        
            if num_coins < min_coins:
                min_coins = num_coins                       # reset min if we have new min
                known_results[target] = min_coins           # reset the known result
                
    return min_coins

target = 74
coins = [1,5,10,25]
known_results = [0]*(target+1)        #why?

rec_coin_dynam(target, coins, known_results)

# dynamic solution explained at https://runestone.academy/runestone/books/published/pythonds/Recursion/DynamicProgramming.html
def coin_dynam(coinValueList, change, minCoins, coinsUsed):
    for cents in range(change+1):
        coinCount = cents
        newCoin = 1
        for j in [c for c in coinValueList if c <= cents]:
            if minCoins[cents-j] + 1 < coinCount:
                coinCount = minCoins[cents-j]+1
                newCoin = j
        minCoins[cents] = coinCount
        coinsUsed[cents] = newCoin
    return minCoins[change]

def printCoins(coinsUsed, change):
    coin = change
    while coin > 0:
        thisCoin = coinsUsed[coin]
        print(thisCoin, end=', ')
        coin = coin - thisCoin

amnt = 63
coin_list = [1,5,10,21,25]
coinsUsed = [0]*(amnt+1)
coinCount = [0]*(amnt+1)

print("Making change for",amnt,"requires")
print(coin_dynam(coin_list, amnt, coinCount, coinsUsed), "coins")
print("They are:")
printCoins(coinsUsed, amnt)
print("\nThe used list is as follows:")
print(coinsUsed)

def printCountDP(dist): 
    count = [0] * (dist + 1) 
      
    # Initialize base values - one way to cover 0 and 1 distances; two ways to cover 2 distance
    count[0] = 1
    count[1] = 1
    count[2] = 2
      
    # Fill the count array in bottom up manner 
    for i in range(3, dist + 1):
        count[i] = (count[i-1] + count[i-2] + count[i-3])
          
    return count[dist]; 
  

dist = 100
print( printCountDP(dist)) 

# example - factorial
def fact(n):
    '''
    Returns n!
    '''    
    if n == 0:                   # BASE CASE!
        return 1    
    else:                        # Recursion!
        return n * fact(n-1)
        
fact(5)

# example - sum from 0 to n
def rec_sum(n):    
    
    if n == 0:                    # Base Case
        return 0    
    else:                         # Recursion
        return n + rec_sum(n-1)
    
rec_sum(100)

# example - sum of all indiv digits of n
def sum_func(n):
    
    if len(str(n)) == 1:                  # Base case
        return n    
    else:                                 # Recursion
        return n%10 + sum_func(n//10)
    
sum_func(4321)

# example - split a phrase into words
def word_split(phrase, list_of_words, output=None):
    '''
    Parameters:
        phrase: string phrase
        list_of_words: list of words
    Returns:
        string split with words from list_of_words
    ''' 
    
    # Checks if output initiated; if default output=[], it will be overwritten in every recursion!
    if output is None:
        output = []
        
    for word in list_of_words:
                
        if phrase.startswith(word):                        
            output.append(word)                        
            return word_split(phrase[len(word):], list_of_words, output)        # recursion - pass along the output
    
    # return output if no phrase.startswith(word) is True
    return output        

print(word_split('themanran',['the','ran','man']))
print(word_split('ilovedogsJohn',['i','am','a','dogs','lover','love','John']))
print(word_split('themanran',['clown','ran','man']))

# Create cache for known results
def factorial(n):    
    if n < 2: 
        return 1    
    if not n in memo:
        memo[n] = n*factorial(n-1)        
    return memo[n]

memo = {}
factorial(5)

class Memoize:
    def __init__(self, f):
        self.f = f
        self.memo = {}
    def __call__(self, *args):
        if not args in self.memo:
            self.memo[args] = self.f(*args)
        return self.memo[args]

def factorial(n):    
    if n < 2: 
        return 1    
    return n * factorial(n-1)

factorial = Memoize(factorial)
factorial(5)

# recursive - exponential time O(2^n)
def fib_rec(n):    
    if n == 0 or n == 1:                                # basea case
        return n    
    else:
        return fib_rec(n-1) + fib_rec(n-2)

for i in range(40):
    print(fib_rec(i), end=', ')

# dynamic - cache is set beforehand based on n
# checking if cache[n] != None means checking to know if we should keep setting cache (keep cache of old results!)
def fib_dyn(n):    
    
    if n == 0 or n == 1:                             # base case
        return n    
    
    if cache[n] != None:                             # check cache
        return cache[n]    
    
    cache[n] = fib_dyn(n-1) + fib_dyn(n-2)           # keep setting cache
    
    return cache[n]

# instantiate cache
for i in range(40):
    n = i
    cache = [None] * (n + 1)

    print(fib_dyn(n), end=', ')

# iterative - tuple unpacking!
def fib_iter(n):
        
    a = 0
    b = 1
        
    for i in range(n):        
        a, b = b, a + b
        
    return a

for i in range(40):
    print(fib_iter(i), end=', ')