rustgym 0.2.0

rustgym solutions
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

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);
}