Simple Hill Climbing Algorithm (Heuristic +1 -1)  ----------------------------------------------------------------------

from copy import deepcopy as dc
def heuristic(state,goal): 
    val = 0                 # heuristic value to return at end
    for ps in state:        # loop through all pairs in state
        for pg in goal:     # loop through all pair in goal state
            if(ps[1] == pg[1]):
                if(ps[0] == pg[0]):   # if block on correct block +1 val
                    val +=1
                else:
                    val -= 1                # else -1 val
                break
    return val


def get_top_blocks(state):  # return name of block which can be moved
    top = ['A', 'B', 'C', 'D']
    for p in state:
        if p[0] in top:
            top.remove(p[0])
    return top


def update(state, entry):   # add new pos of block specified by entry and remove previous position
    for i in range(len(state)):
        if state[i][1] == entry[1]:
            state[i] = entry
            return


def move(init, goal):       # produce steps and return one with more heuristic value then init state
    state = dc(init)
    heu = heuristic(init, goal)
    top = get_top_blocks(state)
    # n^2 moves n = len(top)
    for i in range(len(top)):
        for j in range(len(top)):
            if i == j:  # place ith block on ground
                update(state, (None, top[i]))
                if heuristic(state, goal) > heu:
                    return state
                state = dc(init)
            else:  # place the ith block on top of jth block
                update(state, (top[j], top[i]))
                if heuristic(state, goal) > heu:
                    return state
                state = dc(init)
    return None  # if no better state found return none to show failure of simple hill climb


def print_state(state):     # print state array as list of tuple rather than user defined class pair
    for p in state:
        print((p[0], p[1]), end=', ')
    print()


def solve(init, goal):      # try solving blocks world problem using simple hill climb 
    steps = 0
    #creating the deep copy
    state = dc(init)
    while state is not None:
        print_state(state)
        if heuristic(state, goal) == len(state):
            print('Hill Climb Successful')
            print('Steps taken:', steps)
            return
        else:
            state = move(state, goal)
        steps += 1
    print('Hill Climb Unsuccessful!')
    return


if __name__ == '__main__':
    init = [(None, 'B'), ('B', 'C'), ('C', 'D'), ('D', 'A')]
    goal = [(None, 'A'), ('A', 'B'), ('B', 'C'), ('C', 'D')]
    solve(init, goal)

 

--------------------------------------------------------------------------------------------------------------------------------------------------------------------Simple Hill Climbing Algorithm (Heuristic +n -n)  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------



from copy import deepcopy as dc

def state_level_map(state):
    level_map = {-1: [None] ,0:[],1:[],2:[],3:[]}
    for i in range(4):
        if(len(level_map[i-1])==0):
            break
        for p in state:
            if p[1] in level_map[i-1]:
                level_map[i].append(p[0])
    return level_map

def get_below(state,block):
    if(block == None):
        return None
    for p in state:
        if(p[0] == block):
            return p[1]

def heuristic(state,goal):
    state_level  = state_level_map(state)
    goal_level = state_level_map(goal)
    val = 0
    for i in range(1,len(state)):
        if(len(state_level[i])>0 and len(goal_level[i])>0):
            for block in state_level[i]:
                if block in goal_level[i]:
                    bi = block
                    bg = bi
                    add = True
                    for k in range(i,0,-1):
                        bi = get_below(state,bi)
                        bg = get_below(goal,bg)
                        if(bi!=bg):
                           val -= i
                           add = False
                           break
                    if(add):
                        val += i
                else:
                    val -= i
        elif(len(state_level[i])!= 0):
            val -= i
        else:
            return val
    return val

def get_top_blocks(state):
    top = ['A','B','C','D']
    for p in state:
        if p[1] in top:
            top.remove(p[1])
    return top

def update(state,entry):
    for p in state:
        if(p[0] == entry[0]):
            state.remove(p)
            state.append(entry)
            return

def move(init,goal):
    state = dc(init)
    heu = heuristic(init,goal)
    top = get_top_blocks(state)
    for i in range(len(top)):
        for j in range(len(top)):
            if( i == j ):
                update(state,(top[i],None))
                if(heuristic(state,goal)>heu):
                    return state
                state = dc(init)
            else:
                update(state,(top[i],top[j]))
                if(heuristic(state,goal)>heu):
                    return state
                state = dc(init)
    return None

def print_state(state):
    for p in state:
        print((p[1],p[0]),end=', ')
    print()

def solve(init,goal):
    steps = 0
    state = dc(init)
    goal_heu = heuristic(goal,goal)
    while(state!=None):
        print_state(state)
        if(heuristic(state,goal)==goal_heu):
            print('Hill Climb Successful')
            print('Steps taken:',steps)
            return
        else:
            state = move(state,goal)
        steps +=1
    print('Hill Climb Unsuccessful')
    return

if(__name__=='__main__'):
    init = [('B',None),('C','B'),('D','C'),('A','D')]
    goal = [('A',None),('B','A'),('C','B'),('D','C')]
    solve(init,goal)
    
    
 ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------steepest hill climbing using h: +n - n---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------


