Ai 56

Assignment 5(a)
NAME – Shivam Kumar GROUP NO. –G2

ROLL NO. - 2100270140052
5(a). Solve two jug Problem.
from collections import deque
def BFS(a, b, target):
m = {}
isSolvable = False
path = []
q = deque()
q.append((0, 0))
while (len(q) > 0):
u = q.popleft()
if ((u[0], u[1]) in m):
continue
if ((u[0] > a or u[1] > b or
u[0] < 0 or u[1] < 0)):
continue
path.append([u[0], u[1]])
m[(u[0], u[1])] = 1
if (u[0] == target or u[1] == target):
isSolvable = True
if (u[0] == target):
if (u[1] != 0):
path.append([u[0], 0])
else:
if (u[0] != 0):
path.append([0, u[1]])
sz = len(path)
for i in range(sz):
print("(", path[i][0], ",",
path[i][1], ")")
break
q.append([u[0], b])
q.append([a, u[1]])
for ap in range(max(a, b) + 1):
c = u[0] + ap
d = u[1] - ap
if (c == a or (d == 0 and d >= 0)):
q.append([c, d])
c = u[0] - ap
d = u[1] + ap
if ((c == 0 and c >= 0) or d == b):
q.append([c, d])
q.append([a, 0])
q.append([0, b])
if (not isSolvable):
print("No solution");
if __name__ == '__main__':
Jug1=int(input("Enter the cpacity of jug1 : "));
Jug2=int(input("Enter the capacity of jug2 : "));
target=int(input("Enter the target you want to achive : "));
BFS(Jug1, Jug2, target)
OUTPUT
Enter the cpacity of jug1 : 4
Enter the capacity of jug2 : 6
Enter the target you want to achive : 2
(0,0)
(0,6)
(4,0)
(4,6)
(4,2)
(0,2)
Assignment 5(b)
NAME – Shivam Kumar GROUP NO. – G2

ROLL NO. - 2100270140052
5(b). Implement Tic- Tac-Toe.
import random
class TicTacToe:
def __init__(self):
self.board = []
def create_board(self):
for i in range(3):
row = []
for j in range(3):
row.append('-')
self.board.append(row)
def get_random_first_player(self):
return random.randint(0, 1)
def fix_spot(self, row, col, player):
self.board[row][col] = player
def is_player_win(self, player):
win = None
n = len(self.board)
for i in range(n):
win = True
for j in range(n):
if self.board[i][j] != player:
win = False
break
if win:
return win
for i in range(n):
win = True
for j in range(n):
if self.board[j][i] != player:
win = False
break
if win:
return win
win = True
for i in range(n):
if self.board[i][i] != player:
win = False
break
if win:
return win
win = True
for i in range(n):
if self.board[i][n - 1 - i] != player:
win = False
break
if win:
return win
return False
for row in self.board:
for item in row:
if item == '-':
return False
return True
def is_board_filled(self):
for item in row:
if item == '-':
return False
return True
def swap_player_turn(self, player):
return 'X' if player == 'O' else 'O'
def show_board(self):
for item in row:
print(item, end=" ")
print()
def start(self):
self.create_board()
player = 'X' if self.get_random_first_player() == 1 else 'O'
while True:
print(f"Player {player} turn")
self.show_board()
row, col = list(
map(int, input("Enter row and column numbers to fix spot: ").split()))
print()
self.fix_spot(row - 1, col - 1, player)
if self.is_player_win(player):
print(f"Player {player} wins the game!")
break
if self.is_board_filled():
print("Match Draw!")
break
player = self.swap_player_turn(player)
print()
self.show_board()
tic_tac_toe = TicTacToe()
tic_tac_toe.start()
OUTPUT
Player X turn
---
---
---
Enter row and column numbers to fix spot: 3 3
Player O turn
---
---
--X
Player X turn
O--
---
--X
Player O turn
O-X
---
--X
Player X turn
O-X
--O
--X
Player O turn
O-X
--O
X-X
Player X turn
O-X
-OO
X-X
Player X wins the game!
O-X
-OO
XXX
Assignment 6(a)

ROLL NO. - 2100270140052
6(a). Implement Depth First Search.
graph = {
'6' : ['5','4'],
'4' : ['3', '5'],
'5' : ['7'],
'3' : [],
'7' : ['6'],
'2' : ['5'],
'1' : ['2','3']
}
visited = set()
def dfs(visited, graph, node):

if node not in visited:
print (node)
visited.add(node)
for neighbour in graph[node]:
dfs(visited, graph, neighbour)
print("The Depth-First Search traversal is: ")

dfs(visited, graph, '1')
OUTPUT
The Depth-First Search traversal is:

1
2
5
7
6
4
3
Assignment 6(b)

ROLL NO. - 2100270140052
6(b). Implement Breadth First Search.

from collections import defaultdict as dd
class Graph:
def __init__(self):
self.graph = dd(list)
def addEdgetoGraph(self, x, y):
self.graph[x].append(y)
def BFSearch(self, n):
visited_vertices = ( len(self.graph ))*[False]
queue = []
visited_vertices[n] = True
queue.append(n)
while queue:
n = queue.pop(0)
print (n)
for v in self.graph[ n ]:
if visited_vertices[v] == False:
queue.append(v)
visited_vertices[v] = True
graph = Graph()
graph.addEdgetoGraph(0, 1)
print ( " The Breadth First Search Traversal is : " )
graph.BFSearch(1)
OUTPUT
The Breadth First Search Traversal is :
1
3
2
4
5

Ai 56

Uploaded by

Copyright:

Available Formats

Ai 56

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Ai 56

Uploaded by

Copyright:

Available Formats

Assignment 5(a)

NAME – Shivam Kumar GROUP NO. –G2

NAME – Shivam Kumar GROUP NO. – G2

Player X wins the game!

NAME – Shivam Kumar GROUP NO. – G2

def dfs(visited, graph, node):

print("The Depth-First Search traversal is: ")

The Depth-First Search traversal is:

NAME – Shivam Kumar GROUP NO. – G2

6(b). Implement Breadth First Search.

You might also like