-------------------------------------------------------------------------------
Michael Locasto                       Introduction to Computer Programming in C
Homework 4                                                            Fall 2005
$Id: hw4.txt,v 1.2 2005/12/03 00:09:40 locasto Exp $
-------------------------------------------------------------------------------

Due: December 13th, 2005 at 23:59:59 (Courseworks timestamp).


0) Word transformation games. (100 pts)

   A common and fun game for car trips is to transform one word into
   another (keeping the same number of letters) by changing one letter
   at a time until the original word has been transformed into the
   target word. All intermediate strings must be legal words.

   An example of this is changing the word 'cat' into 'dog'

   cat
   cad
   cod
   cot
   dot
   dog

   Implement a program called 'wt' to play this game. This assignment
   is harder than it looks. Your program will need several components,
   including a training phase and a dictionary. In effect, it needs to be
   able to check for illegal transformations.

   Thus, calling your program:

   $ ./wt cat dog

   should produce the output above (or another variation).

   Another example is:

   $ ./wt cow cat
   cow
   cot
   cat

   If you provide the -t or --train parameter to your program, then wt
   will attempt to provide a transformation, but ask you for advice at
   each step. If the word it has created is not valid, then it will
   attempt to create another one. In this way, it can build up its
   database of words without you having to create an extensive
   dictionary.

   You will need to save this dictionary in a file so that your
   program gains experience and becomes more playable. Decide on the
   format of this file. Keep in mind that this file could get quite
   large. Is it better to store a binary representation of some
   in-memory data structure or a list of ASCII strings line by line?
   At what point does it make a difference? How long does it take your
   program to load this dictionary? Do you load the whole dictionary
   into memory or just parts of it?

   Hints: You may wish to look into using the 'trie' or 'patricia trie'
   data structure, but you are not required to use it. Implementing it
   doesn't get you extra points, but advanced programmers may find it
   useful now and in the future.

   Questions:

   0) Race your program at three different points:
       - before you have given it a dictionary
       - when you have given it a moderate amount of training
       - when you have given it an extensive dictionary
      When did your program win? Is your program smarter than you?
   1) What is the longest word you can transform? What is the
      longest word your program can transform? It should transform
      words of at least length 4.

/************************ EXTRA CREDIT *************************/

5) Game Passwords (35 pts)

   Many older computer games were 'locked' with a passphrase from the
   owner's manual. The game asked you for the i-th word of the n-th
   section. If you supplied the correct word, you were allowed to
   play the game, the logic being that you were in legal possession of
   the hard copy of the owners manual (which supposedly meant that you
   had purchased the game or otherwise complied with the software
   license).

   Implement a utility that, given a file of text and a word position,
   outputs the word at that position. Do not store the text in an array.
   (10 pts)

   Your program should be called 'fword' and include the standard
   help and version capabilities. It should be invoked like this:

   $ ./fword [i] [file]

   and should print out the i-th word of the file. Think about what a
   'word' is.

   Questions:

   0) Describe 2 strategies to attack this vestigial DRM scheme.

   1) Alter your program to keep track of sections and find the i-th
      word of the n-th section. A section is delimited by a blank
      line between paragraphs. More precisely, this means \n\n.

   3) This program is extremely slow when processing large text files. Can
      you improve the performance given the use case? If you can, implement
      the appropriate algorithm and data structure. If you cannot, can you
      describe a simpler scheme that produces the same effect but does not
      have to process the whole file?