from copy import deepcopy as dc
def state_level_map(state):         
    # return the map of level vs list of block at that level (used to cal heuristic value)
    level_map = {-1: [None], 0: [], 1: [], 2: [], 3: []}
    for i in range(len(state)):
        if len(level_map[i-1]) == 0:
            break
        for p in state:
            if p[0] in level_map[i-1]:
                level_map[i].append(p[1])
    return level_map


def get_below(state, block):     
    # in given state return the block below the specified block
    if block is None:
        return None
    for p in state:
        if p[1] == block:
            return p[0]


def heuristic(state, goal):      
    # calculate the heuristic value as +n : if block at correct pos with all below at correct and -n otherwise
    # n = no of block below
    state_level  = state_level_map(state)
    goal_level = state_level_map(goal)
    val = 0
    for i in range(1, len(state)):
        if len(state_level[i]) > 0 and len(goal_level[i]) > 0:
            for block in state_level[i]:
                if block in goal_level[i]:
                    bi = block
                    bg = bi
                    add = True
                    for k in range(i, 0, -1):
                        bi = get_below(state, bi)
                        bg = get_below(goal, bg)
                        if bi != bg:
                           val -= i
                           add = False
                           break
                    if add:
                        val += i
                else:
                    val -= i
        elif len(state_level[i]) != 0:
            val -= i
        else:
            return val
    return val


def get_top_blocks(state):              
    # get block on top which can only move
    top = ['A', 'B', 'C']
    for pair in state:
        if pair[0] in top:
            top.remove(pair[0])
    return top


def update(state, entry):         
    # add entry state to state array and remove prev state
    for p in state:
        if p[1] == entry[1]:
            state.remove(p)
            state.append(entry)
            return


def move(init, goal):    
    # generate all possible moves and return one with best heuristic value
    state = dc(init)
    max_heu = heuristic(init, goal)
    ret_state = init
    top = get_top_blocks(state)
    # n^2 move n = len(top)
    for i in range(len(top)):
        for j in range(len(top)):   # place the ith block on top of jth block
            if i == j:   # place ith block on ground
                update(state, (None, top[i]))
                h_val = heuristic(state, goal)
                if h_val >= max_heu:
                    max_heu = h_val
                    ret_state = dc(state)
                state = dc(init)
            else:
                update(state, (top[j], top[i]))
                h_val = heuristic(state, goal)
                if h_val >= max_heu:
                    max_heu = h_val
                    ret_state = dc(state)
                state = dc(init)
    if ret_state == init:
        return None             # return None to show failure of Steepest Hill Climb 
    return ret_state


def print_state(state):
    for below, block in state:
        print((below, block), end=', ')
    print()
        

def solve(init,goal):       # solve block world problem using the steepest hill climb and given heuristic
    steps = 0
    state = dc(init)
    goal_heu = heuristic(goal,goal)
    while(state!=None):
        print_state(state)
        if(heuristic(state,goal)==goal_heu):
            print('Steepest Hill Climb Successfull')
            print('Steps taken:',steps)
            return
        else:
            state = move(state,goal)
        steps +=1
    print('Steepest Hill Climb Unsuccessfull!')
    return
            


if __name__ == '__main__':
    init = [(None, 'C'), ('C', 'A'), (None, 'B')]
    goal = [(None, 'A'), ('A', 'B'), ('B', 'C')]
    solve(init, goal)

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------beam search--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------



# vals in queue as (heu,parent,node)
# vals in parent as (parent,node)


def explore(graph,val,pq,parent,beta): # add child node to the queue
    if(graph[val]==None):
        return 

    for heu,name in graph[val]:
        node = (heu,val,name)
        pq.append(node)
        parent.append((val,name))      # set parent of each child node
    pq.sort()                           # sort priority queue in incr order of heuristic value
    while(len(pq)>beta):
        pq.pop(beta)        # restrict the number of elements in queue by beta

def get_steps(parent,goal):    # traverse from goal to init node to get path
    node = goal             
    steps = []
    while(node!=None):
        steps.insert(0,node)    # since going backward each node inserted at 0 idx
        for p in parent:
            if(p[1]==node):
                node = p[0]     # set node to the parent of node
                break
    return steps

def beam_search(graph,init,goal,beta):
    pq = [(None,None,init)]     # priority queue of max length beta
    parent=[(None,init)]        # maintain parent of each node help to get path if found
    while(pq):                  # loop till priority queue is not empty
        val = pq.pop(0)[2]      # get node with min heuristic value
        if(val == goal):        # if node is goal node break and return steps
            steps = get_steps(parent,goal)
            return steps
        else:
            explore(graph,val,pq,parent,beta)   # explore child node and add them to pq
    return None


if(__name__=='__main__'):
    graph = {
        'A' : [(1,'B'),(3,'C')],
        'B' : [(2,'D'),(2,'E')],
        'C' : [(3,'F'),(0,'G')],
        'D' : None,
        'E' : None,
        'F' : None,
        'G' : None,
    }
    init = 'A'
    goal = 'G'

    beta = 2
    steps = beam_search(graph,init,goal,beta)
    if(steps == None):
        print('\nBeam Search unsuccessful for beta:',beta)
    else:
        print('Steps:')
        print(steps)


    beta = 3
    steps = beam_search(graph,init,goal,beta)
    if(steps == None):
        print('\nBeam Search unsuccessful for beta:',beta)
    else:
        print('\nSteps for beta',beta,':')
        print(steps)
        
        

