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.

Terminal

A little while ago I installed Ubuntu 8.10 onto my desktop, along with Windows XP. Truthfully speaking, the only reason I boot into Windows more often is because I have a program that lets me watch tv on my computer (which is nice seeing as how I don't currently have a real tv).

Anyway, after changing most of the Ubuntu settings so that things are the way I like them; I realized that I still hadn't "fixed" the terminal size. Well at first I did a little Google search to see what the necessary command(s) I would have to run were. However, most of what I found required me to make a launcher, which I didn't want to do. Though I have a feeling that this is the way I solved this issue when I installed Ubuntu onto a portable HD for my laptop.

Finally I found a much nicer way to change the default terminal size. Here it is;

1) Open up a terminal

2) Tyep the following:

sudo gedit /usr/share/vte/termcap/xterm

*in the above you could replace gedit with vim if you wanted, but I just like using gedit personally.

3) Find the following line:

:co#80:it#8:li#24

4) Change it to the following:

:co#A:it#8:li#B

Where A and B are the dimensions you desire. (Your teminal will have dimensions A x B)

Daydreamin

Yesterday I went to a Lupe Fiasco concert. Definitely not an experience that will be forgotten any time soon. My only complaint would have to be the excessive use of strobe lights, though after a while I did manage to get used to them.

There was one song in particular that he performed that stood out more than the others. Not because of the lyrics or the beat, but rather because of a past experience that involved the song. I won't go into what the experience was on this blog, but you will get a video of the song, along with the lyrics.




Lyrics:

Daydream
I fell asleep beneath the flowers
For a couple of hours
On a beautiful day
Daydream
I dream of you amid the flowers
For a couple of hours
Such a beautiful day

[Lupe Fiasco]
As I spy from behind my giant robot's eyes
I keep him happy 'cause I might fall out if he cries
Scared of heights so I might pass out if he flies
Keep him on autopilot 'cause I can't drive
Room enough for one I tell my homies they can't ride
Unless they sittin on the shoulders but that's way too high
Let's try not to step on the children
The news cameras filmin
This walkin project buildin
Now there's hoes sellin hoes like right around the toes
And the crackheads beg at about the lower leg
There's crooked police that's stationed at the knees
And they do drive-bys like up and down the thighs
And there's a car chase goin on at the waist
Keep a vest on my chest
I'm sittin in my room as I'm lookin out the face
Somethin to write about
I still got some damage from fightin the whitehouse, just a

Daydream
I fell asleep beneath the flowers
For a couple of hours
On a beautiful day
Daydream
I dream of you amid the flowers
For a couple of hours
Such a beautiful day

[Lupe Fiasco]
Now come on everybody, let's make cocaine cool
We need a few more half naked women up in the pool
And hold this MAC-10 that's all covered in jewels
And can you please put your titties closer to the 22s?
And where's the champagne? We need champagne
Now look as hard as you can with this blunt in your hand
And now hold up your chain slow motion through the flames
Now cue the smoke machines and the simulated rain
But not too loud 'cause the baby's sleepin
I wonder if it knows what the world is keepin
Up both sleeves while he lay there dreamin
Me and my robot tip-toe 'round creepin
I had to turn my back on what got you paid
I couldn't see half the hood on me like Abu Ghraib
But I'd like to thank the streets that drove me crazy
And all the televisions out there that raised me, I was

Daydream
I fell asleep beneath the flowers
For a couple of hours
On a beautiful day
Daydream
I dream of you amid the flowers
For a couple of hours
Such a beautiful day

Daydream
I fell asleep beneath the flowers
For a couple of hours
On a beautiful day
Daydream
I dream of you amid the flowers
For a couple of hours
Such a beautiful day

Drains

This post just made my day. The next time I have a blocked drain I am totally going to try this.

http://hpuew.blogspot.com/2009/04/bi-carb-soda.html