Idiomatic implementation of the tribonacci sequence in Rust

Question

I’m new to Rust, but as a fan of Haskell, I greatly appreciate the way match works in Rust. Now I’m faced with the rare case where I do need fall-through – in the sense that I would like all matching cases of several overlapping ones to be executed. This works:

fn options(stairs: i32) -> i32 {
    if stairs == 0 {
        return 1;
    }
    let mut count: i32 = 0;
    if stairs >= 1 {
        count += options(stairs - 1);
    }
    if stairs >= 2 {
        count += options(stairs - 2);
    }
    if stairs >= 3 {
        count += options(stairs - 3);
    }
    count
}

My question is whether this is idiomatic in Rust or whether there is a better way.

The context is a question from Cracking the Coding Interview: “A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.”

Trinitroglycerin

TIL that a tribonacci sequence exists ^^. – Chockablock

Answer 1

Based on the definition of the tribonacci sequence I found you could write it in a more concise manner like this:

fn options(stairs: i32) -> i32 {
    match stairs {
        0 => 0,
        1 => 1,
        2 => 1,
        3 => 2,
        _ => options(stairs - 1) + options(stairs - 2) + options(stairs - 3)
    }
}

I would also recommend changing the funtion definition to only accept positive integers, e.g. u32.

Chockablock

Great idea! My code is subtly different from that sequence (but thanks for teaching me it exists!) but I can adapt your idea to return the same results by using these anchors: 0 => 0, 1 => 1, 2 => 2, 3 => 4. I’ll add the context to my question. – Trinitroglycerin

This code is certainly idiomatic, elegant, and incredibly readable! A performance/efficiency disadvantage is that it will recursively call the options function an exponential number of times. On the Rust playground, I found that it timed out before computing options(40). – Beall

Ah, I think this should actually be: 0 => 1, 1 => 1, 2 => 2, 3 => 4. Kind of weird to think about, but there is one way to climb up zero stairs. This is similar to why 0! = 1 (an "empty product"). – Beall

Answer 2

To answer the generic question, I would argue that match and fallthrough are somewhat antithetical.

match is used to be able to perform different actions based on the different patterns. Most of the time, the very values extracted via pattern matching are so different than a fallthrough does not make sense.

A fallthrough, instead, points to a sequence of actions. There are many ways to express sequences: recursion, iteration, ...

In your case, for example, one could use a loop:

for i in 1..4 {
    if stairs >= i {
        count += options(stairs - i);
    }
}

Of course, I find @ljedrz' solution even more elegant in this particular instance.

Isadoraisadore

Thanks! Not sure which answer to accept. Yours is as generic as my question was, and is basically “No, this is fine.” Ljedrz’ is a very welcome improvement over my particular example. I’ll sleep over it. – Trinitroglycerin

@DenisDrescher: I would advise to accept ljedrz's answer. On StackOverflow the score of an answer represents its usefulness in general while the "accepted" mark represents its usefulness for the OP; thus, since ljedrz's answer is an extremely elegant solution for this particular case, I would personally accept it rather than a more general (and vague) statement. – Isadoraisadore

I see, thanks! I wasn’t aware of the difference in meaning. :-) – Trinitroglycerin

Answer 3

I would advise to avoid recursion in Rust. It is better to use iterators:

struct Trib(usize, usize, usize);

impl Default for Trib {
    fn default() -> Trib {
        Trib(1, 0, 0)
    }
}

impl Iterator for Trib {
    type Item = usize;
    fn next(&mut self) -> Option<usize> {
        let &mut Trib(a, b, c) = self;
        let d = a + b + c;
        *self = Trib(b, c, d);
        Some(d)
    }
}

fn options(stairs: usize) -> usize {
    Trib::default().take(stairs + 1).last().unwrap()
}

fn main() {
    for (i, v) in Trib::default().enumerate().take(10) {
        println!("i={}, t={}", i, v);
    }

    println!("{}", options(0));
    println!("{}", options(1));
    println!("{}", options(3));
    println!("{}", options(7));
}

Playground

Laresa

Oh darn, but as a Pythonista I can’t complain. Your code is very interesting, and it’ll take me a bit of research to understand. Thanks! – Trinitroglycerin

Answer 4

Your code looks pretty idiomatic to me, although @ljedrz has suggested an even more elegant rewriting of the same strategy.

Since this is an interview problem, it's worth mentioning that neither solution is going to be seen as an amazing answer because both solutions take exponential time in the number of stairs.

Here is what I might write if I were trying to crack a coding interview:

fn options(stairs: usize) -> u128 {
    let mut o = vec![1, 1, 2, 4];
    for _ in 3..stairs {
        o.push(o[o.len() - 1] + o[o.len() - 2] + o[o.len() - 3]);
    }
    o[stairs]
}

Instead of recomputing options(n) each time, we cache each value in an array. So, this should run in linear time instead of exponential time. I also switched to a u128 to be able to return solutions for larger inputs.

Keep in mind that this is not the most efficient solution because it uses linear space. You can get away with using constant space by only keeping track of the final three elements of the array. I chose this as a compromise between conciseness, readability, and efficiency.

Beall