//! 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;

}