#AI ALGORISMS

#1-BFS

#declaring the graph as a dictionary
graph = {
  'S' : [ 'A','B','D'],
  'A' : ['C'],
  'B' : ['D'],
  'C' : ['D','G'],
  'D' : ['G'],
  'G' : []
}
def bfs(graph, start, goal):
    #create a list to store the visited nodes and a queue to store the nodes
    visited = []
    queue = [[start]]

    #loop through the queue if it's not empty
    while queue:
        path = queue.pop(0) #remove from the left
        node = path[-1]

        if node == visited:
            continue
        visited.append(node)
        if node == goal:
            return path
        else:
            adjacent_nodes = graph.get(node, [])
            for adjacent_node in adjacent_nodes:
                new_path = path.copy()
                new_path.append(adjacent_node)
                queue.append(new_path)
    return print("The queue is empty, no solution found.")

solution = bfs(graph,'S','G')
print('Solution is ' , solution)


#2-DFS

#declaring the graph as a dictionary
graph = {
  'S' : [ 'A','B','D'],
  'A' : ['C'],
  'B' : ['D'],
  'C' : ['D','G'],
  'D' : ['G'],
  'G' : []
}
def dfs(graph, start, goal):
    #create a list to store the visited nodes and a stack to store the nodes
    visited = []
    stack = [[start]]

    #loop through the stack if it's not empty
    while stack:
        path = stack.pop() #remove from the right
        node = path[-1]

        if node == visited:
            continue
        visited.append(node)
        if node == goal:
            return path
        else:
            adjacent_nodes = graph.get(node, [])
            for adjacent_node in adjacent_nodes:
                new_path = path.copy()
                new_path.append(adjacent_node)
                stack.append(new_path)
    return print("The stack is empty, no path found.")

solution = dfs(graph,'S','G')
print('Solution is ' , solution)


#3-AlphaBeta
import math

def alpha_beta_minimax(cd, node, alpha, beta, maxt, scr, td):
    if cd == td:
        return scr[node]
    if maxt:
        v = -math.inf
        for child in [node*2, node*2+1]:
            v = max(v, alpha_beta_minimax(cd+1, child, alpha, beta, False, scr, td))
            alpha = max(alpha, v)
            if alpha >= beta:
                break
        return v
    else:
        v = math.inf
        for child in [node*2, node*2+1]:
            v = min(v, alpha_beta_minimax(cd+1, child, alpha, beta, True, scr, td))
            beta = min(beta, v)
            if alpha >= beta:
                break
        return v

scr = []
x = int(input('Enter Total Number of leaf nodes: '))
for i in range(x):
    y = int(input('Enter leaf value: '))
    scr.append(y)

td = math.log(len(scr), 2)
cd = int(input('Enter current depth value: '))
nodev = int(input('Enter node value: '))
alpha = -math.inf
beta = math.inf
maxt = True


answer = alpha_beta_minimax(cd, nodev, alpha, beta, maxt, scr, td)
print('The answer is: ',answer)

#4-GBS

#NOTE that Gready_best_search depends on H_cost only
graph={
    'S':[('A',1),('B',4)],
    'A':[('B',2),('C',5),('G',12)],
    'B':[('C',2)],
    'C':[('G',3)]
}
# The hurestic of each node
H_table={
    'S':7,
    'A':6,
    'B':4,
    'C':2,
    'G':0
}
#To calculate the H_cost of any path
def path_h_cost(path):
    for (node,cost) in path:
       last_node = path[-1][0] #C
       h_cost = H_table[last_node] #2
    return h_cost , last_node

#to check the path_h_cost function
# path=[('S', 0), ('A', 1), ('C', 5)]
# print(path_f_cost (path))
#SOLUTION = (2 , C)

def gready_best_search(graph, start, goal):

    visited=[]
    queue=[[(start,0)]]

    while queue:

        queue.sort(key=path_h_cost) #sorting by least f-cost
        path = queue.pop(0) #pop from left
        node = path[-1][0]
        if node in visited:
            continue
        visited.append(node)
        if node == goal:
             return path
        else:
            adjacent_nodes = graph.get(node,[])
            for (adjacent_node,cost) in adjacent_nodes:
                new_path =path.copy()
                new_path.append((adjacent_node, cost))
                queue.append(new_path)