----------------------------------------------------------- Best First Search Graph
 
from queue import PriorityQueue
 
# function to implement best first search
def Best_FS(start, target):
  visited = []
 
  pq = PriorityQueue()
  pq.put((0, start))
 
  while not pq.empty():
    u = pq.get()[1] # pg.get() returns (cost, node)
    
    # Displaying the path having the lowest cost
    print(u, end="\t")
 
    # if target is reached, return
    if u == target:
      return
 
    for v, c in graph[u]:
      if v not in visited:
        visited.append(v)
        pq.put((c, v))
 
 
graph = {
    'Black': [('Red', 4), ('Yellow', 1), ('Blue', 2)],
    'Red': [('Pink', 8), ('Orange', 6)],
    'Yellow': [('Orange', 10), ('Green', 15)],
    'Blue': [('Green', 9)],
    'Pink': [],
    'Orange': [],
    'Green': []
}
 
Best_FS('Black', 'Orange')
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------best first search for 8 puzzle-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

import sys
import copy
# global q
# global visited

q = []
visited = []

def compare(s,g):
    if s==g:
        return(1)
    else:
        return(0)

def find_pos(s):
    
    for i in range(3):
        for j in range(3):
            if s[i][j] == 0:
                return([i,j])


def up(s,pos):
    
    i = pos[0]
    j = pos[1]
    
    if i > 0:
        temp = copy.deepcopy(s)
        temp[i][j] = temp[i-1][j]
        temp[i-1][j] = 0
        return (temp)
    else:
        return (s)

    
def down(s,pos):
    
    i = pos[0]
    j = pos[1]
    
    if i < 2:
        temp = copy.deepcopy(s)
        temp[i][j] = temp[i+1][j]
        temp[i+1][j] = 0
        return (temp)
    else:
        return (s)


def right(s,pos):
    
    i = pos[0]
    j = pos[1]
    
    if j < 2:
        temp = copy.deepcopy(s)
        temp[i][j] = temp[i][j+1]
        temp[i][j+1] = 0
        return (temp)
    else:
        return (s)

def left(s,pos):
    
    i = pos[0]
    j = pos[1]
    
    if j > 0:
        temp = copy.deepcopy(s)
        temp[i][j] = temp[i][j-1]
        temp[i][j-1] = 0
        return (temp)
    else:
        return (s)

def enqueue(s,val):
    global q
    q = q + [(val,s)]

def heuristic(s,g):
    d = 0
    for i in range(3):
        for j in range(3):
            if s[i][j] != 0:
              # The divmod() method takes two parameters x and y, 
              # where x is treated as numerator and y is treated as the denominator.
              #  The method calculates both x // y and x % y and returns both the values. 
                x, y = divmod(s[i][j] - 1, 3) # coordinates of the tile in the goal state
                d += abs(x - i) + abs(y - j)
    return d

                
def dequeue(g):
    
    global q
    global visited
    
    q.sort()
    visited = visited + [q[0][1]]
    
    elem = q[0][1]
    del q[0]
    return (elem)
    
def search(s,g):
    
    curr_state = copy.deepcopy(s)
    if s == g:
        return

    global visited
    while(1):
        
        pos = find_pos(curr_state)
        new = up(curr_state,pos)

        if new != curr_state:
            if new == g:
                print ("found!! The intermediate states are:")
                print (visited + [g])
                return
            else:
                if new not in visited:
                    enqueue(new,heuristic(new,g))
            

        new = down(curr_state,pos)

        if new != curr_state:
            if new == g:
                print ("found!! The intermediate states are:")
                print (visited + [g])
                return
            else:
                if new not in visited:
                    enqueue(new,heuristic(new,g))

        new = right(curr_state,pos)

        if new != curr_state:
            if new == g:
                print ("found!! The intermediate states are:")
                print (visited + [g])
                return
            else:
                if new not in visited:
                    enqueue(new,heuristic(new,g))

        new = left(curr_state,pos)

        if new != curr_state:
            if new == g:
                print ("found!! The intermediate states are:")
                print (visited + [g])
                return
            else:
                if new not in visited:
                    enqueue(new,heuristic(new,g))
        
        if len(q) > 0:
            curr_state = dequeue(g)
        else:
            print ("not found")
            return
        


s = [[2,0,3],[1,8,4],[7,6,5]]
g = [[1,2,3],[8,0,4],[7,6,5]]
    
visited = visited + [s]
    
search(s,g)  


---------------------------------------------------------------------------- Simple Hill Climbing Graph
 
from queue import PriorityQueue
from collections import defaultdict
import random
 
 
 
# # Declaring the heuristic values of the nodes
Heuristic = {
    'a': 10,
    'b': 9,
    'd': 4,
    'c': 2,
    'h': 0,
    'j': 8,
    'k': 0,
    'f': 7,
    'e': 5,
    'g': 3,
    'i': 4,
}
 
