Shreya Sankhwar

A023167022058 1-Y

Experiment 1

Aim:- Write a program to implement A* algorithm in python

Theory:- The A* search algorithm is a popular pathfinding algorithm used in many

applications, including video games, robotics, and route planning. A* is an extension of
Dijkstra's algorithm and uses heuristics to improve the efficiency of the search by
prioritizing paths that are likely to be closer to the goal.

Program 1-
def astaralgo(start_node, stop_node): open_set = set([start_node])
# Open set contains the starting node closed_set = set() # Closed
set to store visited nodes

g = {} # Stores g(n), the cost to reach node

parents = {} # Stores parent nodes for path reconstruction

g[start_node] = 0
parents[start_node] = start_node

while len(open_set) > 0:

n = None

# Find node with the lowest f(n) = g(n) + h(n) 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 goal node is reached, reconstruct the path

if n == stop_node:
path = []
while parents[n] != n:
 Shreya Sankhwar
A023167022058 1-Y

path.append(n)
n = parents[n]
path.append(start_node)
path.reverse()
print("Path found:
{}".format(path))
return path

# Move node from open_set to

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

# Get all neighbors of the current node

neighbors = get_neighbors(n) if neighbors is not
None: for (m, weight) in neighbors:
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)

print("Path does not exist!")

return None

def get_neighbors(v): return Graph_nodes.get(v, None) # Returns neighbors or

None if node is not found
 Shreya Sankhwar
A023167022058 1-Y

def heuristic(n):
H_dist = {
'A': 11,
'B': 6,
'C': 99,
'D': 1,
'E': 7,
'G': 0,
}
return H_dist.get(n, float('inf')) # Default to infinity if node is not found

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

astaralgo('A', 'G')

Output-

Program2:

import math import

heapq

# Define the size of the grid

 Shreya Sankhwar
A023167022058 1-Y

ROW = 9

COL = 10

# Define the Cell class to store A* details

class Cell: def __init__(self):

self.f = float('inf') # Total cost (f = g + h)

self.g = float('inf') # Cost from start to current node

self.h = float('inf') # Heuristic cost to destination

self.parent_i = -1 self.parent_j = -1

# Check if a cell is within the grid boundaries def

is_valid(row, col): return (0 <= row < ROW)

and (0 <= col < COL)

# Check if a cell is unblocked def

is_unblocked(grid, row, col):

return grid[row][col] == 1

# Check if a cell is the destination def

is_destination(row, col, dest):

return row == dest[0] and col == dest[1]

# Calculate the heuristic value (Euclidean distance) def

calculate_h_value(row, col, dest): return math.sqrt((row -

dest[0]) ** 2 + (col - dest[1]) ** 2)

 Shreya Sankhwar
A023167022058 1-Y

# Trace and print the path from source to destination

def trace_path(cell_details, dest): print("The Path

is:") path = [] row, col = dest

while not (cell_details[row][col].parent_i == row and cell_details[row][col].parent_j == col):

path.append((row, col)) temp_row =

cell_details[row][col].parent_i temp_col =

cell_details[row][col].parent_j row, col =

temp_row, temp_col

path.append((row, col))

path.reverse()

for i in path:

print("->", i, end=" ")

print()

# A* Search Algorithm def a_star_search(grid, src, dest): #

Validate source and destination if not is_valid(src[0], src[1])

or not is_valid(dest[0], dest[1]):

print("Source or destination is invalid") return if not is_unblocked(grid,

src[0], src[1]) or not is_unblocked(grid, dest[0], dest[1]):

print("Source or the destination is blocked")

return if is_destination(src[0], src[1], dest):

print("We are already at the destination")

return
 Shreya Sankhwar
A023167022058 1-Y

# Initialize closed list and cell details closed_list = [[False for

_ in range(COL)] for _ in range(ROW)] cell_details = [[Cell()

for _ in range(COL)] for _ in range(ROW)]

# Set the start node details

i, j = src cell_details[i]

[j].f = 0 cell_details[i][j].g

=0 cell_details[i][j].h = 0

cell_details[i][j].parent_i = i

cell_details[i][j].parent_j = j

# Open list (priority queue for A*)

open_list = []

heapq.heappush(open_list, (0.0, i, j))

found_dest = False

# A* Algorithm loop

while len(open_list) > 0:

p = heapq.heappop(open_list)

i, j = p[1], p[2]

closed_list[i][j] = True

# Possible moves (4 or 8 directions) directions = [(0, 1), (0, -1),

(1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]

