LIST OF PROGRAMS

1. Implement Breadth First Search (BFS) for a given graph or maze.

2. Implement Depth First Search (DFS) for a tree or graph structure.
3. Solve the 8-Puzzle Problem using A* Search Algorithm.
4. Implement Hill Climbing Algorithm for numerical optimization or pathfinding.
5. Implement Simulated Annealing Algorithm for constraint-based search problems.
6. Solve Water Jug Problem using state-space search (BFS or DFS).
7. Write Prolog programs to define family relationships using predicates.
8. Implement 4-Queens Problem in Prolog using backtracking.
9. Implement Unification Algorithm in Python or Prolog.
10. Implement Forward and Backward Chaining in a rule-based system (manual or code-based).
11. Demonstrate Resolution in Propositional Logic through a basic example (e.g., proving a theorem).
12. Remove punctuation and stop words from a paragraph using nltk.
13. Perform stemming and lemmatization on user-input text.
14. Apply POS (Part of Speech) tagging using NLTK on a given sentence.
15. Build a simple text classifier using NLTK (e.g., classify messages as spam/ham).
16. Implement Tic-Tac-Toe game with a basic AI opponent.
17. Implement Min-Max (Minimax) Algorithm for decision making in turn-based games.
18. Enhance the game with Alpha-Beta Pruning to optimize Min-Max.
19. Simulate a Vacuum Cleaner Agent that intelligently cleans a 2D environment.
20. Build a simple chatbot using rules or pre-trained logic (can use regex or basic intent matching).
21. Design a Constraint Satisfaction Problem solver, e.g., Sudoku, or Map Coloring.
22. Perform simple Bayesian reasoning for a probability-based decision problem (e.g., medical diagnosis).
Note: The Instructor may add/delete/modify/tune experiments
 PROGRAMS

PROGRAM1: Write a python program to implement Breadth First Search Traversal?

Objective:

To implement the Breadth First Search (BFS) algorithm, which explores a graph level by level. It is typically
used to find the shortest path in unweighted graphs or traverse trees/graphs systematically.

from collections import deque

# Function to perform BFS

defbfs(graph, start):
visited = set()
queue = deque([start])
bfs_order = []

while queue:
vertex = [Link]()
if vertex notin visited:
[Link](vertex)
bfs_order.append(vertex)
[Link]([neighbor for neighbor in graph[vertex] if neighbor notin visited])

return bfs_order

# Sample graph represented as an adjacency list

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

# Starting node for BFS

start_node = 'A'

# Run BFS
bfs_result = bfs(graph, start_node)

# Output the result

print("BFS Traversal Order:", bfs_result)

Output:
BFS Traversal Order: ['A', 'B', 'C', 'D', 'E', 'F']
2. Implement Depth First Search (DFS) for a tree or graph structure.

Objective:

Implement Depth First Search (DFS)** to traverse a tree or graph structure. DFS explores as far as possible
along each branch before backtracking, typically using a stack (explicitly or via recursion).

defdfs(graph, node, visited=None):

if visited isNone:
visited = set()
[Link](node)
print(node, end=' ') # Print node during visit

for neighbor in graph[node]:

if neighbor notin visited:
dfs(graph, neighbor, visited)

# Sample graph as an adjacency list

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

# Start DFS from node 'A'

print("DFS Traversal Order:")
dfs(graph, 'A')

Sample Output:
DFSTraversalOrder:
ABDEFC
3. Solve the 8-Puzzle Problem using A* Search Algorithm.

Objective:

To solve the 8-Puzzle problem (a sliding tile puzzle) by finding the shortest sequence of moves from a given
start state to the goal state using the A* search algorithm. The heuristic used is the Manhattan distance (sum
of distances of tiles from their goal positions).

import heapq

# Goal state of the puzzle

goal_state = (1, 2, 3,
4, 5, 6,
7, 8, 0) # 0 represents the blank tile

# Moves: up, down, left, right (index changes)

moves = {
'up': -3,
'down': 3,
'left': -1,
'right': 1
}

