Progress Update I

So far everything is going pretty smoothly. This is due largely in part to having created a UML, and doing some documentation before I started coding. However, I feel that I will have to go back and change and/or add somethings. The biggest problem right now is memory management. I don't yet fully understand how the delete keyword works, so my classes at this point don't have deconstructors (yes I know wasted memory, but the game shouldn't be that big so I will worry about it later). This is the main reason that I considered writing the game in Java and not C++.


Creating and using my own header files is actually easier that I had first assumed. Every now and then I will make sure that they work by trying to use them in a small test program that I wrote. Most of the time if there is a problem with a file it is because of a stupid typo or forgetting to include another needed header file, so nothing too detrimental.

Even though everything works so far, and by that I mean compiles with no errors or warning, I still have no idea if they work as intended.

I'll post a quick overview of all the current and planned header files in the next update.

Y-Game

So I have come up with a personal summer project. I am going to recreate "Y-Game". Basically this was a text bases RPG that my friend created back in high school for the TI-83/84.
Right now it will still be text based, but that might change depending on how much time I end up having. Also it will be more elaborate since I will be writing the game in C++ (or Java, but not likely).
From this I am basically hoping to become more familiar with header files, linking files, and most of all writing and reading data from a file. I already know how to read and write to a file, I would like to do that so that it is possible to save your progress in the game and then come back at a later time and continue.
More than likely the next few post will be updates on how things are coming along.

Moving Through Trees

Well this week has been pretty successful so far. I've managed to solve 4 SPOJ problems I think, though one was just applying a "basic" geometry formula.

Of the remaining problems the first was about playing a game optimally. Usually I detest doing these kinds of problems, but once I noticed that there were solutions in Brainf**k I knew that there was something I was missing. Here is the link to the problem, as far as hints go all I will say is play the game by hand for the first few (under 30) numbers and you should notice a pattern.

The next two problems are pretty similar. Since I am going be describing how I actually solved them I will not be providing a link. They were both asking you to find the longest path within a given tree. The naive approach (and probably more difficult to program) approach would be to find the distance between very possible pair of vertices. This is going to result in an O(n^2) algorithm, and not to mention that it isn't immediately obvious how to find the distance between two given vertices. Naturally the next I idea was to use a depth first or breath first search, the issue now becomes knowing if you have found the longest path. Well here is the approach that I used; start with any vertex of the tree and then use DFS (depth first search) to find the vertex that is farthest from it, call this vertex X1. Now do another DFS starting with X1 and find the vertex X2 that it is furthers from. The distance between X1 and X2 will be the longest path in the tree (though I don't feel like proving rigerously or even using hand waving to explain why).

Here is a sample of the code I used to solve the case where all the paths had the same length. It isn't too difficult to modify for weighted trees.

pair< int,int > dfs(vector< int > >&G,int v)
{
   stack< int > S;
   S.push(v);
   vector< int > visit(G.size(),0);
   while(!S.empty())
   {
      int parent=S.top();
      S.pop();
      tr(G[parent],i)
      {
         if(visit[*i]==0)
         {
            S.push(*i);
            visit[*i]=visit[parent]+1;
         }
      }
    }
    vector< int >::iterator    i=max_element(visit.begin(),visit.end());
   return make_pair(i-visit.begin(),*i);
}

The first entry of the returned pair is the vertex farthest from the starting point, while the second entry is the distance. Thus you will run the DFS two times as previously mentioned. So the complexity of this method is O(n) which is much better than the other approach.
It should be noted that the following is at the beginning of the code

#define tr(a,i) for(typeof(a.begin()) i=a.begin();i!=a.end();++i)

Summer Job

So I most likely will have to find a job this summer. I am pretty set on avoiding fast food and being a waiter. As of now the list of potential places of employment are as follows:

• Kohl's
• ACM
• Boston Market
• Jo-Ann's
• Sears

I don't really consider Boston Market to be quite as bad as normal fast food restaurants so that is why it is included on the list.

In addition to possibly working I will also be preparing for the GRE and hopefully start studying for the FM actuarial exam. Oh and I should also email my thesis advisor asking him if there are any papers he would like me to read over the summer.