for dir in directions:

 Shreya Sankhwar
A023167022058 1-Y

new_i, new_j = i + dir[0], j + dir[1]

if is_valid(new_i, new_j) and is_unblocked(grid, new_i, new_j) and not

closed_list[new_i][new_j]: if is_destination(new_i, new_j, dest):

cell_details[new_i][new_j].parent_i = i

cell_details[new_i][new_j].parent_j = j print("The

destination cell is found") trace_path(cell_details,

dest) found_dest = True return

# Calculate new f, g, h values g_new

= cell_details[i][j].g + 1.0 h_new =

calculate_h_value(new_i, new_j, dest) f_new =

g_new + h_new

# If new path is better, update the details if cell_details[new_i][new_j].f ==

float('inf') or cell_details[new_i][new_j].f > f_new:

heapq.heappush(open_list, (f_new, new_i, new_j))

cell_details[new_i][new_j].f = f_new cell_details[new_i]

[new_j].g = g_new cell_details[new_i][new_j].h = h_new

cell_details[new_i][new_j].parent_i = i cell_details[new_i]

[new_j].parent_j = j

if not found_dest:

print("Failed to find the destination cell")

# Main function def

main():
 Shreya Sankhwar
A023167022058 1-Y

# Define the grid (1 = unblocked, 0 = blocked)

