# 818 Race Car

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.

Now for some target position, say the **length** of the shortest sequence of instructions to get there.

```
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.
```

**Note:**

* `1 <= target <= 10000`.

**The Idea**: Perform a BFS with added DP and tree pruning. Begin from the base position. From there we have two choices. If we ever come back to the same position AND speed, then we know we're just looping back into the tree - so ignore those. Another optimization is that from our two options, our target position will never be exceed by what twice it.

![race car](/files/-LoJIiQEUuTFqLRlaMKv)

**Complexity:** O(2^n) time and space (absolute worse case)

```python
import queue


class Solution:
    def racecar(self, target):
        """
        :type target: int
        :rtype: int
        """

        history = set()
        q = queue.Queue()

        history.add((0, 1))
        q.put(((0, 1), 0))

        while not q.empty():
            pos_speed, lvl = q.get()
            pos, speed = pos_speed[0], pos_speed[1]
            r1, r2 = (pos + speed, speed * 2), (pos, -1 if speed > 0 else 1)
            target2 = target + target

            if pos == target:
                return lvl
            if pos + speed < target2 and r1 not in history:
                q.put((r1, lvl + 1))
                history.add(r1)
            if pos < target2 and r2 not in history:
                q.put((r2, lvl + 1))
                history.add(r2)
        return -1
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/818-race-car.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.