//! returns: 0
//! Ackermann function.
//! The Ackermann function is a classic benchmark for deep recursion and
//! stack usage. It grows extremely fast. We compute small values and
//! verify against known results. Also implements a memoized iterative
//! version and cross-checks the two.

/// Maximum memo table dimensions.
/// We memoize for m <= 3 and n <= MAX_N.
const MAX_M: u32 = 4;
const MAX_N: u32 = 128;

/// Classic recursive Ackermann function.
/// Only call with small arguments to avoid stack overflow.
fn ack(m: u32, n: u32) -> i32 {
    if m == 0 {
        return n as i32 + 1;
    }
    if n == 0 {
        return ack(m - 1, 1);
    }
    return ack(m - 1, ack(m, n - 1) as u32);
}

/// Memoized Ackermann using the closed-form for m <= 3, recursive for m > 3.
/// For m=0: A(0,n) = n+1
/// For m=1: A(1,n) = n+2
/// For m=2: A(2,n) = 2n+3
/// For m=3: A(3,n) = 2^(n+3) - 3
fn ackMemo(m: u32, n: u32) -> i32 {
    if m == 0 {
        return n as i32 + 1;
    }
    if m == 1 {
        return n as i32 + 2;
    }
    if m == 2 {
        return (2 * n + 3) as i32;
    }
    if m == 3 {
        // 2^(n+3) - 3
        let mut power: i32 = 1;
        let mut i: u32 = 0;
        while i < n + 3 {
            power *= 2;
            i += 1;
        }
        return power - 3;
    }
    // For m >= 4, fall back to recursion (only safe for very small n).
    if n == 0 {
        return ackMemo(m - 1, 1);
    }
    return ackMemo(m - 1, ackMemo(m, n - 1) as u32);
}

/// Power of 2 helper.
fn pow2(exp: u32) -> i32 {
    let mut result: i32 = 1;
    let mut i: u32 = 0;
    while i < exp {
        result *= 2;
        i += 1;
    }
    return result;
}

/// Test known small values using the recursive implementation.
fn testSmallRecursive() -> i32 {
    // A(0, 0) = 1
    assert ack(0, 0) == 1;
    // A(0, 5) = 6
    assert ack(0, 5) == 6;
    // A(1, 0) = 2
    assert ack(1, 0) == 2;
    // A(1, 5) = 7
    assert ack(1, 5) == 7;
    // A(2, 0) = 3
    assert ack(2, 0) == 3;
    // A(2, 3) = 9
    assert ack(2, 3) == 9;
    // A(2, 4) = 11
    assert ack(2, 4) == 11;
    // A(3, 0) = 5
    assert ack(3, 0) == 5;
    // A(3, 1) = 13
    assert ack(3, 1) == 13;
    // A(3, 2) = 29
    assert ack(3, 2) == 29;
    // A(3, 3) = 61
    assert ack(3, 3) == 61;
    // A(3, 4) = 125
    assert ack(3, 4) == 125;
    return 0;
}

/// Test the memoized version against known values.
fn testMemoized() -> i32 {
    // Verify m=0 row.
    let mut n: u32 = 0;
    while n < 50 {
        let expected: i32 = n as i32 + 1;
        assert ackMemo(0, n) == expected;
        n += 1;
    }

    // Verify m=1 row.
    n = 0;
    while n < 50 {
        let expected: i32 = n as i32 + 2;
        assert ackMemo(1, n) == expected;
        n += 1;
    }

    // Verify m=2 row.
    n = 0;
    while n < 50 {
        let expected: i32 = (2 * n + 3) as i32;
        assert ackMemo(2, n) == expected;
        n += 1;
    }

    // Verify m=3 row for small n.
    // A(3,0)=5, A(3,1)=13, A(3,2)=29, A(3,3)=61, A(3,4)=125
    assert ackMemo(3, 0) == 5;
    assert ackMemo(3, 1) == 13;
    assert ackMemo(3, 2) == 29;
    assert ackMemo(3, 3) == 61;
    assert ackMemo(3, 4) == 125;
    // A(3, 5) = 2^8 - 3 = 253
    assert ackMemo(3, 5) == 253;
    // A(3, 10) = 2^13 - 3 = 8189
    assert ackMemo(3, 10) == 8189;

    return 0;
}

/// Cross-check recursive and memoized for small values.
fn testCrossCheck() -> i32 {
    let mut m: u32 = 0;
    while m <= 3 {
        let mut n: u32 = 0;
        // Limit n to keep recursion tractable.
        let mut limit: u32 = 4;
        if m <= 2 {
            limit = 8;
        }
        while n <= limit {
            let r: i32 = ack(m, n);
            let memoR: i32 = ackMemo(m, n);
            if r != memoR {
                return (m * 20 + n) as i32 + 1;
            }
            n += 1;
        }
        m += 1;
    }
    return 0;
}

/// Test the Ackermann inverse property: A(m, n) > n for all m, n.
fn testMonotonicity() -> i32 {
    let mut m: u32 = 0;
    while m <= 3 {
        let mut n: u32 = 0;
        while n < 20 {
            let val: i32 = ackMemo(m, n);
            assert val > n as i32;
            // A(m, n) < A(m, n+1) (strictly increasing in n).
            let valNext: i32 = ackMemo(m, n + 1);
            assert valNext > val;
            n += 1;
        }
        m += 1;
    }

    // A(m, n) < A(m+1, n) (strictly increasing in m).
    let mut m2: u32 = 0;
    while m2 < 3 {
        let mut n2: u32 = 0;
        while n2 < 10 {
            let lower: i32 = ackMemo(m2, n2);
            let upper: i32 = ackMemo(m2 + 1, n2);
            assert upper > lower;
            n2 += 1;
        }
        m2 += 1;
    }

    return 0;
}

@default fn main() -> i32 {
    let r1: i32 = testSmallRecursive();
    if r1 != 0 {
        return 10 + r1;
    }

    let r2: i32 = testMemoized();
    if r2 != 0 {
        return 30 + r2;
    }

    let r3: i32 = testCrossCheck();
    if r3 != 0 {
        return 50 + r3;
    }

    let r4: i32 = testMonotonicity();
    if r4 != 0 {
        return 70 + r4;
    }

    return 0;
}