Margana v1.1 ------------ Thanks for choosing Margana. It is one-of-a-kind, as far as I can tell. I know you will enjoy using it :) ABOUT ----- Margana is a general purpose interactive anagrammer, with the extra ability to perform pattern-anchored anagramming. This feature is especially useful for players of Scrabble and other word games. With Margana, I have included the Official Scrabble Player's Dictionary 3rd edition wordlist (OSPD3) in the file called "words". This should save you some time in finding a suitable wordlist. See the technical details at the bottom for some banter about memory management and tries COMPILING --------- Simply run 'make' in the directory you extracted from the tarball. You will end up with an executable called "margana" in the current directory. INVOKING -------- Invoke margana with --help as its only commandline parameter for brief usage information. Margana needs to have a word list to operate. If no commandline parameters are specified, it is assumed that the wordlist file is called "words" and is in the current directory. To override this, you may specify an alternate filename as the first commandline parameter to margana. Alternatively, this may be changed permanently by changing the setting at the top of the source code, and recompiling. USING ----- Margana prompts for a rack of letters, and a pattern of open letters and surrounding spaces on the board. It then returns all words composed of at least one letter on the board and at least one letter from your rack, that fit _within_ the given pattern. If the board pattern provided is a single * character, all possible anagrams of any size, that can be made from your rack, will be shown. If the board pattern contains all ? characters, all anagrams of your letters that fit within the number of spaces indicated will be shown. To exit Margana, hit Ctrl-C. EXAMPLE ------- $ ./margana Margana v1.0, (c) 2001 Moshe Jacobson Invoke with --help for usage information. Indexing dictionary . . . done. Rack ('?' for blanks) []: margan? Board pattern ('?' for open spaces), or * []: * aa ab ad ae ag ah ai al am an ar as at aw ax ay ba em . . . . . . bagman barman carman engram gagman gasman german graham gramas granum hangar magian manage manger mantra margay margin marina morgan organa parang raglan ragman ragmen sangar anagram grandam grandma manager tangram trangam Rack ('?' for blanks) [margan?]: ?a Board pattern ('?' for open spaces), or * [*]: * aa ab ad ae ag ah ai al am an ar as at aw ax ay ba fa ha ka la ma na pa ta ya Rack ('?' for blanks) [a?]: testing Board pattern ('?' for open spaces), or * [*]: ????p gip nip sip tip snip step genip Rack ('?' for blanks) [testing]: Board pattern ('?' for open spaces), or * [????p]: ???a?e???? en es et na ta age ane ate eng ens eta sea tea agee ages anes ates ease egis engs etna gane gate geta sage sane sate seta tate agene agent eaten egest enate gates nates stage stane state tates tease ageist agenes agents enates estate ingate negate sateen senate tisane ingates neatest negates Rack ('?' for blanks) [testing]: ^C $ SUGGESTIONS ----------- I welcome any suggestions, bug reports, etc. that you may have about Margana. Please direct them to me at moshe@runslinux.net. I am especially looking for suggestions on how to minimize the memory usage of Margana. Speed doesn't seem to be a problem now, but 13 megs of memory to store a 1.7 meg dictionary file? Bah. Please let me know what you figure out. OBTAINING --------- The latest version of Margana is always available at: http://runslinux.net/projects/margana NOTES ----- This program took a good bit of tweaking before it was released. If you'll look at the source code, you'll notice that when the dictionary is indexed into memory, it is stored into a data structure called a 'trie'. Each node in this specialized tree represents a letter of a word. The head of the tree is where you start when you want to look up a word. The head has (up to) 26 child nodes, each representing a letter of the alphabet. Say we wanted to look up the word 'ace'. We would start at the head, and visit the 1st child node (representing 'a'). From there, we'd visit the 3rd child node (representing 'c'). And finally, we'd go to the 5th child from there (representing 'e'). Now we look at this node's boolean 'isword' indicator. If it is '1', 'ace' is a word. If it is '0', 'ace' is not a word. The problem with this trie structure, at first, was that most nodes in the trie only had a small few children actually present, while the rest of the child pointers were set to NULL. This lead to a huge waste in unused pointers. When the program started up and indexed the dictionary, it would use 41 megs of RAM! This, I felt, was unacceptable. So I thought, what if there was a way not to allocate space for all those unused pointers? Is there a way to make it so the most often used pointers appear toward the start of the pointer array, so that I can allocate only as much of the left side of the array as I needed? I decided to find the frequencies of each letter in the file, and use a mapping from letters to their rankings, so that the most common letters would appear toward the beginning of the child pointer arrays, and the least common would appear toward the end, and I'd only malloc as much of the array as neccessary. This took the program's memory footprint from 41 megs down to 16. I was pleased, but I knew I could do better. I then decided to make the mapping different for each letter. Indeed, there are different relative frequencies of the letters in the alphabet when you consider them after each of the other letters. So now we have a two dimensional array listing the rankings of each letter after each other letter and at the start of words. Now the program took only 13.5 megs of memory. Can I do better? I don't know. That's what I want YOU to figure out :) Another interesting thing about this program is that it uses two different algorithms for anagramming. The first that I wrote, which was quite easy, would take in each dictionary word, one at a time, and see if it could make that word with the letters on the rack. This always takes the same amount of time to run, regardless of the size of your rack or how many blank tiles you have. The only problem is that it can't do pattern anchored anagrams. The 2nd algorithm used by Margana is to permute the rack letters into the board space in all possible configurations, checking if each permutation is a valid word. This is where the trie data structure comes in. Looking up words in the trie is very fast. The time required to look up a word increases linearly with the length of the word. However, anagramming this way is very slow nonetheless, especially when there are blank tiles on the rack. Each one increases the running time by a factor of 26, as you can probably guess. This is why I have disallowed this algorithm when the rack has over 2 blanks on it. Anyway, that's about all I have to say. Enjoy the program! - Moshe