This assignment is about anagrams, which are pairs of distinct words that contain the same letters. One example is the pair ALLERGY and LARGELY. By reordering their letters, we 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 first letter in the word and insert it into any other position. For example, we can start with ALLERGY, remove its first letter, A, and insert it into the fourth position of the new word to get LLEARGY. Then we can take another step to modify the new word, and so on until we reach LARGELY. For example: ALLERGY move the first letter to position 4: LLEARGY move the first letter to position 6: LEARGLY move the first letter to position 2: ELARGLY move the first letter to position 5: LARGELY We want to use the A* algorithm to find an optimal (minimum number of steps) solution for a given pair of start and goal words. For this purpose, please start with the attached file assignment1.py which includes the base code. (10 pts) 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