graph = {
    'a': [('b', 10), ('j', 8), ('f', 7)],
    'b': [('d', 4), ('c', 2)],
    'd': [],
    'c': [('h', 0)],
    'h': [],
    'j': [('k', 0)],
    'k': [],
    'f': [('e', 5), ('g', 3)],
    'g': [],
    'e': [('i', 6)],
    'i': [('k', 0)],
    }
 
# Function for simple hill climbing algorithm
def SHC(start, target, path):
 
  # visited = []
 
  # make the grqaph global
  global graph
  global Heuristic
  
  # visited.append(start)
  path.append(start)
 
  if(start == target):
    print(f"\nWe've found the path to the target node: {path}")
    return 
  
  # Calculating the total number of children
  total = 0
  for i in graph[start]:
    total += 1
 
  # If there is no child then return false
  if (total==0):
    print("\nThe path to target node was not found.") 
    return False
 
  # choosing the random child
  child_number = random.randint(0,total-1)
  print(f"Total Children: {total}")
  print(f"Child: {child_number}")
  child = graph[start][child_number][0]
  print(f"child: {child}")
 
  # Proceed if the heuristic value of the child node is less than the  current heuristic value 
  if(Heuristic[start] < Heuristic[child]):
    return SHC(child, target, path)
  else:
    print("\nThe path to target node was not found.") 
    return False
 
# Call simple hill climbing algorithm for 'k'
SHC('a', 'k', [])


------------------------------------------------------------------------ Steepest Hill Climbing Graph
 
from queue import PriorityQueue
 
visited = []
 
def SHC(start, target, path):
  
  global graph
  pq = PriorityQueue()
  visited.append(start)
  path.append(start)
 
  if(start == target):
    print(f"\nWe've found the path to the target node: {path}")
    return 
  
  # pushing all the adjacent nodes in the priority queue.
  for v, c in graph[start]:
    if v not in visited:
      pq.put((c,v))
 
  # If queue is empty then that means, we haven't reached the target
  if pq.empty():
    print("\nThe target element was not found.")
    return 
 
  # selecting the node with the highest priority/ least cost
  m = pq.get(0)[1]
 
  # Recursive call
  return SHC(m, target, path)
 
 
 
 
graph = {
    'Black': [('Red', 4), ('Yellow', 1), ('Blue', 2)],
    'Red': [('Pink', 8), ('Orange', 6)],
    'Yellow': [('Orange', 10), ('Green', 15), ('Red', 1)],
    'Blue': [('Green', 9)],
    'Pink': [],
    'Orange': [],
    'Green': []
}
 
# Calling the function
SHC('Black', 'Red', [])
 
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------simple hill climbing for 8 puzzle (works fine)----------------------------------------------------------------

import copy

def up(state):
    emptyIndex = state.index(0)
    if emptyIndex in [6, 7, 8]:
        return None
    newState = copy.deepcopy(state)
    newState[emptyIndex] = newState[emptyIndex + 3]
    newState[emptyIndex + 3] = 0
    return newState

def down(state):
    emptyIndex = state.index(0)
    if emptyIndex in [0, 1, 2]:
        return None
    newState = copy.deepcopy(state)
    newState[emptyIndex] = newState[emptyIndex - 3]
    newState[emptyIndex - 3] = 0
    return newState

def left(state):
    emptyIndex = state.index(0)
    if emptyIndex in [2, 5, 8]:
        return None
    newState = copy.deepcopy(state)
    newState[emptyIndex] = newState[emptyIndex + 1]
    newState[emptyIndex + 1] = 0
    return newState

def right(state):
    emptyIndex = state.index(0)
    if emptyIndex in [0, 3, 6]:
        return None
    newState = copy.deepcopy(state)
    newState[emptyIndex] = newState[emptyIndex - 1]
    newState[emptyIndex - 1] = 0
    return newState

def emptyTileIndex(state):
    return state.index(0)

def isGoalReached(state, goalState):
    return state == goalState

def displayState(state):
    print('-------------------')
    for i in range(0,8,3):
        print(state[i], state[i+1], state[i+2])
    print('-------------------')

def possible_nextstates(state):
    stateList=[]
    newState = up(state)
    if newState:
        stateList.append(newState)
    newState = down(state)
    if newState:
        stateList.append(newState)
    newState = left(state)
    if newState:
        stateList.append(newState)
    newState = right(state)
    if newState:
        stateList.append(newState)
    return stateList

def heuristic(state, goalState):
    cnt=0
    for i in range(0,9):
        if goalState[i]!=0 and goalState[i]!=state[i]:
            cnt=cnt+1
    return cnt

def HillClimbing(startState, goalState):
    isopen=[]
    closed=[]
    nextStates=[]
    isopen.append(startState)
    while isopen:
        thisState=isopen.pop(0)
        displayState(thisState)
        print('Value of heuristic :', heuristic(thisState, goalState))
        if thisState not in closed:
            closed.append(thisState)
            if isGoalReached(thisState, goalState):
                print('Goal state is found ..stopping search')
                
                break
            nextStates=possible_nextstates(thisState)
            for eachstate in nextStates:
                if eachstate not in closed and eachstate not in isopen:
                    if heuristic(eachstate, goalState) < heuristic(thisState, goalState):
                        isopen.append(eachstate)
                        closed.append(thisState)


