Task 5 - Heuristics
In this task, we will start by developing a heuristic based on the frequency of English letters. This is the idea: imagine you counted the frequencies of the letters in the secret message and found that X was most common. Then, you counted the frequencies of letters in normal English texts, and found that E was most common. Could you guess what X in the secret message stood for? (Yes! E!) We will use this idea when developing our heuristic.
(By the way, the process of comparing letter frequencies to decrypt messages is called frequency analysis, and it can be applied even when the message has no spaces, punctuation or capitalisation).
According to this table, if we sort the English letters from most frequent to least frequent, we get E T A O I N S H R D L… If we limit that to just the letters A E N O S and T (which are the only ones swapped in the secret message), then the ordering becomes E T A O N S. Your task is to write a function that compares this theoretical ordering to the letter ordering in a given message, then estimates how many letter swaps would be needed to make them the same. The function should take two inputs:
1. The name of a text file containing the message
2. A boolean (either True or False) indicating whether this message corresponds to a goal node. (We need this because, to be valid, a heuristic must always estimate the cost at a goal node to be 0)
The program should output 0 if this is a goal node. Otherwise, it should count how many times the letters A, E, N, O, S, and T occur in the message and sort them from most common to least common. For example, if T was the most common letter in the message, followed by E, then O, then A, then S, then N, then the sorted string would be TEOASN. Note that, if two letters have the same frequency, you should use alphabetical order to break ties (e.g. A comes before E).
The program should then compare this sorted string to the theoretical goal (ETAONS) and count how many letters are in the wrong place. For example, all 6 letters are in the wrong place in TEOASN, but only three are wrong for TAEONS. Finally, the output heuristic value should be ceiling(n/2), where n is the number of letters out of place, and the ceiling function rounds up to the nearest integer. Thus we roughly estimate how many swaps we need to make the ordering the same. Some example function calls and results are given below.
>>> print(task5('freq_eg1.txt', False))
3
>>> print(task5('freq_eg1.txt', True))
0
>>> print(task5('freq_eg2.txt', False))
2