Answer must be in python. Consider the example of a breadth-first traversal give

Question

Answer must be in python.

Consider the example of a breadth-first traversal given in Figure 8.17.
Using the annotated numbers from that figure, describe the contents of
the queue before each pass of the while loop in Code Fragment 8.14. To
get started, the queue has contents {1} before the first pass, and contents
{2,3,4} before the second pass.

Code Fragment 8.14:

#Algorithm for performing a breadth-first traversal of a tree

Algorithm breadthfirst(T):
Initialize queue Q to contain T.root( )
while Q not empty do
p = Q.dequeue( ) {p is the oldest entry in the queue}
perform the “visit” action for position p
for each child c in T.children(p) do
Q.enqueue(c) {add p’s children to the end of the queue for later visits}

Figure 8.17:

Explanation / Answer

Contents of Queue as per The Given Figure :
Before 1st Pass: {1}

Before 2nd Pass: {2, 3, 4}

Before 3rd Pass: {3, 4, 5, 6,}

Before 4th Pass: {4, 5, 6, 7, 8, 9, 10, 11}

Before 5th Pass: {5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}

Before 6th Pass: {6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}

Before 7th Pass: {7, 8, 9, 10, 11, 12, 13, 14, 15, 16}

Before 8th Pass: {8, 9, 10, 11, 12, 13, 14, 15, 16}

Before 9th Pass: {9, 10, 11, 12, 13, 14, 15, 16}

Before 10th Pass: {10, 11, 12, 13, 14, 15, 16}

Before 1th Pass: {11, 12, 13, 14, 15, 16}

Before 12th Pass: {12, 13, 14, 15, 16}

Before 13th Pass: {13, 14, 15, 16}

Before 14th Pass: {14, 15, 16}

Before 15th Pass: {15, 16}

Before 16th Pass: {16}

Here is the Code In Python :

import random
user_side = ''
machine_side = ''
null = ''
new = ['','','','','','','','','']

def sign_val(user_side, machine_side):
user_side = raw_input("Which Team you want to play with ? X or O ?")
while user_side not in ('x','X','o','O'):
print "Wrong Choice!"
user_side = raw_input("Which Team you want to play with ? X or O ")
if user_side == 'x' or user_side == 'X':
print "Ok, 'X' is yours side!"
machine_side = 'o'
else:
print "Ok, 'O' is yours side!"
machine_side = 'x'
return user_side.upper(), machine_side.upper()
  
  
def decide_turn_side():
turn_side = None
while turn_side not in ('y','Y','n','N'):
turn_side = raw_input("Do you want to go first? ")
if turn_side == 'y' or turn_side == 'Y':
return 1
elif turn_side == 'n' or turn_side == 'N':
return 0
else:
print "its a wrong choice."

def draw_game(a):
  
print " ",a[0],"|",a[1],"|",a[2]
print " ", "--------"
print " ",a[3],"|",a[4],"|",a[5]
print " ", "--------"
print " ",a[6],"|",a[7],"|",a[8], " "

def congo_user_side():
print "You won the game !!!"

def congo_machine_side():
print "Hahaha, I won the game!!!!"

def user_side_first(user_side, machine_side, new):
while winn(user_side, machine_side, new) is None:
move = user_side_move(user_side, new)
new[int(move)] = user_side
draw_game(new)
if winn(user_side, machine_side, new) != None:
break
else:
pass
print "umm...i'll take the move."
p_move = machine_side_move(user_side, machine_side, new)
print p_move
new[int(p_move)] = machine_side
draw_game(new)
q = winn(user_side, machine_side, new)
if q == 1:
congo_user_side()
elif q == 0:
congo_machine_side()
else:
print "Its tie user_side..."

def machine_side_first(user_side, machine_side, new):
while not winn(user_side, machine_side, new):
print "i'll take the move."
p_move = machine_side_move(user_side, machine_side, new)
print p_move
new[p_move] = machine_side
draw_game(new)
if winn(user_side, machine_side, new) != None:
break
else:
pass
move = user_side_move(user_side, new)
new[int(move)] = user_side
draw_game(new)
q = winn(user_side, machine_side, new)
if q == 1:
congo_user_side()
elif q == 0:
congo_machine_side()
else:
print "It's tie user_side..."

def winn(user_side, machine_side, new):
ways = ((0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6))
for i in ways:
if new[i[0]] == new[i[1]] == new[i[2]] != null:
winner = new[i[0]]
if winner == user_side:
return 1
elif winner == machine_side:
return 0
if null not in new:
return 'TIE'
if null not in new:
return 'TIE'
return None

def user_side_move(user_side, new):
a = raw_input("where you want to go next? ")
while True:
if a not in ('0','1','2','3','4','5','6','7','8'):
print "Sorry, wrong move"
a = raw_input("where you want to go next? ")
elif new[int(a)] != null:
print "Sorry, place is already taken !"
a = raw_input("where you want to go next? ")
else:
return int(a)

  
def machine_side_move(user_side, machine_side, new):
best = [4, 0, 2, 6, 8]
blank = []
for i in range(0,9):
if new[i] == null:
blank.append(i)
  
for i in blank:
new[i] = machine_side
if winn(user_side, machine_side, new) is 0:

return i
new[i] = null

for i in blank:
new[i] = user_side
if winn(user_side, machine_side, new) is 1:

return i
new[i] = null

return int(blank[random.randrange(len(blank))])
  

  
def main(user_side, machine_side, new):
  
print "so lets begin the game !"
a = sign_val(user_side, machine_side)
user_side = a[0]
machine_side = a[1]
b = decide_turn_side()
if b == 1:
print "Ok, you got the first turn!"
print "Lets get started, heres a new board!"
draw_game(new)
user_side_first(user_side, machine_side, new)
elif b == 0:
print "Ok, I got the first turn!"
print "So, lets start.."
draw_game(new)
machine_side_first(user_side, machine_side, new)
else:
pass

main(user_side, machine_side, new)
raw_input("press Enter to exit the game")

Thanks.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.