Solving the JetBrains Mono C# snippet challenge using Rust.

golomb.rs

/// On the JetBrains Mono showcase page, there are some code snippets. In the C# snippet, you'll find a
/// puzzle/challenge...
///
/// - https://www.jetbrains.com/lp/mono/
/// - https://imgur.com/a/GIZfnJ4
///
/// This challenge is interesting because, at first glance, it's easy. The code is already there, all you have to do is
/// run it! The problem comes from the recursive definition of the Golomb Sequence. `g(100_000)` will require calling
/// `g(99_999)`, `g(1479)`, and `g(99_891)`. Then, each of those require their own set of `g(...)` calls. This
/// completely destroys the stack. Herein lies the challenge.


const GOAL: usize = 100_000_000;

fn main() {
    let mut g = Vec::with_capacity(GOAL);
    let mut sum = 1; // includes the starting 1
    g.push(1);

    for n in 1..GOAL {
        // G(1) = 1
        // G(n) = G(n - G(G(n - 1))) + 1

        let a = g[n - 1];
        let b = g[a - 1]; // subtract to account for 0-based index
        let c = g[n - b];

        g.push(c + 1);
        sum += c + 1;
    }

    println!("Last few of sequence is:");

    for n in (GOAL - 10)..=GOAL {
        println!("g({n:>10}) = {}", g[n - 1]);
    }

    println!("https://jb.gg/correctNumberIs{sum}");
}