This is the post to describe my approach of my solution. Here is my source code:
http://shinh.skr.jp/dat_dir/icfpc.zip
* FAQs
Before the detailed descriptions, I put some questions asked by other contestants.
Q. Did you go to the moon?
A. No, I couldn't. I considered if I could go to the moon a bit, but I decided not to go the moon. As it takes a lot of fuel and the score of far debris aren't big, I prioritized improvement of stability and faster arrivals at near debris.
Q. Did you solve traveling salesman problem?
A. No. I chose the next target almost greedy. Please see the following details as well.
Q. Did you solve difficult mathematic formulas?
A. No. Though I tried to find an analytic solutions, the effort was just waste of time. Basically, I only used Hohmann transfer. Even if we had a analytic solutions, we would need some adjustment for errors due to discrete space anyway.
Q. 1 person team?
A. Yes. I always attend this contest because I'd like to do everything by myself.
Q. How long did you sleep?
A. Not sure, but maybe ~20 hours. I cannot write valid code with few sleep. It is the lesson learned from previous contests.
Q. Why C++?
A. I love C++. By the way, I think I'm not offensive to functional programming languages. Actually, I tried some of them a bit (maybe I wrote from ~1k to ~3k lines of toy code for each of them). I thought OCaml is good but it's standard library is poor. Perhaps I should have tried ExtLib or something like this. Haskell was slow when I tried. I read some of assemblies GHC produced, but it was very difficult for me to understand it... I tried Scheme interpreter and it was interpreter after all. Maybe I'll want to try compilers (Stalin?). Commercial common LISP processors sound great, but I only have opensource implementations. So, I'm thinking C++ is the most practical languages to me for now. I know I'm biased - I spent much more time for C++ than other languages. I'm looking forward continuing functional programming funs' great work.
Q. Why not other imperative languages?
A. I feel Java is less free than C++. As for C#, my experience with C# is too small to discuss it. I'm (or was?) a fun of D and actually I used D for this contest three times (2004, 2006, and 2007), but I don't use it these days. Maybe I'll want to use it again for the next year's contest.
* Detail
This post is based on the script of my talk for vidiowiki: http://vidiowiki.com/watch/m844dyn/ (Hmm... it's embarrassing to watch I'm talking with my poor English. But it is good experience to me.)
Overall, I think my approach wasn't so special. Just like many teams might do, I wrote a VM, a visualizer, a physic simulator, and hoahman transfer.
My VM was fast because it translates the input binary into C code. Otherwise it's normal.
The visualizer is also a normal stuff. Nothing to say about it. You can see a YouTube video at (sorry for its poor quality) http://www.youtube.com/watch?v=IUGiiFsnLLs
I also had a physic simulator. It calculates the states of future quickly. Due to two reasons, it was a bit tricky to implement the simulator correctly. The first reason is that the binary organizers provided was wrong. The gravity from the moon didn't affect to our spaceship. Also, the gravity from the moon is calculated by g(t+1) = G*M/(p(t+1)-pm(t))^2 where p is the position of a body and pm is the position of the moon. I think pm(t) should have been pm(t+1). Anyway, with some reverse engineering works, I could implement the simulator correctly. It helped me a lot by its fast simulation.
With these three tools, I implemented my strategy, which was basically, kind of bruteforce.
First my simulator calculates the future positions of a target for 5000 seconds. The track should be an elliptic arc around the earth. And then, it checks if I have a chance to reach a point which is close enough to the arc with ideal Hoahman transfer.
As there are the gravity from the Moon and the program is running in discrete space, there should be some errors. Things are not ideal. Therefore, my program starts adjustment as the next step when it finds it can go close to the track of the target. It runs simulations for various initial velocities again and again. This process takes a lot of time. My fast simulator helped this process.
The last question is how to decide the next target from 10 targets. My approach was a greedy algorithm with a heuristics. If it finds a promissing plan for a target, it starts the journey except for two cases. One case is that it withdraws the plan if the plan takes too much fuel. Another case is that the target is too far. The latter exception is a performance optimization. It is considered before it starts the first step to reduce unnecessary calculations for too far targets (e.g., the debri around the moon isn't good candidate as the first target). I know this is not optimal, but it seemed it was acceptable enough.
So, as I described, I think my approach isn't the smartest way. but I guess the good point of my program was its robustness. I've heard that there are some teams whose program unfortunately crashed with some typical test cases and some teams' solution only work for the given test cases.
The performance might be also the key of my success. It seemed that there are some teams whose solutions are similar to mine. However, most of them don't have fast simulator and they just use VM to simulate the physics. Also, I think C++ helps me to write solid and fast code.
Thanks the organizers for the excellent contest!
