Name : Md Aamir Ansari
roll no: 2200291520107
sec: CSE(AI)
1. BFS using python
from collections import deque
def bfs(graph, start):
visited = set() # To keep track of visited nodes
queue = deque([start]) # Initialize a queue with the starting node
while queue:
node = queue.popleft() # Remove the first element from the queue
if node not in visited:
print(node, end=" ") # Process the node (e.g., print it)
visited.add(node) # Mark the node as visited
# Add all unvisited neighbors to the queue
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
# Example usage:
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
bfs(graph, 'A') # Start BFS from node 'A'
2. DFS using python
def dfs_iterative(graph, start):
visited = set() # To keep track of visited nodes
stack = [start] # Use a stack for DFS, starting with the initial node
while stack:
node = stack.pop() # Get the last element (LIFO order) from the stack
if node not in visited:
print(node, end=" ") # Process the node (e.g., print it)
visited.add(node) # Mark the node as visited
# Add all unvisited neighbors to the stack
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
# Example usage:
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
dfs_iterative(graph, 'A') # Start DFS from node 'A'
3. TIC TAC TOE prunning
Pruning in the context of a Tic-Tac-Toe game is typically implemented using the Minimax algorithm with
Alpha-Beta Pruning to make the AI's decision-making more efficient. Minimax helps determine the best
move by simulating all possible moves and picking the one that maximizes the AI's chances of winning
while minimizing the opponent's chances.
Alpha-Beta Pruning optimizes the Minimax by “pruning” branches that do not need to be explored
because they will not affect the final decision. This helps reduce the number of computations,
making the algorithm faster.
Here’s an example of implementing Tic-Tac-Toe with Minimax and Alpha-Beta Pruning:
import math
# Representing the board with a list of 9 elements
# Each cell is either "X", "O", or None (empty)
def print_board(board):
for i in range(3):
print(board[3 * i: 3 * i + 3])
def is_winner(board, player):
# Winning combinations
win_combinations = [
[0, 1, 2], [3, 4, 5], [6, 7, 8], # Rows
[0, 3, 6], [1, 4, 7], [2, 5, 8], # Columns
[0, 4, 8], [2, 4, 6] # Diagonals
]
return any(all(board[pos] == player for pos in combo) for combo in win_combinations)
def is_draw(board):
return all(cell is not None for cell in board)
def minimax(board, depth, is_maximizing, alpha, beta):
# Check for terminal conditions
if is_winner(board, "O"):
return -1 # Minimizing player won
elif is_winner(board, "X"):
return 1 # Maximizing player won
elif is_draw(board):
return 0 # Draw
# Maximizing player (AI)
if is_maximizing:
max_eval = -math.inf
for i in range(9):
if board[i] is None:
board[i] = "X"
eval = minimax(board, depth + 1, False, alpha, beta)
board[i] = None
max_eval = max(max_eval, eval)
alpha = max(alpha, eval)
if beta <= alpha:
break # Beta cutoff
return max_eval
# Minimizing player (opponent)
else:
min_eval = math.inf
for i in range(9):
if board[i] is None:
board[i] = "O"
eval = minimax(board, depth + 1, True, alpha, beta)
board[i] = None
min_eval = min(min_eval, eval)
beta = min(beta, eval)
if beta <= alpha:
break # Alpha cutoff
return min_eval
def best_move(board):
best_val = -math.inf
move = -1
for i in range(9):
if board[i] is None:
board[i] = "X"
move_val = minimax(board, 0, False, -math.inf, math.inf)
board[i] = None
if move_val > best_val:
best_val = move_val
move = i
return move
# Example gameplay
board = [None] * 9
current_player = "X" # AI starts as "X"
while True:
if current_player == "X":
move = best_move(board)
print(f"AI chooses position {move}")
board[move] = "X"
else:
print("Current board:")
print_board(board)
move = int(input("Enter your move (0-8): "))
if board[move] is None:
board[move] = "O"
else:
print("Invalid move. Try again.")
continue
if is_winner(board, current_player):
print_board(board)
print(f"{current_player} wins!")
break
elif is_draw(board):
print_board(board)
print("It's a draw!")
break
# Switch player
current_player = "O" if current_player == "X" else "X"
4. Hangman game
import random
# List of words to choose from
word_list = ["python", "hangman", "challenge", "programming", "computer"]
def choose_word():
return random.choice(word_list).upper()
def display_progress(word, guessed_letters):
return " ".join([letter if letter in guessed_letters else "_" for letter in word])
def hangman():
word = choose_word()
guessed_letters = set()
attempts = 6 # Number of allowed wrong guesses
print("Welcome to Hangman!")
print(f"The word has {len(word)} letters.")
while attempts > 0:
print(f"\nAttempts left: {attempts}")
print("Guessed letters:", " ".join(sorted(guessed_letters)))
print("Current word:", display_progress(word, guessed_letters))
guess = input("Guess a letter: ").upper()
# Check if the letter has already been guessed
if guess in guessed_letters:
print("You already guessed that letter. Try again.")
continue
# Add the letter to guessed letters
guessed_letters.add(guess)
# Check if the guessed letter is in the word
if guess in word:
print(f"Good guess! '{guess}' is in the word.")
# Check if the player has won
if all(letter in guessed_letters for letter in word):
print(f"Congratulations! You've guessed the word: {word}")
break
else:
attempts -= 1
print(f"Sorry, '{guess}' is not in the word.")
if attempts == 0:
print(f"Game over! The word was: {word}")
# Run the game
hangman()
5. Water jug problem
from collections import deque
def water_jug_bfs(jug1_capacity, jug2_capacity, target):
# Edge case: target cannot be more than the capacity of the largest jug
if target > max(jug1_capacity, jug2_capacity):
return "No solution possible"
# BFS queue, starting with both jugs empty
queue = deque([(0, 0)]) # Each state is (jug1 amount, jug2 amount)
visited = set() # To track visited states
visited.add((0, 0))
# Parent dictionary to trace steps
parent = {}
parent[(0, 0)] = None
while queue:
jug1, jug2 = queue.popleft()
# Check if we have reached the target in either jug
if jug1 == target or jug2 == target:
# Reconstruct the path from start to target
path = []
while (jug1, jug2) is not None:
path.append((jug1, jug2))
jug1, jug2 = parent[(jug1, jug2)]
path.reverse()
return path
# All possible actions
possible_actions = [
(jug1_capacity, jug2), # Fill jug1
(jug1, jug2_capacity), # Fill jug2
(0, jug2), # Empty jug1
(jug1, 0), # Empty jug2
(min(jug1 + jug2, jug1_capacity), jug2 - (min(jug1 + jug2, jug1_capacity) - jug1)), # Pour jug2 ->
jug1
(jug1 - (min(jug1 + jug2, jug2_capacity) - jug2), min(jug1 + jug2, jug2_capacity)) # Pour jug1 ->
jug2
]
for new_state in possible_actions:
if new_state not in visited:
visited.add(new_state)
parent[new_state] = (jug1, jug2) # Record the parent for path reconstruction
queue.append(new_state)
return "No solution possible"
# Example usage
jug1_capacity = 4
jug2_capacity = 3
target = 2
solution_path = water_jug_bfs(jug1_capacity, jug2_capacity, target)
if isinstance(solution_path, list):
print("Solution path (jug1, jug2):")
for step in solution_path:
print(step)
else:
print(solution_path)
6. Sort the sentence in alphabetical order/ remove punctuations from the given string
import string
def sort_sentence(sentence):
# Remove punctuation from the sentence
sentence = sentence.translate(str.maketrans("", "", string.punctuation))
# Split the sentence into words and sort alphabetically
words = sentence.split()
words.sort(key=str.lower) # Case-insensitive sorting
# Join the sorted words back into a sentence
sorted_sentence = " ".join(words)
return sorted_sentence
# Example usage
sentence = "Hello, world! This is a test sentence."
sorted_sentence = sort_sentence(sentence)
print("Sorted sentence:", sorted_sentence)
7. Remove stop words for a given passage from a text file using NLTK.
from nltk.corpus import stopwords
import string
def remove_stopwords_from_file(filename):
# Load stop words from NLTK
stop_words = set(stopwords.words('english'))
# Read text from the file
with open(filename, 'r') as file:
text = file.read()
# Remove punctuation and split the text into words
words = text.translate(str.maketrans("", "", string.punctuation)).split()
# Filter out stop words
filtered_words = [word for word in words if word.lower() not in stop_words]
# Join the filtered words into a sentence
filtered_text = " ".join(filtered_words)
return filtered_text
# Example usage
filename = 'passage.txt' # Replace with your text file's name
filtered_text = remove_stopwords_from_file(filename)
print("Text after removing stop words:")
print(filtered_text)
8.Text Classification for the give sentence using NLTK
from nltk.corpus import movie_reviews
from nltk.classify import NaiveBayesClassifier
from nltk.classify.util import accuracy
from nltk.corpus import stopwords
from nltk.tokenize import word_tokenize
import string
import random
# Prepare stop words and punctuation
stop_words = set(stopwords.words('english'))
punctuations = set(string.punctuation)
# Define a feature extractor
def extract_features(words):
words = [word.lower() for word in words if word.lower() not in stop_words and word
not in punctuations]
return {word: True for word in words}
# Prepare the labeled dataset for training
documents = [(list(movie_reviews.words(fileid)), category)
for category in movie_reviews.categories()
for fileid in movie_reviews.fileids(category)]
# Shuffle the dataset
random.shuffle(documents)
# Extract features and split into training and testing sets
featuresets = [(extract_features(doc), category) for (doc, category) in documents]
train_set, test_set = featuresets[:1500], featuresets[1500:]
# Train the Naive Bayes Classifier
classifier = NaiveBayesClassifier.train(train_set)
# Evaluate accuracy
print("Classifier accuracy percent:", accuracy(classifier, test_set) * 100)
# Classify a new sentence
def classify_sentence(sentence):
words = word_tokenize(sentence)
features = extract_features(words)
return classifier.classify(features)
# Example usage
sentence = "This movie was absolutely fantastic and thrilling!"
classification = classify_sentence(sentence)
print("Classification:", classification)
