import random import math import time import psutil import os from collections import deque class Board: def __init__(self,tiles): self.size = int(math.sqrt(len(tiles))) # defining length/width of the board self.tiles = tiles def execute_action(self,action): new_tiles = self.tiles[:] empty_index = new_tiles.index('0') if action=='l': if empty_index%self.size>0: new_tiles[empty_index-1],new_tiles[empty_index] = new_tiles[empty_index],new_tiles[empty_index-1] if action=='r': if empty_index%self.size<(self.size-1): new_tiles[empty_index+1],new_tiles[empty_index] = new_tiles[empty_index],new_tiles[empty_index+1] if action=='u': if empty_index-self.size>=0: new_tiles[empty_index-self.size],new_tiles[empty_index] = new_tiles[empty_index],new_tiles[empty_index-self.size] if action=='d': if empty_index+self.size < self.size*self.size: new_tiles[empty_index+self.size],new_tiles[empty_index] = new_tiles[empty_index],new_tiles[empty_index+self.size] return Board(new_tiles) class Node: def __init__(self,state,parent,action): self.state = state self.parent = parent self.action = action def __repr__(self): return str(self.state.tiles) def __eq__(self,other): return self.state.tiles == other.state.tiles def generate_puzzle(size): numbers = list(range(size*size)) random.shuffle(numbers) return Node(Board(numbers),None,None) def get_children(parent_node): children = [] actions = ['l','r','u','d'] # left,right, up , down ; actions define direction of movement of empty tile for action in actions: child_state = parent_node.state.execute_action(action) child_node = Node(child_state,parent_node,action) children.append(child_node) return children def find_path(node): path = [] while(node.parent is not None): path.append(node.action) node = node.parent path.reverse() return path def run_bfs(root_node): start_time = time.time() frontier = deque([root_node]) explored = [] count=0 while(len(frontier)>0): cur_node = frontier.popleft() count+=1 explored.append(cur_node) if(goal_test(cur_node.state.tiles)): path = find_path(cur_node) end_time = time.time() return path,count,(end_time-start_time) for child in get_children(cur_node): if child in explored: continue else: frontier.append(child) print("frontier empty") return False def main(): process = psutil.Process(os.getpid()) initial_memory = process.memory_info().rss / 1024.0 initial = str(input("initial configuration: ")) initial_list = initial.split(" ") root = Node(Board(initial_list),None,None) print(run_bfs(root)) final_memory = process.memory_info().rss / 1024.0 print(str(final_memory-initial_memory)+" KB") def goal_test(cur_tiles): return cur_tiles == ['1','2','3','4','5','6','7','8','9','10','11','12','13','14','15','0'] if __name__=="__main__": main() This is working code i need the final solution in the format Moves: RDLDDRR Number of Nodes expanded: 361 TIme Taken: 0.238 Memory Used: 704kb

import random import math import time import psutil import os from collections import deque class Board: def init(self,tiles): self.size = int(math.sqrt(len(tiles))) # defining length/width of the board self.tiles = tiles def execute_action(self,action): new_tiles = self.tiles[:] empty_index = new_tiles.index('0') if action=='l': if empty_index%self.size>0: new_tiles[empty_index-1],new_tiles[empty_index] = new_tiles[empty_index],new_tiles[empty_index-1] if action=='r': if empty_index%self.size<(self.size-1): new_tiles[empty_index+1],new_tiles[empty_index] = new_tiles[empty_index],new_tiles[empty_index+1] if action=='u': if empty_index-self.size>=0: new_tiles[empty_index-self.size],new_tiles[empty_index] = new_tiles[empty_index],new_tiles[empty_index-self.size] if action=='d': if empty_index+self.size < self.sizeself.size: new_tiles[empty_index+self.size],new_tiles[empty_index] = new_tiles[empty_index],new_tiles[empty_index+self.size] return Board(new_tiles) class Node: def init(self,state,parent,action): self.state = state self.parent = parent self.action = action def repr(self): return str(self.state.tiles) def eq(self,other): return self.state.tiles == other.state.tiles def generate_puzzle(size): numbers = list(range(sizesize)) random.shuffle(numbers) return Node(Board(numbers),None,None) def get_children(parent_node): children = [] actions = ['l','r','u','d'] # left,right, up , down ; actions define direction of movement of empty tile for action in actions: child_state = parent_node.state.execute_action(action) child_node = Node(child_state,parent_node,action) children.append(child_node) return children def find_path(node): path = [] while(node.parent is not None): path.append(node.action) node = node.parent path.reverse() return path def run_bfs(root_node): start_time = time.time() frontier = deque([root_node]) explored = [] count=0 while(len(frontier)>0): cur_node = frontier.popleft() count+=1 explored.append(cur_node) if(goal_test(cur_node.state.tiles)): path = find_path(cur_node) end_time = time.time() return path,count,(end_time-start_time) for child in get_children(cur_node): if child in explored: continue else: frontier.append(child) print("frontier empty") return False def main(): process = psutil.Process(os.getpid()) initial_memory = process.memory_info().rss / 1024.0 initial = str(input("initial configuration: ")) initial_list = initial.split(" ") root = Node(Board(initial_list),None,None) print(run_bfs(root)) final_memory = process.memory_info().rss / 1024.0 print(str(final_memory-initial_memory)+" KB") def goal_test(cur_tiles): return cur_tiles == ['1','2','3','4','5','6','7','8','9','10','11','12','13','14','15','0'] if name=="main": main() This is working code i need the final solution in the format Moves: RDLDDRR Number of Nodes expanded: 361 TIme Taken: 0.238 Memory Used: 704kb

