Programming Contest 42 - Fast Racing Car

In this contest your program reads a file full of track segments and then works out the acceleration (or braking) needed to move your car round the track faster than any other car.

The Track

Each segment of the track is defined by two numbers A and D. A is an angle value 0-11 which represents a multiple of 30 degrees, with 0 north, 3 (3 x 30=90) east, 6 south and 9 west. It's almost the same as a clock except for the 0 instead of 12. D is the distance the track runs in that direction in meters, with a maximum value of 500. So an entire race track is defined by a list of segments.

Note that track can change direction by up to +/- 4 (each is 30 degrees) angles. I.e. the maximum curve angle is 120 degrees, the smallest is 30 degrees. This is simplified for the contest; all curves have the same radius.

The maximum speed of your car on the track is 200 mph but each 30 degree curve direction change reduces this by 40 mph. I.e. to go through a 120 degree bend, your car must be going no faster than 40 mph (=200-4*40) when it enters, 80 mph through a 90 degree curve etc. For time/speed purposes a curve is always 100 m long irrespective of angle and there is a curve between every track segment but not before the first segment or after the last.

Your car must enter a curve at the speed limit or below and if it is above the speed limit it crashes out and it's game over man! However, if it doesn't crash out, it can immediately accelerate out of the curve. Your car's move (see below) might take it so it is positioned one meter into the curve and traveling at the curve's top speed. Your car's next move can have full acceleration (5 m/s²) even though this would in theory have it traveling above the curve's top speed. Only entering the curve above top speed causes a crash.

Acceleration and Deceleration

All cars have a top acceleration of 5m/s². This means that every second, its speed can increase by 5m/s. From standing still, after 1 second it is traveling at 5 m/s, after 2 it's at 10. etc. Cars can decelerate by up to 20 m/s² but they don't go backwards or faster than 200 MPH.

Your challenge is to write a program that reads the track segments and then generate moves to take your car through the course as fast as possible without crashing.

Input File

This is a single file track.txt in the same location as your exe consisting of pairs of numbers, comma separated each on a line. The first number is the Angle as a multiple of 30 degrees (0-11) (Same as on a clock face except 0 instead of 12), the second a distance in meters.

• Download track.txt.

Output File

You should create a file drive.txt in the same location as the input file track.txt that has pairs of numbers, comma separated, one pair on each line. The first is the time in seconds eg 10.65 (2 decimal places is fine) and the second is the acceleration or deceleration, a value between -20 and + 5. Acceleration is a +ve value from 0.01 to 5. Deceleration is a -_ve value from -0.01 to -20. Fractional values such as 0.56 (again 2 decimal places) are ok.

A program of mine will read your output file, calculate speed and distance traveled and work out if your car crashes at any corners (too high speed) and the total time taken to complete one lap.

Notes

This contest requires a slight familiarity with the four simple equations of motion. These use these variables:

• u -- Initial velocity in M/sec (Meters Per second)
• v -- Final velocity in (M/Sec)
• a -- Acceleration in M²/sec
• S -- Distance M in Meters
• t -- Time in seconds

Equations

• v = u + a*t
• v² = u² + 2*a*s
• S = ut + 0.5*A*t²
• s = (u+v)/2*t

The four equations may come in useful for working out how far your car will travel etc. If it is doing 20 m/s (u) and you apply an acceleration (a) of 2.4 m/s for 5 seconds (t) then after 5 seconds it will

1. be traveling at 32 m/s (v=u+a*t = 20+5*2.4)
2. have traveled 130 meters. (s=ut + 0.5*a*t² = 20*5 + 0.5*2.4*5²)

There's a bit more background on GCSE Maths but don't fret; this is not a complicated contest. Those equations just let you work out the speed or distance traveled for a given set of conditions. All values are metric which simplifies things, apart from the track speed limits which are in MPH.

Meters/Second and Miles Per Hour

One meter per second = 2.23693629 mph. So 10 m/s is ~ 22.369 mph. Here's a useful conversion table.

MPH  M/S
40   17.88
80   35.76
120  53.64
160  71.53
200  89.41

Results

Congratulations to Pedro Graca whose car managed to just beat Jason Mark's by a 1/2 second. James's car seemed to have a lots of fits and starts (Kangaroo fuel?).

1. Pedro Graca 18 - C 73.48
2. Jason Marks 18 - C++ 74.01
3. James Borden 18 - C# 1005.5

This was not an easy puzzle and it took me a day or two to get the marking program correct. Thanks to all three entrants.

Rules

This is for glory only. About.com does not permit prizes to be given.

Please submit your source code and the output file to the cplus.guide@about.com?subject=Programming Contest 42 email address with the subject line Programming Contest 42.

It must compile with Open Watcom, Microsoft Visual C++ 2008/2010 Express Edition/Microsoft Visual Studio 2008/2010 or Borland Turbo C++ Explorer, Microsoft Visual C# 2008/2010 Express Edition or GCC/G++. If it doesn't compile, it can't be run so is automatically disqualified.

Please include your name, age (optional), blog/website url (optional) and country. Your email address will not be kept, used or displayed except to acknowledge your challenge entry. You can submit as many entries as you like before the deadline which is December 31 2010.

The top ten entries will be listed, judged purely on points. A condition of entry is that you allow your source code to be published on this website, with full credits to you as the author.

• An index of Every Past Programming Contest on this site