ICFP 2003 contest - my poor contribution

The problem

The best way is to go to the contest's page to know what's all this about.

My contribution

I did not make the "rally" mode, I did not have enough time.

My results are poor.

Here comes the README coming with my entry.

            ICFP 2003 code contest

       -=[ Drunk Sed team info file ]=-

Hi !

This is my poor attempt to ICFP.
I could not solve all the mazes, my program is fooled
like a poor rabbit.

I started the contest with a friend of mine
(does he want to be named after seing my
poor performance ?), we wanted to do some
exhaustive search, use O'Caml as language
(since my friend loves it), have some nice
hacks here and there, but we did not succeed.

After some sleep, on sunday 15:00 GMT if I remember,
I started this on my own. Of course, the ideas
we had together with some I already had helped
a lot, but the time was short.

Here is the result...

I'll try to create
http://sed.free.fr/icfp2003
when I'll get some time.

How does it work ?
==================

First of all, I look for a short path in the map, using
some modified version of Dijkstra algorithm. Mainly,
instead of computing the cost of an atomic arc, I take
the father too. I could repeat this process up to the
root of the tree, but well... not much time to hack
more. So I associate some cost with this, if you turn
too much, the cost is different than if you go straight.

The problem with this is that you only look at the squares,
so the distances are estimated, some may be wrong. All in
all, you don't get the shortest path. And you don't take
too much into account the properties of the car.

A lot could be done to optimize this phaze of the program.

Then, I start on a point of this curve and run the car,
only doing acceleration, acceleration and turn left,
acceleration and turn right. I take the farthest point
of the curve accesible like this. I then do this process
again from this new point with a starting speed of 0.

It will give me a path of points that the car can access
by only accelerating and turning. (If it 'magically'
stops when it arrives.)

Then, the final step is to glue all these points together,
and this is where all goes wrong. It's too late to
do better, so you can see that the car driver looks
a bit drunk, doing a lot of useless loops. This is
because the car _must_ pass through the control point,
in order to be sure I can go to the next. But it does
not always work, and when it does, you may loop weirdly.

In this step of the program, since I previously reseted
the speed to 0 at each point, I have to smooth the speeds
so that the transition may be possible. This is done by
choosing a number of little steps (a, r, l, la, lr) and
doing some b (brake) from there up to the end of the
portion of the curve considered, which should lead us
to the next control point. If it fails, I start the b
earlier on the curve. Of course, this does not always
work, and when it does, it sometimes produces weird loops.

Unfortunately, I am alone, too much optimization to do, etc.
Thus, I get bad results...

The lesson I'll get from this contest is that I hardly
can work with others.

Another lesson is that C is nice :) but I already knew it.
(Well, one could say it's not, since I have bad performance.
Ok, that's a way of seing things. I hardly can disagree with
these views. :))

How to use ?
============

The program to run to get the dump is
in the 'basic' subdirectory.
The 'simulator' subdirectory will take a file as input,
a trace on stdin, and produce a picture of the car steps.

There are some useless programs in images subdirectory,
that I used to watch the files we had to work on.

Is all this material copyrighted ?
==================================

No, I don't like copyrights. All this is in the
public domain.

Period.

I am deadly tired, no more subways nor buses, it's soon
2 AM here in Paris, when the contest will stop, I will
have to walk home (around 1 hour, 1 hour 30), all this
for nothing since I will lose.
Life sucks sometimes, huh ?
But it was fun (even if I should work on my PhD instead
of wasting my time for such useless stuff) (ok,
I am really tired, stop this crap)

CÚdric.

Tue,  1 Jul 2003 01:32:07 +0200

The sources

Here are the sources: src.tar.gz (18,978 bytes).

You still need the maps, that you can find on the contest's page.

The code is terrifyingly ugly. It's just a big hack. The allocated memory is not freed, there is a lot of dead code, no comments, probably bad overall design. And of course, the algorithms are not so good.

