Algod/dynamic_programming/
egg_dropping.rs

1/// # Egg Dropping Puzzle
2
3/// `egg_drop(eggs, floors)` returns the least number of egg droppings
4///     required to determine the highest floor from which an egg will not
5///     break upon dropping
6///
7/// Assumptions: n > 0
8pub fn egg_drop(eggs: u32, floors: u32) -> u32 {
9    assert!(eggs > 0);
10
11    // Explicity handle edge cases (optional)
12    if eggs == 1 || floors == 0 || floors == 1 {
13        return floors;
14    }
15
16    let eggs_index = eggs as usize;
17    let floors_index = floors as usize;
18
19    // Store solutions to subproblems in 2D Vec,
20    // where egg_drops[i][j] represents the solution to the egg dropping
21    // problem with i eggs and j floors
22    let mut egg_drops: Vec<Vec<u32>> = vec![vec![0; floors_index + 1]; eggs_index + 1];
23
24    // Assign solutions for egg_drop(n, 0) = 0, egg_drop(n, 1) = 1
25    for egg_drop in egg_drops.iter_mut().skip(1) {
26        egg_drop[0] = 0;
27        egg_drop[1] = 1;
28    }
29
30    // Assign solutions to egg_drop(1, k) = k
31    for j in 1..=floors_index {
32        egg_drops[1][j] = j as u32;
33    }
34
35    // Complete solutions vector using optimal substructure property
36    for i in 2..=eggs_index {
37        for j in 2..=floors_index {
38            egg_drops[i][j] = std::u32::MAX;
39
40            for k in 1..=j {
41                let res = 1 + std::cmp::max(egg_drops[i - 1][k - 1], egg_drops[i][j - k]);
42
43                if res < egg_drops[i][j] {
44                    egg_drops[i][j] = res;
45                }
46            }
47        }
48    }
49
50    egg_drops[eggs_index][floors_index]
51}
52
53#[cfg(test)]
54mod tests {
55    use super::egg_drop;
56
57    #[test]
58    fn zero_floors() {
59        assert_eq!(egg_drop(5, 0), 0);
60    }
61
62    #[test]
63    fn one_egg() {
64        assert_eq!(egg_drop(1, 8), 8);
65    }
66
67    #[test]
68    fn eggs2_floors2() {
69        assert_eq!(egg_drop(2, 2), 2);
70    }
71
72    #[test]
73    fn eggs3_floors5() {
74        assert_eq!(egg_drop(3, 5), 3);
75    }
76
77    #[test]
78    fn eggs2_floors10() {
79        assert_eq!(egg_drop(2, 10), 4);
80    }
81
82    #[test]
83    fn eggs2_floors36() {
84        assert_eq!(egg_drop(2, 36), 8);
85    }
86
87    #[test]
88    fn large_floors() {
89        assert_eq!(egg_drop(2, 100), 14);
90    }
91}
Algod/dynamic_programming/egg_dropping.rs

Algod/dynamic_programming/
egg_dropping.rs