defmanhattan_distance(state):
"""Calculate sum of Manhattan distances of tiles from goal positions."""
distance = 0
for i, tile inenumerate(state):
if tile != 0:
goal_pos = goal_state.index(tile)
current_row, current_col = divmod(i, 3)
goal_row, goal_col = divmod(goal_pos, 3)
distance += abs(current_row - goal_row) + abs(current_col - goal_col)
return distance

defget_neighbors(state):
"""Generate all possible states from the current state by moving the blank tile."""
neighbors = []
zero_pos = [Link](0)
zero_row, zero_col = divmod(zero_pos, 3)

for move, pos_change in [Link]():

new_pos = zero_pos + pos_change

# Check boundaries for left/right moves

if move == 'left'and zero_col == 0:
continue
if move == 'right'and zero_col == 2:
continue

# Check boundaries for up/down moves

if move == 'up'and zero_row == 0:
continue
if move == 'down'and zero_row == 2:
continue

# Create new state by swapping blank tile

new_state = list(state)
new_state[zero_pos], new_state[new_pos] = new_state[new_pos], new_state[zero_pos]
[Link](tuple(new_state))

return neighbors

defreconstruct_path(came_from, current):
"""Reconstruct path from start to goal state."""
path = [current]
while current in came_from:
current = came_from[current]
[Link](current)
return path[::-1]

defa_star(start_state):
"""Perform A* search to solve the 8-puzzle."""
open_set = []
[Link](open_set, (manhattan_distance(start_state), 0, start_state))
came_from = {}
g_score = {start_state: 0}
visited = set()

while open_set:
_, current_cost, current = [Link](open_set)

if current == goal_state:
return reconstruct_path(came_from, current)

[Link](current)

for neighbor in get_neighbors(current):

tentative_g_score = g_score[current] + 1

if neighbor in visited and tentative_g_score >= g_score.get(neighbor, float('inf')):

continue

if tentative_g_score < g_score.get(neighbor, float('inf')):

came_from[neighbor] = current
g_score[neighbor] = tentative_g_score
f_score = tentative_g_score + manhattan_distance(neighbor)
[Link](open_set, (f_score, tentative_g_score, neighbor))

returnNone# No solution found

defprint_state(state):
"""Helper to print the puzzle state."""
for i inrange(0, 9, 3):
print(state[i:i+3])
print()

# Example start state (can be changed)

start_state = (1, 2, 3,
4, 0, 6,
7, 5, 8)

print("Start State:")
print_state(start_state)

solution_path = a_star(start_state)

if solution_path:
print(f"Solution found in {len(solution_path) - 1} moves:")
for step in solution_path:
print_state(step)
else:
print("No solution found.")

Sample Output:
yaml
CopyEdit
Start State:
(1,2,3)
(4,0,6)
(7,5,8)

Solution found in 4 moves:

(1,2,3)
(4,0,6)
(7,5,8)

(1,2,3)
(4,5,6)
(7,0,8)

(1,2,3)
(4,5,6)
(7,8,0)

(1,2,3)
(4,5,6)
(7,8,0)
4. Hill Climbing Algorithm (Numerical Optimization)
Objective:

Use hill climbing to find a local maximum of a mathematical function by iteratively moving in the direction of
increasing value.

import random

deffunc(x):
# Example function: -x^2 + 4x + 6 (has a max)
return -x**2 + 4*x + 6

defhill_climbing(start, step_size=0.1, max_iter=100):

current = start
for i inrange(max_iter):
neighbors = [current + step_size, current - step_size]
neighbor_values = [func(n) for n in neighbors]
max_value = max(neighbor_values)
max_index = neighbor_values.index(max_value)

if max_value > func(current):

current = neighbors[max_index]
print(f"Iteration {i+1}: Moved to {current} with value {max_value}")
else:
print(f"Iteration {i+1}: No better neighbors found. Stopping.")
break

return current, func(current)

# Starting point
start_point = 0

optimal_x, optimal_val = hill_climbing(start_point)

print(f"\nOptimal x: {optimal_x}, Optimal value: {optimal_val}")

Sample Output:
Iteration 1: Moved to0.1with value 6.39
Iteration 2: Moved to0.2with value 6.76
Iteration 3: Moved to0.30000000000000004with value 7.11
Iteration 4: Moved to0.4with value 7.44
...
Iteration 40: No better neighbors found. Stopping.