s = [2,0,3,1,8,4,7,6,5]
g = [1,2,3,8,0,4,7,6,5]
HillClimbing(s,g)


---------------------------------------------------------------------------------------------------------------------------------------------------------------- 8 Puzzle Problem using Steepest Hill Climbing-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------


import sys
import copy as c
init=[[2,0,3],[1,8,4],[7,6,5]]
fin=[[1,2,3],[8,0,4],[7,6,5]]
open=[]
closed=[]

def check(aa,bb):
    if aa==bb:
        return 1
    else:
        return -1

def pos_find(aa):
    dup=[]
    for i in range(3):
        for j in range(3):
            if aa[i][j]==0:
                dup.append(i)
                dup.append(j)
                return dup

def difference(aa,bb):
    count=0
    for i in range(3):
        for j in range(3):
            if aa[i][j]!=bb[i][j]:
                count=count+1
    return count
def left(l,a,b):
    if b==0:
        open.append([0])
        return 10
    ll=c.deepcopy(l)
    ll[a][b],ll[a][b-1]=ll[a][b-1],ll[a][b]
    s=closed.count(ll)+open.count(ll)
    if s==0:
        t=difference(ll,fin)
        open.append(ll)
        return t
    else:
        open.append([0])
        return 10

def up(l,a,b):
    if a==0:
        open.append([0])
        return 10
    ll=c.deepcopy(l)
    ll[a][b],ll[a-1][b]=ll[a-1][b],ll[a][b]
    s=closed.count(ll)+open.count(ll)
    if s==0:
        t=difference(ll,fin)
        open.append(ll)
        return t
    else:
        open.append([0])
        return 10
    
def right(l,a,b):
    if b==2:
        open.append([0])
        return 10
    ll=c.deepcopy(l)
    ll[a][b],ll[a][b+1]=ll[a][b+1],ll[a][b]
    s=closed.count(ll)+open.count(ll)
    if s==0:
        t=difference(ll,fin)
        open.append(ll)
        return t
    else:
        open.append([0])
        return 10
        
def down(l,a,b):
    if a==2:
        open.append([0])
        return 10
    ll=c.deepcopy(l)
    ll[a][b],ll[a+1][b]=ll[a+1][b],ll[a][b]
    s=closed.count(ll)+open.count(ll)
    if s==0:
        t=difference(ll,fin)
        open.append(ll)
        return t
    else:
        open.append([0])
        return 10

def jump(): 
    global open
    if open==[]:
        print("FAILED TO FIND THE SOLUTION")
        sys.exit(0)
    s=open.pop()
    closed.append(s)
    gg=c.copy(pos_find(s))
    a=gg[0]
    b=gg[1]
    
    cc=check(s,fin)
    if cc==1:
        print("FINALLY FOUND THE SOLUTION")
        print("PATH: ",closed)
        print("PATH COST: ",len(closed))
        sys.exit()
        

    initi=c.deepcopy(s)
    t=difference(initi,fin)
    
    r1=left(initi,a,b)
    r2=right(initi,a,b)
    r3=up(initi,a,b)
    r4=down(initi,a,b)
    li=[r1,r2,r3,r4]
    mini=li.index(min(li))
    m=min(li)
    if m>t:
        print("CANT FIND THE ANSWER")
        sys.exit()
    f=open[mini]
    open=[f]
    jump()

open.append(init)
jump()
    
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------A* algo------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------


from queue import PriorityQueue
graph = {
    'S': [('A', 1), ('B', 4)],
    'A': [('B', 2), ('C', 5), ('D', 12)],
    'B': [('C', 2)],
    'C': [('D', 3)],
    'D': [],
}

def h(n):
    H = {
       'S': 7,
        'A': 6,
        'B': 2,
        'C': 1,
        'D': 0,
    }

    return H[n]

def get_neighbors(v):
    return graph[v]

def a_star_algorithm(start, stop):
    open_lst = set([start])
    closed_lst = set([])
    #g(n)
    g = {} # stores the cost from the start node to each node in the graph
    g[start] = 0

    par = {}
    par[start] = start

    while len(open_lst) > 0:
        n = None

        for v in open_lst:
            if n == None or g[v] + h(v) < g[n] + h(n):
                n = v

        if n == None:
            print('Path does not exist!')
            return None

        if n == stop:
            reconst_path = []

            while par[n] != n:
                reconst_path.append(n)
                n = par[n]

            reconst_path.append(start)
            reconst_path.reverse()

            print('Path found: {}'.format(reconst_path))
            return reconst_path

        for (m, weight) in get_neighbors(n):
            if m not in open_lst and m not in closed_lst:
                open_lst.add(m)
                par[m] = n
                g[m] = g[n] + weight

            else:
                if g[m] > g[n] + weight:
                    g[m] = g[n] + weight
                    par[m] = n

                    if m in closed_lst:
                        closed_lst.remove(m)
                        open_lst.add(m)

        open_lst.remove(n)
        closed_lst.add(n)

    print('Path does not exist!')
    return None

a_star_algorithm('S','D')


------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------depth limited dfs------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

