<p>Your car starts at position <code>0</code> and speed <code>+1</code> on an infinite number line. Your car can go into negative positions. Your car drives automatically according to a sequence of instructions <code>&#39;A&#39;</code> (accelerate) and <code>&#39;R&#39;</code> (reverse):</p>

<ul>
	<li>When you get an instruction <code>&#39;A&#39;</code>, your car does the following:

	<ul>
		<li><code>position += speed</code></li>
		<li><code>speed *= 2</code></li>
	</ul>
	</li>
	<li>When you get an instruction <code>&#39;R&#39;</code>, your car does the following:
	<ul>
		<li>If your speed is positive then <code>speed = -1</code></li>
		<li>otherwise <code>speed = 1</code></li>
	</ul>
	Your position stays the same.</li>
</ul>

<p>For example, after commands <code>&quot;AAR&quot;</code>, your car goes to positions <code>0 --&gt; 1 --&gt; 3 --&gt; 3</code>, and your speed goes to <code>1 --&gt; 2 --&gt; 4 --&gt; -1</code>.</p>

<p>Given a target position <code>target</code>, return <em>the length of the shortest sequence of instructions to get there</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> target = 3
<strong>Output:</strong> 2
<strong>Explanation:</strong> 
The shortest instruction sequence is &quot;AA&quot;.
Your position goes from 0 --&gt; 1 --&gt; 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> target = 6
<strong>Output:</strong> 5
<strong>Explanation:</strong> 
The shortest instruction sequence is &quot;AAARA&quot;.
Your position goes from 0 --&gt; 1 --&gt; 3 --&gt; 7 --&gt; 7 --&gt; 6.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= target &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution:
    def racecar(self, target: int) -> int:
        """
        For these hard problems, it's very important to make sure
        that we understand the problem.

        Possible techniques:
        - Dynamic Programming
        - Search

        Let's think about how we might do a best-first search.
        We could store a heap with the following tuples:
        (sequence length, distance to target, current position, current speed)

        We can pop the smallest current sequence from the heap.
        Then, we can take these positions and add the next positions
        to the heap.

        Optionally, we might use a dictionary that maps locations to the
        smallest sequence length to get to that location, which would help us
        to avoid processing any locations more than once.
        This might also simply be a set that contains visited locations.
        This doesn't really work, as we will need to stay in the same position
        if we are even to change direction.
        Also, it's possible to need to be in the same position again at a
        different speed.

        This is the tricky part.
        The number of steps to the goal depends on BOTH the current position
        AND the current speed.
        We can reach the goal at ANY speed.
        This is what makes me doubt Dynamic Programming as an approach.
        It seems like we're not working with finite bounds in terms of both
        position and speed.
        We'd have to build a 2D table over all positions and all speeds, but
        I don't know where the bounds of that would be.
        This is what makes me lean towards using search.

        Could we use a better heuristic?
        Let's turn this into an actual A* problem.
        We need a heuristic that is both admissible and consistent.
        - Admissible: never overestimate the cost to the target
        - Consistent: the current estimate is smaller than the cost to get
            to the next step plus the next step's estimate

        What would give us a consistent heuristic?
        Suppose we are at a current position with a current speed.
        How many steps would it take us naively to get to the target?

        For our heuristic, we need to find k in the following:
        curr_pos + curr_speed * (2 ** k - 1) <= target
        Thus,
        k <= math.floor(math.log2((target - curr_pos) / curr_speed + 1))

        This implementation was valiant, but it still doesn't look like
        it will work for the biggest of use cases.
        I think that we would be best to try to figure out a Dynamic
        Programming solution, like the tagged Topic suggests.

        Is there a way to bound the number of possible positions?
        I'm not sure that iterating through everything would even be faster
        than simply doing the search.
        Could I leverage the formula:
            curr_pos + curr_speed * (2 ** k - 1)
        in any way to be able to reach a solution faster?

        What if I could subtract the above quantity from the target?
        Then, I could get to the closer target as soon as possible, and
        then I could do a sprint to the finish.
        Would this be optimal?


        First of all, is there any reason for the car to go into
        negative positions?
        If we could go into negative positions, and then go forward,
        couldn't we do just as well to start with positive positions and then
        go backward?

        Perhaps Dynamic Programming doesn't have to go over the 

        Test cases: 330, 795, 5478
        """

        def compute_heuristic(curr_pos: int, curr_speed: int) -> int:
            result = 0

            if curr_speed < 0 and target > curr_pos:
                curr_speed = 1
                result += 1

            if curr_speed > 0 and target < curr_pos:
                curr_speed = -1
                result += 1

            result += math.floor(math.log2((target - curr_pos) / curr_speed + 1))

            return result

        start_seq_len = compute_heuristic(0, 1)
        start_pos = 2**start_seq_len - 1
        start_speed = 2**start_seq_len

        # (heuristic, seq_len, curr_pos, curr_speed)
        to_visit = [
            (
                start_seq_len + compute_heuristic(start_pos, start_speed),
                start_seq_len,
                start_pos,
                start_speed,
            )
        ]
        visited = set()

        while to_visit:
            _, seq_len, curr_pos, curr_speed = heapq.heappop(to_visit)

            if curr_pos == target:
                return seq_len

            if (curr_pos, curr_speed) in visited:
                continue

            visited.add((curr_pos, curr_speed))

            # Accelerate
            heapq.heappush(
                to_visit,
                (
                    seq_len
                    + 1
                    + compute_heuristic(curr_pos + curr_speed, curr_speed * 2),
                    seq_len + 1,
                    curr_pos + curr_speed,
                    curr_speed * 2,
                ),
            )

            # Reverse
            heapq.heappush(
                to_visit,
                (
                    seq_len
                    + 1
                    + compute_heuristic(curr_pos, -1 if curr_speed > 0 else 1),
                    seq_len + 1,
                    curr_pos,
                    -1 if curr_speed > 0 else 1,
                ),
            )

        return -1

41184