1
use std::collections::VecDeque;
2

3
#[derive(Clone, Copy)]
4
struct State {
5
  speed: i32,
6
  pos: i32,
7
  moves: i32,
8
}
9
impl Solution {
10
  pub fn racecar(target: i32) -> i32 {
11
    let mut frontier = VecDeque::new();
12
    frontier.push_back(State {
13
      speed: 1,
14
      pos: 0,
15
      moves: 0,
16
    });
17
    while let Some(State { speed, pos, moves }) = frontier.pop_front() {
18
      if pos == target {
19
        return moves;
20
      }
21
      // Always allow accelerating.
22
      frontier.push_back(State {
23
        speed: speed * 2,
24
        pos: pos + speed,
25
        moves: moves + 1,
26
      });
27
      if allow_reverse(target, pos, speed) {
28
        frontier.push_back(State {
29
          speed: -1 * speed.signum(),
30
          pos: pos,
31
          moves: moves + 1,
32
        });
33
      }
34
    }
35
    -1
36
  }
37
}
38

39
pub fn allow_reverse(target: i32, position: i32, speed: i32) -> bool {
40
  // If speed + pos would overshoot target in one direction, allow reverse.
41
  let next_to_target = target - (speed + position);
42
  // If we're before the target and moving forwards, or after the target
43
  // and moving backwards, then we're moving in the correct direction and
44
  // shouldn't allow reverse--this corresponds to a positive sign of
45
  // the product.
46
  speed * next_to_target < 0
47
}