I found a function on Rosseta Code that interested me:
#!/usr/bin/env python
from collections import deque
def ack_ix(m, n):
stack = deque([])
stack.extend([m, n])
while len(stack) > 1:
n, m = stack.pop(), stack.pop()
if m == 0:
stack.append(n + 1)
elif m == 1:
stack.append(n + 2)
elif m == 2:
stack.append(2 * n + 3)
elif m == 3:
stack.append(2 ** (n + 3) - 3)
elif n == 0:
stack.extend([m - 1, 1])
else:
stack.extend([m - 1, m, n - 1])
return stack[0]
print(ack_ix(3, 5))
My attempts to port it to Rust were not successful:
fn rosza3(m: u32, n: u32) -> u32 {
let mut stack: Vec<u32> = Vec::from([m, n]);
while stack.len() > 1 {
let (n, m) = (stack.pop().unwrap(), stack.pop().unwrap());
match (m, n) {
(0, _) => stack.push(n + 1),
(1, _) => stack.push(n + 2),
(2, _) => stack.push(2 * n + 3),
(3, _) => stack.push((n + 3).pow(2) - 3),
(_, 0) => [m - 1, 1].iter().for_each(|i| stack.push(*i)),
_ => [m - 1, m, n - 1].iter().for_each(|i| stack.push(*i)),
}
}
stack[0]
}
fn rosza2(m: u32, n: u32) -> u32 {
let mut stack: Vec<u32> = Vec::from([m, n]);
while stack.len() > 1 {
let (n, m) = (stack.pop().unwrap(), stack.pop().unwrap());
if m == 0 {
stack.push(n + 1);
} else if m == 1 {
stack.push(n + 2);
} else if m == 2 {
stack.push(2 * n + 3);
} else if m == 3 {
stack.push((n + 3).pow(2) - 3);
} else if n == 0 {
[m - 1, 1].iter().for_each(|i| stack.push(*i));
} else {
[m - 1, m, n - 1].iter().for_each(|i| {
stack.push(*i);
});
}
}
stack[0]
}
The result is wrong - it must be 253 for let (m, n) = (3, 5); and not 61. I don't see the error at the moment.
P.S.: This is the ubiquitous working recursive solution:
fn rosza(m: u32, n: u32) -> u32 {
match (m, n) {
(0, n) => n + 1,
(m, 0) => rosza(m - 1, 1),
(m, n) => rosza(m - 1, rosza(m, n - 1)),
}
}