## 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".
```
```Example 2:
Input:
target = 6
Output: 5
Explanation:
The shortest instruction sequence is "AAARA".
```

Note:

• `1 <= target <= 10000`.

## Rust Solution

``````struct Solution;

use std::collections::HashMap;
use std::collections::VecDeque;

impl Solution {
fn racecar(target: i32) -> i32 {
let mut queue: VecDeque<(usize, i32, i32)> = VecDeque::new();
let mut states: HashMap<(i32, i32), usize> = HashMap::new();
queue.push_back((0, 0, 1));
states.insert((0, 1), 0);
while let Some((length, position, speed)) = queue.pop_front() {
if position == target {
return length as i32;
}

for (p, s) in Self::next(position, speed) {
if p > target + target / 3 || p < -target / 3 {
continue;
}
if states.contains_key(&(p, s)) && states[&(p, s)] <= length + 1 {
continue;
}
*states.entry((p, s)).or_default() = length + 1;
queue.push_back((length + 1, p, s));
}
}
0
}

fn next(position: i32, speed: i32) -> Vec<(i32, i32)> {
vec![
(position + speed, speed * 2),
(position, if speed > 0 { -1 } else { 1 }),
]
}
}

#[test]
fn test() {
let target = 3;
let res = 2;
assert_eq!(Solution::racecar(target), res);
let target = 6;
let res = 5;
assert_eq!(Solution::racecar(target), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.