rustgym

rustgym is a repository containing high-performance Rust implementations of common data structures and algorithms. It provides solutions for competitive programming platforms including:

• LeetCode: Solutions optimized to beat 99% of other submissions.
• Advent of Code: Rust implementations of seasonal challenges.
• Google: Solutions to Google-specific coding problems.

Developers can use this repository to study idiomatic Rust patterns for implementing complex structures like UnionFind, Trie, and various graph algorithms.

The main function implements a standard competitive programming execution pattern:

1. It initializes a BufReader on stdin().
2. It reads an initial integer t using parse_line(), representing the number of test cases.
3. It iterates from 1 to t, calling a solve function for each case.
4. It accumulates results into a string buffer and prints the final output to stdout at the end.

When implementing your own solutions, you should follow this pattern to ensure compatibility with the expected input/output format.

fn main() {
    let mut res = "".to_string();
    let mut reader = BufReader::new(stdin());
    let t: usize = reader.parse_line();
    for i in 1..=t {
        solve(i, &mut reader, &mut res);
    }
    print!("{}", res);
}

To use certain features of RustGym (likely related to visualization), you must install graphviz on your system:

macOS

brew install graphviz

Linux

apt install graphviz

When submitting code to the LeetCode online judge, you cannot use rustgym_util. You must replace use rustgym_util::*; with the following boilerplate to define the list! macro and the necessary ListLink types and traits:

#[macro_export]
macro_rules! list {
    () => {
        None
    };
    ($e:expr) => {
        ListLink::link($e, None)
    };
    ($e:expr, $($tail:tt)*) => {
        ListLink::link($e, list!($($tail)*))
    };
}

pub type ListLink = Option<Box<ListNode>>;

pub trait ListMaker {
    fn link(val: i32, next: ListLink) -> ListLink {
        Some(Box::new(ListNode { val, next }))
    }
}

impl ListMaker for ListLink {}

When submitting code to the LeetCode online judge, you cannot use rustgym_util. You must replace use rustgym_util::*; with the following boilerplate to define the tree! macro and the necessary TreeLink types and traits:

#[macro_export]
macro_rules! tree {
    ($e:expr) => {
        TreeLink::leaf($e)
    };
    ($e:expr, $l:expr, $r:expr) => {
        TreeLink::branch($e, $l, $r)
    };
}

pub type TreeLink = Option<Rc<RefCell<TreeNode>>>;

use std::cell::RefCell;
use std::rc::Rc;

pub trait TreeMaker {
    fn branch(val: i32, left: TreeLink, right: TreeLink) -> TreeLink {
        Some(Rc::new(RefCell::new(TreeNode { val, left, right })))
    }
    fn leaf(val: i32) -> TreeLink {
        Some(Rc::new(RefCell::new(TreeNode {
            val,
            left: None,
            right: None,
        })))
    }
}

An example of how water settles on a terrain map.

Input:

• heights: [2, 1, 1, 2, 1, 2, 2]
• V (Volume): 4
• K (Start Index): 3

Output:

• [2, 2, 2, 3, 2, 2, 2]

Step-by-step logic:

1. The first droplet lands at K=3. Moving left would eventually cause it to fall, so it moves left.
2. Subsequent droplets follow the priority: Left movement > Right movement > Stay.
3. The final state represents the total height (terrain + water) at each index.

Input: heights = [2,1,1,2,1,2,2], V = 4, K = 3
Output: [2,2,2,3,2,2,2]

This problem involves validating whether a comma-separated string represents a correct preorder traversal serialization of a binary tree.

Serialization Rules

• Non-null nodes: Recorded as their integer value.
• Null nodes: Recorded using the sentinel value #.
• Traversal: Uses pre-order traversal (Root, Left, Right).

Input Format

• A string of comma-separated values.
• Each value is either an integer or the character #.
• Input is guaranteed to not have consecutive commas (e.g., no "1,,3").

Examples

• Valid: "9,3,4,#,#,1,#,#,2,#,6,#,#" returns true.
• Invalid (Incomplete): "1,#" returns false.
• Invalid (Extra nodes): "9,#,#,1" returns false.

Input: "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true

When implementing or testing the water flow simulation, ensure the following constraints are respected:

• heights length: [1, 100]
• heights values: [0, 99]
• V (Volume): [0, 2000]
• K (Start Index): [0, heights.length - 1]

The solve function provides the entry point for the Advent of Code 2020 Day 16 solution. It processes input from a BufRead source and writes the results to a Write destination. It calculates two specific values: the error rate and the departure product based on ticket ranges and field validity.

// Example usage pattern for the solve function
solve(reader, writer);

The solve function provides the solution for the Advent of Code 2015 Day 10 challenge. It accepts a buffered reader for the input data and a writer for the output results. It calculates two values based on the 'look-and-say' sequence: the length of the sequence at the 40th iteration and the length at the 50th iteration.

pub fn solve(reader: &mut dyn BufRead, writer: &mut dyn Write) {
    // ... implementation
}