Главная Ссылки Тексты Техноложка Разные доки ICFP Contest 2003 О русской революции C++ IDE plugin Разное  
SPB Team: ICFP2003 Programming Contest
Team members:

Dmitry Boulytchev

Anton Moscal

Eugene Vigdorchick

We all are from the Mathematics & Mechanics Faculty of St.Petersburg (Russia) University.

Here is the our group home page.

For contest we are used computers of the IntelliJ Software, which currently is employer of two from us (Dmitry Boulytchev and Eugege Vigdorchik). Thanks, IntelliJ.

Languages used:
We use mix of the O'Caml and the GNU C (we use such GNU-specific features as inline functions and 64-bit arithmetic).

You can download our last submission here.

The results are following:
  Simple: [1_Simple.png] 8258
  Hairpins: [2_Hairpins.png] 12800
  Sepang: [3_Sepang.png] 14971
  EatYouAlive: [4_EatYouAlive.png] 14496
  Car: [5_Car.png] 5650
  IcfpContest: [6_IcfpContest.png] 4956
  Gothenburg: [7_Gothenburg.png] 3400
  ManyWays: [8_ManyWays.png] 7599
  PhilAndSimon: [9_PhilAndSimon.png] 6600
TOTAL: 78730
  Rally: [X_Rally.png] 37195
  Een: [A_Een.png] 8069

SPbTeam Solution Sources:

The sources organized as follows:

  • README -- README file
  • sim.ml -- algorithm body
  • simulator.[ch] -- C runtime (includes fixed poin arith. and step calculator)
  • Makefile
  • util/
    • executor.ml -- trace simulator
    • optimizer.ml -- tiny optimizer
    • painter.ml -- track reducer
    • dijkstra.ml -- Dijkstra's shortest path algorithm
    • morda.ml -- and graphic interface for it
    • simulator.[ch], sim.ml, trace.ml --- parts of ../sim.ml
The Algorithm:

Since we didn't manage to find any proven-optimal algorithm we've used search-and-cut strategy flavoured with miscellaneous heuristics.

The algotrithm look like this:

  1. Choose any state (x, y, v, d, t) from an active set.
  2. For each operation (a., l., r. etc.) apply it to choosen set N times (actually we use different N's from 50 to 150).
  3. Filter obtained set of states.
  4. Repeat until goal is reached.

This is a screenshot of the process:


Initially active set consists of starting state.

Some heuristics used to cut the active set:

  1. States are ordered by distance to goal.
  2. States behind some distance from "leader" are cutted.
  3. If we got state with coordinates, speed and direction close to one of "earliest" states then "new" state is dropped.

Some adaptive features are introduced: "closeness" criteria strengthens near the bounds of track, distance from the "leader" is reduced when active set become too large and increased if active set become too small.


Two optimizations are performed:

  • After first algorithm run the track is reduced to some neihbourghood of resulted trajectory and algorithm repeats with harder parameters.


    This is a screenshot of the "restricted" trace #8

  • Resulted trace optimized: sequence of rolls changed to accelerate-brake sequence, left-right turns changed to roll.