ICFP 2008 report: team ryba
Inspired by many other Adept reports, we took part in ICFP 2007 and ended up taking 4th place. The impressions of last year were the most positive, and this year we gathered again, though in a slightly different composition. This time we also had a lot of fun and we managed to cope with the task as a whole, it remains to wait for the conference and find out how good it is :)
From left to right: adaptive grid, path graph, trajectories
A great introduction for those who do not know what the International Conference on Functional Programming Contest is, how it is going and what task it was this year.
A little about the team.
')
Team ryba ICFP 2008 crew (in alphabetical order :)
Mike aizatsky
Alexey Gopachenko
Maxim mossienko
Roman Shevchenko
We all hold the opinion that the best tool is a proven one that you own the best. It just so happened that for us this is Java, so the question of choosing a language did not arise, especially considering the experience of ICFP 2007.
Like last year, Roma gathered us together. Personally, I prepared very thoroughly - I slept 15 hours before the very beginning.%) The results of last time made the right conclusions and we agreed to try to work no more than 8 hours a day - and if possible all at the same time. The place was chosen too verified - JetBrains office. All but Mike used their workstations under WinXP, and later VMWare Server worked on each with a LiveCD. Mike used his Mac Book Pro and native server as soon as it became available. Development environment - of course IntelliJ IDEA .
All the time the competition Roma followed the competition site, mailing list and compliance with the formalities (scripts, packaging, testing and sending results). He also downloaded and checked the LiveCD in advance and prepared the Subversion repository for the project.
As soon as the assignment was published we plunged into reading for 10 minutes.
The results of the five-minute brainstorming at the blackboard that followed:
Mike knows exactly how to do a search for a path on the map and immediately proceed.
it is necessary to make everything move as quickly as possible
write and link components: incoming / outgoing messages, model of the world, search for the way, taxiing, visualization
need a simple server simulator - because It is not known when the organizers will post it
Mike's solution involved building a graph of possible paths and finding the shortest path using the Dijkstra algorithm . The graph is built on the centers of the grid cells, which is obtained by adaptive recursive division into quadrants%) Writing and checking (using graph paper and a pen :) all this took Mike for an hour or two.
Meanwhile, Max is smartly writing a protocol, starting with the most needed facilities for all Telemetry, Obstacle, etc. Romka - visualization of how the rover sees the world and I started downloading maps with an eye to the implementation of the server. In order not to waste time and not to overburden the project, I used the code from www.json.org/java . Pretty quickly we reached our goal: I loaded the map and built the world view in the basic objects written by Max and Romka drew all this to us. There is no server yet and this is our only way to see the map. We regret to see that the example cards are very simple and very similar, and even with the same parameters of rovers and Martians.
Now Mike can test subdivision and finding the path on real maps. The best way to quickly evaluate tessellation work is visual and Mike appends the appropriate pieces of code to our visualizer. At this moment, for the first time, we see something like the one above. Immediately you can see the search works correctly, you only need to adjust the details and achieve maximum performance. After receiving food for thought (and more convenient toolkit), Mike again plunges his code.
Just as I gathered my courage to simulate physics, an exemplary server became available. Max was just ready for the network code, we raised the LiveCD and saw the creeping Martians. After looking at how everything works, we decided that we would not need our simulator. Just in time :)
I quickly sketched a “naive” work cycle, 1 telemetry => 1 command (AccelerateRightly). Launch and fascinated watch on the server as the rover smartly rolls forward, bounces off the walls and stones.
We come to the conclusion that physics is quite reasonable, and the Martians are surprisingly stupid. Nevertheless, as planned, we include all visible Martians in the graph as a “temporary” obstacle.
In the meantime, 6 hours have passed since the beginning of the competition. We agreed to sleep off properly and start tomorrow at 15:00 and parted.
At the end of the day we can:
connect to the server and parse the message flow
stupidly creep forward :)
divide the map into a grid of passable / forbidden zones (for simplicity, while describing squares around obstacles)
build the shortest path on a map, including any mazes
Appearing first, I proceed to the actual arrival - I listen to telemetry, update the internal map and the status of the rover. After that, I turn on the calculation of the path on the current map from the current position of the rover to the telemetry processing cycle. I see that on my (very powerful) machine it does not have time “in real time” and the latency accumulates. Given the fact that Mike immediately warned that he would seriously accelerate the calculation, I decided not to pay attention to it.
I watch as the map gradually manifests itself on the client, the Martians rush past. We process the end of the round and score. For some time we observe how the Martians rush one after another to the Martians and almost always miss the mark if it moves. Romka continues to work on visualization.
Then I thought of a way to significantly increase the comfort of development under Windows - start the server in a loop: while true; do server map.wrld; done - this way you could just launch the client at any time and watch the work without being distracted by the server console. Later I added svn up there and got the opportunity to conveniently and quickly change the map.
Max comes and we decide that it's time to learn to steer. Here we find that trigonometry was completely forgotten: (I will not describe this shame ... In general, while we re-read the definition of elementary trigonometric functions, late Mike appeared and saved everyone with the help of the pseudoscal product of vectors :) already come with a new search for the way.
As soon as we put all the parts together, the rover immediately became quite successful in reaching the base. Sometimes they could not cope with management, because did not take into account the variable latency of the telecontrol system.
considered their problems with telemetry calculation
take into account the fact that the server can send outdated steering position
By 22:00, we received quite stable results on test cards, and after fine tuning and checking under the LiveCD we sent a code to the ligntning round.
For an hour or two, we played with the code and discussed what needs to be improved and how, and finally forced ourselves to go to rest.
Latency optimization
Yes, yes, because of our schedule, we got 4 days :) On this day, the three of us remained - Mike could not join us.
First we decided to throw the Martians out of the search map. Because at high speed, they always missed their mark (which is not surprising) We decided that we would go on the way and dodge at the last moment. This allowed to recalculate the path only if new objects became visible.
Tuning
Max - speed speed
Yes, the task was very different from previous years, but we found it quite interesting. Yes, the training was clearly disappointed, but our team didn’t meet any obstacles. Although it would be more convenient to get a server under win, albeit without graphics. I really didn’t like the fact that there was little test data and the complete absence of an official way to assess our success ...
cool
colocation
schedule
TOU
stable module interfaces
statistics of tuning results
switching to other strategies
Team reports on the official wiki projects.cecs.pdx.edu/~jgmorris/icfpc08/index.cgi/wiki/TeamPages
Article habrahabr.ru/blog/icfpc/46589.html
From left to right: adaptive grid, path graph, trajectories
A great introduction for those who do not know what the International Conference on Functional Programming Contest is, how it is going and what task it was this year.
A little about the team.
')
Team ryba ICFP 2008 crew (in alphabetical order :)
Mike aizatsky
Alexey Gopachenko
Maxim mossienko
Roman Shevchenko
We all hold the opinion that the best tool is a proven one that you own the best. It just so happened that for us this is Java, so the question of choosing a language did not arise, especially considering the experience of ICFP 2007.
Like last year, Roma gathered us together. Personally, I prepared very thoroughly - I slept 15 hours before the very beginning.%) The results of last time made the right conclusions and we agreed to try to work no more than 8 hours a day - and if possible all at the same time. The place was chosen too verified - JetBrains office. All but Mike used their workstations under WinXP, and later VMWare Server worked on each with a LiveCD. Mike used his Mac Book Pro and native server as soon as it became available. Development environment - of course IntelliJ IDEA .
The first day (Friday 23:00 - Saturday 04:30)
All the time the competition Roma followed the competition site, mailing list and compliance with the formalities (scripts, packaging, testing and sending results). He also downloaded and checked the LiveCD in advance and prepared the Subversion repository for the project.
As soon as the assignment was published we plunged into reading for 10 minutes.
The results of the five-minute brainstorming at the blackboard that followed:
Mike knows exactly how to do a search for a path on the map and immediately proceed.
it is necessary to make everything move as quickly as possible
write and link components: incoming / outgoing messages, model of the world, search for the way, taxiing, visualization
need a simple server simulator - because It is not known when the organizers will post it
Mike's solution involved building a graph of possible paths and finding the shortest path using the Dijkstra algorithm . The graph is built on the centers of the grid cells, which is obtained by adaptive recursive division into quadrants%) Writing and checking (using graph paper and a pen :) all this took Mike for an hour or two.
Meanwhile, Max is smartly writing a protocol, starting with the most needed facilities for all Telemetry, Obstacle, etc. Romka - visualization of how the rover sees the world and I started downloading maps with an eye to the implementation of the server. In order not to waste time and not to overburden the project, I used the code from www.json.org/java . Pretty quickly we reached our goal: I loaded the map and built the world view in the basic objects written by Max and Romka drew all this to us. There is no server yet and this is our only way to see the map. We regret to see that the example cards are very simple and very similar, and even with the same parameters of rovers and Martians.
Now Mike can test subdivision and finding the path on real maps. The best way to quickly evaluate tessellation work is visual and Mike appends the appropriate pieces of code to our visualizer. At this moment, for the first time, we see something like the one above. Immediately you can see the search works correctly, you only need to adjust the details and achieve maximum performance. After receiving food for thought (and more convenient toolkit), Mike again plunges his code.
Just as I gathered my courage to simulate physics, an exemplary server became available. Max was just ready for the network code, we raised the LiveCD and saw the creeping Martians. After looking at how everything works, we decided that we would not need our simulator. Just in time :)
I quickly sketched a “naive” work cycle, 1 telemetry => 1 command (AccelerateRightly). Launch and fascinated watch on the server as the rover smartly rolls forward, bounces off the walls and stones.
We come to the conclusion that physics is quite reasonable, and the Martians are surprisingly stupid. Nevertheless, as planned, we include all visible Martians in the graph as a “temporary” obstacle.
In the meantime, 6 hours have passed since the beginning of the competition. We agreed to sleep off properly and start tomorrow at 15:00 and parted.
At the end of the day we can:
connect to the server and parse the message flow
stupidly creep forward :)
divide the map into a grid of passable / forbidden zones (for simplicity, while describing squares around obstacles)
build the shortest path on a map, including any mazes
Second day (Saturday 4:00 pm - Sunday 3:00 am), Lightening round
Appearing first, I proceed to the actual arrival - I listen to telemetry, update the internal map and the status of the rover. After that, I turn on the calculation of the path on the current map from the current position of the rover to the telemetry processing cycle. I see that on my (very powerful) machine it does not have time “in real time” and the latency accumulates. Given the fact that Mike immediately warned that he would seriously accelerate the calculation, I decided not to pay attention to it.
I watch as the map gradually manifests itself on the client, the Martians rush past. We process the end of the round and score. For some time we observe how the Martians rush one after another to the Martians and almost always miss the mark if it moves. Romka continues to work on visualization.
Then I thought of a way to significantly increase the comfort of development under Windows - start the server in a loop: while true; do server map.wrld; done - this way you could just launch the client at any time and watch the work without being distracted by the server console. Later I added svn up there and got the opportunity to conveniently and quickly change the map.
Max comes and we decide that it's time to learn to steer. Here we find that trigonometry was completely forgotten: (I will not describe this shame ... In general, while we re-read the definition of elementary trigonometric functions, late Mike appeared and saved everyone with the help of the pseudoscal product of vectors :) already come with a new search for the way.
As soon as we put all the parts together, the rover immediately became quite successful in reaching the base. Sometimes they could not cope with management, because did not take into account the variable latency of the telecontrol system.
considered their problems with telemetry calculation
take into account the fact that the server can send outdated steering position
By 22:00, we received quite stable results on test cards, and after fine tuning and checking under the LiveCD we sent a code to the ligntning round.
For an hour or two, we played with the code and discussed what needs to be improved and how, and finally forced ourselves to go to rest.
Third day (Sunday 4:00 pm - Monday 3:00 am)
Latency optimization
Fourth day (Monday 13:00 - 23:00)
Yes, yes, because of our schedule, we got 4 days :) On this day, the three of us remained - Mike could not join us.
First we decided to throw the Martians out of the search map. Because at high speed, they always missed their mark (which is not surprising) We decided that we would go on the way and dodge at the last moment. This allowed to recalculate the path only if new objects became visible.
Tuning
Max - speed speed
Conclusion
Yes, the task was very different from previous years, but we found it quite interesting. Yes, the training was clearly disappointed, but our team didn’t meet any obstacles. Although it would be more convenient to get a server under win, albeit without graphics. I really didn’t like the fact that there was little test data and the complete absence of an official way to assess our success ...
cool
colocation
schedule
TOU
stable module interfaces
statistics of tuning results
switching to other strategies
Shortcuts
Team reports on the official wiki projects.cecs.pdx.edu/~jgmorris/icfpc08/index.cgi/wiki/TeamPages
Article habrahabr.ru/blog/icfpc/46589.html
Source: https://habr.com/ru/post/29137/
All Articles