# Introduction
You, a diligent student, open this task description, ready for whatever search methods challenge you—
Copyright By PowCoder代写 加微信 powcoder
**Wait, what???????**
You scan the task description, only to find that large sections of it are gibberish!!!
*Ytu’vo etenlly doctdod eho aocroe moaango, nsd ahtuld bo vory, vory prtud tf ytur eorrific aonrch akilla :). Stw ehne ytu’vo fisiahod, wo’d liko et loe ytu is ts nstehor aocroe – wo hnvo n apocinl btsua ftr eho ehroo fnaeoae fisiahora tf ehia naaigsmose! Et aoo if ehne’a ytu, plonao gt et tur diacuaaits btnrd nsd aonrch ftr eho phrnao, “Hi ovorytso! Ehia mighe aoom n bie rnsdtm, bue quirky qutkkna nro quritualy queo!”. If st tso hna nlrondy ptaeod ie, ctsgrneulneitsa, ytu nro eho firae porats et ctmploeo eho naaigsmose! Ytu cns mnko n ptae wieh ehia phrnao et rocoivo ns nwnrd. (Steo ehne, et bo oligiblo, ytur ctdo muae hnvo nlrondy pnaaod nll tf eho nuetmneod eoaea boftro ytu mnko eho ptae). Wo nlat hnvo aoctsd nsd ehird plnco nwnrda. If ytu nro aoctsd et fisiah, plonao mnko n ftlltw up ptae wieh eho phrnao, “Aoctsdod, ehoy nro dofisieoly ste quiseoaaoseinl!”. Aimilnrly, eho ehird plnco phrnao ia, “Cnpybnrna nro nlat oxcollose ctseosdora, bue stehisg bonea eho qutkkn.” Ngnis, plonao romombor ytu muae hnvo pnaaod nll eoaea boftro mnkisg ehoao ptaea. Nwnrda will bo givos nfeor eho naaigsmose dondliso. If ytu nros’e firae, aoctsd tr ehird et fisiah, dts’e wtrry! Ytu’vo aeill dtso ns nmnzisg jtb, nsd nro vory wolctmo et ndd ytur tws ctmmose nbtue eho naaigsmose (tr qutkkna) et eho ptae et ctseisuo eho fus. Nlat, if ytu hnvo nsy quoaeitsa nbtue nsy tf etpica wo’vo ctvorod is ehia enak (tr is eho cturao is gosornl), wo’ro nlwnya horo et nsawor, at plonao juae loe ua kstw. Wo ronlly htpo ytu’vo osjtyod eho naaigsmose, nsd lonrse n lte nbtue nll kisda tf aonrch moehtda. Ctsgrneulneitsa ngnis, nsd koop up eho grone wtrk! :)*
**Noooooooo!**
What were the teaching team thinking? How are you supposed to do your assignment when you can’t even read it? (You didn’t ask for a task de**crypt**ion!!)
As you are thinking this, something suddenly occurs to you. You are an AI student now. You’ve studied search methods, and if anyone can solve this mystery, it’s definitely you! 😊
So get ready – it’s time to crack this silly cipher!
**Deadline:** 11:59pm, 8th April 2022 (Friday Week 7)
Late submissions are allowed up until 3 days after the deadline. A penalty of 5% per day late will apply. Assignments more than 3 days late will not be accepted (i.e. will receive 0 marks). The cut-off time for a day is 11:59pm.
**Marking:** The assignment is out of 12 marks, and counts for 12% of your final course mark. All marking is automated through Grok.
**Groups:** Not permitted. This assessment must be completed individually.
**Language:** Your implementation must be written in Python
**Submission:** Submissions must be made through the online submission system Grok. This assignment has 6 parts, for which there are 6 separate problems in this Grok module. Submit your solution for each part to the relevant problem page. Each part has its own testcases. Note that Grok requires you to run your solution to each problem before it will allow you to make a submission.
In this assignment, we will investigate and implement six search algorithms from class: **DFS**, **BFS**, **IDS**, **UCS**, **Greedy Search** and **A\* Search**. We will be applying these algorithms to decode secret messages and, in the process, we will learn about their strengths and weaknesses (and hopefully have a little fun! 😊). In the end, we will aim to decode the large secret message in the assignment introduction!
The 6 tasks of this assignment are designed to incrementally guide us through the problem. In **Task 1**, we will explore how the secret messages are made. In **Tasks 2-3**, we will then discuss how decryption can be viewed as a search problem, and we will set up some important tools for later (i.e. a child generator and a goal test). **Task 4** will involve implementing our uninformed strategies (DFS, BFS, IDS and UCS respectively). After this, we will be ready to move on to informed strategies! In **Task 5**, we will begin by setting up an interesting heuristic based on letter frequencies. We will then use this heuristic in **Task 6** to implement Greedy and A* Search.
We strongly recommend you complete the tasks for this assignment in order. Later tasks will make use of work you did in earlier tasks, so it is a good idea to submit your solution to each task and check that it works properly before proceeding to the next one. You are allowed to copy the code you used in earlier tasks for your solutions to later ones (although of course you are not allowed to copy someone else’s code).
We have provided many visible tests to help you check your work, but there will also be some hidden tests, so it is important to also test your own code. If you have any questions, please feel free to ask on the discussion board. 😊
Good luck, and we hope you enjoy the assignment!
Please read the University policy on [Academic Honesty](https://sydney.edu.au/students/academic-integrity.html) very carefully.
Plagiarism (copying from another student, website or other sources), making your work available to another student to copy, engaging another person to complete the assignments instead of you (for payment or not) are all examples of academic dishonesty. Note that when there is copying between students, both students are penalised – the student who copies and the student who makes his/her work available for copying.
The University penalties are severe and include: 1) a permanent record of academic dishonesty on your student file, 2) mark deduction, ranging from 0 for the assignment to Fail for the course and 3) expulsion from the University and cancelling of your student visa. In addition, the Australian Government passed new legislation in 2019 ([Prohibiting Academic Cheating Services Bill](https://www.aph.gov.au/Parliamentary_Business/Bills_Legislation/Bills_Search_Results/Result?bId=r6483)) that makes it a criminal offence to provide or advertise academic cheating services – the provision or undertaking of work for students which forms a substantial part of a student’s assessment task.
Do not confuse legitimate co-operation and cheating! You can discuss the assignment with another student, this is a legitimate collaboration, but you cannot complete the assignment together – this is an individual assignment and everyone must write their own code.
To detect code similarity in this assignment, we will use Grok’s plagiarism detection system, which is extremely good. If you cheat, the chances that you will be caught are very high. Be smart and don’t risk your future or break the law by engaging in plagiarism and academic dishonesty!
# Task 1 – Secret Messages
Can you guess what the encoded message below says?
*Tha rein in Spein fells meinly in tha mounteins, not pleins*
If you got it, nice work! If not, don’t worry – you’ll have a program to do this very soon! The answer is, “The rain in Spain falls mainly in the mountains, not plains”, and we can get this by replacing all of the e’s in the encoded message with a’s, and vice-versa. (i.e. **A ↔ E**)
Let’s try another one. Can you guess what the message below says?
*I lofe ctudying artivisial intelligense*
This one is harder, because there are two pairs of swapped letters: **V ↔ F** and **S ↔ C**. If we reverse these swaps, then the answer is, “I love studying artificial intelligence”, (which we really hope is true! ). One more puzzle: if you start with the message, “Cabs are taxis.”, and you apply the swaps **A ↔ B**, and then **B ↔ C**, what encoded message would you get?
The answer is, “Bcas cre tcxis”
– Start: Cabs are taxis
– Swap **A ↔ B**: Cbas bre tbxis (adjust colour)
– Swap **B ↔ C**: Bcas cre tcxis (adjust colour)
Notice that the encoded messages so far still resemble the original message, because we haven’t swapped many letters. However, if we continue to add swaps, the messages will become harder to read, so it would be nice to have a program to help us out.
For this task, you will write a function to encode and decode messages using the above letter swapping method (which is the how the secret message in the introduction was encoded). The function should have three parameters:
1. A string specifying the *key* (i.e. the sequence of letter swaps). For example, “AEGHAG”, would mean we should apply the swaps **A ↔ E**, **G ↔ H**, then **A ↔ G** if we’re encoding, or the reverse (**A ↔ G**, **G ↔ H**, then **A ↔ E**) if we’re decoding. Note that “AEGHAG” is the same as “EAGHAG”, since **A ↔ E** is the same as **E ↔ A**.
2. The name of a text file containing the message to be encoded or decoded.
3. Either ‘e’ or ‘d’ indicating whether to encode or decode, respectively.
The function will return the resulting encoded or decoded message as a string, with capitalisation, punctuation and spacing preserved. Here are some example calls to the function:
>>> print(task1(‘AE’, ‘spain.txt’, ‘d’))
The rain in Spain falls mainly in the mountains, not plains.
>>> print(task1(‘VFSC’, ‘ai.txt’, ‘d’))
I love studying artificial intelligence.
>>> print(task1(‘ABBC’, ‘cabs_plain.txt’, ‘e’))
Bcas cre tcxis.
# Task 2 – Search Space
Congratulations! We can now encrypt and decrypt messages if we have the key (i.e. the sequence of letters to swap). However, what happens if we don’t have the key? Well, as the name of this assignment suggests, we’ll have to search for one! In this task, we’ll look at how we can represent our search space as a tree and we’ll also work on a program to generate child nodes for that tree. This will be very helpful when we come to implement our search algorithms later.
Before starting, let’s revise the key elements of a search problem from the lecture slides:
Figure 1: The four elements of search problem formulation (COMP3308/3608 W2 slides)
In our case, the initial state is the encrypted message. Can you work out what each of the other elements (i.e. goal state, operators and path cost function) should be?
The answers are—wait! Are you sure you want to read on? Thinking about these questions is a great exercise (and helpful for the exam 😊). If yes, the answers are as follows: 1) the goal state is the decoded message, 2) the operators are the letter swaps (e.g. A ↔ E), since these transform messages into other messages and 3) the path cost is the number of letter swaps (e.g. if we applied A ↔ E, then E ↔ B, that would have a cost of 2.
Now that we have formulated our search problem, we can start setting up tools to help us with the search. In this task, you will write a function to find all of the successors of a state in our search space, given a set of allowed letters to swap. The function should have two parameters:
1. The name of a text file containing the parent state
2. A string containing all letters that are allowed to be swapped. For example, “ABC� would mean A ↔ B, A ↔ C and B ↔ C are allowed, but nothing else. Note that we are adding this condition so we can make the state space smaller, which will help with debugging. This will also be useful when we come to decoding the secret message.
The function will return a string which includes the number of successor states, followed by a list of these states separated by lines. The successors should be generated by applying the allowed operators in alphabetical order. For example, all of the A swaps (e.g. A ↔ B, A ↔ C, A ↔ D… etc.) should come before the B swaps (e.g. B ↔ C, B ↔ D, B ↔ E etc.). Additionally, A ↔ B should come before A ↔ C., since B comes before C. There is no need to include repeats (e.g. we don’t need B ↔ A, since it is the same as A ↔ B), or operators that do nothing (e.g. A ↔ A always does nothing, and A ↔ B does nothing if the message doesn’t contain any A’s or B’s). Some examples are given below.
>>> print(task2(‘spain.txt’, ‘ABE’))
Thb rein in Spein fells meinly in thb mounteins, not pleins.
The rain in Spain falls mainly in the mountains, not plains.
Tha rbin in Spbin fblls mbinly in tha mountbins, not plbins.
>>> print(task2(‘ai.txt’, ‘XZ’))
>>> print(task3(‘cabs.txt’, ‘ABZD’))
Acbs cre tcxis.
Bcds cre tcxis.
Bczs cre tcxis.
Dcas cre tcxis.
Zcas cre tcxis.
**Note:** you can adapt your code from Task 1 to help you here.
# Task 3 – Goal
Excellent work! Now that we have our successor state program, we’re almost ready to search! We just need one more ingredient – a goal test! In this task, you will write a function to check if a given message is valid English, by comparing it to a common English word list. The function should take three **inputs**:
1. The name of a text file containing the message
2. The name of a text file containing a list of words, in alphabetical order and each on a separate line, which will act as a dictionary of correct words
3. A threshold, t, specifying what percentage of words must be correct for this to count as a goal (given as an integer between 0 and 100). The threshold is important, because we may need a buffer if our dictionary is missing words, or there are some misspelt words in the message.
The function should return a string containing two lines of text. The first line should be “True” if at least t% of the words in the message are correct according to the dictionary and “False” otherwise. The second line should be the percentage of words that were correct, to 2 decimal places (round off any further decimal places; 0.005 rounds up to 0.01). Some examples are given below.
>>> print(task3(‘jingle_bells.txt’, ‘dict_xmas.txt’, ’90’))
>>> print(task3(‘fruit_ode.txt’, ‘dict_fruit.txt’, ’80’))
>>> print(task3(‘amazing_poetry.txt’, ‘common_words.txt’, ’95’))
Dictionary matching is case insensitive; if the dictionary contained only the word ‘apple’, then ‘Apple’, ‘apple’, and ‘aPPle’ in the message should all count as correct words according to the dictionary. Words are separated by whitespace (space and newline characters).
# Task 4 – DFS, BFS, IDS, UCS
Fantastic! We now have tools to help us generate children and to perform goal checks. In this task, you will now combine all your work so far to write a function to perform uninformed searches. It should take six **inputs**:
1. A character (d, b, i or u) specifying the algorithm (DFS, BFS, IDS and UCS, respectively)
2. The name of a text file containing a secret message
3. The name of a text file containing a list of words, in alphabetical order and each on a separate line, which will act as a dictionary of correct words
4. A threshold, t, specifying what percentage of words must be correct for this to count as a goal (given as an integer between 0 and 100).
5. A string containing the letters that are allowed to be swapped
6. A character (y or n) indicating whether to print the messages corresponding to the first 10 expanded nodes.
It should then perform DFS, BFS, IDS or UCS to search for a decryption to the given message, reusing your code from previous tasks if you would like to. Note that children should be generated in the same **order** as in Task 2, and you do not need to handle cycles. In the case of UCS, if two nodes have the same priority for expansion, you should expand the node that was added to the fringe first, first. Additionally, you should stop the search if 1000 nodes have been expanded without finding a solution.
The function should **return** a string. This string must contain the following information, in order:
1. The decrypted message, key for generating that message and the path cost, if a solution was found. If no solution was found, the program should print, “No solution found.”
2. The number of nodes expanded during the search. Note that the start node counts as an expanded node and, in the case of IDS, the final expanded node count should be the sum of the expanded node counts on each iteration.
3. The maximum number of nodes in the fringe at the same time during the search
4. The maximum search depth reached. That is, the depth of the deepest expanded node. Note that the start node has a depth of 0, and its children have depths of 1.
5. (If indicated with y) the messages corresponding to the first 10 expanded nodes in the search. If less than 10 nodes were expanded, it should print all expanded nodes.
Some examples of function calls and results are given below.
Bcas cre tcxis.
Cabs are taxis.
>>> print(task4(‘i’, ‘cabs.txt’, ‘common_words.txt’, 100, ‘ABC’, ‘y’))
Solution: Cabs are taxis.
Path Cost: 2
Num nodes expanded: 9
Max fringe size: 5
Max depth: 2
First few expanded states:
Bcas cre tcxis.
Bcas cre tcxis.
Acbs cre tcxis.
Bacs are taxis.
Cbas bre tbxis.
Bcas cre tcxis.
Acbs cre tcxis.
Bcas cre tcxis.
Cabs are taxis.
# Task 5 – Heuristics
How exciting! We’ve programmed our very own search algorithms! As a reward, here’s a secret: the message in the introduction was generated by only swapping the letters, “A”, “E”, “N”, “O”, “S” and “T”!
But there’s a problem: if we try running our task 4 program using just these letters, we’ll find that none of our four search algorithms actually reaches a solution. We’re going to need something more efficient, so let’s try some informed search strategies. We need a heuristic. 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](https://en.wikipedia.org/wiki/Frequency_analysis), and it can be applied even when the message has no spaces, punctuation or capitalisation).
According to [this table](https://en.wikipedia.org/wiki/Letter_frequency#Relative_frequencies_of_letters_in_other_languages), 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 string (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 TAEON
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com