May-09-2022, 03:23 PM
Hi I wonder if anyone could help me with this issue. So I am doing the pancake flip and I am trying to get the end result as
1b2w3b4b| g:0, h:0 4w|3w2b1w g:4, h:4 4b3w|2b1w g:5, h:4 3b|4w2b1w g:7, h:4 3w4w|2b1w g:8, h:4 4b3b2b1w| g:10, h:4 1b|2w3w4w g:14, h:0 1w2w3w4w g:15, h:0with this input
1b2w3b4b-aHowever, I am getting this instead
1b2w3b4b| g:0, h:4 4w|3w2b1w g:4, h:4 4b3w|2b1w g:5, h:4 3b|4w2b1w g:7, h:4 3w4w|2b1w g:8, h:4 4b3b2b1w| g:10, h:4 1b|2w3w4w g:14, h:1 1w2w3w4w g:15, h:0I wonder if anyone could help me correcting this? Thanks
from heapq import heappop as hpop
from heapq import heappush as hpush
from queue import Queue
from copy import deepcopy as dp
FIRST_INDEX = 1
class A_Star_Node:
def __init__(self, pancake_stack, head, index=None, flip_cost=None):
self.pancake_stack = pancake_stack
self.head = head
self.prev_flip = index
self.g_value = flip_cost + index
if self.pancake_stack[3][1] != 'w' or self.pancake_stack[3][0] != 4:
self.heuristic = 4
elif (self.pancake_stack[2][1] != 'w') or (self.pancake_stack[2][0] != 3):
self.heuristic = 3
elif (self.pancake_stack[1][1] != 'w') or (self.pancake_stack[1][0] != 2):
self.heuristic = 2
elif (self.pancake_stack[0][1] != 'w') or (self.pancake_stack[0][0] != 1):
self.heuristic = 1
else:
self.heuristic = 0
if self.pancake_stack[3][1] != 'w' or self.pancake_stack[3][0] != 4:
self.flip_value = self.g_value + 4
elif (self.pancake_stack[2][1] != 'w') or (self.pancake_stack[2][0] != 3):
self.flip_value = self.g_value + 3
elif (self.pancake_stack[1][1] != 'w') or (self.pancake_stack[1][0] != 2):
self.flip_value = self.g_value + 2
elif (self.pancake_stack[0][1] != 'w') or (self.pancake_stack[0][0] != 1):
self.flip_value = self.g_value + 1
else:
self.flip_value = self.g_value + 0
def flip(self, index):
stack_copy = dp(self.pancake_stack)
pancake_stack = stack_copy[:index]
pancake_stack.reverse()
for pancake in stack_copy[:index]:
if pancake[1] == 'b':
pancake[1] = 'w'
elif pancake[1] == 'w':
pancake[1] = 'b'
first_half_stack = stack_copy[index:]
pancake_stack = pancake_stack + first_half_stack
return pancake_stack
def __gt__(self, next_pancake):
index_num_list = dp(self.pancake_stack)
next_index_num = dp(next_pancake.pancake_stack)
i = 0
while i < 4:
if not next_index_num[i][1]:
next_index_num[i][1] = 'w'
else:
next_index_num[i][1] = True
if not index_num_list[i][1]:
index_num_list[i][1] = 'w'
else:
index_num_list[i][1] = True
i += 1
def flipping_step(self, location):
output_pancake = ''
spatula_index = FIRST_INDEX
for size, orientation in self.pancake_stack:
x = str(size) + orientation
output_pancake += x
if location == spatula_index:
output_pancake = output_pancake + str('|')
spatula_index += 1
return output_pancake
def print_flipped_steps(self):
str_self = str(self)
cost_str = ' g:' + str(self.g_value) + ', h:' + str(self.heuristic)
next_step = str_self + cost_str
while self.head is not None:
location = self.prev_flip
self = self.head
cost_str = ' g:' + str(self.g_value) + ', h:' + str(self.heuristic)
x = cost_str + '\n' + next_step
next_step = self.flipping_step(location) + x
print(next_step)
def __str__(self):
stack_str = ''
for i, j in self.pancake_stack:
x = str(i) + j
stack_str += x
return stack_str
def A_Star_Search_Algorithm(stack):
x = 0
y = 0
root = A_Star_Node(stack, None, x, y)
pancake_stack = list()
z = (root, root)
hpush(pancake_stack, z)
visited = set()
while pancake_stack is not None:
k = hpop(pancake_stack)
current_node = k[1]
goal_state = current_node.pancake_stack
if str(goal_state) not in visited:
if goal_state != [[1, 'w'], [2, 'w'], [3, 'w'], [4, 'w']]:
i = 1
while i < 5:
child_stack = current_node.flip(i)
m = current_node.g_value
child_Node = A_Star_Node(child_stack, current_node, i, m)
f = child_Node.flip_value
x = (f, child_Node)
hpush(pancake_stack, x)
i = i + 1
y = str(current_node.pancake_stack)
visited.add(y)
else:
current_node.print_flipped_steps()
break
class Breadth_First_Search_Node:
def __init__(self, stack=None, head=None, index=None):
self.stack = stack
self.head = head
self.prev_node = index
def flip(self, index):
stack_copy = dp(self.stack)
pancake_stack = stack_copy[:index]
pancake_stack.reverse()
for pancake in stack_copy[index:]:
if pancake[1] == 'b':
pancake[1] = 'w'
elif pancake[1] == 'w':
pancake[1] = 'b'
pancake_stack = pancake_stack + stack_copy[index:]
return pancake_stack
def print_flipped_steps(self):
next_flipped = str(self)
while self.head != None:
location = self.prev_node
self = self.head
stack_str = ''
i = FIRST_INDEX
for i, j in self.stack:
x = str(i) + str(j)
stack_str = stack_str + x
if location == i:
stack_str += '|'
i += 1
x = stack_str
next_flipped = x + '\n' + next_flipped
print(next_flipped)
def __str__(self):
output = ''
for cost, orientation in self.stack:
y = str(cost)
x = y + orientation
output = output + x
return output
def breadth_first_search_algorithm(stack):
root = Breadth_First_Search_Node(stack)
queue_fringe = Queue()
queue_fringe.put(root)
visited_pancake = set()
while queue_fringe.empty() is False:
current_node = queue_fringe.get()
pancake = str(current_node.stack)
if pancake not in visited_pancake:
if current_node.stack != [[1, 'w'], [2, 'w'], [3, 'w'], [4, 'w']]:
i = 1
while i < 5:
x = Breadth_First_Search_Node(current_node.flip(i), current_node, i)
queue_fringe.put(x)
i = i + 1
pancake = str(current_node.stack)
visited_pancake.add(pancake)
else:
current_node.print_flipped_steps()
break
def moodle_input():
user_input = list(input())
stack_pancake = []
i = 0
while i < 4:
size = user_input.pop(0)
x = int(size)
search_type = user_input.pop(0)
pancake = [x, search_type]
stack_pancake.append(pancake)
i += 1
user_input.pop(0)
search_type = user_input.pop(0)
if search_type == 'a':
A_Star_Search_Algorithm(stack_pancake)
elif search_type == 'b':
breadth_first_search_algorithm(stack_pancake)
moodle_input()
