# LeetCode 818: Race Car

## Problem Restatement

We have a race car on an infinite number line.

The car starts at:

```python
position = 0
speed = 1
```

There are two possible instructions.

| Instruction | Effect |
|---|---|
| `"A"` | `position += speed`, then `speed *= 2` |
| `"R"` | If speed is positive, set speed to `-1`; otherwise set speed to `1` |

The `"R"` instruction changes only the direction and resets speed magnitude to `1`. It does not change the position.

Given an integer `target`, return the length of the shortest instruction sequence that makes the car reach exactly `target`. The car is allowed to move into negative positions.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer `target` |
| Output | Minimum number of instructions |
| Start | Position `0`, speed `1` |
| Instruction `"A"` | Move by current speed, then double speed |
| Instruction `"R"` | Reverse direction and reset speed to `1` or `-1` |

## Examples

Example 1:

```python
target = 3
```

Use:

```python
"AA"
```

Simulation:

| Step | Position | Speed |
|---|---:|---:|
| Start | 0 | 1 |
| A | 1 | 2 |
| A | 3 | 4 |

The answer is:

```python
2
```

Example 2:

```python
target = 6
```

One shortest sequence is:

```python
"AAARA"
```

Simulation:

| Step | Position | Speed |
|---|---:|---:|
| Start | 0 | 1 |
| A | 1 | 2 |
| A | 3 | 4 |
| A | 7 | 8 |
| R | 7 | -1 |
| A | 6 | -2 |

The answer is:

```python
5
```

## First Thought: BFS Over States

A direct way is BFS over states:

```python
(position, speed)
```

Each edge is one instruction, either `"A"` or `"R"`.

Since every instruction has cost `1`, BFS can find the shortest sequence.

This works, but the state space is large. We need bounds to avoid exploring too far. A dynamic programming solution is more compact because the target is one-dimensional.

## Key Insight

After driving forward with `k` accelerations from position `0`, the car reaches:

```python
1 + 2 + 4 + ... + 2^(k - 1) = 2^k - 1
```

So positions of the form:

```python
2^k - 1
```

are reachable using exactly `k` instructions.

For a target `t`, let `k` be the smallest integer such that:

```python
2^k - 1 >= t
```

There are two main strategies.

First, if `2^k - 1 == t`, just accelerate `k` times.

Second, if we overshoot to `2^k - 1`, reverse, then solve the remaining distance:

```python
(2^k - 1) - t
```

Third, we may stop before the target. Drive forward `k - 1` times to reach:

```python
2^(k - 1) - 1
```

Then reverse, drive backward for `j` accelerations, reverse again, and solve the remaining distance.

## Algorithm

Let:

```python
dp[t] = minimum instructions needed to reach position t
```

Use memoized recursion.

For a target `t`:

1. Find `k = t.bit_length()`.
2. Let:

```python
forward = (1 << k) - 1
```

3. If `forward == t`, return `k`.

4. Try overshooting:

```python
k + 1 + dp(forward - t)
```

This means:

```python
k accelerations + 1 reverse + solve remaining distance
```

5. Try stopping short.

Let:

```python
before = (1 << (k - 1)) - 1
```

Then for each `j` from `0` to `k - 2`, drive backward `j` accelerations after reversing.

The backward distance is:

```python
back = (1 << j) - 1
```

The remaining distance is:

```python
t - (before - back)
```

The instruction count is:

```python
(k - 1) + 1 + j + 1 + dp(remaining)
```

That is:

```python
forward accelerations + reverse + backward accelerations + reverse + solve remaining
```

Return the minimum among these choices.

## Correctness

The car’s forward-only position after `k` accelerations is exactly `2^k - 1`, because each acceleration moves by the current speed and then doubles the speed.

For a target `t`, choose the first forward-only position that reaches or passes `t`.

If it equals `t`, no shorter sequence can use fewer than `k` accelerations to reach that far from the start, so returning `k` is correct.

If it passes `t`, one valid optimal form is to overshoot, reverse, and solve the remaining distance back toward the target. This gives the overshoot candidate.

The other possible optimal form is to reverse before reaching or passing the target. After `k - 1` accelerations, the car is at the largest forward-only position still below `t`. If it reverses there, it may move backward for `j` accelerations, reverse again, and then solve a smaller forward subproblem. The algorithm checks every possible `j`, so it considers every such early-reverse strategy.

The recurrence therefore covers all optimal first phases: either reach exactly, overshoot once, or stop short and reverse back by some amount before continuing. Since each remaining part is solved optimally by `dp`, the computed minimum is the true shortest instruction length.

## Complexity

Let `T = target`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(T log T)` | Each target value may try up to `O(log T)` reverse distances |
| Space | `O(T)` | Memoization stores results for target distances |

## Implementation

```python
from functools import cache

class Solution:
    def racecar(self, target: int) -> int:
        @cache
        def dp(t: int) -> int:
            k = t.bit_length()
            forward = (1 << k) - 1

            if forward == t:
                return k

            best = k + 1 + dp(forward - t)

            before = (1 << (k - 1)) - 1

            for j in range(k - 1):
                back = (1 << j) - 1
                remaining = t - (before - back)

                best = min(
                    best,
                    (k - 1) + 1 + j + 1 + dp(remaining),
                )

            return best

        return dp(target)
```

## Code Explanation

The recursive function solves one distance:

```python
def dp(t: int) -> int:
```

We compute the number of accelerations needed to reach or pass `t`:

```python
k = t.bit_length()
forward = (1 << k) - 1
```

If `forward == t`, then `k` accelerations land exactly on the target:

```python
if forward == t:
    return k
```

The overshoot option drives to `forward`, reverses, and solves the extra distance:

```python
best = k + 1 + dp(forward - t)
```

Then we try stopping short:

```python
before = (1 << (k - 1)) - 1
```

For each possible backward run:

```python
for j in range(k - 1):
```

we compute how far backward it goes:

```python
back = (1 << j) - 1
```

The position after going forward, reversing, going backward, and reversing again is:

```python
before - back
```

So the remaining distance is:

```python
remaining = t - (before - back)
```

The command count for this strategy is:

```python
(k - 1) + 1 + j + 1 + dp(remaining)
```

Finally, the smallest strategy is returned.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.racecar(1) == 1
    assert s.racecar(2) == 4
    assert s.racecar(3) == 2
    assert s.racecar(4) == 5
    assert s.racecar(5) == 7
    assert s.racecar(6) == 5

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `1` | One acceleration reaches target |
| `2` | Requires overshoot or reverse logic |
| `3` | Exact `2^k - 1` target |
| `4` | Past exact position, needs reverse |
| `5` | Checks stop-short strategy |
| `6` | Official example shape with `"AAARA"` |