//! returns: 0
//! Tower of Hanoi.
//! Solve Tower of Hanoi for N disks, recording moves into an array.
//! Verify the move count and specific moves are correct.

const NUM_DISKS: u32 = 6;
/// 2^6 - 1 = 63 moves.
const MAX_MOVES: u32 = 63;

/// A single move: move a disk from one peg to another.
record Move {
    disk: u32,
    from: u32,
    to: u32,
}

/// Log of all moves performed.
record MoveLog {
    moves: [Move; 63],
    count: u32,
}

/// Record a move.
fn recordMove(ml: *mut MoveLog, disk: u32, from: u32, to: u32) {
    if ml.count < MAX_MOVES {
        ml.moves[ml.count] = Move { disk, from, to };
        ml.count += 1;
    }
}

/// Solve Tower of Hanoi recursively.
/// Move `n` disks from peg `from` to peg `to` using `aux` as auxiliary.
fn hanoi(ml: *mut MoveLog, n: u32, from: u32, to: u32, aux: u32) {
    if n == 0 {
        return;
    }
    hanoi(ml, n - 1, from, aux, to);
    recordMove(ml, n, from, to);
    hanoi(ml, n - 1, aux, to, from);
}

/// Verify total move count.
fn testMoveCount(ml: *MoveLog) -> i32 {
    // For N disks, there are 2^N - 1 moves.
    assert ml.count == MAX_MOVES;
    return 0;
}

/// Verify specific moves.
fn testSpecificMoves(ml: *MoveLog) -> i32 {
    // First move: smallest disk (1) from peg 0 to peg 2.
    assert ml.moves[0].disk == 1;
    assert ml.moves[0].from == 0;
    assert ml.moves[0].to == 2;

    // Middle move (index 31): disk 6 from peg 0 to peg 1.
    assert ml.moves[31].disk == 6;
    assert ml.moves[31].from == 0;
    assert ml.moves[31].to == 1;

    // Last move: smallest disk (1) from peg 2 to peg 1.
    assert ml.moves[62].disk == 1;
    assert ml.moves[62].from == 2;
    assert ml.moves[62].to == 1;
    return 0;
}

/// Peg state: array of 3 pegs, each holding up to NUM_DISKS disks.
/// top[p] = number of disks currently on peg p.
record Pegs {
    stacks: [[u32; 6]; 3],
    top: [u32; 3],
}

fn pegPush(pegs: *mut Pegs, peg: u32, disk: u32) -> bool {
    let t = pegs.top[peg];
    if t > 0 {
        // Check that the top disk is larger than the one being placed.
        if pegs.stacks[peg][t - 1] < disk {
            return false;
        }
    }
    pegs.stacks[peg][t] = disk;
    pegs.top[peg] = t + 1;
    return true;
}

fn pegPop(pegs: *mut Pegs, peg: u32) -> u32 {
    let t = pegs.top[peg];
    if t == 0 {
        // Should not happen in a valid solution.
        return 0;
    }
    pegs.top[peg] = t - 1;
    return pegs.stacks[peg][t - 1];
}

/// Simulate the peg state to verify correctness.
/// Replay all moves and check:
/// 1. No larger disk is placed on a smaller disk.
/// 2. All disks end up on peg 1.
fn testSimulate(ml: *MoveLog) -> i32 {
    let mut pegs = Pegs {
        stacks: [[0; 6]; 3],
        top: [0, 0, 0],
    };

    // Initialize: all disks on peg 0, largest at bottom.
    let mut d: u32 = NUM_DISKS;
    while d >= 1 {
        assert pegPush(&mut pegs, 0, d);
        if d == 0 {
            break;
        }
        d -= 1;
    }

    // Replay all moves.
    let mut i: u32 = 0;
    while i < ml.count {
        let m = ml.moves[i];
        let disk = pegPop(&mut pegs, m.from);
        assert disk == m.disk;
        assert pegPush(&mut pegs, m.to, disk);
        i += 1;
    }

    // All disks should be on peg 1.
    assert pegs.top[0] == 0;
    assert pegs.top[1] == NUM_DISKS;
    assert pegs.top[2] == 0;
    return 0;
}

@default fn main() -> i32 {
    let mut ml = MoveLog {
        moves: [Move { disk: 0, from: 0, to: 0 }; 63],
        count: 0,
    };

    // Solve: move all disks from peg 0 to peg 1 using peg 2.
    hanoi(&mut ml, NUM_DISKS, 0, 1, 2);

    let r1 = testMoveCount(&ml);
    if r1 != 0 {
        return 10 + r1;
    }

    let r2 = testSpecificMoves(&ml);
    if r2 != 0 {
        return 20 + r2;
    }

    let r3 = testSimulate(&ml);
    if r3 != 0 {
        return 30 + r3;
    }
    return 0;
}