9) Write a program to implement Water jug model using python?
The "Water Jug Problem" is a classic problem in artificial intelligence and problem-solving that
involves two jugs with different capacities. The goal is to measure a specific amount of water
using the two jugs.
Here's a typical setup:
You have two jugs: one with a capacity of X liters and the other with a capacity of Y
liters.
The task is to measure Z liters (where Z ≤ max(X, Y)) using these two jugs, but you can
only fill, empty, or transfer water between the jugs.
The challenge lies in determining a sequence of steps to achieve the desired amount of water in
one of the jugs.
Example Problem:
Jug 1 has a capacity of 5 liters.
Jug 2 has a capacity of 3 liters.
You want to measure exactly 4 liters.
Steps to solve:
1. Fill Jug 1 (5 liters).
2. Pour water from Jug 1 into Jug 2 until Jug 2 is full (Jug 1 now has 2 liters, Jug 2 has 3
liters).
3. Empty Jug 2.
4. Pour the remaining 2 liters from Jug 1 into Jug 2 (Jug 1 is empty, Jug 2 now has 2 liters).
5. Fill Jug 1 again (5 liters).
6. Pour water from Jug 1 into Jug 2 until Jug 2 is full. Now, Jug 1 has exactly 4 liters.
This problem is often used in AI to teach concepts like state space search, search algorithms (like
breadth-first search or depth-first search), and goal-oriented problem-solving.
Program
from collections import deque
# Function to perform the BFS
def water_jug_bfs(capacity1, capacity2, target):
# Set to keep track of visited states to avoid loops
visited = set()
queue = deque([(0, 0, [])]) # Start with both jugs empty
while queue:
jug1, jug2, path = [Link]()
# If we have reached the target, return the sequence of steps
if jug1 == target or jug2 == target:
return path + [(jug1, jug2)]
# Mark the current state as visited
if (jug1, jug2) in visited:
continue
[Link]((jug1, jug2))
# Possible actions: fill, empty, or transfer
next_states = [
(capacity1, jug2), # Fill jug1
(jug1, capacity2), # Fill jug2
(0, jug2), # Empty jug1
(jug1, 0), # Empty jug2
(jug1 - min(jug1, capacity2 - jug2), jug2 + min(jug1, capacity2 - jug2)), #
Pour jug1 into jug2
(jug1 + min(jug2, capacity1 - jug1), jug2 - min(jug2, capacity1 - jug1)) #
Pour jug2 into jug1
]
for state in next_states:
new_jug1, new_jug2 = state
if (new_jug1, new_jug2) not in visited:
[Link]((new_jug1, new_jug2, path + [(jug1, jug2)]))
return None # No solution found
# Example usage
capacity1 = 5 # Capacity of Jug 1
capacity2 = 3 # Capacity of Jug 2
target = 4 # Target amount of water
solution = water_jug_bfs(capacity1, capacity2, target)
if solution:
print("Steps to achieve the target:")
for step in solution:
print(f"Jug 1: {step[0]}L, Jug 2: {step[1]}L")
else:
print("No solution found.")
10)ALPHA-BETA PRUNING USING PYTHON?
class Node:
def __init__(self, name, children=None, value=None):
[Link] = name
[Link] = children if children is not None else []
[Link] = value
def evaluate(node):
return [Link]
def is_terminal(node):
return [Link] is not None
def get_children(node):
return [Link]
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 = float('-inf')
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 # Beta cut-off
return max_eval
else:
min_eval = float('inf')
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 # Alpha cut-off
return min_eval
# Create the game tree
D = Node('D', value=3)
E = Node('E', value=5)
F = Node('F', value=6)
G = Node('G', value=9)
H = Node('H', value=1)
I = Node('I', value=2)
B = Node('B', children=[D, E, F])
C = Node('C', children=[G, H, I])
A = Node('A', children=[B, C])
# Run the alpha-beta pruning algorithm
maximizing_player = True
initial_alpha = float('-inf')
initial_beta = float('inf')
depth = 3 # Maximum depth of the tree
optimal_value = alpha_beta_pruning(A, depth, initial_alpha, initial_beta,
maximizing_player)
print(f"The optimal value is: {optimal_value}")
11)8 Queens problem to implement in python?
# Function to print the solution
def print_board(board):
for row in board:
print(' '.join('Q' if cell == 1 else '.' for cell in row))
print()
# Function to check if a queen can be placed on board[row][col]
def is_safe(board, row, col, N):
# Check the column
for i in range(row):
if board[i][col] == 1:
return False
# Check the upper left diagonal
for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
if board[i][j] == 1:
return False
# Check the upper right diagonal
for i, j in zip(range(row-1, -1, -1), range(col+1, N)):
if board[i][j] == 1:
return False
return True
# Function to solve the N-Queens problem using backtracking
def solve_queens(board, row, N):
# If all queens are placed, return True
if row == N:
return True
# Try placing the queen in all columns one by one
for col in range(N):
if is_safe(board, row, col, N):
board[row][col] = 1 # Place the queen
# Recur to place the rest of the queens
if solve_queens(board, row + 1, N):
return True # If placing queen leads to a solution, return True
# Backtrack if placing queen doesn't lead to a solution
board[row][col] = 0 # Remove the queen (backtrack)
return False # No place for queen in this row, return False
# Function to solve the 8-Queens problem and print the solution
def eight_queens(N=8):
# Initialize an empty board with 0s
board = [[0 for _ in range(N)] for _ in range(N)]
# Solve the problem starting from the first row
if solve_queens(board, 0, N):
print_board(board)
else:
print("Solution does not exist.")
# Run the 8 Queens problem
eight_queens()
12) write a program to schedule a meeting among 5 busy persons using
default reasoning. the output should give the time, place and day of the
meeting.
To solve this problem using default reasoning, we'll simulate scheduling a meeting
for 5 busy individuals based on the assumption that certain conditions must hold
true in order to schedule a meeting (i.e., when all the participants are available).
We can follow this outline:
1. Assumptions (i.e., default facts):
o Each person has a set of available times (e.g., hours during the week).
o The default reasoning will pick the first time slot that all participants
have in common.
o We'll assume the meeting place is pre-defined unless another condition
is specified (e.g., virtual vs. in-person).
2. Input: Availability of each person (which days/times they are available).
3. Output: The time, day, and place of the meeting.
from datetime import datetime
Explanation:
1. Person class: Each Person has a name and a list of available_times. The
is_available method checks if the person is available at a specific time.
2. find_meeting_time function: This function takes a list of people and finds the
first common available time slot by comparing the available times for all
participants.
3. Scheduling: The available times of each person are compared, and the first
common time slot is chosen. If no common slot is found, it prints a message
that scheduling is impossible.
4. Meeting Information: The program outputs the time, day, and place of the
meeting. The meeting place is set to "Conference Room A" by default.
program:
# A class to represent each person's availability
class Person:
def __init__(self, name, available_times):
[Link] = name
self.available_times = available_times
def is_available(self, time_slot):
return time_slot in self.available_times
# Function to find the common available time slot
def find_meeting_time(persons):
# Start by considering the first person's available times
common_times = persons[0].available_times
# Find intersection of all available times
for person in persons[1:]:
common_times = [time for time in common_times if
person.is_available(time)]
if common_times:
return common_times[0] # Return the first common available time slot
else:
return None # No common time found
# Define the persons and their available times
person1 = Person("Alice", ["Monday 9am", "Monday 3pm", "Tuesday 9am"])
person2 = Person("Bob", ["Monday 9am", "Tuesday 9am", "Wednesday
3pm"])
person3 = Person("Charlie", ["Monday 9am", "Tuesday 9am", "Thursday
1pm"])
person4 = Person("David", ["Monday 9am", "Wednesday 3pm", "Thursday
1pm"])
person5 = Person("Eve", ["Monday 9am", "Tuesday 9am", "Wednesday
3pm"])
# List of persons
persons = [person1, person2, person3, person4, person5]
# Find the meeting time
meeting_time = find_meeting_time(persons)
if meeting_time:
# Output the result
meeting_day, meeting_hour = meeting_time.split(' ')
meeting_day = meeting_day.capitalize()
print(f"Meeting Scheduled!")
print(f"Time: {meeting_hour}")
print(f"Day: {meeting_day}")
print(f"Place: Conference Room A") # Default place
else:
print("No common time available for all participants.")
13)Unification
def unify(E1, E2):
# Base case: both E1 and E2 are constants or the empty list
if E1 == E2:
return {} # No substitution needed, they are equal
# Case where E1 is a variable
elif isinstance(E1, str) and [Link](): # Assumes variables are lowercase
strings
if E1 in E2: # Check for cyclic unification
return None
else:
return {E1: E2} # E1 is substituted with E2
# Case where E2 is a variable
elif isinstance(E2, str) and [Link](): # Assumes variables are lowercase
strings
if E2 in E1: # Check for cyclic unification
return None
else:
return {E2: E1} # E2 is substituted with E1
# Case where both E1 and E2 are lists (or compound terms)
elif isinstance(E1, list) and isinstance(E2, list):
if len(E1) != len(E2):
return None # Lists must have the same length to unify
# First unify the heads (first elements)
head_subs = unify(E1[0], E2[0])
if head_subs is None:
return None # If unification fails, return None
# Apply the first substitution to the tails (rest of the lists)
tail_E1 = [apply_substitution(head_subs, item) for item in E1[1:]]
tail_E2 = [apply_substitution(head_subs, item) for item in E2[1:]]
# Now unify the tails
tail_subs = unify(tail_E1, tail_E2)
if tail_subs is None:
return None # If unification fails, return None
# Combine the head and tail substitutions
return {**head_subs, **tail_subs}
return None # Return None if no unification is possible
def apply_substitution(subs, term):
"""Apply the substitution to a term."""
if isinstance(term, str) and [Link](): # If it's a variable
return [Link](term, term) # Substitute if a substitution exists
elif isinstance(term, list): # If it's a list, apply substitution to each element
return [apply_substitution(subs, t) for t in term]
else:
return term # Constants are unchanged
# Example usage:
E1 = ['x', 'a']
E2 = ['b', 'a']
result = unify(E1, E2)
print(result) # Expected output: {'x': 'b'}