Optimal x: 2.0, Optimal value: 10.0

5. Simulated Annealing Algorithm (Constraint-based Search)
Objective:

Find a global optimum for a problem with many local optima by probabilistically accepting worse solutions
early on, gradually reducing this acceptance as temperature cools.

import math
import random

deffunc(x):
# Example function with multiple minima
return x**4 - 14*x**3 + 60*x**2 - 70*x

defsimulated_annealing(start, temp=1000, cooling_rate=0.95, step_size=1, max_iter=1000):

current = start
current_val = func(current)
best = current
best_val = current_val

for i inrange(max_iter):
temp = temp * cooling_rate
if temp <= 0.1:
break

# Generate new candidate solution

candidate = current + [Link](-step_size, step_size)
candidate_val = func(candidate)

# Calculate acceptance probability

delta = candidate_val - current_val
if delta <0or [Link](0, 1) < [Link](-delta / temp):
current = candidate
current_val = candidate_val
if current_val < best_val:
best = current
best_val = current_val

print(f"Iteration {i+1}: Current x={current:.4f}, f(x)={current_val:.4f}, Temp={temp:.2f}")

return best, best_val

# Starting point
start_point = 0

best_x, best_val = simulated_annealing(start_point)

print(f"\nBest solution found: x = {best_x}, value = {best_val}")

Sample Output (partial):

Iteration 1:Currentx=0.1345,f(x)=0.3580,Temp=950.00
Iteration 2:Currentx=0.5113,f(x)=0.7892,Temp=902.50
...
Iteration 1000:Currentx=5.3456,f(x)=-45.2345,Temp=0.10

Best solution found:x=5.3456,value=-45.2345

6. Solve Water Jug Problem using BFS (State-Space Search)

Objective:

Given two jugs with capacities (e.g., 4 liters and 3 liters), use BFS to find the sequence of steps to measure an
exact amount of water (e.g., 2 liters).

from collections import deque

defwater_jug_bfs(jug1_capacity, jug2_capacity, target):

# Each state: (jug1_amount, jug2_amount)
start = (0, 0)
queue = deque([start])
visited = set([start])
parent = {start: None}

while queue:
jug1, jug2 = [Link]()

# Check if we reached the target

if jug1 == target or jug2 == target:
# Reconstruct path
path = []
state = (jug1, jug2)
while state:
[Link](state)
state = parent[state]
[Link]()
return path

# Possible actions:
states = set()

# Fill Jug1
[Link]((jug1_capacity, jug2))
# Fill Jug2
[Link]((jug1, jug2_capacity))
# Empty Jug1
[Link]((0, jug2))
# Empty Jug2
[Link]((jug1, 0))
# Pour Jug1 -> Jug2
pour_to_jug2 = min(jug1, jug2_capacity - jug2)
[Link]((jug1 - pour_to_jug2, jug2 + pour_to_jug2))
# Pour Jug2 -> Jug1
 pour_to_jug1 = min(jug2, jug1_capacity - jug1)
[Link]((jug1 + pour_to_jug1, jug2 - pour_to_jug1))

# Visit all new states

for state in states:
if state notin visited:
[Link](state)
parent[state] = (jug1, jug2)
[Link](state)

returnNone# No solution found

# Example: jug capacities 4 and 3 liters, target 2 liters

jug1_capacity = 4
jug2_capacity = 3
target_amount = 2

solution_path = water_jug_bfs(jug1_capacity, jug2_capacity, target_amount)

if solution_path:
print("Solution path:")
for step in solution_path:
print(f"Jug1: {step[0]}L, Jug2: {step[1]}L")
else:
print("No solution found.")

Sample Output:
Solution path:
Jug1:0L,Jug2:0L
Jug1:0L,Jug2:3L
Jug1:3L,Jug2:0L
Jug1:3L,Jug2:3L
Jug1:4L,Jug2:2L
7. Prolog Program for Family Relationships

Objective:

Define family relationships (parent, grandparent, sibling, etc.) using Prolog predicates.

% Facts: parent(child, parent)