def dfs_limited(graph, root, limit):
    open = []
    closed = []
    goal_node = 'E'
    open.append((root, 'Root', 0))
    check = False
    while len(open) > 0:
        if open[0][0] == goal_node:
            closed = closed + [open[0]]
            open.pop(0)
            print('the goal state is reached')
            print(closed)
            check = True
            break
        if open[0][2] >= limit:
            open.pop(0)
            continue
        closed = closed + [open[0]]
        open.pop(0)
        for i in reversed(graph[closed[-1][0]]):
            open = [(i, closed[-1][0], closed[-1][2]+1)] + open
    if len(open) == 0 and check == False:
        print("no such node is found")
graph = {
'A' : ['B' ,'C'] , 'B' : ['D' , 'E'] , 'C' : ['F'] , 'D' : [] , 'E' :[] ,'F' : []
}

dfs_limited(graph, 'A', 2)


----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------iterative deepinig-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------


graph = {
    '5': ['3', '7'],
    '3': ['2', '4'],
    '7': ['8'],
    '2': [],
    '4': ['8'],
    '8': []
}

def dfs_id(graph, start, goal, max_depth):
    for depth in range(max_depth):
        visited = set()
        path = dfs(graph, start, goal, depth, visited)
        if path is not None:
            return path
    return None

def dfs(graph, node, goal, depth, visited):
    if depth < 0:
        return None
    if node == goal:
        return [node]
    visited.add(node)
    for neighbour in graph[node]:
        if neighbour not in visited:
            path = dfs(graph, neighbour, goal, depth - 1, visited)
            if path is not None:
                return [node] + path
    return None

# Driver Code
print("Following is the Depth-First Search with Iterative Deepening")
path = dfs_id(graph, '5', '8', 5)
if path is None:
    print("No path found!")
else:
    print("Path found:", ' -> '.join(path))

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------uniform cost search-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

from queue import PriorityQueue
graph = {
    'A': [('B', 2), ('C', 4)],
    'B': [('D', 3), ('E', 2)],
    'C': [('F', 4)],
    'D': [('G', 1)],
    'E': [('H', 3)],
    'F': [('I', 2)],
    'G': [],
    'H': [('J', 1)],
    'I': [],
    'J': []
}

start_node = 'A'
goal_node = 'J'


def uniform_cost_search(graph, start, goal):
    open_list = PriorityQueue()
    open_list.put((0, start,[]))
    explored = set()

    while not open_list.empty():
        cost, node , path = open_list.get()
        if node not in explored:
            explored.add(node)
            path = path + [node]
        if node == goal:
            return path , cost
        explored.add(node)
        for neighbor, neighbor_cost in graph[node]:
            if neighbor not in explored:
                open_list.put((cost + neighbor_cost, neighbor,path))
    return None

result = uniform_cost_search(graph, start_node, goal_node)
if path is None:
    print("No path found!")
else:
    print("Path found:", path)
 



-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------bidirectional by Rishi----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

class Node:
    def __init__(self, val, neighbors=[]):
        self.val = val
        self.neighbors = neighbors
        self.visited_right = False  # whether the node was reached by the BFS that started from source
        self.visited_left = False  # whether the node was reached by the BFS that started from destination
        self.parent_right = None  # used for retrieving the final path from source to the meeting point
        self.parent_left = None  # used for retrieving the final path from the meeting point to destination


# class Queue:
#    pass  # implement it yourself
from collections import deque

def bidirectional_search(s, t):
    def extract_path(node):
        """return the path when both BFS's have met"""
        node_copy = node
        path = []

        while node:
            path.append(node.val)
            node = node.parent_right
            
        path.reverse()
        del path[-1]  

        while node_copy:
            path.append(node_copy.val)
            node_copy = node_copy.parent_left
        return path
        
    q = deque([])
    q.append(s)
    q.append(t)
    s.visited_right = True
    t.visited_left = True

    while len(q) > 0:
        n = q.pop()
            
        if n.visited_left and n.visited_right:  # if the node visited by both BFS's
            return extract_path(n)
            
        for node in n.neighbors:
            if n.visited_left == True and not node.visited_left:
                node.parent_left = n
                node.visited_left = True
                q.append(node)
            if n.visited_right == True and not node.visited_right:
                node.parent_right = n
                node.visited_right = True
                q.append(node)

    # not found
    return False


n2 = Node(2)
n3 = Node(3)
n4 = Node(4)
n5 = Node(5)
n7 = Node(7)
n8 = Node(8)

n2.neighbors = []
n3.neighbors = [n2, n4]
n4.neighbors = [n8]
n5.neighbors = [n3, n7]
n7.neighbors = [n8]
n8.neighbors = []
print(bidirectional_search(n5,n8))


------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------dfs------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
def dfs(graph ,root ):
    open=[]
    closed=[]
    
    goal_node ='E'
    open.append((root, 'Root'))
    check = False
    while len(open) >0:
        if open[0][0] == goal_node:
            closed = closed + [open[0]]
            open.pop(0)
            print(' the goal state is reached')
            print(closed)
            check = True
            break;
        closed = closed + [open[0]]
        open.pop(0)
        for i in reversed(graph[closed[-1][0]]):
            open = [(i, closed[-1][0])] +open
    if len(open) == 0 and check == False:
        print("no such node is found")
        
