/
Problems.rtf
31 lines (23 loc) · 4.09 KB
/
Problems.rtf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
{\rtf1\ansi\ansicpg1252\deff0\nouicompat{\fonttbl{\f0\froman\fcharset0 Times-Roman;}{\f1\fnil\fcharset2 Symbol;}}
{\*\generator Riched20 6.3.9600}\viewkind4\uc1
\pard\b\f0\fs48\lang22 Problem 1 \par
\b0\fs32 Modify your printStringsWithValues method to print out the Strings in descending order of WWF values. At the end, it should also print out the size of the list. You can see examples of it being called in my output.txt file.\b\fs48\par
Problem 2 \par
\b0\fs32 Write a method\par
\pard{\pntext\f1\'B7\tab}{\*\pn\pnlvlblt\pnf1\pnindent0{\pntxtb\'B7}}\fi-720\li720\tx220\tx720 public static ????? getKey(String s)\par
\pard that returns a key of a type that is for you to determine. The key should be the same for any two strings that have the exact same characters. If two strings have different characters, then they should have different keys. For example, "bat","tab","bta" would all return the same key, but "bat" and "bata" would return different keys. Your method should have comments that briefly explain your key. There are many valid object types that it could return. It might be easiest if you use a familiar class like String or Integer. \par
\b\fs48 Problem 3 \par
\b0\fs32 Write a method\par
\pard{\pntext\f1\'B7\tab}{\*\pn\pnlvlblt\pnf1\pnindent0{\pntxtb\'B7}}\fi-720\li720\tx220\tx720 public static void constructWordListMap()\par
\pard that constructs a map called wordListMap where the keys are of the same type as your key in problem 2. The values will be a list of all valid words that have that key value. Thus, if you are given a key k equal to getKey("abtelt") which is the same k as getKey("battle") or getKey("tablet"), then wordListMap.get(k) will return a value v which is the list \{"battle","tablet"\}. Your keyset for this map should just be the keys associated with all the valid words. Thus for every valid word w, getKey(w) should be in the key set of the wordListMap. See the output.txt file to see what this keyset size should end up being. You can now use this map to quickly return the list of all valid words that are formed from precisely the characters in a given String. For some strings, such as s = "xxxx", getKey(s) will not be in the keyset of wordListMap since you can't form a valid word with "xxxx". \par
\b\fs48 Problem 4 \par
\b0\fs32 Write a method\par
\pard{\pntext\f1\'B7\tab}{\*\pn\pnlvlblt\pnf1\pnindent0{\pntxtb\'B7}}\fi-720\li720\tx220\tx720 public static void constructAllWordsMap(int n)\par
\pard that constructs a map called allWordListMap. This map is similar to the the wordListMap in problem 3. The keys are the same type. There are two crucial differences. The first is that you only need enter keys associated with words that are of length n or less. The second is that instead of storing values that are lists of words made with precisely those characters associated with a key, it is a list of all words that can be formed with any subset(technically a multiset since you have to consider duplicate letters) of those characters. Thus, suppose you had n>=3 and k = getKey("bat"). Then wordListMap.get(k) would be \{bat,tab\} while allWordListMap.get(k) would be \{bat,tab,ab,ba,at,ta\}. You should feel free to add keys that are not associated with valid words if you find that useful. \par
Bonus: I suspect that my implementation is suboptimal. For n = 11, it takes about 45 seconds on my home desktop. You may earn one or two more bonus points if you are able to implement a method that is significantly quicker. Indicate in the comments of your dropbox submission if your method is very efficient and you would like the TAs to test your map with n=11 or greater. You should also include an output.txt file of your own with your ScrabbleTest output pasted into it. \par
\b\fs48 Problem 5 \par
\b0\fs32 Write a method\par
\pard{\pntext\f1\'B7\tab}{\*\pn\pnlvlblt\pnf1\pnindent0{\pntxtb\'B7}}\fi-720\li720\tx220\tx720 public static List<String> allWordsFromString(String s)\par
\pard that returns all valid words that can be formed from subsets (submultisets) of characters in the String. This method should run pretty quickly - see the output.txt file for examples. \par
}