Some parameters have changed over the maps. If you try this code, it may not work. Hey, the goal of the contest was to solve maps, not to code clean, so it's ok. (What did you say? functional programming? huh?)

The maps

Here is a summary of the results I have.

1: 26,527 
2: 39,411 
3: 42,062 
4: not solved 
5: 18,837 
6: 8,096 
7: 14,786 
8: not solved 
9: not solved 
10: not solved 

Here come all the maps, the one I "solved" and the others.

Click to enlarge.

Sorry for blind people. (If you are blind and can view these images, tell me how you do, I am interested.)

It is surely not the best solutions available, but the originality of my contribution is the "drunk" behavior of the car. I swear I did not drink any alcohol while coding this. And I swear I did not create those maps by hand. The program (and my bad algorithmic skills) is the sole responsible for this.

The first map, Simple

I solved this one in 26,527 steps.

Here is the trace.

The second map, Hairpins

I solved this one in 39,411 steps.

Here is the trace.

The third map, Sepang

I solved this one in 42,062 steps.

Here is the trace.

The fourth map, EatYouAlive

I did not solve it.

The fifth map, Car

I solved this one in 18,837 steps.

Here is the trace.

The sixth map, IcfpContest

I solved this one in 8,096 steps.

I don't know what happened, there must have been a bug in my code, it's too fast for me.

Here is the trace.

The seventh map, Gothenburg

I solved this one in 14,786 steps.

Here is the trace.

The eighth map, ManyWays

I did not solve it.

The ninth map, PhilAndSimon

I did not solve it.

The tenth map, Rally

I did not solve it.

An original map

To finish, here is a map. Try your method on it. Yes, it is a valid map, the two circles touch each others!

Here is the map itself: Impossible_Universe.trk.gz.

And here comes a picture of it.

What others did


1_Simple_4.trc: 8171 
2_Hairpins_1.trc: 12661 
3_Sepang_2.trc: 14615 
4_EatYouAlive_1.trc: 15043 
5_Car_1.trc: 5575 
6_IcfpContest_1.trc: 5051 
7_Gothenburg_3.trc: 3305 
8_ManyWays.trc: 7420 
9_PhilAndSimon_1.trc: 7841 
total: 79682 

Our submission can be found at
http://www.gwydiondylan.org/~bruce/submit.tar.gz

Bruce Hoult 
Alex Potanin 
Keith Bauer

Hudson

1: _8127 
2: 12675 
3: 14558 
4: 14228 
5: _5624 
6: _4939 
7: _3308 
8: _7444 
9: _6382 

total: 77285

See his website at http://www.cs.utexas.edu/users/ahudson/.


Kent Dickey

I realized right away I wouldn't have time to make a fully automated
solver, so I made a manual car driving "game" first (as my backup plan)
and then worked on some mixed guided/automatic code which didn't really
work, so I mostly manually drove the car through the courses. Every time
I play I can do a little better, but here's what I submitted: 

10231 1_Simple.trc 
18419 2_Hairpins.trc 
16951 3_Sepang.trc 
16748 4_EatYouAlive.trc 
6074 5_Car.trc 
5455 6_IcfpContest.trc 
4733 7-Gothenburg.trc 
9462 8_ManyWays.trc 
10599 9_PhilAndSimon.trc 
98672 total



I've developed a feel for what the car can do, but I never got around
to working out optimal driving strategies. 

If anyone is tolerant of a horrible user interface (and I mean horrible)
and has Mac OS X, I could make the code and application available.

Jed

I used a (fairly simplistic, all things considered) genetic algorithm to
optimize my paths, but I didn't have time to do any kind of automatic
pathfinding. Which means that I had to be able to "drive" a track by hand
before I could start beating it with CPUs. That said: 

1) 10397 (down from 11668) 

2) 18490 (down from 20763) 

3) 21558 (down from 23095) 

4) 20592 (down from 23188) 

5) 7471 (down from 6222) 

6) 5367 (down from 7296) 

7) Didn't get. Crashed the car quite a few times, though. 

