import heapq class Anagram: num_iterations = 0 def anagram_expand(self, state, goal): node_list = [] for i in range(len(state)): for j in range(i + 1, len(state)): if i == 0: new_state = state[j] + state[i+1:j] + state[i] + state[j+1:] else: new_state = state[:i] + state[j] + state[i+1:j] + state[i] + state[j+1:] if new_state == goal: score = 0 else: score = 0 for s, g in zip(new_state, goal): if s != g: score += 1 node_list.append((new_state, score)) return node_list # def anagram_expand(self, state, goal): # node_list = [] # for pos in range(1, len(state)): # Create each possible state that can be created from the current one in a single step # new_state = state[1:pos + 1] + state[0] + state[pos + 1:] # # TO DO: c. Very simple h' function - please improve! # if new_state == goal: # score = 0 # else: # score = 1 # node_list.append((new_state, score)) # return node_list # TO DO: b. Return either the solution as a list of states from start to goal or [] if there is no solution. def a_star(self, start, goal, expand): frontier = [(0, start)] came_from = {start: None} cost_so_far = {start: 0} f = {start: self.heuristic(start, goal)} while frontier: self.num_iterations += 1 current = heapq.heappop(frontier)[1] if current == goal: return self.reconstruct_path(came_from, current) for neighbor, cost in expand(current, goal): new_cost = cost_so_far[current] + cost if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]: cost_so_far[neighbor] = new_cost priority = new_cost + self.heuristic(neighbor, goal) # f = g + h heapq.heappush(frontier, (priority, neighbor)) came_from[neighbor] = current return [] def heuristic(self, state, goal): score = 0 for s, g in zip(state, goal): if s != g: score += 1 return score def reconstruct_path(self, start_from, current): path = [current] while current in start_from: current = start_from[current] path.append(current) return path[::-1] def solve(self,start, goal): self.num_iterations = 0 str1 = sorted(start.lower()) str2 = sorted(goal.lower()) if str1 != str2: print('This is clearly impossible. I am not even trying to solve this.') return "IMPOSSIBLE" # TO DO: a. Add code below to check in advance whether the problem is solvable # if ... # print('This is clearly impossible. I am not even trying to solve this.') # return "IMPOSSIBLE" self.solution = self.a_star(start, goal, self.anagram_expand) if not self.solution: print('No solution found. This is weird, I should have caught this before even trying A*.') return "NONE" print(str(len(self.solution) - 1) + ' steps from start to goal:') for step in self.solution: print(step) print(str(self.num_iterations) + ' A* iterations were performed to find this solution.') return str(self.num_iterations) if __name__ == '__main__': anagram = Anagram() #anagram.solve('TRACE', 'CRATE') #anagram.solve('TEARDROP', 'PREDATOR') #anagram.solve('THECLASSROOM','SCHOOLMASTER') anagram.solve('ALLERGY', 'LARGELY') Can you please help me with optimal solution for the above code.