graph = {
    'A' : ['B' ,'C'] , 'B' : ['D' , 'E'] , 'C' : ['F'] , 'D' : [] , 'E' :[] ,'F' : []
}

dfs(graph , 'A')

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------bfs----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
#traverses from left to right
def bfs(graph, root):
    open = []
    closed = []

    goal_node = 'E'
    open.append((root, 'Root'))
    check = False
    while len(open) > 0:
        if open[0][0] == goal_node:
            closed = closed + [open[0]]
            open.pop(0)
            print(' the goal state is reached')
            print(closed)
            check = True
            break
        closed = closed + [open[0]]
        open.pop(0)
        for i in graph[closed[-1][0]]:
            open.append((i, closed[-1][0]))

    if len(open) == 0 and check == False:
        print("no such node is found")

graph = {
    'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': [], 'F': []
}

bfs(graph, 'A')

----------------------------------------------question 1 aasg 3--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

from cmath import sqrt

class MyEightPuzzle:
    def __init__(self, startState, goalState, startState2D, goalState2D):
        self.startState=startState
        self.goalState=goalState
        self.startState2D=startState2D
        self.goalState2D=goalState2D

    def euclidean(self): #Euclidean distance
        sum=0
        for i in range(0, 3):
            for j in range(0, 3):
                goalNode=self.goalState2D[i][j]
                if goalNode==0:
                    continue
                goalIndexX=i
                goalIndexY=j

                for k in range(0, 3):
                    for l in range(0, 3):
                        startNode=self.startState2D[k][l]
                        if startNode==goalNode:
                            startIndexX=k
                            startIndexY=l
                            break
                
                x=abs(goalIndexX-startIndexX) #Find the absolute difference of the indices along the rows
                y=abs(goalIndexY-startIndexY) #Find the absolute difference of the indices along the columns
                distance=sqrt( pow(x, 2) + pow(y, 2) )
                sum+=distance
                print(f"Euclidean distance for {goalNode} is {distance}")
        print(f"Heuristic function value for Euclidean distance={sum}")
        
    def manhattan(self): #Manhattan Distance
        sum=0
        for i in range(0, 9):
            
            goalNode=self.goalState[i]
            if goalNode==0:
                continue
            goalIndex=i

            for j in range(0, 9):
                startNode=self.startState[j]
                if startNode==goalNode:
                    startIndex=j
                    break
            
            difference=abs(goalIndex-startIndex) #moves can be either vertical or horizontal
            if difference<3:
                moves=difference 
            elif difference>=3 and difference<6:
                moves=difference%3 + 1
            elif difference>=6 and difference<8:
                moves=difference%3 + 2
            sum+=moves
            print(f"Manhattan distance for {self.goalState[i]} is {moves}")
        print(f"Heuristic function value for Manhattan distance={sum}")
            
    def minkowski(self): #Minkowski distance
        sum=0
        p=float(input("Enter p: ")) #Same as Euclidean but instead of power 2 and 1/2, we use p and 1/p

        for i in range(0, 3):
            for j in range(0, 3):
                goalNode=self.goalState2D[i][j]
                if goalNode==0:
                    continue
                goalIndexX=i
                goalIndexY=j

                for k in range(0, 3):
                    for l in range(0, 3):
                        startNode=self.startState2D[k][l]
                        if startNode==goalNode:
                            startIndexX=k
                            startIndexY=l
                            break
                
                x=abs(goalIndexX-startIndexX)
                y=abs(goalIndexY-startIndexY)
                distance=pow( pow(x, p) + pow(y, p), 1/p )
                sum+=distance
                print(f"Minkowski distance for {goalNode} is {distance}")
        print(f"Heuristic function value for Minkowski distance={sum}")
        

start=[2, 0, 3, 1, 8, 4, 7, 6, 5]
goal= [1, 2, 3, 8, 0, 4, 7, 6, 5]
start2D=[[2, 0, 3], [1, 8, 4], [7, 6, 5]]
goal2D= [[1, 2, 3], [8, 0, 4], [7, 6, 5]]
problem=MyEightPuzzle(start, goal, start2D, goal2D)

problem.euclidean()
problem.manhattan()
problem.minkowski()

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
# 8 Puzzle Problem using A* Algorithm
import sys
import copy as c
init=[[2,0,3],[1,8,4],[7,6,5]]
fin=[[1,2,3],[8,0,4],[7,6,5]]
open=[]
closed=[]
hn=[]
fn=[]
hn_c=[]
fn_c=[]

def check(aa,bb):
    if aa==bb:
        return 1
    else:
        return -1

def pos_find(aa):
    dup=[]
    for i in range(3):
        for j in range(3):
            if aa[i][j]==0:
                dup.append(i)
                dup.append(j)
                return dup

def difference(aa,bb):
    count=0
    for i in range(3):
        for j in range(3):
            if aa[i][j]!=bb[i][j]:

                    count=count+1
    return count

