Daily bit(e) of C++ | Race car
Daily bit(e) of C++ #100, Common interview problem: Race car
Today we will look at a common interview problem: Race car.
Given a target, you are given the following car controls:
accelerate:
position += speed; speed *= 2;reverse:
speed = (speed > 0) ? -1 : 1;
What is the minimum number of steps (A/R) to reach the target? Assume target {1..10’000} and starting speed of one.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/cxqzsxnT4.
Solution
Since we are interested in the minimum number of steps, a.k.a. the minimum path, we can attempt to solve this problem using a breadth-first search.
Our search space will be all positions and all speeds. There are only log(target) possible speeds, so we end up with O(target*log(target)) complexity.
The downside of this approach is that it is very undirected. As we search for the minimum path, we effectively search through all the infeasible paths.
There is a better and more complex approach. Consider what happens when we continually accelerate. The distance travelled will be 1+2+4+8… which means that the resulting number in binary will be 0b11111…
On top of that, there are only two ways we can reach a target:
we overshoot it and need to reverse and go back a bit
we undershoot it, then reverse twice to reset our speed and go forward a bit
This is almost the solution; however, there is a hitch. Consider the target == 5. The optimal solution is AARARAA (move 3, reverse, move 1, reverse, move 3) with length 7. However, the above description would give us the solution AARRAARA (move 3, reset, move 3, reverse, move 1) with the length 8. The tricky part is that when we reverse twice, the optimal solution might involve going back a bit (i.e. the trailing move-back can be inserted between the two reverse operations).
To find these situations, we need not only to take a minimum from the two options (undershoot and overshoot) but also iterate over feasible move-backs that are inserted in between the two reverse operations.
Since we now only work with positions and not speeds, we are slashing the complexity down to O(target); however, since our search is very focused, we will be more in line with log(target) operations.