ICFP Programming Challenge


I entered the contest (see icfp 2003) to see if TCL was up to the task of other language. Although the challenge is aimed at function langauges, any language can be used in the contest.

Due to an unfortunate set of circumstances I did not receive the contest start notification until a day after the start. I almost did not take up the challenge because of this , but eventually decided to as an academic exercise.
I had only Two days to write the code and did not get it completely finished before the deadline. I achieved the following:

  1. Read tack file and display.
  2. Code fixed point arithmetic routines.
  3. Run Example simulation file and produce same results as test file.
  4. Automatically Find Route through two mazes.
  5. Basics of drive routine but not complete control.
  6. 90% of User interface.

I carried on coding up until I hade spent the alloted time on the contest. The current state of the code and this documentation was the result.

The task description can be found here


The archive of the code that was created can be found here.


Due to the presure of a late start I did not look at the example data and started from the route finding code. This in hindsight was a mistake as this was not an important part of getting a result.

Once I moved onto the simulator I saw that it was just as easy to create the route by hand and get the car to try and follow the manually created route. Had I started with this end I could have solved some of the tracks in the time I had.


Route finding

Because iterative methods in Tcl become impractical due to the time required to iterate over the millions of combinations , a simpler approach was used based in the Sober Sailer analogy.
Unlike the drunken sailor we work purposefully (but no necessarily optimally) towards the goal.

We start at the start and cast rays out in a given direction. We then test for collision. If none we continue from the end of the ray in the same direction.
When we collide we backup and then change direction slightly and try again. If a route cannot proceed in any direction, or it crosses our path , we backtrack in the path and try another direction.

This approach quickly finds a way from start to end. It does not however compute the optimal path, not does it construct the path in a way that matches the dynamics of the car. This means that there is no gaurentee that the car can actually drive the path at speed.

Collision detection

Rather than maintaining an associative array of objects and bounding boxes, the objects were drawn on a canvas.
Since the canvas coordinates are floating point values, they can be used directly without having to be mapped between different geometry spaces.
There are problems due to round off errors accumulating due to the testing system using fixed point arithmetic only.

Because of the number of points was too much for TCL to handle efficiently, the images were rasterised into linesegments. While only two types of points existed, go, no go, there could have been a small number of lines used to represent them.
However visually the nogo areas were coloured so they we kept as seperate entities so they could be rendered as intended.

A problem was found when attempting to test if a proposed travel direction intersected a line. This was caused by limits in precision.
The solution to this was to rasterize the image in both the x and y directions. This ensured that there was always one line segment out of the three that was not coincident so the intersection test would be reliable.

A better approach would have been to use a flood fill to obtain the bounding box of an area and then represent this with a polygon object.

When casting a ray and checking for collision. the command canvas find could be used to return a list of possible line segments that would be intersected with our proposed path.
However to do the actual intersection test required iterating through each line found and doing the required number of tests for collision. One advantage of not using rectangles was that a smaller number of objects need to be tested as only those objects within the bounding box of the ray need to be tested. A polygon object could occupy three quarters of the problem space and thus would have to be tested with virtually all path segments.


Driving the car is straight forward. One has a limited number of options and the functions are mostly linear functions.

We turn the car and accelerate to the next point in the path. Once we hit the point we slow down. We constantly turn to drive toward the next mark. If we overshoot the mark we change to the next point in the path and try to head for this new point. If we are more than 10% different in direction that we are heading with respect with the direction we should be going then we stop accelerating and just turn.

What is missing is feedback. Once the directions have been found , the simulation data should be used as feedback to modify the placement of the path within the boundary of acceptable area.

If for example on driving the route, a wall is hit, it the required modification to the route could then be computed to prevent this from happening. Ie Either slow down eairlier of move a prior path segment further from the obstical that was hit.

One could then use graph searching to compute the list of possiblities and each of these tried in turn to see which one is quicker (not necessarily the shortest path).

This is a simple algorithm but requires that the point in the path be placed appropriately.

An alternative approach is to only accelerate for half ( actually 60% ) the length of line and then brake for the rest so that we gaurantee that we hit the next point. This however would not be a very fast way to travel the route.


During development there were some areas that caused problems. These are explained here.

Canvas Performance

The canvas performacnce drops exponentially when there are lots of objects with the same tag occuping spatially different locations. While the use of tags was not absolutely necesssary , it was the obvious way of coding the data.
There is a practical limit of approximately 10000 canvas items.

The number of points in a line also affected performance. I originally drew a trail of the cars position using 10 pixel resolution. Once the trail got to over 1000 coordinates the time to draw an extra coordinate became increasingly longer.

Data structures

There are well known solutions to this type of problem. Graph searches are one of the most common. Tcl only supports linked and nested structures by use of associated arrays. The lookup time for these sparse arrays is too long to be practical for use in this problem.


The exercise was to test TCL in a real world application. The contest example was infact more a test of high order mathmatics rather than a coding challenge.

If one has an advanced understanding of Newtonian Physics and Mathmatics, then the solution would have been easy. It was infact a mathmatics exercise rather than a programming one.

The following observations were made about the abilites of TCL for this challenge:

  1. Visual Components
    It was easy to draw the tracks and display the information during the simulation process. Other functions such as intersection detection on the canvas had to be hand coded.
    With some acceptability of round off errors, the canvas could be used as the database for the track data as well as car position.

  2. Debugging
    It was easy to debug most aspects of the system due to the interpreted nature of the language. The readline library caused problems with being called when an asynchronous procedure was being executed and calling update to allow user interaction.

  3. Speed
    This was the real weakness of the language. Tcl struggled to give an acceptable level of performance which dramitically slowed down development.
    This was due to A) The problem required using fixed point mathmatics to ensure that the same results were generated with different computer architectures. And B) The iterative nature of the problem, requiring many loops of the code.

  4. Numeracy
    Since this was the whole crux of finding a solution. The ability of expr to handle 64 bit integers made it easy to implement the fixed point arithmetic. Having to use expr to iteratively compute solutions was not conducive to high speed computing. Apart from the tan function having a range of -pi/2 to pi/2 rather than -pi to pi, TCL was able to produce the precision necessary in the generated data.

  5. Practicality
    If this challenge was a task to be solved in real time in say a Car Navigation product then TCL would struggle to do the job. In all likely hood the programmer would resort to using a C extension for the computational parts and use TCL as the GUI.


I still use TCL in real world applications, including GPS navigation systems.
However as a complete solution I found in this case (as I often do) that 80% of the problem can be implemented very quickly. Unfortunately the remaining 20% sometimes is unachievable and one has to resort to another language to complete the task.
While it may have never been intended that TCL was a solution in it's own right, it has the flexibility to do most jobs asked of it so there becomes the expectation that it should do it all.
Most programmers are not used to using multiple languages (or paradigms) in solving a specific problem, so when faced with the prospect of having to switch to another language, they will favour developing the whole application in the alternate language.

Even using well known algorithms for solving this problem, TCL lacks the speed and depth of data structures to practicaly solve this problem completely. I give Tcl a rating of 7/10 for suitablity to this problem. I give myself 6 / 10 for the suitability of the code used in the algorithms used to solve the problem.

Back To TCL index
1/Jul 2003
Copyright © Q Solutions 2003Contact