The best way is to go to the contest's page to know what's all this about.
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
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?)
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.
I solved this one in 26,527 steps.
Here is the trace.
I solved this one in 39,411 steps.
Here is the trace.
I solved this one in 42,062 steps.
Here is the trace.
I did not solve it.
I solved this one in 18,837 steps.
Here is the trace.
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.
I solved this one in 14,786 steps.
Here is the trace.
I did not solve it.
I did not solve it.
I did not solve it.
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.
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 athttp://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?
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.
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.