Data Structures | Python | Algorithm代写 – 这是一个基于python的数据结构联系
FIT2004 S2/2018: assignment3
Scrabble 2.
Cindy is upset, very upset. She got to know that you helped Alice for their scrabble game. Cindy: I found out that you helped Alice beat me in scrabble. Congratulations, she won by a big margin. Happy now? I did not expect this from you. You … You: ummmmm, I didnt mean to hurt you. I thought I was just helping a friend. Cindy: And I thought I was your friend too. Anyway, never mind!. You: You ARE my friend Cindy!. Cindy: If so, you have to help me too!. You give up: Okay, tell me how can I make up for this. Cindy smirks: You helped Alice by writing an efficient scrabble helper. You can make up for this by writing a more efficient and more powerful scrabble helper for me. The Algorithmyou write for Task 1 and Task 2 must be optimal so that Alice cannot get more efficient algorithms
c Muhammad Aamir Cheema, Monash University
than those. In addition, I need a functionality which returns me the word with the highest score that can be made using the tiles. You: Ohkay, I willtriemy best. But I will help you on one condition: you will not tell Alice about it. Although I love to solve interesting problems, I dont want to be involved in your rivalry anymore. Cindy: Deal! Thank you so much.
Input
You have been provided with a zipped file namedtester.zipwhich contains all the files you need for the assignment and to run the tester. Your program will take two input files namedDictionary.txtandSocres.txt. Dictionary.txtconsists of over 80,000 words not necessarily in a sorted order. Each word consists of only lowercase English characters, i.e., there is no uppercase letter, whitespace, and hyphen – etc. Below are first few words in the dictionary.
abaca
abacinate
abacination
abaciscus
abacist
aback
Each scrabble tile (English letter) has a score associated with it. The file Scores.txt records the score for each tile. Below are the first few lines fromScores.txt.
a:
b:
c:
d:
e:
f:
Each letter and its score is separated by a colon:, e.g., the scores fora,bandcare 1, 3 and 3, respectively. The scores of tiles are required in Task 3 of the assignment.
Template file
tester.zipalso contains a template file namedscrabble2.pywhich helps you to print the output in the required format. YouMUSTimplement your algorithms in this file within the given functions and youMUSTuse the given print functions to print the output for each task. DO NOTrename this file. The template program also reads the input and iteratively asks for the query strings until the user enters***when the program quits.DO NOTmodify any line below the block with the warning. More details are given within each task. tester.zipalso contains a file namenaive-solution.pywhich contains a naive solution for the assignment. You can refer to this file to see how the template file is to be used. You can also use this file to compare your solution with other test cases.
Task 1: Largest group of anagrams (1 mark)
This task is the same as Task 1 in the assignment 1, i.e., you have to find the largest group of ana- grams in alphabetical order. You must implement your solution in the functionsolve_task1(). This function must return a list that contains anagrams in the largest group in sorted order. For the example input files, it must return a list["astel", "laste", "lates", "least", "satle", "slate", "stale", "steal", "stela", "tales"]. Once the list is returned, the template program will print the results in the required format. Similar to assignment 1, if there is a tie (two or more largest groups have the same size), you can choose to print any group of your choice.However, the words in the group must be in alphabetical order. Complexity Requirement.Note that the size ofScores.txtis constant because there are only 26 English letters. LetTbe the total number of characters in the input fileDictionary.txt. Your algorithm must return the largest group of anagrams inO(T) worst-case time andO(T) worst-case space complexity. For the assignment 1, the requirement wasO(M N) whereN is the number of words andM is the maximum number of characters in any word. Note that O(T)O(M N). Therefore, your solution for assignment 1 was not necessarily optimal. If you solve this task inO(T) space and time complexity, this is optimal because the input size isO(T) and no algorithm can do better (because reading the input itself takesO(T)). Throughout this assignment, we assume that comparing two strings of sizektakesO(k) time.
Task 2: Scrabble words finder (1 mark)
This task is the same as Task 2 of the assignment 1. Specifically, after your program has printed the largest group of anagrams, the template program asks the user to enter a string of letters calledquerystring. Your program must then printall words in the dictionary that can be made usingallletters in the query string. For example, if the query string isalppe, the output will consist of the wordsappel, andapple. Note thatpaleis not in the output because it does not containallof the letters in the query string. Similarly,appealis not in the output because it cannot be made using the input letters, e.g., the input contains only onea. The output must be sorted in alphabetical order. You must implement your solution in the function solve_task2(query). This function must return a list containing, in sorted order, all words that can be made using all letters in the query string, e.g., if query isalppe, the function must return["appel", "apple"]. Once the list is returned, the template program prints it in the required format. Complexity Requirement.For a query string consisting ofkcharacters,solve_task2(query) must return the output inO(k+W) in the worst-case whereW is the output size (i.e., the number of characters in the output). This is optimal because reading the input takesO(k) and writing the output takesO(W) (thus, no algorithm can do better thanO(k+W)). Recall that string comparison (e.g.,str1<str2orstr1 == str2) takesO(k) in the worst-case wherekis the number of characters in the smaller string. You are allowed to use the Data Structuresthat you created to solve the previous task.
Task 3: Finding the word with the highest score (3 marks)
First, we describe how to compute the score of any given word. The score of a word is computed using the scores of the tiles (letters) used in the word. Scores of the tiles/letters are given in the fileScores.txtand the template program reads these scores in a list calledscore_list. In Scrabble, some cells on the boardboost the score of the tile that is placed on that cell. In
addition to the query string, the user will also enter a string representing information for the score boost. This information is entered in the form ofx:ywherexandyare two integers representing that the score ofx-th letter in the word will be boosted (and will becomeytimes its original score). Consider the example of a wordgamewhere the scores of the lettersa,e,g andmare 1, 1, 2, and 3, respectively (as can be seen inScores.txt). If the score boost is2:3, this means the score of the second letter in the word will be 3 times its original score. So the total score ofgameis 2 + (13) + 3 + 1 = 9. If the score boost is1:5(the score of first letter is 5 times its original score), the score ofgamewill be (25) + 1 + 3 + 1 = 15. In this task, the user will enter boost information in addition to the provided query string. A candidate word is a word in the dictionary that can be made using the tiles in the query string. You will have to find the candidate word with the highest score. If two or more words have the highest score, you must break the tie by returning the word that is alphabetically smallest among these words. Assume that the query string isaelpp. The candidate words of this query string are the following: appel, apple, lapp, leap, pale, palp, pape, peal, pela, plea. Note that appeal is NOT a candidate word because it cannot be made using the tiles in query string (because query string has only onea). Assume that the score boost is4:5, i.e., score of the 4-th letter in a word becomes 5 times its original score. The scores of all the candidate words are given below (where the tilesa,e,landphave scores 1, 1, 1, and 3, respectively).
appel = 1 + 3 + 3 + 1×5 + 1 = 13 apple = 1 + 3 + 3 + 1×5 + 1 = 13 lapp = 1 + 1 + 3 + 3×5 = 20 leap = 1 + 1 + 1 + 3×5 = 18 pale = 3 + 1 + 1 + 1×5 = 10 palp = 3 + 1 + 1 + 3×5 = 20 pape = 3 + 1 + 3 + 1×5 = 12 peal = 3 + 1 + 1 + 1×5 = 10 pela = 3 + 1 + 1 + 1×5 = 10 plea = 3 + 1 + 1 + 1×5 = 10
Among the candidate words, lappand palphave the highest score. However, lappis alphabetically smaller. So,lappis to be returned. You need to implement your solution in solve_task3(query, x, y)which takes three parameters:queryis the query string andxandyprovide the information of score boost, e.g., the score of x-th letter of the word must beytimes its original score. The function must return a list containing two values in the form[best_word,score]where the first value is the word with the highest score and the second value is its score. For the above example, your solution must return["lapp",20]. The template program then prints it in the required output format. Consider another example where the query string isanzebanaand the score boost is5: (score of the 5th letter of a word is boosted 3 times). Candidate words areanan, anna, banana, bane, bean, naze, zenanaand their scores are calculated as follows (where the tilesa,b,e,nandzhave scores 1, 3, 1, 1 and 10, respectively.
anan = 1 + 1 + 1 + 1 = 4 anna = 1 + 1 + 1 + 1 = 4 banana = 3 + 1 + 1 + 1 + 1×3 + 1 = 10 bane = 3 + 1 + 1 + 1 = 6 bean = 3 + 1 + 1 + 1 = 6
naze = 1 + 1 + 10 + 1 = 13 zenana = 10 + 1 + 1 + 1 + 1×3 + 1 = 17
The word with the highest score iszenana. So,solve_task3()must return["zenana",17]. Note that, in this example, the score boost5:3applies ONLY to those words that have at least 5 letters, i.e., foranan, the boost is not applicable because its 5th letter does not exist. For the same queryanzebana, if the score boost is3:2, the scores of these words are:
anan = 1 + 1 + 1×2 + 1 = 5 anna = 1 + 1 + 1×2 + 1 = 5 banana = 3 + 1 + 1×2 + 1 + 1 + 1 = 9 bane = 3 + 1 + 1×2 + 1 = 7 bean = 3 + 1 + 1×2 + 1 = 7 naze = 1 + 1 + 10×2 + 1 = 23 zenana = 10 + 1 + 1×2 + 1 + 1 + 1 = 16
Thus, the answer will benaze. So, your function must return["naze",23]. Note that, for some queries, there may be NO candidate words. In this case, your function must return["n/a",0]representing that no word can be made using query tiles. For example, if the query string isbtrqp, your function must return["n/a",0]. Complexity Requirement.Letkbe the number of characters in the query string. You must return the word with the highest score inO(2k.k) in the worst-case. You are allowed to use the data structures that you created to solve the previous tasks. LetM be the total number of candidate words (i.e., the number of words that can be made using the query string). It is relatively easy to solve this task inO(2k.k+M) in the worst-case. If the time complexity of your solution isO(2k.k+M), you will receiveat most 1 .5 marks for this task (out of 3).
Output
Once you correctly implement your solutions in the template program provided, it will produce the output in required format. Below is a sample execution of the programscrabble2.pyon the input filesDictionary.txtandScores.txt. You can assume that the query string will consist of only lowercase characters and will only contain English letters.
The largest group of anagrams: astel, laste, lates, least, satle, slate,
stale, steal, stela, tales
Enter the query string: aelpp
Enter the score boost: 4:
Scores of letters in query: a:1, e:1, l:1, p:
Words using all letters in the query (aelpp): appel, apple
The best word for query (aelpp,4:5): lapp, 20
Enter the query string: ablet
Enter the score boost: 1:
Scores of letters in query: a:1, b:3, e:1, l:1, t:
Words using all letters in the query (ablet): bleat, table
The best word for query (ablet,1:4): bleat, 16
Enter the query string: algorithm
Enter the score boost: 5: Scores of letters in query: a:1, g:2, h:4, i:1, l:1, m:3, o:1, r:1, t:
Words using all letters in the query (algorithm): logarithm
The best word for query (algorithm,5:2): logarithm, 16
Enter the query string: acre
Enter the score boost: 1: Scores of letters in query: a:1, c:3, e:1, r:
Words using all letters in the query (acre): care, race
The best word for query (acre,1:5): care, 18
Enter the query string: esrotz
Enter the score boost: 3: Scores of letters in query: e:1, o:1, r:1, s:1, t:1, z:
Words using all letters in the query (esrotz): zoster
The best word for query (esrotz,3:4): toze, 43
Enter the query string: anzebana
Enter the score boost: 5: Scores of letters in query: a:1, b:3, e:1, n:1, z:
Words using all letters in the query (anzebana):
The best word for query (anzebana,5:3): zenana, 17
Enter the query string: anzebana
Enter the score boost: 3: Scores of letters in query: a:1, b:3, e:1, n:1, z:
Words using all letters in the query (anzebana):
The best word for query (anzebana,3:2): naze, 23
Enter the query string: btrqp
Enter the score boost: 2:
Scores of letters in query: b:3, p:3, q:10, r:1, t:
Words using all letters in the query (btrqp):
The best word for query (btrqp,2:3): n/a, 0
Enter the query string: gamed
Enter the score boost: 1:
Scores of letters in query: a:1, d:2, e:1, g:2, m:
Words using all letters in the query (gamed): madge
The best word for query (gamed,1:3): madge, 15
Enter the query string: ***
See ya!
Reminder/Things to note
Your program will be tested on a different dictionary file and a different scores file. If your solution does not produce correct results even for the sample test cases and sample test files provided, you will lose all marks for that task. YouMUSTwrite your solution in the template file provided so that your program prints the output in the required format. The tester files are also provided so that you can test your solutions. The zipped file that you submit must contain ONLY two files namedscrabble2.py and a PDF file describing your solution (DO NOT submit other files such as tester files, dictio- nary or scores file). Failing to follow the instructions in the assignment will result in penalties being applied. If you have questions about using the template program or tester, feel free to talk to us. If you decide to use in-built Python functions and structures, you must carefully consider their worst-case complexities. For example, inserting/retrieving an element in Python dictio- nary (which uses hashing) takesO(N) in worst-case. Have fun!!!
-=o0o=-
END
-=o0o=-