818. Race Car Hard

1/**
2 * [818] Race Car
3 *
4 * 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):
5 * 
6 * 	When you get an instruction 'A', your car does the following:
7 * 	
8 * 		position += speed
9 * 		speed *= 2
10 * 	
11 * 	
12 * 	When you get an instruction 'R', your car does the following:
13 * 	
14 * 		If your speed is positive then speed = -1
15 * 		otherwise speed = 1
16 * 	
17 * 	Your position stays the same.
18 * 
19 * For example, after commands "AAR", your car goes to positions 0 --> 1 --> 3 --> 3, and your speed goes to 1 --> 2 --> 4 --> -1.
20 * Given a target position target, return the length of the shortest sequence of instructions to get there.
21 *  
22 * Example 1:
23 * 
24 * Input: target = 3
25 * Output: 2
26 * Explanation: 
27 * The shortest instruction sequence is "AA".
28 * Your position goes from 0 --> 1 --> 3.
29 * 
30 * Example 2:
31 * 
32 * Input: target = 6
33 * Output: 5
34 * Explanation: 
35 * The shortest instruction sequence is "AAARA".
36 * Your position goes from 0 --> 1 --> 3 --> 7 --> 7 --> 6.
37 * 
38 *  
39 * Constraints:
40 * 
41 * 	1 <= target <= 10^4
42 * 
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/race-car/
47// discuss: https://leetcode.com/problems/race-car/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50
51impl Solution {
52    pub fn racecar(target: i32) -> i32 {
53        0
54    }
55}
56
57// submission codes end
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test_818() {
65    }
66}
67