parent(john, michael).
parent(john, sarah).
parent(mary, michael).
parent(mary, sarah).
parent(michael, robert).
parent(sarah, linda).

% Define mother and father

mother(X, Y) :- parent(X, Y), female(X).
father(X, Y) :- parent(X, Y), male(X).

% Define gender
female(mary).
female(sarah).
female(linda).

male(john).
male(michael).
male(robert).

% Define sibling: share at least one parent

sibling(X, Y) :- parent(P, X), parent(P, Y), X \= Y.

% Define grandparent
grandparent(X, Y) :- parent(X, Z), parent(Z, Y).

% Define uncle
uncle(X, Y) :- sibling(X, Z), parent(Z, Y), male(X).

% Define aunt
aunt(X, Y) :- sibling(X, Z), parent(Z, Y), female(X).

SampleOutput:
?- sibling(john, mary).
true.

?- grandparent(michael, robert).
true.

?- uncle(robert, linda).
false.

?- aunt(sarah, robert).
false.
8. Implement 4-Queens Problem in Prolog using Backtracking
Objective:

Place 4 queens on a 4x4 chessboard so that no two queens attack each other (no same row, column, or
diagonal). Use Prolog backtracking to find solutions.

solve_4_queens(Solution) :-
Solution = [Q1, Q2, Q3, Q4],
% Queens positions (columns) in rows 1..4
permutation([1,2,3,4], Solution),
safe(Solution).

% Check no two queens attack each other diagonally

safe([]).
safe([Q|Qs]) :-
safe(Qs),
no_attack(Q, Qs, 1).

no_attack(_, [], _).

no_attack(Q, [Q1|Qs], D) :-
Q =\= Q1 + D,
Q =\= Q1 - D,
D1 is D + 1,
no_attack(Q, Qs, D1).

?- solve_4_queens(Solution).

Prolog will backtrack and give solutions like:

Solution = [2, 4, 1, 3] ;
Solution = [3, 1, 4, 2] ;
false.
9. Implement Unification Algorithm in Python

Objective:

Implement a simple unification algorithm that attempts to unify two logical expressions (terms) with variables.

defis_variable(x):
returnisinstance(x, str) and [Link]()

defunify(x, y, subst={}):
if subst isNone:
returnNone
elif x == y:
return subst
elif is_variable(x):
return unify_var(x, y, subst)
elif is_variable(y):
return unify_var(y, x, subst)
elifisinstance(x, list) andisinstance(y, list) andlen(x) == len(y):
for xi, yi inzip(x, y):
subst = unify(xi, yi, subst)
if subst isNone:
returnNone
return subst
else:
returnNone

defunify_var(var, x, subst):
if var in subst:
return unify(subst[var], x, subst)
elif x in subst:
return unify(var, subst[x], subst)
else:
subst[var] = x
return subst

# Example usage:
expr1 = ['f', 'x', ['g', 'y']]
expr2 = ['f', 'a', ['g', 'b']]

result = unify(expr1, expr2)

print("Unification result:", result)

Sample Output:
Unification result: {'x': 'a', 'y': 'b'}
10. Forward and Backward Chaining in a Rule-Based System

Objective:

Implement simple rule-based inference using Forward and Backward chaining.

# Facts and Rules

facts = {'A', 'B'}
rules = [
('A', 'B', 'C'), # If A and B then C
('C', 'D') # If C then D
]

# Forward chaining
defforward_chaining(facts, rules):
inferred = set()
whileTrue:
new_inferred = set()
for rule in rules:
premises, conclusion = rule[:-1], rule[-1]
ifall(p in facts for p in premises) and conclusion notin facts:
new_inferred.add(conclusion)
ifnot new_inferred:
break
[Link](new_inferred)
[Link](new_inferred)
return facts

print("Forward Chaining Result:", forward_chaining(set(facts), rules))

# Backward chaining
defbackward_chaining(goal, facts, rules):
if goal in facts:
returnTrue
for rule in rules:
premises, conclusion = rule[:-1], rule[-1]
if conclusion == goal:
ifall(backward_chaining(p, facts, rules) for p in premises):
returnTrue
returnFalse

