首页
网站开发
桌面应用
管理软件
微信开发
App开发
嵌入式软件
工具软件
数据采集与分析
其他
首页
>
> 详细
program代写、代做Python/Java程序语言
项目预算:
开发周期:
发布时间:
要求地区:
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 viceversa. (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'))
3
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'))
0
>>> print(task3('cabs.txt', 'ABZD'))
5
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))
True
90.00
>>> print(task3('fruit_ode.txt', 'dict_fruit.txt', 80))
False
50.00
>>> print(task3('amazing_poetry.txt', 'common_words.txt', 95))
True
95.65
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.
>>> print(task4('d', 'cabs.txt', 'common_words.txt', 100, 'ABC', 'y'))
No solution found.
Num nodes expanded: 1000
Max fringe size: 2001
Max depth: 999
First few expanded states:
Bcas cre tcxis.
Acbs cre tcxis.
Bcas cre tcxis.
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, 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
Task 6 - Greedy, A*
In this final task, you should modify your solution to Task 4 to include the greedy and
A* algorithms. The input and output should be in exactly the same format. The only
difference is that the first input can now be d, b, i, u, g or a, where g indicates greedy
search and a indicates A* search. Use the heuristic we developed in Task 5 for these
informed search strategies.
Once you are finished, try running your greedy and A* searches with the following
inputs to decrypt the secret message :
>>> task6('g', 'secret_msg.txt', 'common_words.txt', 90, 'AENOST', 'n')
>>> task6('a', 'secret_msg.txt', 'common_words.txt', 90, 'AENOST', 'n')
软件开发、广告设计客服
QQ:99515681
邮箱:99515681@qq.com
工作时间:8:00-23:00
微信:codinghelp
热点项目
更多
cis432代做、代写python/java程...
2024-05-04
eeen3007j代写、c++程序设计代...
2024-05-04
代写data程序、代做c/c++, jav...
2024-05-04
comp2006代做、代写c++程序语言
2024-05-04
comp26020代做、java/c++设计编...
2024-05-04
csci251 advanced programming...
2024-05-03
cs 6290: high-performance co...
2024-05-03
assignment 2: executing and ...
2024-05-03
ecse427/comp310 programmin...
2024-05-03
cs 452 (fall 22): operating...
2024-05-03
comp9414 23t2 assignment 2 ...
2024-05-03
dpst1091 23t1 assignment 2 ...
2024-05-03
program代做、代写python设计编...
2024-05-03
热点标签
finm8007
comp2006
comp26020
comp1721
eeen3007j
cis432
csci251
comp5125m
com398sust
32022
mth6158
comp328
finn41615
2024
mec302
mgmt3004
mgt7158
com160
as.640.440
econ3016
finm7405
econ7021
fin600
infs4205/7205
mktg2510-
f27sb
csse2310/csse7231
rv32i
eecs 113
comp1117b
cs 412
comp 315
econ7300
comp2017
ecs 116
fit5046
com6511
comp30024
acs341
econ1020
isys3014
acc408
comp1047
csc 256
cs 6347
finm7008
comp34212
csmde21
estr2520
comp285/comp220
mds5130/iba6205
finc6010
is3s665
busi2194
125.785
iom209
msin0041
econ339
cmt218
mast10007
comp5349
ecx2953/ecx5953
bios706
comp3310
mth6150
comp30027
comp20005
eec286
busi2211
bff2401
fnce90046
visu2001
mang6554
finc6001
125785
data423-24s1
engi 1331
fint2100
(520|600).666
can202
cs 61b
mast20029
info20003
stat512
econ3208
cmpsc311
engg1340
ecmt1010
fit5216
basc0003
ee3121
acct2002
comp5313
busi2131
ise529
elec372/472
csit940/csit440
cenv6141
comp3027/comp3927
ftec5580
comp1433
msci223
mark203
en3098
eden1000
ece6483
econ4410
mats16302
cs 6476
com6521
comp222
comp3211
comp10002
csc1002
chc6186
cs 161
comp27112
comp282
swen20003
comm1190
elec9764
acfi3308
acct7101
fin6035
comp2048
geog0163
comp2013
coen 146
dts101tc
sehh2042
comp30023
comp4880/8880
cs 455
07
stat0045.
fil-30023
celen085
psyc40005
math40082
are271
comp9311
ee5311
imse2113
comp 2322
acct2102
fnd109
int102
is3s664
is6153
data4000
accfin5034
fit5212
cs536-s24
fit5225
ecos3006
mes202tc
finc5001
stat3061
csc171
cs1b
7ssmm712
bu.450.760
cs170
comp3411
swen90004
cpt206
comp5313/comp4313—large
bl5611
kxo206
comp532
elec207
kxo151
cs 2820
cpt108
math2319
dts204tc
qm222
comp2511
ccs599
infs1001
mat2355
eeee4123
25721
ifn647
pols0010
hpm 573
qbus6860
comp9417
csci 1100
stat0023
cse340
comp2003j
cs 2550
cs360
fin 3080
ierg 4080
cs6238
cit 594
finm7406
hw6
联系我们
- QQ: 9951568
© 2021
www.rj363.com
软件定制开发网!