Problem
Your car starts at position 0 and speed +1 on an infinite number line. Your car can go into negative positions. Your car drives automatically according to a sequence of instructions ‘A’ (accelerate) and ‘R’ (reverse):
When you get an instruction ‘A’, your car does the following:
position += speed
speed *= 2
When you get an instruction ‘R’, your car does the following:
If your speed is positive then speed = -1, otherwise speed = 1
Your position stays the same.
For example, after commands “AAR”, your car goes to positions 0 –> 1 –> 3 –> 3, and your speed goes to 1 –> 2 –> 4 –> -1.
Given a target position target, return the length of the shortest sequence of instructions to get there.
Testcases
Example 1:
Input: target = 3
Output: 2
Explanation: The shortest instruction sequence is “AA”. Your position goes from 0 –> 1 –> 3.
Example 2:
Input: target = 6
Output: 5
Explanation: The shortest instruction sequence is “AAARA”. Your position goes from 0 –> 1 –> 3 –> 7 –> 7 –> 6.
Initial Result
Time spent: 50 min
Fail. Passed both provided testcases and didn’t face the (expected) time limit error but instead failed to understand basic testcases.
Initial Approach
I immediately thought of dynamic programming based on the goal of finding the length of the shortest length sequence. I drew more (suboptimal) test cases for target = 6 in hopes of realizing when to “turn around” (change the multiplier and reset the index of a list (doesn’t have to be a list, but I tried either way) that increases the power of 2 used to change the total sum). My takeaways were that the goal is to find the turnaround points by checking values beyond the “peak” that is just beyond the value desired since we can always traverse by small steps (0, 1, 3, etc.) in order to readjust in the opposite direction.
After that, I didn’t really think too hard about implementing this solution and getting it to pass the 2 provided testcases took about 30 minutes, which is itself quite long. I’m not too worried about this since I think there are underlying speedups in eliminating ideas (like this solution which didn’t work) that will shorten this topic selection process to 10-15 minutes (and hopefully improve the final implementation too).
What I Missed
Before even looking at the solution, I know that I don’t understand testcases like target = 4 –> count = 5… Now that I’ve looked at the solution, I see that I don’t really need to know to solve that by hand. The difficulty in finding the solution is a hint to the appropriate algorithm to use: BFS (for one solution at least). I need to reinforce graph use cases more, and the one of interest here is using BFS for any shortest path problem in an unweighted graph. I actually am pretty sure I would be able to find the optimization for BFS that leads to a correct solution (see below).
Approach to the Solution
Add the results of the two possible moves (A and R) to the queue and evaluate. This simple solution unfortunately gives a TLE (though I noticed a MLE first due to the queue).
There are two successful solutions: modified BFS or DP.
Modified BFS Solution
The queue gets too big so we need to filter what goes in it. The solution I saw removed the actions variable from the queue and made it into a global variable, but this is actually not necessary. The important part is that we only add an “accelerate” action when we are in the positive region and have travelled less than 2 * target from 0 (essentially going past target no more than the distance to target itself). The logic against these cases seems to be that the subproblem of going back to target shouldn’t itself be larger than the original problem in any optimal solution.
DP Solution
Consider two ways to reach target: overshoot (go past target and come back) vs undershoot (start n - 1 acceleration steps before target, reverse back twice, and then accelerate to fill the gap). This can be expressed as the following recurrence relation: $dp[t] = min(1 + nafter_t + dp[2nafter_t - 1 - t], 2 + dp[t - (2n*before_t - 1) + (2m - 1)])$. n is bit length, and it’s relevance isn’t clear to me. I’m not gonna explore this solution any further since it’s beyond the scope of my current goals (but will be loads of fun later).
Key Takeaways
Write things in order on the page and always start on a new page. Continue commenting code extensively (even while brainstorming due to virtual whiteboard-style interviews). Learn when to use which graph algorithm and why and always ask yourself if graph algos or DP are more applicable to your path-finding problem. Be cautious about assuming aspects of the pattern in an abstract problem like this one (brute force is basically the answer after all).