problem is about anagrams pairs of distinct words that contain the same letters.

One example is the pair ALLERGY and LARGELY. By reordering their letters, I can turn one word into the other. Note that the same letter can appear multiple times in each word, such as the letter L appearing twice in each word here. It always has to be the same number for both words. Now let us assume that we want to turn one word of an anagram into the other by a series of steps. In each step, we can remove the last letter in the word and insert it into any other position. For example, we can start with ALLERGY and move its last letter, Y, into the third position, to get ALYLERG. Then we can take another step to modify the new word, and so on, until we reach LARGELY. For example:

ALLERGY move last letter to position 3: ALYLERG move last letter to position 2: AGLYLER move last letter to position 2: ARGLYLE move last letter to position 4: ARGELYL move last letter to position 1: LARGELY complete the following python program, use the A* algorithm to find an optimal(minimum number of steps)solution for a given pair of start and goal words.

(a) Even before applying the A* algorithm, you can already decide whether a given problem is solvable or not. Please add code to anagram_solver to perform this check and terminate to avoid running A* on a problem that has no solution (starting in line 52).

(b) The code already includes a very simple expand function anagram_expand that, for a given state (i.e., the current word), returns a list of pairs, indicating all successor states and their h scores. It is a complete function, i.e., the code is already able to solve some simple problems such as the first two examples at the bottom of the code that you can uncomment to test your function. The code also includes a global counter variable to tell you how many A* iterations were performed to find the solution. However, the given scoring function is extremely simple: It returns 1 if the current state is not a solution and 0 otherwise. Because of this poor function, solving the last two example problems is impossible within a reasonable amount of time. Therefore, your task is to replace the scoring function (lines 12 to 16) so that it can solve problems more efficiently. It does not necessarily have to solve all sample problems but it should at least solve the first two problems with fewer iterations than the original function does. A_stars.py

global num_iterations

def anagram_expand(state, goal): node_list = [] for pos in range(len(state) - 1): # Create each possible state that can be created from the current one in a single step new_state = state[:pos] + state[-1:] + state[pos:-1] # Very simple h' function - please improve! if new_state == goal: score = 0 else: score = 1 node_list.append((new_state, score)) return node_list def a_star(start, goal, expand): global num_iterations open_list = [([start], -1)] while open_list: num_iterations += 1 open_list.sort(key = lambda x: len(x[0]) + x[1]) if open_list[0][1] == 0: return open_list[0][0] ancestors = open_list[0][0] open_list = open_list[1:] new_nodes = expand(ancestors[-1], goal) for (new_state, score) in new_nodes: append_new_node = True for ancestor in ancestors: if new_state == ancestor: # Modified from Assignment #2 solutions to avoid numpy append_new_node = False break if append_new_node: open_list.append((ancestors + [new_state], score)) return []

# Finds a solution, i.e., a placement of all rectangles within the given field, for a rectangle puzzle def anagram_solver(start, goal): global num_iterations num_iterations = 0 #Add code here to check in advance whether the problem is solvable # if ... print('This is clearly impossible. I am not even trying to solve this.') return solution = a_star(start, goal, anagram_expand) if not solution: print('No solution found. This is weird, I should have caught this before even trying A*.') return print(str(len(solution) - 1) + ' steps from start to goal:') for step in solution: print(step) print(str(num_iterations) + ' A* iterations were performed to find this solution.') anagram_solver('CRATE', 'TRACE')

anagram_solver('RESCUE', 'SECURE')

anagram_solver('PREDATOR', 'TEARDROP')

anagram_solver('SCHOOLMASTER', 'THECLASSROOM')