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.
 * Given a target position target, return 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.
 * Constraints:
 * 1 <= target <= 104
 */
impl Solution {
  pub fn racecar(target: i32) -> i32 {
    use std::collections::{HashMap, VecDeque};
    let mut dist: HashMap<(i32,i32), i32> = HashMap::new();
    let mut queue: VecDeque<(i32, i32, i32)> = VecDeque::new();
    queue.push_back((0, 1, 0)); // pos, speed, steps
    dist.insert((0, 1), 0);
    while let Some((pos, spd, steps)) = queue.pop_front() {
      if pos == target { return steps; }
      // Accelerate
      let npos = pos + spd;
      let nspd = spd * 2;
      if npos.abs() <= 2 * target && !dist.contains_key(&(npos, nspd)) {
        dist.insert((npos, nspd), steps + 1);
        queue.push_back((npos, nspd, steps + 1));
      }
      // Reverse
      let rspd = if spd > 0 { -1 } else { 1 };
      if !dist.contains_key(&(pos, rspd)) {
        dist.insert((pos, rspd), steps + 1);
        queue.push_back((pos, rspd, steps + 1));
      }
    }
    -1
  }
}