hoge

ICFP Programming Contest 2009

2009-09-12T13:41:00.000-07:00

Surprisingly, I won the first place in the ICFP programming contest 2009. I'm very appreciated for this result - it was much better than my expectation. I was in 9th place before the validation process.

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!

Symbolic Polyglot Quine

2009-08-02T08:51:00.000-07:00

Recently, I wrote the following code:

http://shinh.skr.jp/obf/sym_poly_quine.txt

This script is a Quine, so it outputs the program itself into stdout without file input. You can run this script by Ruby, Perl, and JavaScript. This script is a polyglot of these three languages. And, this script was written only with symbolic characters (!"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~). There should be no alphabets, numbers, whitespaces, and 8bit characters.

Perl is OK only with symbolic characters. You can convert any Perl scripts into symbolic style scripts using Acme::EyeDrops. This module is awesome.

http://search.cpan.org/dist/Acme-EyeDrops/

Also, all JavaScript scripts can be converted into symbolic style. jjencode does the magic.

http://utf-8.jp/public/jjencode.html

As for Ruby, Ruby 1.9 is perfect for symbolic programming. kurimura found the way to convert arbitrary Ruby scripts into symbolic format.

http://d.hatena.ne.jp/kurimura/20080824

Unfortunately, I think Ruby 1.8's symbolic programming is very limited. For example, you cannot create a loop. As quine only require substitutions and outputs for stdout, which is doable with symbolic Ruby 1.8, my script can run with Ruby 1.8.

There are some other weird code like this:

http://shinh.skr.jp/obf/

TCC 0.9.25

2009-06-05T15:58:00.000-07:00

I worked on porting TCC into x86-64 and the project has recently released a new version which contains my changes.

http://bellard.org/tcc/

I confirmed that my changes pass the tests in TCC and successfully compile some applications such as link and Lua.

As there should be some bugs in the x86-64 support, I'll be really appreciated if you try this release with x86-64 and report bugs.

Regarding implementation... It was more difficult than I expected. Code generation for x86-64 was relatively straightforward because there was support for x86, which is similar to x86-64. The most difficult part was relocation related stuff. As distance of two addresses in 64bit address space can be larger than 32bit, some 32bit relative references need to be fixed by PLT and GOT. TCC's -run mode support was also tricky by the same reason.

Other things by which I was often confused were 64bit system itself. As much code of TCC depends on 32bit system, sometimes it casts pointers into int, which is sometimes incorrect on 64bit system. The following simple code would show the difficulty of 64bit system:


int main() {
    printf("%p\n", malloc(10));
    printf("%p\n", malloc(1000000));
}

This code produces outputs like


0xfa1010
0x7f3658acd010

on my linux box. When we allocate small memory chunk from heap, it returns addresses which is smaller than INT_MAX. So, even if we cast the returned pointer into 32bit integer, it has no problem as long as we allocate small memory chunks. This hided many bugs from me. This kind of bugs only appears with big programs. It means that it's difficult to create minimal failure cases...

TLE

2009-04-07T08:50:00.001-07:00

I got the 1st prize in the first TLE programming contest.

http://felicity.iiit.ac.in/tle/

This contest had unique problems. For example, we should have written a C program with no semi-colons in the test run of this contest. The answer was:

main(){if(printf("Hello, world!")){}}

In this contest, the most problems require short coding to get better score. I like short coding and I used a lot of time for this competition (I even took a day off). That's why my performance was surprisingly good in this contest.

Unfortunately, there were some issues in the contest. Since competitors wrote much shorter code than organizers had expected, the score of each problem is imbalanced. For example, the maximum score of problem "CLASS" was 200. On the other hand, some competitors awarded over 2000 points in problem "SHORTEN". Anyway I think this issue didn't break the fun of this contest, and this kind of issues were unavoidable as this was the first attempt for the organizers to run this kind of contest.

Though there were some issues in the contest, it was great fun! I hope I will attend this contest again in the next year. I must thank organizers for the excellent contest.

hh.gif

2008-11-29T13:55:00.001-08:00

I created another GIF file. This has 7 hidden keywords.

http://slashdot.jp/sp/binary2008/data/hh.gif

* This GIF file is

- a GIF file which shows "Happy Hacking".

- a MS-DOS COM program which shows "Happy Hacking".

% cp hh.gif
% dosemu -dumb hh.com
Happy Hacking!

- a Perl program which converts a ASCII formatted COM file.

If you provide no arguments, it converts itself. So, you can do

% perl hh.gif > hh.pl.com
% dosemu -dumb hh.pl.com
Happy Hacking!

There are no binaries or control code in hh.pl.com.

- a Ruby program which converts a ASCII formatted COM file.

% ruby hh.gif > hh.rb.com
% dosemu -dumb hh.rb.com
Happy Hacking!

- the Perl program shows "be" if you provide 1111 as the command line option.

% perl hh.gif 1111
be

- a Java program in jar which shows "assimilated".

% java -jar hh.gif
assimilated

- the word *WILL* is hidden in the GIF file in UTF8.

- this is an animation GIF, after waiting 10mins, the image shows "You".

- "Resistance" is embed in this GIF image.

http://shinh.skr.jp/misc/dat_dir/steg.gif

* The outputted ASCII formatted COM file is

- a COM file

- a Perl program which produces the original COM file

% diff =(perl hh.pl.com) hh.com
% diff =(perl hh.rb.com) hh.com
%

- a Ruby program which produces the original COM file

% diff =(ruby hh.pl.com) hh.com
% diff =(ruby hh.rb.com) hh.com
%

- a Python program which outputs "futile"

% python hh.pl.com
futile

- a Haskell program which outputs "is"

% cp hh.pl.com hh.hs
% ghc hh.hs
% ./a.out
is

* Overall, the hidden phrases are "Resistance is futile. You will be assimilated"

Here is the archive to create this file

http://shinh.skr.jp/binary/happy.tgz

fizzbuzz7.gif

2008-10-27T09:53:00.001-07:00

I updated the previous polyglot (http://shinhoge.blogspot.com/2008/10/fizzbuzzgif.html).

http://shinh.skr.jp/dat_dir/fizzbuzz7.gif

This GIF file has 7 meanings:

- a GIF file
- a Fizz Buzz program in Ruby (1.8)
- a Fizz Buzz program in Perl
- a Fizz Buzz program in Befunge (http://en.wikipedia.org/wiki/Befunge)
- a Fizz Buzz program in z80, which runs with my golf server's emulator. (see http://golf.shinh.org/ or http://sites.google.com/site/codegolfingtips/Home/z80 for detail)
- a Fizz Buzz program in x86 & MS-DOS. (you can rename this to fizzbuzz.com and run on Windows or dosemu)
- a Fizz Buzz program in x86, MBR image. (you can run with QEMU or something: qemu -boot c -hda fizzbuzz.gif)

The source code is

http://shinh.skr.jp/dat_dir/fizzbuzzgif.tgz

google-glog

2008-10-18T05:40:00.000-07:00

I'm working on an opensource project as my 20%.

http://code.google.com/p/google-glog/

fizzbuzz.gif

2008-10-12T12:32:00.000-07:00

http://shinh.skr.jp/obf/fizzbuzz.gif

This GIF file has 6 meanings:

- a GIF file
- a Fizz Buzz program in Ruby (1.8)
- a Fizz Buzz program in Perl
- a Fizz Buzz program in z80, which runs with my golf server's emulator. (see http://golf.shinh.org/ or http://sites.google.com/site/codegolfingtips/Home/z80 for detail)
- a Fizz Buzz program in x86 & MS-DOS. (you can rename this to fizzbuzz.com and run on Windows or dosemu)
- a Fizz Buzz program in x86, MBR image. (you can run with QEMU or something: qemu -boot c -hda fizzbuzz.gif)

This is the NASM source code which was used to create this GIF file.

http://shinh.skr.jp/obf/fizz_gif.asm

ICFPC 2008

2008-09-25T07:19:00.001-07:00

It seems that I've got the second place in ICFPC 2008. I'm really appreciated this result. I think I was very lucky. I don't think my program was excellent. For example, my rover would run poorly if there are difficult maps, like complicated maze.

I'd like to put some notes on my implementation. My rover had three parts:

Calculate geometry informations: Just like other teams, my rover guessed some parameters using the information. Since there are some latency between server and client, my rover calculates the future position using the log of commands sent to the server.

Macroscopic planning: All obstacles are memorized. If some of them are near enough each other, they are considered as a cluster. If there is a obstacle between the rover and the home, my rover decides left or right using some heuristics. The heuristics was like 1. if my rover is far from the obstacle, choose the way which makes the path after the obstacle easier (with this logic, my rover could solve easy mazes) 2. otherwise, consider safety first, then consider distance. Hmm... actually, I forgot the detail.

Avoid risk: Suppose that the state of my rover is "accel and right turn". Simulate a second using the current state. If it turns out that my rover will die, my rover considers that the current state is risky. In this case, my rover tries 8 simulations with other states. If there is a state which can avoid the risk, my rover sends the commands to be the safe state, ignoring the macroscopic decision. If all states is risky, choose the state which can alive as long as possible.

I wrote a visualizer. It was important for me to fix many bugs. It shows the macroscopic plan using line. Also, it changes the color if my rover considers it's risky.

http://shinh.skr.jp/dat_dir/icfp08.png

After the contest, I wrote some scripts to show statistics.

http://shinh.skr.jp/icfp08/

Anyway, it was fun and I feel happy. Thanks for organizers!

start

2008-09-25T06:48:00.001-07:00

I have had a plan to start to write my note (I somehow don't like the word blog) in English long time, but I didn't. I am lazy, and I don't like to write English. Anyway, now I want to write an entry. So, I decided to start.