goal = 'D'
print(f"Backward Chaining: Is '{goal}' provable? ", backward_chaining(goal, facts, rules))

Sample Output:
Forward Chaining Result: {'A', 'B', 'C', 'D'}
Backward Chaining: Is'D' provable? True
11. Demonstrate Resolution in Propositional Logic

Objective:

Use resolution to prove a theorem from a knowledge base

defresolve(ci, cj):
for di in ci:
for dj in cj:
if di == f'¬{dj}':
resolvent = set(ci) - {di} | set(cj) - {dj}
return resolvent
if dj == f'¬{di}':
resolvent = set(ci) - {di} | set(cj) - {dj}
return resolvent
returnNone

KB = [
{'A', 'B'},
{'¬B', 'C'},
{'¬C'},
{'¬A'} # Negation of goal
]

defresolution(KB):
new = set()
whileTrue:
n = len(KB)
pairs = [(KB[i], KB[j]) for i inrange(n) for j inrange(i+1, n)]
for (ci, cj) in pairs:
resolvent = resolve(ci, cj)
if resolvent == set():
returnTrue# empty clause found
if resolvent and resolvent notin KB and resolvent notin new:
[Link](frozenset(resolvent))
ifnot new:
returnFalse
for r in new:
[Link](set(r))
[Link]()

print("Is goal proved by resolution? ", resolution(KB))

Sample Output:
Is goal proved by resolution? True
12. Remove punctuation and stop words from a paragraph using NLTK

Objective:
Clean a paragraph by removing punctuation and common English stop words to keep only meaningful words.

import nltk

from [Link] import stopwords

from [Link] import word_tokenize
import string

[Link]('punkt')
[Link]('stopwords')

defclean_text(text):
tokens = word_tokenize([Link]())
tokens = [word for word in tokens if [Link]()] # remove punctuation
stop_words = set([Link]('english'))
filtered_tokens = [word for word in tokens if word notin stop_words]
return filtered_tokens

paragraph = "Hello! This is a sample paragraph, demonstrating: punctuation removal, and stop word filtering."
cleaned = clean_text(paragraph)
print("Cleaned tokens:", cleaned)

Sample Output:

Cleanedtokens: ['hello', 'sample', 'paragraph', 'demonstrating', 'punctuation', 'removal', 'stop', 'word', 'filtering']
13. Perform stemming and lemmatization on user-input text

Objective:

Reduce words to their root forms via stemming and normalize to dictionary form using lemmatization.

from [Link] import PorterStemmer, WordNetLemmatizer

from [Link] import word_tokenize
import nltk

[Link]('punkt')
[Link]('wordnet')
[Link]('omw-1.4')

defstem_and_lemmatize(text):
ps = PorterStemmer()
lemmatizer = WordNetLemmatizer()
tokens = word_tokenize([Link]())
stemmed = [[Link](word) for word in tokens if [Link]()]
lemmatized = [[Link](word) for word in tokens if [Link]()]
return stemmed, lemmatized

user_text = input("Enter text: ")

stemmed_words, lemmatized_words = stem_and_lemmatize(user_text)
print("Stemmed:", stemmed_words)
print("Lemmatized:", lemmatized_words)

Sample Output (for input "running runs runner"):

Stemmed: ['run', 'run', 'runner']

Lemmatized: ['running', 'run', 'runner']
14. Apply POS tagging using NLTK on a given sentence

Objective:

Assign part-of-speech tags (noun, verb, adjective, etc.) to words in a sentence.

