This handout does two things. First it goes over the anagram example from lecture. Then I present the first ever (to the best of my knowledge) AI solver for Bananagrams

Bananagrams, which builds off of Anagrams

Ananagrams

In class we solved this particularly interesting poblem: Write a program to find all anagrams of a word the user types. You may use a file which contains all english words.

To find all anagrams of a word we used a function `sortLetters(str)` that took a string and would return the same string with all of its letters in sorted order. Lets call the returned string the key. We realized that this was particularly useful because it is always true that:

If two words are anagrams calling `sortLetters` on both words will always return the same key.

If two words are not anagrams calling `sortLetters` on both words will return two distinct keys.

From that point, our strategy was to employ our new tool `Map`. We built a map that related every key to the set of all words in English that you could form with the letters in that key. It was amazingly fast. Here is the code:

Bananagrams

Anagrams was fast. So fast in fact that it inspired me to use it to solve an even bigger problem. I dig the game Banangrams so I thought it would be cool to have a computer that could play it. If you don't know Banangrams head to the book store, buy a copy, take a few late days on your assignment and figure it out (kidding).

On some level Banangrams is a hard problem. There are so many potential ways of laying out tiles on a grid that it could take the lifetime of the universe to try them all. To make the problem easier I formulated my solution as: (A) Come up with the best first word possible using heuristics then (B) assume that is fixed and try and place your remaining tiles. It worked! Here are two example games with the tiles the AI was presented with, and the boards it discovered:

Getting the best first word (similar to getting subsequent good words) is hard. You really want to try all combinations of including and excluding tiles. To solve this problem I used a thought process called Breadth First Search, which is similar to how you are going to solve Word Ladder.

Bellow is the code. You can also peruse bananagrams.cpp if you want it as a file. I would consider this an example of CS106B expectations for style. The functions are generally bite size and nicely decompose the hard problem into smaller pieces. Functions are well named and have comments. I use const int instead of raw "magic" numbers. Enjoy.