Race Car: Minimum Instructions to Reach a Target

The phone screen used LeetCode 818, Race Car, in its standard form: find the minimum instruction count needed for a car with position and signed speed to reach a target. Requirements The car starts at position 0 with speed +1. Instruction A moves the car by its current speed and then doubles that speed. Instruction R leaves the position unchanged and reverses the direction, resetting the speed magnitude to 1. Given a target position, return the minimum number of instructions needed to reach it. Notes This is LeetCode 818, Race Car, in its standard form. Define the reachable state and search bounds explicitly; an unbounded position-speed space is not directly implementable. Be prepared to justify why the chosen recurrence or traversal returns the global minimum rather than merely a valid instruction sequence. Preparation Derive the state transitions and stopping bounds on paper before implementing them. Implement both a shortest-state-search version and a memoized recurrence, then compare their state counts on increasing targets. Rehearse the overshoot-and-reverse cases, which are the key correctness test for the model.