import nltk
from [Link] import word_tokenize
[Link]('punkt')
[Link]('averaged_perceptron_tagger')
sentence = "The quick brown fox jumps over the lazy dog."
tokens = word_tokenize(sentence)
pos_tags = nltk.pos_tag(tokens)
print("POS tags:", pos_tags)
Sample Output:
POStags: [('The', 'DT'), ('quick', 'JJ'), ('brown', 'JJ'), ('fox', 'NN'), ('jumps', 'VBZ'), ('over', 'IN'), ('the', 'DT'),
('lazy', 'JJ'), ('dog', 'NN'), ('.', '.')

15. Build a simple text classifier using NLTK (Spam vs Ham)

Objective:

Classify short text messages as spam or ham using Naive Bayes classifier based on presence of words.

import nltk
from [Link] import NaiveBayesClassifier
from [Link] import word_tokenize

# Sample training data

train_data = [
("Free entry in 2 a wkly comp to win FA Cup final tkts 21st May 2005.", "spam"),
("Nah I don't think he goes to usf, he lives around here though.", "ham"),
("WINNER!! You have been selected to receive a £900 prize reward!", "spam"),
("Hey, are we still meeting for lunch?", "ham"),
]

defextract_features(text):
words = set(word_tokenize([Link]()))
return {f"contains({word})": Truefor word in words}

featuresets = [(extract_features(text), label) for (text, label) in train_data]

classifier = [Link](featuresets)

test_text = "Congratulations! You won a prize."

test_features = extract_features(test_text)
print("Classification:", [Link](test_features))
Sample Output:

Classification: spam
16. Implement Tic-Tac-Toe game with a basic AI opponent

Objective:

Create a console-based Tic-Tac-Toe game where a human plays against a random-move AI.

import random

defprint_board(board):
for row in board:
print(' | '.join(row))
print('-' * 5)

defcheck_winner(board, player):
lines = [
board[0], board[1], board[2], # rows
[board[0][0], board[1][0], board[2][0]], # cols
[board[0][1], board[1][1], board[2][1]],
[board[0][2], board[1][2], board[2][2]],
[board[0][0], board[1][1], board[2][2]], # diagonals
[board[0][2], board[1][1], board[2][0]],
]
return [player, player, player] in lines

defget_available_moves(board):
return [(i, j) for i inrange(3) for j inrange(3) if board[i][j] == ' ']

defbasic_ai_move(board):
moves = get_available_moves(board)
return [Link](moves) if moves elseNone

deftic_tac_toe():
board = [[' ']*3for _ inrange(3)]
current_player = 'X'# Human

whileTrue:
print_board(board)
if current_player == 'X':
row = int(input("Enter row (0-2): "))
col = int(input("Enter col (0-2): "))
if board[row][col] != ' ':
print("Invalid move! Try again.")
continue
else:
print("AI's turn...")
move = basic_ai_move(board)
if move:
row, col = move
else:
print("Draw!")
break
board[row][col] = current_player

if check_winner(board, current_player):
print_board(board)
print(f"{current_player} wins!")
break

ifnot get_available_moves(board):
print_board(board)
print("Draw!")
break

current_player = 'O'if current_player == 'X'else'X'

tic_tac_toe()

Sample Output (User plays moves, AI responds):

| |
-----
| |
-----
| |
Enter row (0-2): 0
Enter col (0-2): 0
AI's turn...
| |
-----
|O|
-----
| |
Enter row (0-2): ...
...
17. Implement Minimax Algorithm for Tic-Tac-Toe

Objective:

Implement the Minimax algorithm for Tic-Tac-Toe AI to make optimal moves.

defminimax(board, is_maximizing):
if check_winner(board, 'O'):
return1
elif check_winner(board, 'X'):
return -1
elifnot get_available_moves(board):
return0

if is_maximizing:
best_score = -float('inf')
for i, j in get_available_moves(board):
board[i][j] = 'O'
score = minimax(board, False)
board[i][j] = ' '
best_score = max(score, best_score)
return best_score
else:
best_score = float('inf')
for i, j in get_available_moves(board):
board[i][j] = 'X'
score = minimax(board, True)
board[i][j] = ' '
best_score = min(score, best_score)
return best_score

defbest_move(board):
best_score = -float('inf')
move = None
for i, j in get_available_moves(board):
board[i][j] = 'O'
score = minimax(board, False)
board[i][j] = ' '
if score > best_score:
best_score = score
move = (i, j)
return move
18. Enhance Minimax with Alpha-Beta Pruning

Objective:

Optimize Minimax search by pruning branches that won’t affect the final decision.

defalphabeta(board, alpha, beta, is_maximizing):

if check_winner(board, 'O'):
return1
elif check_winner(board, 'X'):
return -1
elifnot get_available_moves(board):
return0

if is_maximizing:
max_eval = -float('inf')
for i, j in get_available_moves(board):
board[i][j] = 'O'
eval = alphabeta(board, alpha, beta, False)
board[i][j] = ' '
max_eval = max(max_eval, eval)
alpha = max(alpha, eval)
if beta <= alpha:
break
return max_eval
else:
min_eval = float('inf')
for i, j in get_available_moves(board):
board[i][j] = 'X'
eval = alphabeta(board, alpha, beta, True)
board[i][j] = ' '
min_eval = min(min_eval, eval)
beta = min(beta, eval)
if beta <= alpha:
break
return min_eval
19. Simulate a Vacuum Cleaner Agent in a 2D environment

Objective:

Model an agent that moves in a grid to clean dirty spots intelligently.

defvacuum_agent(environment, start_pos=(0, 0)):

x, y = start_pos
cleaned = set()

defis_dirty(pos):
return [Link](pos, 'clean') == 'dirty'

moves = [(0,1), (1,0), (0,-1), (-1,0)] # up, right, down, left

whilelen(cleaned) <len(environment):
if is_dirty((x,y)):
environment[(x,y)] = 'clean'
print(f"Cleaning at {(x,y)}")
[Link]((x,y))

for dx, dy in moves:

nx, ny = x + dx, y + dy
if (nx, ny) in environment and (nx, ny) notin cleaned:
x, y = nx, ny
break
else:
break# no new moves

env = {
(0,0): 'dirty', (0,1): 'clean', (0,2): 'dirty',
(1,0): 'clean', (1,1): 'dirty', (1,2): 'clean',
}

vacuum_agent(env)

Sample Output:

Cleaning at(0, 0)
Cleaning at(0, 2)
Cleaning at(1, 1)
20. Build a simple chatbot using regex pattern matching

Objective:

Create a rule-based chatbot responding to user input using regex.

import re

responses = {
r"hi|hello": "Hello! How can I help you?",
r"how are you": "I'm good, thanks!",
r"bye|exit": "Goodbye! Have a nice day.",
}

defchatbot():
print("Chatbot (type 'exit' to quit)")
whileTrue:
user_input = input("You: ").lower()
if user_input == 'exit':
print("Chatbot: Goodbye!")
break
response = "Sorry, I didn't understand that."
for pattern, reply in [Link]():
if [Link](pattern, user_input):
response = reply
break
print("Chatbot:", response)

chatbot()
21. Sudoku Solver (CSP solver)

Objective:

Solve a Sudoku puzzle by assigning digits 1-9 to empty cells satisfying constraints.

defis_valid(board, row, col, num):

for i inrange(9):
if board[row][i] == num or board[i][col] == num:
returnFalse
start_row, start_col = 3*(row//3), 3*(col//3)
for i inrange(start_row, start_row+3):
for j inrange(start_col, start_col+3):
if board[i][j] == num:
returnFalse
returnTrue

defsolve_sudoku(board):
for row inrange(9):
for col inrange(9):
if board[row][col] == 0:
for num inrange(1, 10):
if is_valid(board, row, col, num):
board[row][col] = num
if solve_sudoku(board):
returnTrue
board[row][col] = 0
returnFalse
returnTrue

# Example Sudoku puzzle (0 = empty)

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

if solve_sudoku(board):
for row in board:
print(row)
else:
print("No solution found")

Sample Output (partial):

[5, 3, 4, 6, 7, 8, 9, 1, 2]
[6, 7, 2, 1, 9, 5, 3, 4, 8]
...

22. Simple Bayesian Reasoning Example

Objective:

Compute the probability of a disease given a positive test using Bayes' theorem.

p_disease = 0.01
p_positive_given_disease = 0.99
p_positive_given_no_disease = 0.05

defbayes(p_disease, p_pos_given_dis, p_pos_given_no_dis):

numerator = p_pos_given_dis * p_disease
denominator = numerator + p_pos_given_no_dis * (1 - p_disease)
return numerator / denominator

posterior = bayes(p_disease, p_positive_given_disease, p_positive_given_no_disease)

print(f"Probability of disease given positive test: {posterior:.4f}")

Sample Output:

Probability of disease given positive test: 0.1662

test_feat))