Please make sure you are familiar with the resources and policies outlined in the syllabus and the take-home assessments page.

A6 - Anagram Solver

Initial Submission by Thursday 11/18 at 11:59 pm.

Specification Intro Video Submit Code and Reflection

You may submit any part of the assignment as many times as you want before the initial submission. To submit on EdStem, you should use the Mark button to submit your code. You can view your past submissions using the “Submissions” button.

Please make sure you are familiar with the resubmission and late work policy on the syllabus

Extra Resources

You’ll find the video linked above helpful in seeing an example run-through of how to explore all of the possibilities for this assignment. Below we have linked the text of the trace we produced as well as a decision tree showing all of the decisions made.

Developing at Home

You are welcome to use Ed as your environment to work on the homework, but we recommend setting up a local environment following our Desktop Software instructions. This will allow you to work offline, and access the great debugger provided by jGrasp! You can download the code from Ed and when you want to submit, upload it again and then pressing Mark to submit.

Useful Resources

Frequently Asked Questions (FAQ)

Q: I’m having a hard time with recursive backtracking. What should I do?

A: Take advantage of the examples we’ve seen in lecture and in section. In particular, take some time to understand the diceSum and 8-queens examples from lecture. Notice how the eight queens problem stops after finding one possible solution, but the diceSum example finds all possible solutions, like your program should. From the section handout, subsets, gradingOrder, and arrangements are some especially applicable methods.

Q: How am I supposed to get print to print no more than a certain number of words?

A: This is a harder aspect of this assignment, so you shouldn’t tackle it first. Get your print method working so that it will print all appropriate anagrams regardless of how many words long they are. Once you have handled this somewhat easier problem, then take a look at only outputting the anagrams with no more than max words.

Q: Should print keep looking for anagrams once it exceeds max?

A: No. It is inefficient for your code to keep running down paths once you know that they won’t yield a viable solution.

Q: We’ve learned that recursive backtracking often involves examining all combinations of a set of choices. In this problem, the choices are the words that can be formed from the phrase. Should my program consider every word in the original dictionary as a possible choice?8

A: No. There is no need to spend time examining words that couldn’t even be made using the original phrase. First, find a collection of words from the dictionary that can be made using the phrase. Then, use these possibilities as your “choices”.

Q: Should we only output anagrams that use up all of the letters in the given word/LetterInventory?

A: Yes. The writeup explains, “An anagram is a word or phrase made by rearranging the letters of another word or phrase”. For example, [love, lace] would not be an appropriate anagram for the string Ada Lovelace because it doesn’t use the letters ada.

Q: How can I tell if my program is finding all of the correct anagrams?

A: Testing! Just like always, it’s best to start small and then work your way up from there. Start off by using dict0.txt as your dictionary since it’s small enough to check which of the words can be made from a given phrase just by looking at it. Once you’ve convinced yourself that your program works with this small dictionary, you should move on to the larger ones. The Output Comparison Tool on the Homework page of the course website shows output for various phrases from various dictionaries. Make sure to take advantage of this valuable resource! Remember that the tests from the comparison tool are not exhaustive, but it’s a good place to start.

Q: How do I debug my recursive method?

A: Try using System.out.println to find out what the anagram looks like at certain points in your program. Try before and after your recursive step as well as in your base case. You might also find the debugger in jGRASP useful.

Q: My recursive method is really long and icky. How can I make it cleaner?

A: Start off by making sure you can identify the base case and the recursive case clearly. You want to practice recursion ‘zen’ by not burying your base case in your recursive method. Make sure you’re not making any needless or redundant checks inside of your code.

Q: How can I make sure I get the best grade possible on this (or any) assignment?

A: The writeup is the key! It usually has all of the details of how your program should behave, what subtle cases you should make sure to cover, and anything else you might need to know to complete the assignment successfully. Use it like a checklist before, during, and after you do the assignment to make sure you do everything correctly.