solution= gready_best_search(graph, 'S', 'G')
print('Solution is : ', solution)
solution_path = [node for (node,_) in solution] #_ to ignore the cost of nodes
print('The path of Solution : ', solution_path)
print('H_cost of solution is', path_h_cost(solution)[0])

#5-A*
#NOTE that a* depends on F_cost = G_cost + H_cost

graph={
    'S':[('A',1),('B',4)],
    'A':[('B',2),('C',5),('G',12)],
    'B':[('C',2)],
    'C':[('G',3)]
}
# The hurestic of each node
H_table={
    'S':7,
    'A':6,
    'B':4,
    'C':2,
    'G':0
}

#To calculate the F_cost of any path
def path_f_cost(path):
    g_cost= 0
    for (node,cost) in path:
        g_cost += cost
    last_node = path[-1][0] #C
    h_cost = H_table[last_node] #2
    f_cost = g_cost + h_cost
    return f_cost , last_node

#to check the path_f_cost function
# path=[('S', 0), ('A', 1), ('C', 5)]
# print(path_f_cost (path))
#SOLUTION = (8 , C)

def a_star_search(graph, start, goal):

    visited=[]
    queue=[[(start,0)]]

    while queue:

        queue.sort(key=path_f_cost) #sorting by least f-cost
        path = queue.pop(0) #pop from left
        node = path[-1][0]
        if node in visited:
            continue
        visited.append(node)
        if node == goal:
             return path
        else:
            adjacent_nodes = graph.get(node,[])
            for (adjacent_node,cost) in adjacent_nodes:
                new_path =path.copy()
                new_path.append((adjacent_node, cost))
                queue.append(new_path)


solution= a_star_search(graph, 'S', 'G')
print('Solution is : ', solution)
solution_path = [node for (node,_) in solution] #_ to ignore the cost of nodes
print('The path of Solution : ', solution_path)
print('F_cost of solution is', path_f_cost(solution)[0])

#6-UCS

#NOTE that Uniform_cost_search depends on G_cost of path

#create a function to calculate path_cost
def path_cost(path):
    total_cost = 0
    for (node , cost) in path:
        total_cost += cost
    return total_cost , path[-1][0]

#declaring the graph as a dictionary with it's cost
graph = {
  'S' : [ ('A',2),('B',3),('D',5)],
  'A' : [('C',4)],
  'B' : [('D',4)],
  'C' : [('D',1),('G',2)],
  'D' : [('G',5)],
  'G' : []
}
def ucs(graph, start, goal):
    #create a list to store the visited nodes and a queue to store the nodes
    visited = []
    queue = [[(start,0)]]

    #loop through the queue if it's not empty
    while queue:
        queue.sort(key=path_cost) #sorting by lowest path_cost
        path = queue.pop(0)
        node = path[-1][0]

        if node in visited:
            continue
        visited.append(node)
        if node == goal:
            return path
        else:
            adjacent_nodes = graph.get(node, [])
            for (adjacent_node,cost) in adjacent_nodes:
                new_path = path.copy()
                new_path.append((adjacent_node,cost))
                queue.append(new_path)
    return print("The queue is empty, no solution found.")

solution = ucs(graph,'S','G')
print('Solution is ' , solution)
print('Cost of solution is ' , path_cost(solution)[0])

#7-MinMax

import math
def Minmax(cd,node,maxt,scr,td):
    if(cd==td):
        return scr[node]
    if(maxt):
        return max(Minmax(cd+1,node*2,False,scr,td),Minmax(cd+1,node*2+1,False,scr,td))
    else:
        return min(Minmax(cd+1,node*2,True,scr,td),Minmax(cd+1,node*2+1,True,scr,td))


scr=[]
x=int(input('Enter Total Nymber of leaf node= '))
for i in range (x):
    y=int(input('Enter leaf value: '))
    scr.append(y)



td=math.log(len(scr),2)
cd=int(input('Enter current depth value: '))
nodev=int(input('Enter node value: '))
maxt=True
print('The answer is : ',end=" ")
answer=Minmax(cd,nodev,maxt,scr,td)
print(answer)