Computer Networking: A Top-Down Approach (7th Edition)

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

See similar textbooks

Related questions

Question

100%

import random

import math

import time

import psutil

import os

from collections import deque

class Board:

def __init__(self,tiles):

self.size = int(math.sqrt(len(tiles))) # defining length/width of the board

self.tiles = tiles

def execute_action(self,action):

new_tiles = self.tiles[:]

empty_index = new_tiles.index('0')

if action=='l':

if empty_index%self.size>0:

new_tiles[empty_index-1],new_tiles[empty_index] = new_tiles[empty_index],new_tiles[empty_index-1]

if action=='r':

if empty_index%self.size<(self.size-1):

new_tiles[empty_index+1],new_tiles[empty_index] = new_tiles[empty_index],new_tiles[empty_index+1]

if action=='u':

if empty_index-self.size>=0:

new_tiles[empty_index-self.size],new_tiles[empty_index] = new_tiles[empty_index],new_tiles[empty_index-self.size]

if action=='d':

if empty_index+self.size < self.size*self.size:

new_tiles[empty_index+self.size],new_tiles[empty_index] = new_tiles[empty_index],new_tiles[empty_index+self.size]

return Board(new_tiles)

class Node:

def __init__(self,state,parent,action):

self.state = state

self.parent = parent

self.action = action

def __repr__(self):

return str(self.state.tiles)

def __eq__(self,other):

return self.state.tiles == other.state.tiles

def generate_puzzle(size):

numbers = list(range(size*size))

random.shuffle(numbers)

return Node(Board(numbers),None,None)

def get_children(parent_node):

children = []

actions = ['l','r','u','d'] # left,right, up , down ; actions define direction of movement of empty tile

for action in actions:

child_state = parent_node.state.execute_action(action)

child_node = Node(child_state,parent_node,action)

children.append(child_node)

return children

def find_path(node):

path = []

while(node.parent is not None):

path.append(node.action)

node = node.parent

path.reverse()

return path

def run_bfs(root_node):

start_time = time.time()

frontier = deque([root_node])

explored = []

count=0

while(len(frontier)>0):

cur_node = frontier.popleft()

count+=1

explored.append(cur_node)

if(goal_test(cur_node.state.tiles)):

path = find_path(cur_node)

end_time = time.time()

return path,count,(end_time-start_time)

for child in get_children(cur_node):

if child in explored:

continue

else:

frontier.append(child)

print("frontier empty")

return False

def main():

process = psutil.Process(os.getpid())

initial_memory = process.memory_info().rss / 1024.0

initial = str(input("initial configuration: "))

initial_list = initial.split(" ")

root = Node(Board(initial_list),None,None)

print(run_bfs(root))

final_memory = process.memory_info().rss / 1024.0

print(str(final_memory-initial_memory)+" KB")

def goal_test(cur_tiles):

return cur_tiles == ['1','2','3','4','5','6','7','8','9','10','11','12','13','14','15','0']

if __name__=="__main__":

main()

This is working code i need the final solution in the format

Moves: RDLDDRR
Number of Nodes expanded: 361
TIme Taken: 0.238
Memory Used: 704kb

Write a program which performs a breadth-first search to find the solution to any given
board position for 15 puzzle
Input
The input should be given in the form of a sequence of numbered tiles for initial board
configuration, '0' indicating the empty space (see example below)
Output
1. Moves
2. Number of Nodes expanded
3. Time Taken
4. Memory Used
Example
> 1024573 896 11 12 13 10 14 15
Moves: RDLDDRR
Number of Nodes expanded: 361
Time Taken: 0.238
Memory Used: 704kb
Hint
You can use hashset to keep track of explored nodes and fast lookup

Figure 3.9
function
BREADTH-FIRST-SEARCH(problem)
node + NODE(problem.INITIAL)
if problem.IS-GOAL(node.STATE)
frontiera FIFO queue, with node as an element
reached{problem. INITIAL}
then return node
while not IS-EMPTY(frontier) do
node POP(frontier)
for each child in EXPAND(problem, node) do
s+child.STATE
returns a solution node or failure
if problem.IS-GOAL(s) then return child
if s is not in reached then
add s to reached
add child to frontier
return failure
function UNIFORM-COST-SEARCH(problem) returns a solution node, or failure
return BEST-FIRST-SEARCH(problem, PATH-COST)

Expert Solution

Step 1

Algorithm:

The algorithm for the given program can be summarized as follows:

Initialization: Initialize the state of the problem by defining a class "Board" which takes a list of tiles as input and calculates the size of the board based on the length of the list.
Node Definition: Define a class "Node" which represents the node in the search tree. A node consists of state, parent, and previous action.
Generate Puzzle: Create a random puzzle by generating a list of numbers from 0 to (size*size) - 1 and shuffle the list.
Get Children: Given a parent node, this function generates its children by simulating the four possible actions (left, right, up, down) on the empty tile.
Find Path: Given a node, this function backtracks from the node to the root node to find the solution path.
BFS Function: The function "run_bfs" implements the breadth-first search algorithm. It takes the root node as input and returns the solution path, the number of nodes expanded, and the total time taken. The function uses a deque to implement the frontier, a list to keep track of explored nodes, and the "get_children" function to generate children from the parent node.
Main Function: The main function takes input from the console, calls the "run_bfs" function to solve the puzzle, and shows the output.

Trending now

This is a popular solution!

Step by step

Solved in 4 steps with 4 images

SEE SOLUTION Check out a sample Q&A here