Guessers (Conceptual)

PAGA Example: getGuess(String pattern, List<Character> guesses)

Suppose we have the dictionary: [alf, bed, bee, cat, dog, zoo, fish, cows]

• Suppose we make the call getGuess("---", [])

​

​

​

​

​

​

​

We can rule out fish and cows since they are the wrong length.

​

Among the remaining words, e and o occur the most times (3 respectively).

• Since e is earlier in the alphabet, the PAGALetterFreqGuesser’s getGuess method should return e.

PAGA Example: getGuess(String pattern, List<Character> guesses)

Suppose we have the dictionary: [alf, bed, bee, cat, dog, zoo, fish, cows]

• Suppose we make the call getGuess("b--", [b])

​

​

​

​

​

​

​

Here we can narrow it down to the words bed and bee.

• Can’t be fish or cows (wrong length).
• Can’t be alf, cat, dog, or zoo (don’t match the pattern).

Note that even though the PAGAFequencyGuesser would never select ‘b’ as its first guess, its still a valid argument for the guesses to start with b.

PAGA Example: getGuess(String pattern, List<Character> guesses)

Suppose we have the dictionary: [alf, bed, bee, cat, dog, zoo, fish, cows]

• Suppose we make the call getGuess("---", [a])

​

​

​

​

​

​

​

Here we can narrow it down to the words bed, bee, dog, and zoo.

• Can’t be fish or cows (wrong length).
• Can’t be alf (guesses include a, but pattern has - in first position).
• Can’t be cat (guesses include a, but pattern has - in second position).

PAGA Example: getGuess(String pattern, List<Character> guesses)

Suppose we have the dictionary: [alf, bed, bee, cat, dog, zoo, fish, cows]

• Suppose we make the call getGuess("be-", [b, e])

​

​

​

​

​

​

​

Here we can narrow it down to just the word bed.

• Can’t be fish or cows (wrong length).
• Can’t be alf, cat, dog, or zoo (do not match pattern).
• Can’t be bee (guesses contain e, but third character in pattern is -, not e).

There were two typos on this slide. Oops! Fixed.

PAGA Example: getGuess(String pattern, List<Character> guesses)

You don’t need to worry about degenerate cases.

• Patterns without corresponding guesses.

PAGA Example: getGuess(String pattern, List<Character> guesses)

You don’t need to worry about degenerate cases.

• Patterns without corresponding guesses.
• Invalid patterns.

PAGA Example: getGuess(String pattern, List<Character> guesses)

You don’t need to worry about degenerate cases.

• Patterns without corresponding guesses.
• Invalid patterns.
• Guesses where there are no valid letters to pick.

Guessers (Coding)

Syntax Tip: getOrDefault

The getOrDefault method allows you to concisely handle situations where keys are missing.

​

if (!map.containsKey(k)){

map.put(k, 0);

}

map.put(k, map.get(k) + 1);

map.put(k, map.getOrDefault(k, 0));

Performance Tips

The tests in NaiveLetterFreqGuesserTest, PatternAwareLetterFreqGuesserTest, and PAGALetterFreqGuesserTest should run in milliseconds.

• If the tests significantly longer than 1 second on the large files, you’re doing something unnecessarily slow.

​

Performance tips:

• Triple nested loops indicate an inefficient design.
• String concatenation can be slow (see next slide).
• Calling .remove on a list can be slow (see two slides later).

​

Note: Make sure you have the latest tests. Your PatternAwareLetterFreqGuesserTest and PAGALetterFreqGuesserTest files should include a final test called testGetGuess_o__a_PatternLargeFile.

• If you don’t see this, re-pull from the skeleton code.

Performance Tip: String Concatenation vs. StringBuilder

Some students have solutions that involve adding thousands of strings to an existing string.

• This is very slow in Java! Every time you add a word, it results in an entirely new string.
• In other words, adding ‘a’ to a string that is 1,000,000 characters long requires building an entirely new 1,000,001 character long string.
• Note that the “+=” is highlighted by IntelliJ. If you mouse over, you’ll see “string concatenation += in loop” is called out as a warning, because this is slow.
• Either come up with a new design, or use the alt+shift+enter keyboard shortcut.

​

​

​

​

​

​

Note: It’s ok to do string concatenation in a loop if it’s only a few strings, such as building a pattern character by character.

List Removal

Calling remove on a list of strings is very slow.

• Java has to iterate over the entire list to find then remove the list.

​

Two ways to fix this:

• Come up with a new design that doesn’t involve removal from a list.
• Use a “TreeSet” instead of a list. The remove operation for a TreeSet is very fast.
• Note: We haven’t covered sets in Java yet, but you’re welcome to use them.
• Example of converting a list of strings into a set of strings:

​

• If you use this approach, make sure not to create have any loops that repeatedly convert lists to sets or vice versa.

listOfStrings.remove(word);

Set<String> setOfStrings = new TreeSet<>(listOfStrings);

Choosers

Tips coming soon

Coming soon