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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

struct Solution;
use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::collections::HashMap;

#[derive(PartialEq)]
struct State {
    id: usize,
    prob: f64,
}

impl State {
    fn new(id: usize, prob: f64) -> Self {
        State { id, prob }
    }
}

impl Eq for State {}

impl PartialOrd for State {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        self.prob.partial_cmp(&other.prob)
    }
}

impl Ord for State {
    fn cmp(&self, other: &Self) -> Ordering {
        self.partial_cmp(&other).unwrap()
    }
}

impl Solution {
    fn max_probability(
        n: i32,
        edges: Vec<Vec<i32>>,
        succ_prob: Vec<f64>,
        start: i32,
        end: i32,
    ) -> f64 {
        let n = n as usize;
        let start = start as usize;
        let end = end as usize;
        let mut adj: Vec<HashMap<usize, f64>> = vec![HashMap::new(); n];
        for (i, edge) in edges.into_iter().enumerate() {
            let u = edge[0] as usize;
            let v = edge[1] as usize;
            let p = succ_prob[i];
            adj[u].insert(v, p);
            adj[v].insert(u, p);
        }
        let mut probs: Vec<f64> = vec![0.0; n];
        let mut queue: BinaryHeap<State> = BinaryHeap::new();
        queue.push(State::new(start, 1.0));
        probs[start] = 1.0;
        while let Some(parent) = queue.pop() {
            if parent.id == end {
                return parent.prob;
            }
            for (&child_id, &prob) in &adj[parent.id] {
                let new_prob = parent.prob * prob;
                if new_prob > probs[child_id] {
                    probs[child_id] = new_prob;
                    queue.push(State::new(child_id, new_prob));
                }
            }
        }
        0.0
    }
}

#[test]
fn test() {
    use assert_approx_eq::assert_approx_eq;
    let n = 3;
    let edges = vec_vec_i32![[0, 1], [1, 2], [0, 2]];
    let succ_prob = vec![0.5, 0.5, 0.2];
    let start = 0;
    let end = 2;
    let res = 0.25;
    assert_approx_eq!(
        Solution::max_probability(n, edges, succ_prob, start, end),
        res
    );

    let n = 3;
    let edges = vec_vec_i32![[0, 1], [1, 2], [0, 2]];
    let succ_prob = vec![0.5, 0.5, 0.3];
    let start = 0;
    let end = 2;
    let res = 0.3;
    assert_approx_eq!(
        Solution::max_probability(n, edges, succ_prob, start, end),
        res
    );

    let n = 3;
    let edges = vec_vec_i32![[0, 1]];
    let succ_prob = vec![0.5];
    let start = 0;
    let end = 2;
    let res = 0.00000;
    assert_approx_eq!(
        Solution::max_probability(n, edges, succ_prob, start, end),
        res
    );
}