// Tower of Hanoi

use std::collections::LinkedList;

// Inner field stores the disk's width
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
struct Disk(usize);

#[derive(Debug, Clone)]
struct Rod(LinkedList<Disk>);

impl Rod {
    #[inline]
    fn new() -> Self {
        Rod(LinkedList::new())
    }

    #[inline]
    fn len(&self) -> usize {
        self.0.len()
    }

    #[inline]
    fn is_empty(&self) -> bool {
        self.len() == 0
    }

    fn is_descending_order(&self) -> bool {
        let mut last = Disk(0);

        for elem in &self.0 {
            if *elem < last {
                return false;
            }

            last = *elem;
        }

        true
    }

    #[inline]
    fn push(&mut self, d: Disk) {
        self.0.push_front(d);
    }

    #[inline]
    fn top(&self) -> Option<Disk> {
        self.0.front().cloned()
    }

    fn move_to(&mut self, dest: &mut Rod) -> bool {
        let x1 = match self.top() {
            Some(d) => d,
            None => return false,
        };

        let x2 = match dest.top() {
            Some(d) => d,
            None => {
                dest.push(self.0.pop_front().unwrap());
                return true;
            }
        };

        if x1 < x2 {
            dest.push(self.0.pop_front().unwrap());

            true
        } else {
            false
        }
    }

    #[inline]
    fn move_to_either(&mut self, c1: &mut Rod, c2: &mut Rod) -> bool {
        self.move_to(c1) || self.move_to(c2)
    }
}

fn compute_moves(n: usize) -> Vec<String> {
    let mut root = Rod::new();
    let mut aux = Rod::new();
    let mut res = Rod::new();

    for i in (1..=n).rev() {
        // number of disks
        root.push(Disk(i));
    }

    let mut alt = 0;

    while res.len() != n-1 {
        match alt {
            0 => {
                root.move_to_either(&mut res, &mut aux);
            }
            1 => {
                aux.move_to_either(&mut res, &mut root);
            }
            2 => {
                res.move_to_either(&mut aux, &mut root);
            }
            _ => unreachable!(),
        }

        alt = (dbg!(alt) + 1) % 3;

        if !res.is_empty() && res.is_descending_order() && res.len() == n-1 {
            break;
        }
    }

    dbg!((root, aux, res));
    Vec::new()
}

fn main() {
    compute_moves(3);
}