8) Didn't have anything in time, but current evolution is at 13957 (down
from 15590) and falling. Of course, the path I picked out while careering
wildly amidst the squares is probably highly suboptimal. 

9) Yow. No. Although it is an inspiration to try and use the GA to find the
initial solution... 

X) I refuse to acknowledge the existence of the skid rules. /-:

Kuang-che Wu

I drive the car by handcraft, 
and it seems not so bad. 
1:8611 
2:13294 
3:15681 
4:15290 
5:5552 
6:4906 
7:4122 
8:8463 
9:7685 
total 83604

SomeOne

I didn't have time to do this ... 
I could only made the game in allegro and played... 

1: 14708 
2: 22717 
3: 33058 
4: 35875 
5: 10537 
6: 12914 
7: 10608 
8: 37840 
9: 41373 

Total (till 9): 219630 SUCKED! 

I didn't have time to implement the skidding and I made X with the same
program ... 

X: 60586 

Total: 280216 

Really bad ...

Sidoine

1_Simple 13905 
2_Hairpins 20579 
3_Sepang 20588 
4_EatYouAlive 21832 
5_Car 8337 
6_IcfpContest 6647 
7_Gothenburg 6509 
8_ManyWays 22023 
9_PhilAndSimon 15031 

Total 135451 

Not good but it works so I'm happy with it. Maybe with some more tuning
I could have done slighty better but not as good as Hudson or Bruce Hoult. 
http://www.sidoine.net/icfp/
Croco

Well.. 

1: 12177 
2: 20335 
3: 21975 
4: 26642 
5: 8846 
6: 7247 
7: 8520 
8: 20329 
9: 30943 

Sum: 157014 

Nothing to be happy with. Okay, may be I should have taken a look at visual
simulations of my traces -- I never did so. The simulator is fully automated.
BTW, each track is solved in 5 minutes or so using my celeron333. 

There are lots of heuristically-choosen constants to change in my code. All
heuristics are buggy, or else they'd be algorythms 

Sami

1 - 8168 
2 - 12730 
3 - 14910 
4 - 14281 
5 - 5565 
6 - 4937 
7 - 3387 
8 - 7523 
9 - 7719 
-------------- 
total 79220 

I used a stochastic greedy algorithm but couldn't get it working well
enough; I knew I'd take a beating on track 9 . Pruning the state space
more systematically would have been a better approach - congrats to AIDude
and Hudson! And thanks to all involved, it was lotsa fun.

abagar

well, we used a RRT based path planner. It could solve only one track (7)with
original source and goal. Then we provided the algorithm some guidence with
intermediate goals, it solved 4 more. 3 more we solved by a very crude human
directed greedy algo. The big numbers out there come from this 3rd approach.
9th we could not solve. 

Here are the approximate numbers : 

1. ~12000 
2. 40337 
3. ~37000 
4. 40100 
5. 7673 
6. 8773 
7. 6798 
8. 12276 
9. Could not solve. 

But it was lots of fun and lots of learning. Kudos to organizers 
and in case u are wondering, we did it in Java. What about others?

http://zolo.freelsd.net/~sts/ICFP2003/
this is our website where you can find 
some pictures of our works 

regards 

-- 
h

There is also the webpage of the team Team Spud http://madbean.com/icfp2003/.

And the webpage of the team Fastest Finishers http://www24.brinkster.com/srineet/ICFP2003/ICFP2003.html.

And the one of the team The 4 Caml Riders of the Apocalypse http://www.lri.fr/~filliatr/icfp-2003/index.en.html.

Go here to get all the web pages of the participants that have been submitted to the organizers.


Creation time: Tue, 1 Jul 2003 03:34:11 +0200
Last update: Wed, 2 Jul 2003 15:26:09 +0200

Contact: sed@free.fr
Please avoid html, uuencode, base64, mime, etc.
Prefered mail format is raw text, 80 column width maximum. Other formats may get lost, wrongly tagged as undesired data.

Sorry for my poor english.