#1 A-star algorithm
import heapq
romania_map = {
'Arad': {'Sibiu': 140},
'Sibiu': {'Arad': 140, 'Rimnicu Vilcea': 80, 'Fagaras': 99},
'Rimnicu Vilcea': {'Sibiu': 80, 'Pitesti': 97},
'Fagaras': {'Sibiu': 99, 'Bucharest': 211},
'Pitesti': {'Rimnicu Vilcea': 97, 'Bucharest': 101},
'Bucharest': {}
}
heuristic = {
'Arad': 366,
'Sibiu': 253,
'Rimnicu Vilcea': 193,
'Fagaras': 176,
'Pitesti': 100,
'Bucharest': 0
}
def a_star_search(graph, start, goal, heuristic):
open_list = []
heapq.heappush(open_list, (0, start))
g_score = {city: float('inf') for city in graph}
g_score[start] = 0
while open_list:
f_score, current = heapq.heappop(open_list)
if current == goal:
return g_score[goal]
for neighbor, distance in graph[current].items():
tentative_g = g_score[current] + distance
if tentative_g < g_score[neighbor]:
g_score[neighbor] = tentative_g
f_score = tentative_g + heuristic[neighbor]
heapq.heappush(open_list, (f_score, neighbor))
return float('inf')
start = 'Arad'
goal = 'Bucharest'
distance = a_star_search(romania_map, start, goal, heuristic)
print(f"Shortest distance from {start} to {goal} is {distance} km")
#2 vaccum cleaner
import random
def display(room):
for row in room:
print(row)
print()
def is_all_clean(room):
for row in room:
if 1 in row:
return False
return True
def move_vacuum(x, y, n):
moves = ['Up', 'Down', 'Left', 'Right']
move = random.choice(moves)
if move == 'Up' and x > 0:
x -= 1
elif move == 'Down' and x < n - 1:
x += 1
elif move == 'Left' and y > 0:
y -= 1
elif move == 'Right' and y < n - 1:
y += 1
return x, y
def calculate_performance(dirty_rooms, total_rooms):
return 100 - ((dirty_rooms / total_rooms) * 100)
n = int(input("Enter the size of the room (n x n): "))
room = [[random.choice([0, 1]) for _ in range(n)] for _ in range(n)]
print("Initial room state:")
display(room)
x, y = random.randint(0, n - 1), random.randint(0, n - 1)
print(f"Vacuum cleaner starts at position ({x}, {y})\n")
rounds = 0
total_rooms = n * n
while not is_all_clean(room):
rounds += 1
dirty_rooms = 0
if room[x][y] == 1:
print(f"Cleaning room at position ({x}, {y})")
room[x][y] = 0
else:
print(f"Room at position ({x}, {y}) is already clean")
for row in room:
dirty_rooms += row.count(1)
performance = calculate_performance(dirty_rooms, total_rooms)
print(f"Performance after round {rounds}: {performance:.2f}%\n")
x, y = move_vacuum(x, y, n)
print(f"Room state after round {rounds}:")
display(room)
print(f"Simulation complete! Total rounds: {rounds}")
print("Final room state:")
display(room)
#3 minmax
import math
def minimax(depth, node_index, is_maximizing, scores, height):
if depth == height:
return scores[node_index]
if is_maximizing:
return max(
minimax(depth + 1, node_index * 2, False, scores, height),
minimax(depth + 1, node_index * 2 + 1, False, scores, height)
)
else:
return min(
minimax(depth + 1, node_index * 2, True, scores, height),
minimax(depth + 1, node_index * 2 + 1, True, scores, height)
)
scores = [-1, 4, 2, 6, -3, -5, 0, 7]
height = int(math.log2(len(scores)))
optimal_value = minimax(0, 0, True, scores, height)
print("The optimal value is:", optimal_value)
#4
INFINITY = float('inf')
def alpha_beta_pruning(node, depth, alpha, beta, maximizing_player):
if depth == 0 or is_terminal(node):
return evaluate(node)
if maximizing_player:
max_eval = -INFINITY
for child in get_children(node):
eval = alpha_beta_pruning(child, depth - 1, alpha, beta, False)
max_eval = max(max_eval, eval)
alpha = max(alpha, eval)
if beta <= alpha:
break
return max_eval
else:
min_eval = INFINITY
for child in get_children(node):
eval = alpha_beta_pruning(child, depth - 1, alpha, beta, True)
min_eval = min(min_eval, eval)
beta = min(beta, eval)
if beta <= alpha:
break
return min_eval
def is_terminal(node):
return node.get('terminal', False)
def get_children(node):
return node.get('children', [])
def evaluate(node):
return node.get('value', 0)
if __name__ == "__main__":
tree = {
'children': [
{
'children': [
{
'children': [
{'value': 2, 'terminal': True},
{'value': 3, 'terminal': True}
]
},
{
'children': [
{'value': 5, 'terminal': True},
{'value': 9, 'terminal': True}
]
}
]
},
{
'children': [
{
'children': [
{'value': 0, 'terminal': True},
{'value': 1, 'terminal': True}
]
},
{
'children': [
{'value': 7, 'terminal': True},
{'value': 5, 'terminal': True}
]
}
]
}
]
}
alpha = -INFINITY
beta = INFINITY
depth = 3
result = alpha_beta_pruning(tree, depth, alpha, beta, True)
print(f"Best value (Maximized): {result}")
#5 tic tac toe
import os
import random
turn = 'X'
win = False
spaces = 9
def clear_console():
if os.name == 'nt':
os.system('cls')
else:
os.system('clear')
def draw(board):
print("\n")
for i in range(0, 7, 3):
print(' ' + board[i] + ' | ' + board[i + 1] + ' | ' + board[i + 2])
if i < 6:
print('---|---|---')
print("\n")
def player_input(board, spaces):
pos = -1
print("Player X's turn:")
while pos == -1:
try:
print("Pick position 1-9:")
pos = int(input())
if pos < 1 or pos > 9 or board[pos - 1] != ' ':
print("Invalid position. Try again.")
pos = -1
except:
print("Enter a valid number.")
board[pos - 1] = 'X'
spaces -= 1
return board, spaces
def machine_move(board, spaces):
print("Machine O's turn...")
available_positions = [i for i in range(9) if board[i] == ' ']
pos = random.choice(available_positions)
board[pos] = 'O'
spaces -= 1
return board, spaces
def check_win(board):
for i in range(0, 7, 3):
if board[i] == board[i + 1] == board[i + 2] != ' ':
return board[i]
for i in range(3):
if board[i] == board[i + 3] == board[i + 6] != ' ':
return board[i]
if board[0] == board[4] == board[8] != ' ':
return board[0]
if board[2] == board[4] == board[6] != ' ':
return board[2]
return None
board = [' '] * 9
while not win and spaces:
clear_console()
draw(board)
if turn == 'X':
board, spaces = player_input(board, spaces)
turn = 'O'
else:
board, spaces = machine_move(board, spaces)
turn = 'X'
win = check_win(board)
clear_console()
draw(board)
if win:
print(f"{win} wins!")
else:
print("It's a draw!")
#6 iterative dfs
class Graph:
def __init__(self):
self.graph = {}
def add_edge(self, u, v):
if u not in self.graph:
self.graph[u] = []
self.graph[u].append(v)
def dls(self, node, target, depth, visited):
if node == target:
return True
if depth <= 0:
return False
visited.add(node)
for neighbor in self.graph.get(node, []):
if neighbor not in visited:
if self.dls(neighbor, target, depth - 1, visited):
return True
return False
def iddfs(self, start, target, max_depth):
for depth in range(max_depth + 1):
visited = set()
if self.dls(start, target, depth, visited):
print(f"Found at depth: {depth}")
return True
return False
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(4, 5)
g.add_edge(5, 2)
start = 0
target = 5
max_depth = 5
if g.iddfs(start, target, max_depth):
print("Target found!")
else:
print("Target not found!")
#7 mcpn
class McCullochPittsNeuron:
def __init__(self, weights, threshold):
self.weights = weights
self.threshold = threshold
def activate(self, inputs):
weighted_sum = sum(w * i for w, i in zip(self.weights, inputs))
return 1 if weighted_sum >= self.threshold else 0
def AND_function(x1, x2):
weights = [1, 1]
threshold = 2
neuron = McCullochPittsNeuron(weights, threshold)
return neuron.activate([x1, x2])
def OR_function(x1, x2):
weights = [1, 1]
threshold = 1
neuron = McCullochPittsNeuron(weights, threshold)
return neuron.activate([x1, x2])
def XOR_function(x1, x2):
or_neuron = McCullochPittsNeuron([1, 1], 1)
nand_neuron = McCullochPittsNeuron([-2, -2], -1)
and_neuron = McCullochPittsNeuron([1, 1], 2)
or_output = or_neuron.activate([x1, x2])
nand_output = nand_neuron.activate([x1, x2])
return and_neuron.activate([or_output, nand_output])
def AND_NOT_function(x1, x2):
weights = [1, -1]
threshold = 1
neuron = McCullochPittsNeuron(weights, threshold)
return neuron.activate([x1, x2])
print("AND Function:")
print(f"AND(0, 0) = {AND_function(0, 0)}")
print(f"AND(0, 1) = {AND_function(0, 1)}")
print(f"AND(1, 0) = {AND_function(1, 0)}")
print(f"AND(1, 1) = {AND_function(1, 1)}\n")
print("OR Function:")
print(f"OR(0, 0) = {OR_function(0, 0)}")
print(f"OR(0, 1) = {OR_function(0, 1)}")
print(f"OR(1, 0) = {OR_function(1, 0)}")
print(f"OR(1, 1) = {OR_function(1, 1)}\n")
print("XOR Function:")
print(f"XOR(0, 0) = {XOR_function(0, 0)}")
print(f"XOR(0, 1) = {XOR_function(0, 1)}")
print(f"XOR(1, 0) = {XOR_function(1, 0)}")
print(f"XOR(1, 1) = {XOR_function(1, 1)}\n")
print("AND-NOT Function:")
print(f"AND-NOT(0, 0) = {AND_NOT_function(0, 0)}")
print(f"AND-NOT(0, 1) = {AND_NOT_function(0, 1)}")
print(f"AND-NOT(1, 0) = {AND_NOT_function(1, 0)}")
print(f"AND-NOT(1, 1) = {AND_NOT_function(1, 1)}")
#8 perceptrron
import numpy as np
x = np.array([[0, 0], [0, 1], [1, 0], [1, 1]])
y = np.array([0, 0, 0, 1])
weights = np.array([0, 0], dtype=float)
bias = 0.0
learning_rate = 0.1
iterations = 0
max_iterations = 100
def perceptron(x, y, weights, bias, learning_rate, max_iterations):
global iterations
while iterations < max_iterations:
error_count = 0
for i in range(len(x)):
activation = np.dot(x[i], weights) + bias
output = 1 if activation >= 0 else 0
if output != y[i]:
error_count += 1
weights += learning_rate * (y[i] - output) * x[i]
bias += learning_rate * (y[i] - output)
iterations += 1
if error_count == 0:
break
return weights, bias, iterations
weights, bias, iterations = perceptron(
x, y, weights, bias, learning_rate, max_iterations
)
print("Final weights:", weights)
print("Final bias:", bias)
print("Number of iterations to converge:", iterations)
def test_perceptron(x, weights, bias):
predictions = []
for i in range(len(x)):
activation = np.dot(x[i], weights) + bias
output = 1 if activation >= 0 else 0
predictions.append(output)
return predictions
predictions = test_perceptron(x, weights, bias)
print("Predictions for the AND gate:", predictions)
#9 SVM classifier
import pandas as pd
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.svm import SVC
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
data = pd.DataFrame({
'tweet': [
"I love this product",
"This is worst experience",
"Very happy with service",
"I hate this",
"Awesome and amazing",
"Bad quality"
],
'label': [
'positive',
'negative',
'positive',
'negative',
'positive',
'negative'
]
})
X = data['tweet']
y = data['label']
vectorizer = TfidfVectorizer()
X_vector = vectorizer.fit_transform(X)
X_train, X_test, y_train, y_test = train_test_split(
X_vector,
y,
test_size=0.2,
random_state=42
)
model = SVC(kernel='linear')
model.fit(X_train, y_train)
y_pred = model.predict(X_test)
print("Accuracy:", accuracy_score(y_test, y_pred))
sample = vectorizer.transform(["I really love this"])
print("Prediction:", model.predict(sample))
#10 kmeans
import pandas as pd
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
data = pd.DataFrame({
'Annual_Income': [40000, 50000, 20000, 80000, 90000, 30000, 100000, 25000],
'Spending_Score': [60, 65, 30, 80, 85, 40, 90, 35]
})
X = data[['Annual_Income', 'Spending_Score']]
kmeans = KMeans(n_clusters=3, random_state=42)
kmeans.fit(X)
data['Cluster'] = kmeans.labels_
print(data)
plt.scatter(X['Annual_Income'], X['Spending_Score'], c=kmeans.labels_)
plt.xlabel("Income")
plt.ylabel("Spending Score")
plt.title("Customer Segmentation")
plt.show()