def temp(s,f_new,h_new,l):
    if s==0:
        open.append(l)
        fn.append(f_new)
        hn.append(h_new)

    elif open.count(l)!=0:
        ind=open.index(l)
        ff=fn[ind]
        if f_new<ff:
            open[ind]=l
            fn[ind]=f_new
            hn[ind]=h_new
    
    elif closed.count(l)!=0:
        ind=closed.index(l)
        ff=fn_c[ind]
        if f_new<ff:
            closed[ind]=l
            fn_c[ind]=f_new
            hn_c[ind]=h_new
            improve(l,fn_c,hn_c)

def left(ll,f,h,a,b):
    if b==0:
        return
    l=c.deepcopy(ll)
    l[a][b],l[a][b-1]=l[a][b-1],l[a][b]
    s=closed.count(l)+open.count(l)
    g_new=f-h+1
    h_new=difference(l,fin)
    f_new=g_new+h_new
    temp(s,f_new,h_new,l)

def up(ll,f,h,a,b):
    if a==0:
        return
    l=c.deepcopy(ll)
    l[a][b],l[a-1][b]=l[a-1][b],l[a][b]
    s=closed.count(l)+open.count(l)
    g_new=f-h+1
    h_new=difference(l,fin)
    f_new=g_new+h_new
    temp(s,f_new,h_new,l)
    
def right(ll,f,h,a,b):
    if b==2:
        return
    l=c.deepcopy(ll)
    l[a][b],l[a][b+1]=l[a][b+1],l[a][b]
    s=closed.count(l)+open.count(l)
    g_new=f-h+1
    h_new=difference(l,fin)
    f_new=g_new+h_new
    temp(s,f_new,h_new,l)
        
def down(ll,f,h,a,b):
    if a==2:
        return
    l=c.deepcopy(ll)
    l[a][b],l[a+1][b]=l[a+1][b],l[a][b]
    s=closed.count(l)+open.count(l)
    g_new=f-h+1
    h_new=difference(l,fin)
    f_new=g_new+h_new
    temp(s,f_new,h_new,l)
        
        
def improve(l,f,h):
    li=c.deepcopy(l)
    gg=pos_find(l)
    left(li,f,h,gg[0],gg[1])
    right(li,f,h,gg[0],gg[1])
    up(li,f,h,gg[0],gg[1])
    down(li,f,h,gg[0],gg[1])

def jump(): 
    global open,closed,fn,hn
    if open==[]:
      return 0
        # sys.exit(0)
    
    mini=fn.index(min(fn))
    i=open.pop(mini)
    f=fn.pop(mini)
    h=hn.pop(mini)
    closed.append(i)
    fn_c.append(f)
    hn_c.append(h)
    
    if check(i,fin)==1:
        a=len(fn_c)-1
        print("LEAST PATH COST: ",fn_c[a])
        print("closed list: ",closed)
        return
        # sys.exit()
    
    gg=pos_find(i)
    left(i,f,h,gg[0],gg[1])
    right(i,f,h,gg[0],gg[1])
    up(i,f,h,gg[0],gg[1])
    down(i,f,h,gg[0],gg[1])

    jump()

t=difference(init,fin)
open.append(init)
fn.append(t)
hn.append(t)
jump()





#hill climbing for tsp
import random

def randomSolution(tsp):
    cities = list(range(len(tsp)))
    solution = []

    for i in range(len(tsp)):
        randomCity = cities[random.randint(0, len(cities) - 1)]
        solution.append(randomCity)
        cities.remove(randomCity)

    return solution

def routeLength(tsp, solution):
    routeLength = 0
    for i in range(len(solution)):
        routeLength += tsp[solution[i - 1]][solution[i]]
    return routeLength

def getNeighbours(solution):
    neighbours = []
    for i in range(len(solution)):
        for j in range(i + 1, len(solution)):
            neighbour = solution.copy()
            neighbour[i] = solution[j]
            neighbour[j] = solution[i]
            neighbours.append(neighbour)
    return neighbours

def getBestNeighbour(tsp, neighbours):
    bestRouteLength = routeLength(tsp, neighbours[0])
    bestNeighbour = neighbours[0]
    for neighbour in neighbours:
        currentRouteLength = routeLength(tsp, neighbour)
        if currentRouteLength < bestRouteLength:
            bestRouteLength = currentRouteLength
            bestNeighbour = neighbour
    return bestNeighbour, bestRouteLength

def hillClimbing(tsp):
    currentSolution = randomSolution(tsp)
    currentRouteLength = routeLength(tsp, currentSolution)
    neighbours = getNeighbours(currentSolution)
    bestNeighbour, bestNeighbourRouteLength = getBestNeighbour(tsp, neighbours)

    while bestNeighbourRouteLength < currentRouteLength:
        currentSolution = bestNeighbour
        currentRouteLength = bestNeighbourRouteLength
        neighbours = getNeighbours(currentSolution)
        bestNeighbour, bestNeighbourRouteLength = getBestNeighbour(tsp, neighbours)

    return currentSolution, currentRouteLength

def main():
    tsp = [
        [0, 400, 500, 300],
        [400, 0, 300, 500],
        [500, 300, 0, 400],
        [300, 500, 400, 0]
    ]

    print(hillClimbing(tsp))

if __name__ == "__main__":
    main()