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

visited = []
queue = []

def bfs(visited,graph,node):
visited.append(node)
queue.append(node)
while queue:
m = queue.pop(0)
print(m,end=" ")
for neighbor in graph[m]:
if neighbor not in visited:
visited.append(neighbor)
queue.append(neighbor)

print("The BFS for given graph is: ")
bfs(visited,graph,'5')

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

visited = set()
stack =[]

def dfs(graph,node):
stack.append(node)
while stack:
m = stack.pop()
if m not in visited:
print(m,end=" ")
visited.add(m)

        for neighbor in reversed(graph[m]):
            if neighbor not in visited:
               stack.append(neighbor)
            

print("The DFS for given graph is: ")
dfs(graph,'5')

def print_board(board):
for row in board:
print(" ".join(row))

def check_winner(board):
for row in board:
if row[0] == row[1]== row[2]!=' ':
return row[0]
for col in range(3):
if board[0][col]==board[1][col]==board[2][col]!=' ':
return board[0][col]
if board[0][0]==board[1][1]==board[2][2]!=' ':
return board[0][0]
if board[0][2]==board[1][1]==board[2][0]!=' ':
return board[1][1]

return None

def if_draw(board):
for row in board:
if ' ' in row:
return False
return True

def tictactoe():
board = [[' ' for _ in range(3)] for _ in range(3)]
player ='X'
while True:
print_board(board)
print(f"Player {player}'s turn.")
row = int(input("Enter row number(0,1,2): "))
col= int(input("Enter column number(0,1,2): "))

    if row<0 or row>2 or col<0 or col>2:
        print("Invalid!!Enter correct row and column number!")
        continue
    if board[row][col]==' ':
        board[row][col]= player
    else:
        print("Already Taken!!")
        continue
    winner = check_winner(board)
    if winner:
        print_board(board)
        print(f"Player {player} won!!")
        break
    if if_draw(board):
        print_board(board)
        print("It's a draw!")
        break
    
    player = 'O' if player=='X' else 'X'
    
    

tictactoe()

from collections import deque

def print_s(path):
for state in path:
print(f"Jug1: {state[0]} L, Jug2: {state[1]} L")

def next_states(state, capacities):
next_state = []
jug1, jug2 = state
cap1, cap2 = capacities

next_state.append((cap1, jug2))
next_state.append((jug1, cap2))
next_state.append((0, jug2))
next_state.append((jug1, 0))
p = min(jug1, cap2 - jug2)
next_state.append((jug1 - p, jug2 + p))
p = min(cap1 - jug1, jug2)
next_state.append((jug1 + p, jug2 - p))

return next_state

def check_if_reached(state, target):
return (state[0] == target and state[1] == 0) or (state[0] == 0 and state[1] == target)

def water_jug(capacities, target):
initial_state = (0, 0)
queue = deque([(initial_state, [initial_state])])
visited = set()
visited.add(initial_state)

while queue:
    current_state, path = queue.popleft()
    if check_if_reached(current_state, target):
        return path
    
    for nexts in next_states(current_state, capacities):
        if nexts not in visited:
            visited.add(nexts)
            queue.append((nexts, path + [nexts]))

return None

cap1 = int(input("Enter capacity of jug1: "))
cap2 = int(input("Enter capacity of jug2: "))
target = int(input("Enter target: "))

capacities = (cap1, cap2)
solution = water_jug(capacities, target)

if solution:
print_s(solution)
else:
print("No solution")

def aStarAlgo(start_node, stop_node):
open_set = set([start_node])
closed_set = set()
g = {}
parents = {}
g[start_node] = 0
parents[start_node] = start_node

while len(open_set) > 0:
    n = None

    for v in open_set:
        if n is None or (g[v] + heuristic(v) < g[n] + heuristic(n)):
            n = v

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

    if n == stop_node:
        path = []
        while parents[n] != n:
            path.append(n)
            n = parents[n]
        path.append(start_node)
        path.reverse()
        print('Path found: {}'.format(path))
        return path

    for (m, weight) in get_neighbors(n):
        if m not in open_set and m not in closed_set:
            open_set.add(m)
            parents[m] = n
            g[m] = g[n] + weight
        else:
            if g[m] > g[n] + weight:
                g[m] = g[n] + weight
                parents[m] = n
                if m in closed_set:
                    closed_set.remove(m)
                    open_set.add(m)

    open_set.remove(n)
    closed_set.add(n)

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

def get_neighbors(v):
if v in Graph_nodes:
return Graph_nodes[v]
else:
return None

def heuristic(n):
H_dist = {
'A': 11,
'B': 6,
'C': 99,
'D': 1,
'E': 7,
'G': 0
}
return H_dist[n]

Graph_nodes = {
'A': [('B', 2), ('E', 3)],
'B': [('C', 1), ('G', 9)],
'C': [],
'E': [('D', 6)],
'D': [('G', 1)],
}

aStarAlgo('A', 'G')

from collections import deque

goal_state = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]

def print_state(state):
for row in state:
print(row)
print()

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

def move(state, direction):
new_state = [row[:] for row in state]
x, y = find_zero_position(new_state)

if direction == 'up' and x > 0:
    new_state[x][y], new_state[x-1][y] = new_state[x-1][y], new_state[x][y]
