algorithms_edu/problems/misc/
tower_of_hanoi.rs

1//! - [Wikipedia](https://www.wikiwand.com/en/Tower_of_Hanoi)
2
3// WIP
4
5#[derive(Debug)]
6pub struct TowerOfHanoi {
7    a: Vec<usize>,
8    b: Vec<usize>,
9    c: Vec<usize>,
10    history: Vec<(Vec<usize>, Vec<usize>, Vec<usize>)>,
11}
12
13impl TowerOfHanoi {
14    fn init(size: usize) -> Self {
15        Self {
16            a: (1..=size).rev().collect(),
17            b: vec![],
18            c: vec![],
19            history: Vec::new(),
20        }
21    }
22
23    pub fn solve(size: usize) -> Vec<(Vec<usize>, Vec<usize>, Vec<usize>)> {
24        let mut tower = Self::init(size);
25        fn _move(
26            n: usize,
27            tower: *mut TowerOfHanoi,
28            source: &mut Vec<usize>,
29            target: &mut Vec<usize>,
30            auxiliary: &mut Vec<usize>,
31        ) {
32            if n > 0 {
33                // Move n - 1 disks from source to auxiliary, so they are out of the way
34                _move(n - 1, tower, source, auxiliary, target);
35                // Move the nth disk from source to target
36                target.push(source.pop().unwrap());
37                // Update progress
38                unsafe {
39                    (*tower).history.push((
40                        (*tower).a.clone(),
41                        (*tower).b.clone(),
42                        (*tower).c.clone(),
43                    ))
44                };
45
46                // Move the n - 1 disks that we left on auxiliary onto target
47                _move(n - 1, tower, auxiliary, target, source)
48            }
49        }
50        _move(
51            size,
52            &mut tower as *mut TowerOfHanoi,
53            &mut tower.a,
54            &mut tower.b,
55            &mut tower.c,
56        );
57        tower.history
58    }
59}
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64    #[test]
65    pub fn test_tower_of_hanoi() {
66        let history = TowerOfHanoi::solve(4);
67        assert_eq!(
68            &history,
69            &[
70                (vec![4, 3, 2], vec![], vec![1]),
71                (vec![4, 3], vec![2], vec![1]),
72                (vec![4, 3], vec![2, 1], vec![]),
73                (vec![4], vec![2, 1], vec![3]),
74                (vec![4, 1], vec![2], vec![3]),
75                (vec![4, 1], vec![], vec![3, 2]),
76                (vec![4], vec![], vec![3, 2, 1]),
77                (vec![], vec![4], vec![3, 2, 1]),
78                (vec![], vec![4, 1], vec![3, 2]),
79                (vec![2], vec![4, 1], vec![3]),
80                (vec![2, 1], vec![4], vec![3]),
81                (vec![2, 1], vec![4, 3], vec![]),
82                (vec![2], vec![4, 3], vec![1]),
83                (vec![], vec![4, 3, 2], vec![1]),
84                (vec![], vec![4, 3, 2, 1], vec![])
85            ]
86        );
87    }
88}
algorithms_edu/problems/misc/tower_of_hanoi.rs

algorithms_edu/problems/misc/
tower_of_hanoi.rs
