How to implement solution for Race simulation problems

Question

There was a question asked in an interview:

In a Formula-1 challenge, there are n teams numbered 1 to n. Each team has a car and a driver. Car’s specification are as follows:

• Top speed: (150 + 10 * i) km per hour
• Acceleration: (2 * i) meter per second square.
• Handling factor (hf) = 0.8
• Nitro : Increases the speed to double or top speed, whichever is less. Can be used only once.

Here i is the team number. The cars line up for the race. The start line for (i + 1)th car is 200 * i meters behind the ith car.

All of them start at the same time and try to attain their top speed. A re-assessment of the positions is done every 2 seconds(So even if the car has crossed the finish line in between, you’ll get to know after 2 seconds). During this assessment, each driver checks if there is any car within 10 meters of his car, his speed reduces to: hf * (speed at that moment). Also, if the driver notices that he is the last one on the race, he uses ‘nitro’.

Taking the number of teams and length of track as the input, calculate the final speeds and the corresponding completion times.

I don't understand how to approach this kind of problems. For each instance should I be checking all C(n,2) combinations of every pair of drivers and compute the result? But how can I figure out at what instance I should make the calculations?

Answer 1

If you check the Conway's Game of Life you will find that there is a lot in common with the Race Problem.

Here is the analogy:

• The initial state (the seed of the system):
  • Game of Life: initial pattern on the grid. Every cell having the following parameters:
    • x and y coordinate
    • whether the cell is alive or dead
  • Race Problem: n cars each one having predetermined parameters and the length of the track l. Every car has the following parameters:
    • top speed
    • acceleration
    • handling factor
    • position on track
    • current speed
• The rules are applied at discrete moments which are called ticks.
  • Game of Life: the rules are applied simultaneously to every cell from the previous generation producing a next generation. Each generation is a pure function of the preceding one.
  • Race Problem: the rules are applied simultaneously to every car from the previous state producing a next state. This happens every 2 seconds. Same as in Game of Life each step is a pure function of the preceding one which means that it only depends on the parameters of the cars from the previous state.

What's different is that the Game of Life never ends whereas the Race Problem should terminate when the current position of every car is greater or equal to the track length l (Although the last statement is arguable: due to the handling factor it's possible that in some conditions some cars will never reach the finish line).

The key point is that calculations are done at discrete moments which answers your question:

But how can I figure out at what instance I should make the calculations?

You can take the idea from the Algorithms section to solve this problem. You need to have 2 arrays of cars: one representing the current state and the other representing the next step. On each iteration you recalculate the current position and the speed of every car following the rules from the assignment and check whether the loop should terminate. Before the next iteration you swap the array roles so that the successor array in the last iteration becomes the current array in the next iteration.

The high level pseudo-code may look like this:

n = ..; // initial number of cars
l = ..; // track length
Car[] currentState = initializeState(n, l);
Car[] nextState = clone(currentState);
for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) {
    calculateNextState(currentState, nextState, iteration);
    swap(currentState, nextState);
    if (shouldTerminate(currentState, l) {
        break;
    }
}

printResultOrClaimNotTerminated(currentState);

The rules are applied in the calculateNextState(..) function. In the most naive implementation you check every pair of cars which gives you

O (C(n, 2)) = O (n * (n - 1) / 2) = O (n ^ 2)

complexity for each iteration. However you can think of possible optimizations here. For example you can sort the cars by current position first (O (n * log(n))) and then traverse the sorted array checking only adjacent cars (O (2 * n)). You can do this since if the 10 meters condition doesn't satisfy for adjacent cars it won't satisfy for non-adjacent cars. This will give you the resulting complexity of:

O (n * log(n))

which is much better. The sorted array of cars will naturally give you the car with last position to which you need to apply the nitro boost rule. Probably there can be other optimizations. This answers your question:

For each instance should I be checking all C(n,2) combinations of every pair of drivers and compute the result?