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.

818. Race Car
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);
}