How does the smoothing calculation work?

The images below demonstrate how the "nearby" points are determined. For each image, the points on the planner defined path are represented by black dots and the highlighted A,B, and C show the coordinates used to calculate the "smoothness" for the second point in the path (point B).

The first figure represents the path for "1 1 2 1 2 2 2 3". In this case to calcuate the smoothness for the second point (B) the points A, B and C are used, where C is the point on the path distance 1.0 between the second and third points, as shown in the figure.

This path with a sharp 90 degree turn has a smoothness cost of \(2*k_s\).

The figure below represents the path for "1 1 1.5 1 2 1.5 2 3". This path is smoother because the 90 degree angle has been replaced with a diagonal. To calcuate the smoothness for the second point (B) in this path the points A, B and C are used, where A has been projected from the first line segment a distance 1.0 from B (before the path even starts). The point C is the distance 1.0 in the other direction, which in this case is on the line segment between the 3rd and 4th points.

The total smoothness cost for this path, including both moderate angles is \(\sim1.75*k_s\).

What square do the coordinates (1.5, 2.49999) correspond to?

Normal rounding rules apply, so the point (1.5, 2.49999) is in the same square as (2,2).

Why do I get a "wall clock time limit" message?

The most common cause (aside from being very slow), is that your program is buffering too much. Many high level languages are optimized for bulk data processing and don't actually return a line of data until many lines are read under the hood. For instance, in python, you need to use the "-u" command line option and use the sys.stdin.readline() method to avoid additional buffering. Other languages and environments have similar approaches to avoid getting stuck.

#!/usr/bin/python -u

import sys

while True:
  a = sys.stdin.readline()
  print a,

If you buffer too much, the dispatcher thinks it has sent a query, but your application code hasn't seen it and thus can't respond. The dispatcher never sends a second query until the first has been responded to, so it just sits there and waits until the time limit expires.

How is the score determined for each map?

The dispatcher sends up to 1,000 queries for each map (less if you hit the time limits). Your score is the sum of the score for all paths returned. Thus, your score improves as you respond to more queries, assuming the resulting paths are of the same quality. For instance, the trivial solution should be able to respond to all queries easily, but the paths are not particularly high quality so the overall score is not very good. A more sophisticated solution will run into the time limit, in which case making it faster is another way to improve your score.

Where is the barrier? What happens if I hit it?

The barrier is defined by the "#" in the map. As with the example maps, all maps are rectangular and outermost rectangle of each map is composed of barrier squares. For example the upper left most square, with coordinate (0, 0), is always a barrier, as is anything in the top row or first column, etc. Flying into the barrier is a fatal event for the robot, however, none of the queries require you to fly into a barrier. If you attempt to fly over a barrier, you will get an error like:

Error:error handling path: '1 1 0.499 2 2 2', path crosses barrier 

In this example, the second point (0.499, 2) is part of the left barrier of the map, because 0.499 rounds to zero, thus the point is in the square for (0, 2).