elif direction == 'down' and x < 2:
    new_state[x][y], new_state[x+1][y] = new_state[x+1][y], new_state[x][y]
elif direction == 'left' and y > 0:
    new_state[x][y], new_state[x][y-1] = new_state[x][y-1], new_state[x][y]
elif direction == 'right' and y < 2:
    new_state[x][y], new_state[x][y+1] = new_state[x][y+1], new_state[x][y]

return new_state

def bfs(initial_state):
visited = []
queue = deque()
queue.append((initial_state, []))
visited.append(initial_state)

while queue:
    current_state, path = queue.popleft()
    
    print("Current state:")
    print_state(current_state)
    print("Steps taken:", path)
    print("------")
    
    if current_state == goal_state:
        print("Puzzle Solved!")
        print_state(current_state)
        print("Steps to solve:", path)
        return
    
    for direction in ['up', 'down', 'left', 'right']:
        new_state = move(current_state, direction)
        if new_state not in visited:
            queue.append((new_state, path + [direction]))
            visited.append(new_state)

initial_state = [[1, 2, 3],
[4, 8, 6],
[7, 5, 0]]

print("-----8-Puzzle Problem using BFS-----")
bfs(initial_state)

import random

cities = ["City A", "City B", "City C", "City D"]

distances = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]

def total_path_distance(path):
total_distance = 0
for i in range(len(path) - 1):
total_distance += distances[path[i]][path[i + 1]]
total_distance += distances[path[-1]][path[0]]
return total_distance

def hill_climbing():
current_path = list(range(len(cities)))
random.shuffle(current_path)
current_distance = total_path_distance(current_path)

open_list = [current_path]
closed_list = []

best_path = current_path
best_distance = current_distance

while open_list:
    current_path = open_list.pop(0)
    closed_list.append(current_path)
    
    current_distance = total_path_distance(current_path)
    
    for i in range(len(cities)):
        for j in range(i + 1, len(cities)):
            new_path = current_path[:]
            new_path[i], new_path[j] = new_path[j], new_path[i]
            
            if new_path not in closed_list:
                new_distance = total_path_distance(new_path)
                
                if new_distance < best_distance:
                    best_path = new_path
                    best_distance = new_distance
                    open_list.append(new_path)

return [cities[i] for i in best_path] + [cities[best_path[0]]], best_distance

best_path, best_distance = hill_climbing()
print("Best path:", best_path)
print("Best distance:", best_distance)

def is_safe(graph, colors, v, c):
for neighbor in graph[v]:
if colors[neighbor] == c:
return False
return True

def graph_coloring(graph, colors, v):
if v == len(graph):
return True

for c in color_avail:
    if is_safe(graph, colors, v, c):
        colors[v] = c
        if graph_coloring(graph, colors, v + 1):
            return True
        colors[v] = None

return False

def solve_graph_coloring(graph):
colors = [None] * len(graph)
if not graph_coloring(graph, colors, 0):
return "No solution exists"

for v in range(len(graph)):
    print(f"Vertex {v} ---> {colors[v]}")
return colors

graph = {
0: [1, 2],
1: [0, 2, 3],
2: [0, 1, 3],
3: [1, 2]
}

color_avail = ["Red", "Green", "Blue"]

solve_graph_coloring(graph)

import heapq

def uniform_cost_search(graph, start, goal):
# Priority queue to store (cost, node, path) tuples
queue = [(0, start, [])]
visited = set()

while queue:
    # Pop the node with the lowest cost
    cost, node, path = heapq.heappop(queue)

    # Skip if the node has already been visited
    if node in visited:
        continue

    # Add the node to the visited set
    visited.add(node)
    path = path + [node]

    # If goal is reached, return the path and cost
    if node == goal:
        return path, cost

    # Explore neighbors and add them to the queue with updated costs
    for neighbor, edge_cost in graph.get(node, []):
        if neighbor not in visited:
            heapq.heappush(queue, (cost + edge_cost, neighbor, path))

# If goal is not reachable, return None
return None

Define the graph as an adjacency list

graph = {
'A': [('B', 1), ('C', 4)],
'B': [('A', 1), ('C', 2), ('D', 5)],
'C': [('A', 4), ('B', 2), ('D', 1)],
'D': [('B', 5), ('C', 1)]
}

Run UCS

start, goal = 'A', 'D'
result = uniform_cost_search(graph, start, goal)

if result:
path, cost = result
print("Path:", path)
print("Cost:", cost)
else:
print("Goal not reachable")

ye expert system wala bhi upload kardena
def classify_animal():
decision_tree = {
"Is it a mammal?": {
"yes": {
"Does it have stripes?": {
"yes": "It's a tiger!",
"no": "It's a monkey!"
}
},
"no": {
"Does it live in water?": {
"yes": "It's a fish!",
"no": "It's a bird!"
}
}
}
}

def ask_question(node):
    if isinstance(node, dict):
        question = list(node.keys())[0]
        print(question)
        answer = input("Type 'yes' or 'no': ").strip().lower()
        
        if answer in node[question]:
            return ask_question(node[question][answer])
        else:
            print("Please answer with 'yes' or 'no'")
            return ask_question(node)
    else:
        return node

result = ask_question(decision_tree)
print(result)

classify_animal()