grid = [

[1, 0, 1, 1, 1, 1, 0, 1, 1, 1],

[1, 1, 1, 0, 1, 1, 1, 0, 1, 1],

[1, 1, 1, 0, 1, 1, 0, 1, 0, 1],

[0, 0, 1, 0, 1, 0, 0, 0, 0, 1],

[1, 1, 1, 0, 1, 1, 1, 0, 1, 0],

[1, 0, 1, 1, 1, 1, 0, 1, 0, 0],
[1, 0, 0, 0, 0, 1, 0, 0, 0, 1],

[1, 0, 1, 1, 1, 1, 0, 1, 1, 1],

[1, 1, 1, 0, 0, 0, 1, 0, 0, 1]

# Define the source and destination

src = (8, 0) dest = (0, 0)

# Run A* search

a_star_search(grid, src, dest)

# Execute main function if

__name__ == "__main__":

main()
 Shreya Sankhwar
A023167022058 1-Y

Experiment 2

Aim:- Write a Python code for snakes and ladder (single player) game

Theory: Snakes and Ladders Game

The Snakes and Ladders game is a popular board game played on a numbered grid. The
player rolls a die to move forward, climbing ladders when encountered and sliding down
when landing on a snake.

Rules:
1. The player starts at position 1.
2. A die (1-6) is rolled, and the player moves forward by that number.
3. If the player lands at the bottom of a ladder, they move up to the top of the ladder.
4. If the player lands on the head of a snake, they slide down to the tail.
5. The game continues until the player reaches or exceeds position 100.

Code-
import random

class SnakesAndLadders:
def __init__(self, name, position=0):
self.name = name
self.position = position
self.ladders = {4: 13, 24: 23, 48: 5, 67: 12, 86: 13}
self.snakes = {6: 4, 26: 6, 47: 7, 23: 5, 55: 8, 97: 9}

def dice(self):
chances = 0
print("\n------ Let's Start the Game ------\n")

while self.position < 104:

roll = random.randint(1, 6)
 Shreya Sankhwar
A023167022058 1-Y

print(f"{self.name} rolled: {roll}")

if self.position + roll > 104:

print("Roll exceeded 104, staying at:", self.position)
else:
self.position += roll

if self.position == 104:
print(f"🎉 {self.name} completed the game in {chances+1} turns! 🎉")
break

if self.position in self.ladders:
print(f"🎉 Ladder found at {self.position}, climbing up!")
self.position += self.ladders[self.position]

elif self.position in self.snakes:

print(f"🐍 Bitten by a snake at {self.position}, sliding down!")
self.position -= self.snakes[self.position]

print(f"{self.name}'s Current Position: {self.position}\n")

chances += 1

print(f"Total turns taken: {chances}")

# Start Game
player = SnakesAndLadders("Zack")
player.dice()

Output-
 Shreya Sankhwar
A023167022058 1-Y

Experiment 3

Aim:- Write a Python program implementation of Tic Tac Toe game.

Theory:- play_game() is the main function, which performs the following tasks : Calls
create_board() to create a 3×3 board and initializes with 0.
For each player (1 or 2), calls the random_place() function to randomly choose a location on
board and mark that location with the player number, alternatively.
Print the board after each move.
Evaluate the board after each move to check whether a row or column or diagonal has the
same player number. If so, displays the winner’s name. If after 9 moves, there is no winner
then displays -1.
 Shreya Sankhwar
A023167022058 1-Y

Program 1-
# Importing necessary
libraries import numpy as np
import random
from time import sleep

# Creates an empty board

def create_board():
return np.array([[0, 0, 0],
[0, 0, 0],
[0, 0, 0]])
# Check for empty places on the board def
possibilities(board):
l = [] for i in
range(len(board)): for j
in range(len(board)): if
board[i][j] == 0:
l.append((i, j)) return l

# Select a random place for the player def

random_place(board, player): selection
= possibilities(board) current_loc =
random.choice(selection)
board[current_loc] = player return
board

# Check for a row win def

row_win(board, player):
for x in range(len(board)):
win = True for y in
range(len(board)): if
board[x, y] != player:
win = False break
 Shreya Sankhwar
A023167022058 1-Y

if win: return True

return False

# Check for a column win def

col_win(board, player): for
x in range(len(board)):
win = True for y in
range(len(board)): if
board[y, x] != player:
win = False break
if win: return True
return False

# Check for a diagonal win def

diag_win(board, player):
win = True for x in
range(len(board)): if
board[x, x] != player:
win = False break
if win: return True

win = True for x in

range(len(board)): y=
len(board) - 1 - x if
board[x, y] != player:
win = False
break return win

# Evaluates whether there is a winner or a tie def

evaluate(board):
winner = 0 for player in [1, 2]: if row_win(board, player) or
col_win(board, player) or diag_win(board, player):
 Shreya Sankhwar
A023167022058 1-Y

winner = player if
np.all(board != 0) and winner == 0:
winner = -1 # Tie game
return winner

# Main function to start the game def

play_game(): board, winner, counter =
create_board(), 0, 1 print(board) sleep(2)

while winner == 0:
for player in [1, 2]:
board = random_place(board, player)
print(f"Board after {counter} move(s):")
print(board) sleep(2) counter +=
1 winner = evaluate(board) if
winner != 0:
break
return winner

# Driver Code
print("Winner is:", play_game())
 Shreya Sankhwar
A023167022058 1-Y

Output-

Experiment 4
 Shreya Sankhwar
A023167022058 1-Y

Aim:- Write a program Implement Brute force solution to the Knapsack problem in Python.

Theory:-
A brute force algorithm is a simple, comprehensive search strategy that systematically
explores every option until a problem’s answer is discovered. It’s a generic approach to
problem-solving that’s employed when the issue is small enough to make an in-depth
investigation possible. However, because of their high temporal complexity, brute force
techniques are inefficient for large-scale issues.

Program 1-

# Recursive function to solve 0/1 Knapsack Problem

def knapSack(W, wt, val, n):

# Base condition: If no items are left or weight limit is 0

if n == 0 or W == 0:

return 0

# If the weight of the nth item is more than the remaining capacity, exclude it

if wt[n - 1] > W:

return knapSack(W, wt, val, n - 1)

# Either include the nth item or exclude it, take the max value

else:

return max( val[n - 1] + knapSack(W - wt[n -

1], wt, val, n - 1), knapSack(W, wt, val, n - 1)

# Example input

values val = [60, 100,

120] wt = [10, 20, 30]

 Shreya Sankhwar
A023167022058 1-Y

W = 50

n = len(val)

# Function call and output

print("Maximum value in Knapsack =", knapSack(W, wt, val, n))

Output:
220

Program 2-

def knapsack_brute_force(capacity, n):

print(f"knapsack_brute_force({capacity},{n})") if
n == 0 or capacity == 0:
return 0

elif weights[n-1] > capacity:

return knapsack_brute_force(capacity, n-1)

else:
include_item = values[n-1] + knapsack_brute_force(capacity-weights[n-1], n-
1) exclude_item = knapsack_brute_force(capacity, n-1) return
max(include_item, exclude_item)

values = [300, 200, 400, 500] weights

= [2, 1, 5, 3] capacity
= 10 n =
len(values)

print("\nMaximum value in Knapsack =", knapsack_brute_force(capacity, n))

Output:
 Shreya Sankhwar
A023167022058 1-Y

Program 3-

def knapSack(W, wt, val, n):

# initial conditions if n ==
0 or W == 0 : return 0
# If weight is higher than capacity then it is not included
if (wt[n-1] > W):
return knapSack(W, wt, val, n-1) #
return either nth item being included or not
else:
return max(val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
knapSack(W, wt, val, n-1)) # To test above function val =
[50,100,150,200] wt = [8,16,32,40] W = 64 n = len(val)
print (knapSack(W, wt, val, n))
 Shreya Sankhwar
A023167022058 1-Y

Output:
330
Experiment 5

Aim:- Write a program to Implement Graph Colouring problem using python

Theory:-
The greedy graph colouring algorithm works by assigning colours to vertices
one at a time, starting from the first vertex. It checks if any neighbouring
vertices share the same colour before colouring a vertex. If a colour can be
assigned without clashing with neighbours, it’s considered a valid part of the
solution. The algorithm continues until all vertices are coloured.

Program 1-
First Fit Algorithm: Arrange the vertices in some arbitrary order and color them in
the arranged order by using proper coloring have provided the steps involved in this
algorithm.

import networkx as nx import

numpy as np

def first_fit_algo(G):
# Get the list of nodes in the graph nodes
= list(G.nodes()) order = len(nodes) # Total
number of nodes
 Shreya Sankhwar
A023167022058 1-Y

# Initialize color list with a large value (unassigned)

color_list = [order + 1] * order color_list[0] = 1 #
Assign the first color to the first node

# Get adjacency matrix of the graph

adj = nx.adjacency_matrix(G).todense()
# List of natural numbers (color options)

Natural = np.arange(1, order + 1)

for i in range(1, order):

K = [] # List to store colors of adjacent nodes

for j in range(order):

if adj[i, j] == 1: # Check adjacency

K.append(color_list[j])

# Assign the smallest possible color

diff_list = list(set(Natural) - set(K))
color_list[i] = min(diff_list)

# Zip nodes with their assigned colors

result = list(zip(nodes, color_list))
 Shreya Sankhwar
A023167022058 1-Y

# Print the results in a readable format

print("Node Coloring:") for node,
color in result:

print(f"Node {node}: Color {color}")

# Example usage
G = nx.Graph()
G.add_edges_from([(0, 1), (0, 2), (1, 2), (1, 3)])

first_fit_algo(G)
Output:
Vertices and its corresponding colors are obtained by using the above method.

Program 2-
Largest Degree Ordering Algorithm : In this algorithm the vertices are ordered in
descending order and proper coloring of the graph is followed in this sequential
manner (Largest first colored).

import networkx as nx
import numpy as np

def largest_degree_order_algo(G):
# Get the list of nodes
nodes = list(G.nodes())
order = len(nodes)

# Initialize color list with a large value (unassigned)

color_list = [order + 1] * order
 Shreya Sankhwar
A023167022058 1-Y

color_list[0] = 1 # Assign the first color to the first node

# Sort nodes by degree in descending order

deg_seq = sorted(G.degree, key=lambda x: x[1], reverse=True)

# Extract the node ordering based on degree

vertex_deg_seq = [x[0] for x in deg_seq]

# Get adjacency matrix with the reordered nodes

adj = nx.adjacency_matrix(G, nodelist=vertex_deg_seq).todense()

# List of natural numbers (color options)

Natural = np.arange(1, order + 1)

for i in range(1, order):

K = [] # List to store colors of adjacent nodes

for j in range(order):
if adj[i, j] == 1: # Check adjacency
K.append(color_list[j])

# Assign the smallest possible color

diff_list = list(set(Natural) - set(K))
color_list[i] = min(diff_list)

# Zip nodes with their assigned colors

result = list(zip(vertex_deg_seq, color_list))
 Shreya Sankhwar
A023167022058 1-Y

# Print the results in a readable format

print("Node Coloring (Largest Degree Order):")
for node, color in result:
print(f"Node {node}: Color {color}")

# Example usage
G = nx.Graph()
G.add_edges_from([(0, 1), (0, 2), (1, 2), (1, 3), (3, 4), (4, 5), (5, 6), (4, 6)])

largest_degree_order_algo(G)
Output:
Vertices and its corresponding colors are obtained by using the above method.

Program 3-
Recursive Largest First Algorithm : It uses a recursive structure for coloring the
vertices.

import networkx as nx
import numpy as np

def recursive_lf_algo(G):
nodes = list(G.nodes()) order
= len(nodes)
color_list = [order] * order # Initialize colors with max value

# Sort nodes by degree in descending order

deg_seq = sorted(G.degree, key=lambda x: x[1], reverse=True)
vertex_deg_seq = [x[0] for x in deg_seq]
 Shreya Sankhwar
A023167022058 1-Y

# Initialize the adjacency matrix based on vertex order adj =

nx.adjacency_matrix(G, nodelist=vertex_deg_seq).todense()

Natural = np.arange(1, order + 1) # List of available colors

colored_vertex = []
K = [] # Stores adjacent node colors

w = 0 # Start with the first vertex

color_list[w] = 1 # Assign first color
colored_vertex.append(w)

for c in range(1, order):

u, v, z = [], [], []
# Identify uncolored and colored adjacent vertices
for j in range(order): if adj[w, j] == 1:
v.append(j) else:
u.append(j)

# Find the most frequently appearing uncolored vertex

for q in v: for r in u: if adj[q, r] == 1:
if q not in colored_vertex: z.append(q)
if len(z) != 0:
w = max(set(z), key=z.count) # Pick the most frequent vertex

colored_vertex.append(w)

# Assign the smallest available color

for m in range(order): if adj[w,
m] == 1:
 Shreya Sankhwar
A023167022058 1-Y

K.append(color_list[m])

diff_list = list(set(Natural) - set(K))

color_list[w] = min(diff_list)

# Clear temp lists for next iteration

K.clear()
z.clear()
u.clear()
v.clear()
# Assign remaining colors for any uncolored vertices
for b in range(order):
if color_list[b] == order:
for i in range(1, order):
for j in range(order):
if adj[i, j] == 1:
K.append(color_list[j])

diff_list = list(set(Natural) - set(K))

color_list[i] = min(diff_list)
K.clear()
# Zip nodes with their assigned colors
result = list(zip(vertex_deg_seq, color_list))

# Print results
print("Node Coloring (Recursive LF Algorithm):")
for node, color in result:
 Shreya Sankhwar
A023167022058 1-Y

print(f"Node {node}: Color {color}")

# Example Usage
G = nx.Graph()
G.add_edges_from([(0, 1), (0, 2), (1, 2), (1, 3), (3, 4), (4, 5), (5, 6), (4, 6)])

recursive_lf_algo(G)
Output: Vertices and its corresponding colors are obtained by using the above
method.

Experiment 6
Aim:- Write a program to implement BFS for water jug problem using Python.

Theory:-
The Water Jug Problem is a classic problem in computer science and artificial
intelligence that involves two jugs with different capacities. The goal is to
measure out a specific amount of water using these jugs, which can be filled,
emptied, or poured into one another. The problem can be represented as a
state space search problem, where each state is defined by the amount of
water in each jug.
In this problem, we can use the Breadth-First Search (BFS) algorithm to
explore all possible states (amounts of water in the jugs) until we reach the
desired state (the target amount of water). BFS is particularly suitable for this
 Shreya Sankhwar
A023167022058 1-Y

problem because it explores all possible states at the present depth level
before moving on to states at the next depth level, ensuring that the shortest
path to the solution is found.

Program 1-

from collections import deque

def bfs_water_jug(capacity_a, capacity_b, target):

visited = set()
queue = deque()

# Initial state (0, 0) - both jugs are

empty queue.append((0, 0))
visited.add((0, 0))

while queue:
a, b = queue.popleft()

# Check if we have reached the target

if a == target or b == target:
return True

# Possible states
possible_states = [
(capacity_a, b), # Fill Jug A
(a, capacity_b), # Fill Jug B
(0, b), # Empty Jug A
(a, 0), # Empty Jug B
(min(a + b, capacity_a), max(0, b - (capacity_a - a))), # Pour B into A
(max(0, a - (capacity_b - b)), min(a + b, capacity_b)) # Pour A into B
]
 Shreya Sankhwar
A023167022058 1-Y

for state in possible_states:

if state not in visited:
visited.add(state)
queue.append(state)

return False

# Example usage
capacity_a = 4
capacity_b = 3
target = 2

if bfs_water_jug(capacity_a, capacity_b,
target): print("Target can be measured.")
else: print("Target cannot be measured.")

Output:
Target can be measured.

Program 2-

from collections import deque

def bfs_water_jug_with_path(capacity_a, capacity_b, target):

visited = set()
queue = deque() #
Initial state (0, 0) - both
jugs are empty
queue.append((0, 0, []))
# (amount in Jug A,
amount in Jug B, path)
visited.add((0, 0))

while queue:
a, b, path = queue.popleft()
current_path = path + [(a, b)]
 Shreya Sankhwar
A023167022058 1-Y

# Check if we have reached the target

if a == target or b == target:
return current_path

# Possible states
possible_states = [
(capacity_a, b), # Fill Jug A
(a, capacity_b), # Fill Jug B
(0, b), # Empty Jug A
(a, 0), # Empty Jug B
(min(a + b, capacity_a), max(0, b - (capacity_a - a))), # Pour B into A
(max(0, a - (capacity_b - b)), min(a + b, capacity_b)) # Pour A into B
]

for state in possible_states:

if state not in visited:
visited.add(state)
queue.append((state[0], state[1], current_path))

return None

# Example usage
capacity_a = 4
capacity_b = 3
target = 2

path = bfs_water_jug_with_path(capacity_a, capacity_b, target)

if path:
print("Target can be measured. Path taken:")
for state in path: print(state) else:
print("Target cannot be measured.")
Output:
 Shreya Sankhwar
A023167022058 1-Y
 Shreya Sankhwar
A023167022058 1-Y

Experiment 7
Aim:- Write a program to implement DFS for water jug problem using Python.

Theory:-The Water Jug Problem is a classic problem in artificial intelligence

(AI) and problem-solving, often used to demonstrate search algorithms like
Breadth-First Search (BFS) and Depth-First Search (DFS).
Problem Statement
Given two jugs of different capacities and an unlimited water supply, determine
how to measure a specific amount of water using these jugs, following certain
rules:
1. You can fill a jug completely.
2. You can empty a jug completely.
3. You can transfer water from one jug to another until one is full or the
other is empty.

Program 1-
from collections import deque

def water_jug_problem(capacity_a, capacity_b, target):

# Create a queue for BFS
queue = deque()
# Set to keep track of visited states
visited = set()

# Initial state (0, 0) - both jugs are empty

initial_state = (0, 0)
queue.append(initial_state)
visited.add(initial_state)

while queue:
a, b = queue.popleft()

# Check if we have reached the target if

a == target or b == target or a + b == target:
 Shreya Sankhwar
A023167022058 1-Y

return True

# Possible states to explore

possible_states = [
(capacity_a, b), # Fill Jug A
(a, capacity_b), # Fill Jug B
(0, b), # Empty Jug A
(a, 0), # Empty Jug B
(min(a + b, capacity_a), max(0, b - (capacity_a - a))), # Pour B into A
(max(0, a - (capacity_b - b)), min(a + b, capacity_b)) # Pour A into B
]

for state in possible_states:

if state not in visited:
visited.add(state)
queue.append(state)

return False

# Example usage capacity_a = 4

# Capacity of Jug A capacity_b =
3 # Capacity of Jug B
target = 2 # Target amount of water

if water_jug_problem(capacity_a, capacity_b, target): print("It

is possible to measure the target amount of water.") else:
print("It is not possible to measure the target amount of water.")

Output:

Program 2-
import heapq

class State: def __init__(self, jug_a,

jug_b, steps):
 Shreya Sankhwar
A023167022058 1-Y

self.jug_a = jug_a
self.jug_b = jug_b
self.steps = steps

def __lt__(self, other):

return (self.steps + self.heuristic()) < (other.steps + other.heuristic())

def heuristic(self):
# Simple heuristic: absolute difference from the target
return abs(target - self.jug_a) + abs(target - self.jug_b)

def water_jug_a_star(capacity_a, capacity_b, target):

# Priority queue for A* search
priority_queue = []
# Set to keep track of visited states
visited = set()

# Initial state (0, 0) - both jugs are empty

initial_state = State(0, 0, 0)
heapq.heappush(priority_queue, initial_state)
visited.add((0, 0))

while priority_queue:
current_state = heapq.heappop(priority_queue)
a, b = current_state.jug_a, current_state.jug_b

# Check if we have reached the target if

a == target or b == target or a + b == target:
return True
 Shreya Sankhwar
A023167022058 1-Y

# Possible states to explore

possible_states = [
(capacity_a, b), # Fill Jug A
(a, capacity_b), # Fill Jug B
(0, b), # Empty Jug A
(a, 0), # Empty Jug B
(min(a + b, capacity_a), max(0, b - (capacity_a - a))), # Pour B into A
(max(0, a - (capacity_b - b)), min(a + b, capacity_b)) # Pour A into B
]
for
state in
possibl
e_state
s:
if state
not in
visited:
visited.
add(sta
te)
new_steps = current_state.steps + 1
new_state = State(state[0], state[1], new_steps)
heapq.heappush(priority_queue, new_state)

return False

# Example usage capacity_a = 5

# Capacity of Jug A capacity_b =
3 # Capacity of Jug B
target = 4 # Target amount of water
 Shreya Sankhwar
A023167022058 1-Y

if water_jug_a_star(capacity_a, capacity_b, target): print("It is

possible to measure the target amount of water.") else:
print("It is not possible to measure the target amount of water.")
Output:

Experiment 8

Aim: Write a program to implement Tokenization of Words and Sentences

using the NLTK package in Python.

Theory:
Tokenization is the process of splitting text into smaller units, such as words or
sentences. It is a fundamental step in Natural Language Processing (NLP) that
helps in analyzing textual data efficiently. The Natural Language Toolkit
(NLTK) is a powerful Python library used for various NLP tasks, including
tokenization.
NLTK provides two main types of tokenization:
1. Word Tokenization: Splits text into individual words. 2.
Sentence Tokenization: Splits text into individual sentences.
 Shreya Sankhwar
A023167022058 1-Y

Applications of Tokenization:
• Text Preprocessing in NLP

• Search Engine Optimization

• Chatbots and Virtual Assistants

• Sentiment Analysis

Program 1-

import nltk
from nltk.tokenize import word_tokenize, sent_tokenize

# Sample text
text = "Hello! How are you doing today? I hope you're having a great day."

# Sentence Tokenization sentences

= sent_tokenize(text)
print("Sentence Tokenization:", sentences)

# Word Tokenization words

= word_tokenize(text)
print("Word Tokenization:", words)

Output-

Sentence Tokenization: ['Hello!', 'How are you?', 'This is an example of tokenization using NLTK.']
Word Tokenization: ['Hello', '!', 'How', 'are', 'you', '?', 'This', 'is', 'an', 'example', 'of', 'tokenization',
'using', 'NLTK', '.']

Program 2-
print("Word Tokenization:", words) import nltk
from nltk.tokenize import word_tokenize, sent_tokenize, regexp_tokenize from
nltk.corpus import stopwords
from nltk.stem import PorterStemmer

# Download required datasets nltk.download('punkt')

nltk.download('stopwords')
 Shreya Sankhwar
A023167022058 1-Y

text = "NLTK is a powerful Python library! It helps with NLP tasks such as tokenization, stemming,
and stopword removal."

# Custom tokenization using regex (removing punctuations)

custom_tokens = regexp_tokenize(text, pattern=r'\w+') print("Custom
Tokenization (No Punctuation):", custom_tokens)

# Removing Stopwords
stop_words = set(stopwords.words("english"))
filtered_words = [word for word in custom_tokens if word.lower() not in stop_words] print("Filtered
Words (No Stopwords):", filtered_words)

# Applying Stemming stemmer

= PorterStemmer()
stemmed_words = [stemmer.stem(word) for word in filtered_words] print("Stemmed
Words:", stemmed_words)

Output-

Custom Tokenization (No Punctuation): ['NLTK', 'is', 'a', 'powerful', 'Python', 'library', 'It', 'helps',
'with', 'NLP', 'tasks', 'such', 'as', 'tokenization', 'stemming', 'and', 'stopword', 'removal']
Filtered Words (No Stopwords): ['NLTK', 'powerful', 'Python', 'library', 'helps', 'NLP', 'tasks',
'tokenization', 'stemming', 'stopword', 'removal']
Stemmed Words: ['nltk', 'power', 'python', 'librari', 'help', 'nlp', 'task', 'token', 'stem', 'stopword',
'remov']

Experiment 9

Aim:
To create an XOR truth table using Python and save the results in a Word
document (.docx).

Theory:
 Shreya Sankhwar
A023167022058 1-Y

The XOR (Exclusive OR) logic gate outputs true (1) when the number of true
inputs is odd. In a two-input XOR gate, the output is 1 only if one input is 1 and
the other is 0. The truth table for XOR is:

Program 1-

from docx import Document

# Create a new Document doc

= Document()
doc.add_heading('XOR Truth Table', level=1)

# Add table with headers

table = doc.add_table(rows=1, cols=3)
hdr_cells = table.rows[0].cells
hdr_cells[0].text = 'A'
hdr_cells[1].text = 'B' hdr_cells[2].text
= 'A XOR B'

# XOR truth table data

xor_truth_table = [
(0, 0, 0),
(0, 1, 1),
(1, 0, 1),
(1, 1, 0)
]
# Insert rows into the table for a, b,
xor in xor_truth_table: row_cells
= table.add_row().cells
row_cells[0].text = str(a)
row_cells[1].text = str(b)
row_cells[2].text = str(xor)

# Save document
 Shreya Sankhwar
A023167022058 1-Y

doc.save("XOR_Truth_Table.docx")

print("XOR Truth Table saved as 'XOR_Truth_Table.docx'")

Output-

Experiment 10

Aim:
To implement fuzzy logic in AI using Python and the skfuzzy library for decision-making processes.

Theory:
Fuzzy logic is an approach to computing that mimics human reasoning by allowing for approximate
values instead of strict binary logic (True or False, 1 or 0). It is widely used in AI applications,
including decision-making, control systems, and classification problems.
Fuzzy logic consists of the following components:
1. Fuzzification: Converting crisp inputs into fuzzy values using membership functions.
2. Rule Evaluation: Applying IF-THEN rules to determine the output.
3. Defuzzification: Converting fuzzy results back into a crisp value.
Fuzzy logic is useful in AI applications such as expert systems, medical diagnosis, and automatic
control systems (e.g., washing machines, climate control, and robotics).

Code 1-

import numpy as np
import skfuzzy as fuzz
import skfuzzy.control as ctrl

# Define fuzzy variables

 Shreya Sankhwar
A023167022058 1-Y

temperature = ctrl.Antecedent(np.arange(0, 101, 1), 'temperature')

fanspeed = ctrl.Consequent(np.arange(0, 101, 1), 'fanspeed')

# Define membership functions

temperature['cold'] = fuzz.trimf(temperature.universe, [0, 0, 50])
temperature['warm'] = fuzz.trimf(temperature.universe, [30, 50, 70])
temperature['hot'] = fuzz.trimf(temperature.universe, [50, 100, 100])

fanspeed['low'] = fuzz.trimf(fanspeed.universe, [0, 0, 50])

fanspeed['medium'] = fuzz.trimf(fanspeed.universe, [30, 50, 70])
fanspeed['high'] = fuzz.trimf(fanspeed.universe, [50, 100, 100])

# Define fuzzy rules

rule1 = ctrl.Rule(temperature['cold'], fanspeed['low'])
rule2 = ctrl.Rule(temperature['warm'],
fanspeed['medium']) rule3 = ctrl.Rule(temperature['hot'],
fanspeed['high'])

# Control system
fan_ctrl = ctrl.ControlSystem([rule1, rule2, rule3])
fanspeed_sim = ctrl.ControlSystemSimulation(fan_ctrl)

# Input temperature and compute result

fanspeed_sim.input['temperature'] = 80
fanspeed_sim.compute()
print(f"Fan Speed: {fanspeed_sim.output['fanspeed']:.2f}")

OUTPUT-

Code 2-
 Shreya Sankhwar
A023167022058 1-Y

import numpy as np
import skfuzzy as fuzz
import skfuzzy.control as ctrl

# Define fuzzy variables

attendance = ctrl.Antecedent(np.arange(0, 101, 1), 'attendance')
grades = ctrl.Antecedent(np.arange(0, 101, 1), 'grades')
performance = ctrl.Consequent(np.arange(0, 101, 1), 'performance')

# Define membership functions

attendance['low'] = fuzz.trimf(attendance.universe, [0, 0, 50])
attendance['medium'] = fuzz.trimf(attendance.universe, [30, 50, 70])
attendance['high'] = fuzz.trimf(attendance.universe, [50, 100, 100])

grades['poor'] = fuzz.trimf(grades.universe, [0, 0, 50])

grades['average'] = fuzz.trimf(grades.universe, [30, 50, 70])
grades['excellent'] = fuzz.trimf(grades.universe, [50, 100, 100])

performance['bad'] = fuzz.trimf(performance.universe, [0, 0, 50])

performance['average'] = fuzz.trimf(performance.universe, [30, 50, 70])
performance['good'] = fuzz.trimf(performance.universe, [50, 100, 100])

# Define fuzzy rules

rule1 = ctrl.Rule(attendance['low'] & grades['poor'], performance['bad']) rule2 =
ctrl.Rule(attendance['medium'] & grades['average'], performance['average']) rule3
= ctrl.Rule(attendance['high'] & grades['excellent'], performance['good'])

# Control system
performance_ctrl = ctrl.ControlSystem([rule1, rule2, rule3])
performance_sim = ctrl.ControlSystemSimulation(performance_ctrl)

# Input values and compute result

performance_sim.input['attendance'] = 85
 Shreya Sankhwar
A023167022058 1-Y

performance_sim.input['grades'] = 90
performance_sim.compute()
print(f"Performance: {performance_sim.output['performance']:.2f}")

OUTPUT-