I moved this week’s programming club meeting to Wednesday so that I could compete on TopCoder on Thursday. This week at the meeting I introduced people to Robocode, which is an environment and API for developing little tank robots. You can control the robot tank’s radar, gun, and movement. The goal is to program the best strategy such that you beat all the other robots.
I had played around with Robocode several years ago and programmed a few different tanks. I thought it might be a nice break for everyone to try another style of programming, rather than strictly problem solving.
After I showed everyone how to build a basic robot, I got the students to start building their robots based on tutorials available on the Robocode Wiki. Next week we will start the meeting off by having our various creations battle each other.
I’ve been working a bit on my own robot. It hasn’t been as effective as I had hoped. I implemented a force directed graph layout to control my robot’s movements. Bullets that I detect, along with enemies are forces that push my robot in certain directions. It’s reasonably effective, meaning I can defeat all the sample bots, but the behavior is a bit erratic at times and doesn’t always make sense to me. I may need to do some tweaking. I’ve also been working on using a different strategy for one on one situations.
Last night I competed in SRM 435 on TopCoder. I solved two of the three problems, however I was considerably slower than need be. I had some computer issues that slowed down my compile and run times, but I also made a number of silly mistakes.
In the first problem, when processing two strings consisting of digits (0-9), I forgot to convert the char representations into integers when performing my math calculations. It didn’t take long to fix, but still cost me a minute or two.
The second problem was pretty simple. It boiled down to having the description of a binary tree, and you had to delete a single node and then determine how many leaf nodes are left. I represented the tree using a vector of vectors, then did a breadth first search starting at the deleted node and marking all visited nodes for deletion. Then I iterated over all nodes and counted how many didn’t have children and that still existed in my graph.
I lost several minutes on this problem due to a stupid mistake. I misread the first sample test case, so when my program first ran I thought I was doing something wrong, but it was in fact working. I spent a few minutes debugging something that wasn’t a bug! I eventually submitted the problem, but I should have been able to get more points for it.
In retrospect, it would have been less code to do this recursively and start at the root, not recurse on the deleted node, and return all leaf nodes encountered.
I had ample time for the last problem, but I wasn’t able to come up with a decent algorithm. It was a probability problem. I tried a randomized algorithm after being stuck for intelligent ideas, but it wasn’t accurate enough. The actual solution involved dynamic programming and I probably should have realized this.
The next TopCoder competition I will be competing in is on the 28th and is a qualification round for the TopCoder Open. I don’t really expect to make it very far in this tournament, but it will be good practice.
