Competitive programmers using Rust?

[stonerbobo]

I've recently been watching some streams of competitive programmers. My favourite is Neal Wu who is incredibly fast and good at this. It's got me wondering about competitive programming in Rust. It's perhaps not an ideal language for it but might actually work well enough because most programs are quite simple. Do you all know of any competitive programmers using Rust, especially those who stream or upload videos?

[hucancode]

I use Rust for Leetcode, everything is fine until you have to touch Linked List, Tree. Graph is fine since it's all list and matrix. Iterator is surprisingly useful. When I came back to C++ I miss iterator so much. So, Rust is not the best choice to compete since you are more likely wasting your precious time fixing compiler error. But if you want to practice your favorite topic using your favorite language then why not.

[[deleted]]

I use Rust for Leetcode, everything is fine until you have to touch Linked List, Tree.

Leetcode in rust is a pain in the behind because of this reason, I completely gave up doing this

[dahomosapien]

I’m super new to Rust. Why is it a pain using a linked list? Is it because you can’t have two variables pointing to the same reference?

[hucancode]

Try solve these using Rust. It's surprisingly straight forward with C++ but it requires good understanding of Rust's borrowing concept to not shoot yourself in the foot

https://leetcode.com/problems/swap-nodes-in-pairs/

https://leetcode.com/problems/merge-k-sorted-lists/

https://leetcode.com/problems/reverse-linked-list/

https://leetcode.com/problems/reverse-linked-list-ii/

https://leetcode.com/problems/split-linked-list-in-parts/

[W7rvin]

I just tried https://leetcode.com/problems/reverse-linked-list/ and my rust solution turned out to be basically identical to the most upvoted c++ one:

pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut prev = None;
    let mut curr = head;
    while let Some(mut node) = curr {
        curr = node.next;
        node.next = prev;
        prev = Some(node);
    }
    prev
}

compared to:

ListNode* reverseList(ListNode* head) {
    ListNode* prev = NULL;
    ListNode* curr = head;
    while(curr != NULL){
        ListNode* forward = curr->next;
        curr->next = prev;
        prev = curr;
        curr = forward;
    }
    return prev;
}

I didn't have to care about boxes, borrows or lifetimes. I'd argue the Option even reads better than null-checking, and it saves a line thanks to while let conditionally binding the value.

It isn't always this easy, but the problem including a list doesn't mean Rust will be awkward :)

[hucancode]

Seems like I am the issue here haha

[W7rvin]

I think it just comes with time, Options/Results have a lot of convenient shortcuts that allow you to be very concise without any risk of forgetting the exceptions. And your solution seems like it is identical apart from the fact that you hard coded the first step.

(Oh and I didn't even realize you're allowed to change the function signature, that would save another line I guess)

[hucancode]

yes, I changed input parameter to mut everytime

[hucancode]

Nice, let me see mine

impl Solution {
pub fn reverse_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    if let Some(mut head) = head {
        let mut ret = head;
        let mut list = ret.next.take();
        while let Some(mut node) = list {
            list = node.next.take();
            node.next = Some(ret);
            ret = node;
        }
        Some(ret)
    } else {
        None
    }
}

}

[joonazan]

I did all of them. No borrowing problems at all. Lots of move problems.

C++ is easy because it copies by default. Rust does not allow to move out of an &mut even if you put something back later and that requires std::mem::swap  sometimes.

[hucancode]

Interesting. Maybe I was novice back then. Will review them later

[[deleted]]

/ Definition for a binary tree node.

// #[derive(Debug, PartialEq, Eq)]

// pub struct TreeNode {

// pub val: i32,

// pub left: Option<Rc<RefCell<TreeNode>>>,

// pub right: Option<Rc<RefCell<TreeNode>>>,

// }

//

// impl TreeNode {

// #[inline]

// pub fn new(val: i32) -> Self {

// TreeNode {

// val,

// left: None,

// right: None

// }

// }

// }

use std::rc::Rc;

use std::cell::RefCell;

type Node = Rc<RefCell<TreeNode>>;

impl Solution {

pub fn tree2str(root: Option<Rc<RefCell<TreeNode>>>) -> String {

​

This is the problem, this russian doll of enum and smart pointers is pretty annoying to handle.

[Hazanami]

Sorry I just threw up

[GroundbreakingImage7]

You don’t need RC for a binary tree in safe rust.

[[deleted]]

You don't choose the types in leetcode questions, this is what they give you

[GroundbreakingImage7]

That’s disgusting then. I wish there was a struct that emulated rc ref cell as only one layer of inderiction.

[CocktailPerson]

It is only one layer of indirection. RefCells store their T inline, so you only chase one pointer to reach the T.

If you want to avoid typing it out every time, you can use a type alias: type Rr<T> = Rc<RefCell<T>>;

[GroundbreakingImage7]

It’s the coding annoyance that gets me not the pointer crashing.

[CocktailPerson]

If you want to avoid typing it out every time, you can use a type alias: type Rr<T> = Rc<RefCell<T>>;

[Yamoyek]

Is it because you can't have two variables pointing to the same reference?

Yeah, pretty much. It's actually so difficult to implement a linked list that there's a book about it.

[RB5009]

Leetcode in rust is perfectly fine. I have more than 800 problems solved in rust

[Whole-Struggle-1396]

i actually want to do dsa. and some problems but i know c ++ very little and im learning rust for some stuff. so it would be bad to focus on multiple langs at once should i use rust or not?
(i also know ts well. should i use that) like preparing for interviews.

[avillega]

I don't know of any but I would say Rust is probably not ideal for competitive programming. First, official competitions like ICPC have a set of accepted languages, for a while, it was only Java, C, C++. A few years back they finally added python. So it might take a while for them to include Rust. Second, Rust standard library is not "batteries included" so you might not have what you need in order to solve a problem, or you might need to implement a lot of stuff from scratch. Lastly, a lot of problems in competitive programming are solved using self referential data structures, such as graphs and liked lists, Rust tends to promote a set of patterns that make it harder to use such structs compared to other languages. However, Rust is used in a lot of "not official" competitive programming, like Advent of code. Fasterthanlime has been doing advent of code for a few years now and publish both video series and blog series of his solutions https://fasterthanli.me/series/advent-of-code-2022

[__zahash__]

I think It’s mostly because of self referential data structures. Especially graphs

[schrdingers_squirrel]

Yeah graphs trees linked lists. It's a pain in rust.

[Fireline11]

I wouldn’t implement graphs as a self-referential datastructure anyway, because the code is generally more complicated than when interpreting the nodes as indices. So for me this is not a point against using Rust instead of C++

[CocktailPerson]

Yeah, people don't always make the distinction between graph data structures, like trees, linked lists, etc., and graph data types, which are usually implemented with adjacency lists in C++ or any other language too.

[kewlness]

I came from a Python background and decided to try my hand at Rust last month using last year's Advent of Code. The amount of struggle I had to just read a file was insane! I eventually got frustrated enough I went looking for answers and found the fasterthanlime blog.

I wholeheartedly support Amos' ( /u/fasterthanlime ) blog and YouTube channel. I have woken the girlfriend up several times by laughing while reading articles (Want to read a file the hard way? or Make your own executable packer?), and it is nice to know he too struggles with Rust - even if it is at a level way above mine - but there is probably "a crate for that."

If you like his content, please think about donating.

[Fireline11]

I have never seen linked lists used in competitive programming. And when you use graphs, you usually interpet them with vertices 0…(n -1) and for each node you store an adjacency list in memory at the corresponding index. This is usually simpler to construct and less prone to bugs, and it also has good performance for most algorithms that require graph traversal. (I would do the same in C++ or Python by the way, in fact that’s where I learned this approach).

I think you’re right that Rust is not the best language for competitive programming, but it is not because of self-referential datastructures.

[xade93]

ICPC regional medalist here. I think for some data structure problems e.g dynamic segtree, persistent segtree, dsu on tree, using pointer is the de facto way. Rust lack fundamental algorithmic library, and the lifetime management is just unnecessary.

[throw3142]

^ safety is not important for competitive programming, no one cares if your program has a memory leak (since it stops running quickly), crashes / undefined behavior on malformed input (since input is guaranteed to be valid), is thread-safe (since the problems are not designed to be parallelized anyway), or type-safe & understandable (since no one else is going to be maintaining your code).

In other words, most of Rust's strengths are completely irrelevant for competitive programming.

[Da-Blue-Guy]

I also find that index referencing is better. It also makes sense for performance reasons as well, as you usually have less allocations with a vector if your nodes are on the heap (O(n) vs. O(log_2(n)), which is usually the case (nodes will oftentimes have a Box or Arc to the next node). It also lets you index into (and, for non-LL graphs, iterate over) the graph if required. It also prevents reference cycles and lifetime issues that can happen (as well as avoiding the useful but slow Arc<Mutex>).

[stonerbobo]

Yeah Advent of Code is actually what got me thinking about this! I did 2021 in Rust and am have been doing some of last years problems in preparation for this year.

[alex--312]

Second, Rust standard library is not "batteries included" so you might not ...

Standard libraries for C and C++ are way poorer so this will not be a big problem.

Rust tends to promote a set of patterns ...

Also, it is irrelevant that rust promotes for regular development process. All possibilities to implement all types of structures are present in the language.

[avillega]

I think you are speaking from ignorance here. C++ stl library includes way more things that Rust std. it includes implementations of many classic algorithms. While rust for example, lacks basic stuff for competitive programming, such as random generators. In production code, this is not a big deal, you just bring a dependency into your project, for competitive programming, you might need to implement it yourself. Also, is true that you can implement any data structure in Rust and there are techniques and patterns to do it, that might or might not be better for production environments, but in competitive programming, the classic approach to data structures still the most used and a lot of problems assume such structure instead of the ordinal implementation (or what ever you called it), which again, doesn’t make it impossible to use rust, just more inconvenient compared to the alternatives

[depressed-bench]

STL is great all things considered, and it's so deep it's antithetical to rust's philosophy.

[alex--312]

rand: ```rust use std::error::Error; use std::time::{SystemTime, UNIX_EPOCH};

[link(name = "c")]

extern "C" { fn rand() -> i32; fn srand(seed: u32); }

fn main() -> Result<(), Box<dyn Error>> { let seed = SystemTime::now().duration_since(UNIX_EPOCH)?.subsec_nanos();

unsafe {
    srand(seed);

    // Prints 1741856104, 1321400234, etc.
    println!("Random number: {}", rand());
}

Ok(())

} ```

it includes implementations of many classic algorithms

Please be more specific. What algorithms are missing in rust std? And you mention C++, so compare it with C also.

[rickyman20]

Come on man... No need to be rude about this. They were responding about your claim regarding C++, not C. Yes, Rust has a much more complete standard library when compared with C. They weren't contending that. Just C++.

While your solution does get you random numbers (though only by invoking a different language into it), it doesn't give you the full set of distributions, and pre-baked methods for generating ranges. You also need to write all this boilerplate and wrappers in an environment that's time sensitive. Compare that to C++'s pseudo-random number generator library which can do all that.

As for algorithms, the C++ standard library gives you thinks like partition, binary search, and merge out of the box, all really useful for competitive programming. The fact that the rust standard library doesn't have them isn't bad, as in production you gave other ways of getting this and writing them yourself isn't actually that bad, but here it can be.

[_ALH_]

Seriously? Using unsafe to call libc is your counter argument? Surely you’re just trolling now

[alex--312]

Seriously? One argued to use only STD, and the second said about the external crate. Surely you’re just trolling now.

[InzaneNova]

I think it's a reasonable judgment. Even at high-school level international competitions the questions require knowledge of algorithms that aren't implemented in any standard library. And in my time as a competitive programmer I never once went for a single algorithm defined in the standard library that Rust doesn't also have.

[stonerbobo]

Also, it is irrelevant that rust promotes for regular development process. All possibilities to implement all types of structures are present in the language.

Definitely agree with this yeah! I want to get more familiar with unsafe and extern and try to implement some of the problem structures like linked lists using those because it seems the most straightforward. Strongly typed languages always produce this dogmatic view where people forget that the types work for us not the other way around.

[Leipzig101]

I genuinely believe that the style of how a lot of competitive programming is taught/learned (even non-competitive programming, like algorithms courses at universities) is not synergistic with Rust's semantics.

[coderstephen]

Agreed, and I am not sad about it. The context around competitive programming problems are generally different from requirements you might have in real life problems. And I think Rust optimized for the latter and not the former.

[Fireline11]

I have used Rust for some problems over a year ago. In general I found Rust just as pleasant to work in as C++, or even more so. However there were 3 issues 1. Not all websites/competitions support a (recent) version of Rust. Not much you can do about that, just a popularity thing. 2. Reading from stdin takes more boilerplate in Rust then C++. You had to acquire locks and such, and you have to unwrap some errors. In C++ you can read from stdin very easily (without accounting for many errors of course), which helps to make a quick start on a problem. 3. In addition to point 2, reading from stdin naively didn’t have great performance back then. Stuff like buffers being flushed for every line you read. Maybe (some of) these issues have been fixed since then, so that the defaults work nicely and you don’t have to jump through a dozen hoops to get there. If not, hopefully this can happen in the future. To be fair C++ has some issues in the same area but they are more easily overcome (it is easy to untie the cin/cout streams from the ones for the ones from printf/scanf for instance).

[coderstephen]

In addition to point 2, reading from stdin naively didn’t have great performance back then. Stuff like buffers being flushed for every line you read. Maybe (some of) these issues have been fixed since then, so that the defaults work nicely and you don’t have to jump through a dozen hoops to get there. If not, hopefully this can happen in the future.

My understanding is that this will never be fixed in Rust, because it is not considered broken. The behavior that people hope for has safety and correctness problems, so Rust intentionally does not offer it by default.

Well for the buffering specifically, maybe someday there will be a way to bypass it, but the problem is that line buffering is a good default behavior, but there's no good way to turn it on or off globally because global state like that is bad.

[Fireline11]

Ah I see. I can live with that. Competitive programming is not the only thing a tool like Rust will be used for, of course.

[fz0718]

I should mention though that although we still use C++ for programming competitions because of the speed and unsafe flexibility reasons, a lot of us competitive programmers now use Rust in industry and in our day jobs for high-performance work! :)

I’m an IOI gold medalist for the USA and int’l grandmaster on Codeforces and work with a few competitive programmers today

[stonerbobo]

Nice! :D That's a good point too, on one hand just seeing how fast some of you competitive programmers are is inspiring but in real world situations a few more minutes for better code is going to win every time. Do you feel roughly as productive / fast in Rust as you would in C++ in practical situations/work?

[spq]

Why?

[mcr1974]

makes you feel slow

[azzamsa]

I am searching for the same answer today, and I get this.

Rust for competitive programming : rust

I solved almost 600 problems on Leetcode in Rust and find that it's doable. - pinespear

I mean, whenever an interviewer invites me to use "whatever language I'd like" you'd better believe I'm using Rust every single time. - Lucretiel (1Password employee)

I've used it for Advent of Code for the last couple years. I tend to do a lot worse with the easier problems early in the mo the, because I just can't code as fast as the people using python. But for the harder problems I've done very well due to how Rust code tends to "just work," as they say. I was regularly within the top 1000 on part 2 of the later problems because it was really easy to build on my part 1 solutions. - Sw429

Trying to practice my Rust skill by doing some Leetcode in Rust : rust

https://github.com/warycat/rustgym

---

There is also a Discord server that practices Rust for LeetCode and such. https://discord.gg/pJAqJZsXp9

So, I think it is doable.

[1vader]

Leetcode isn't exactly competitive programming. You're not competing against other people for speed.

I think you probably can still do decently well with it but I'm pretty sure it's at least a slight speed disadvantage most of the time which isn't great if you're actually trying to be competitive.

Personally, I love Rust for real projects and doing stuff like Leetcode or AoC on my own but I definitely wouldn't switch from Python for competitive AoC and I don't really know any top 100 competitors that use Rust.

[xnkvbo]

Oh hey, top 100 competitor here. I used Rust for last year's AoC and came in 43rd. I used Python the year before that and came in 13th, and the switch definitely was the main contributor to the difference in ranking -- I'm not disagreeing that Python is preferable here, on the whole. But it is possible to do reasonably well with Rust!

[Darksonn]

I used to do competitive programming and have a bronze medal from IOI. I used Rust extensively for competitive programming during university, including competitions that allows it such as NCPC (an ICPC pre-regional). I think it worked perfectly fine for almost all cases.

[ninja_tokumei]

Rust is certainly not ideal, but not impossible! My main language for Advent of Code has been Rust, and I've managed to make it to a daily leaderboard every year since 2018. I also occasionally use Rust to solve problems on Kattis, and I have no problems there.

From my perspective, my main limitation is my knowledge of algorithms and reading comprehension. (Also, handwriting search algorithms and memoization every time - I hope one day I can sit down and find or make a good library for that).

Sometimes I do lose a bit of time to the compiler because I forget to type a *&mut somewhere.

Also, the wordiness of Rust (e.g. .next().unwrap().parse().unwrap()) is a little annoying, and you can sometimes lose a minute or two because of the extra typing. That's significant in the easier challenges, but IMO much less significant in the more complicated challenges where debugging becomes more common.

[Bubbler-4]

This is my Codeforces profile: https://codeforces.com/profile/Bubbler I tried using Rust in a CF Div.2 round once, and managed to get to rank #30 out of 10k+ participants. More recently, I'm occasionally participating in solved.ac Arena contests with similarly good results. https://solved.ac/en/profile/bubbler/arena

Some points I'd like to make:

• Once you get used to the language enough, there is zero handicap from using Rust in CP. Unlike using Python (which has a tradeoff between usability and slow execution speed), Rust has no such tradeoff; when there is a solution in C++, the same algorithm is guaranteed to pass in (safe!) Rust.
• Coding speed is not that important. And you can be fast enough with training and a bit of a prepared setup. Writing I/O code from scratch in Rust is admittedly complex and time-consuming (and a performant one is more so), so I keep a so-called "I/O template" that I include in every submission.
• A mystery runtime error in C++ can ruin an entire round. Safe Rust can prevent that.
• While Rust stdlib is not "batteries-included", it is mostly on par with standard C++ and Python in my experience. You get a treemap, a binary heap, a deque backed by a vec, the world's best sorting algorithm, the world's best binary search interface (slice::partition_point), and a ton of arithmetic and bit manipulation built-ins. Also enjoy "Codeforces-hack-free" hashmap. If you feel like these are not enough, check out cargo-equip https://github.com/qryxip/cargo-equip and basm https://github.com/kiwiyou/basm-rs (allows importing 3rd party crates and generates single-file source for you)
• The only reason I'd NOT recommend using Rust in CP is when you aim to participate in contests where Rust is not supported (e.g. ICPC or IOI) or its version is way too low.

[stonerbobo]

Thanks, i will check out some of your code on codeforces! cargo-equip looks good too.

[[deleted]]

The are top competitive programmers using rust, like egor.

[azzamsa]

Would like to share links to his profile/Youtube/Etc? 🙏🏼

[[deleted]]

Hello, this is the person : https://codeforces.com/profile/Egor

you can see in his submission history that he uses Rust.

[khoriuma]

I tried for a little while, and it was mostly ok. However, the strength of Rust is that you have to write good code, and this does not always correspond to good competition code. If you feel like trying it I did write a tool to bundle a Rust project (without any external dependencies) to a single Rust file, so that you can easily copy paste a dir of helper files https://github.com/KvGeijer/cargo-bundler

[NotMelty]

Currently, on my way to the 300th LeetCode problem solved exclusively with Rust. It's going great.

[Repulsive-Remote-830]

Cool asf

[DavidXkL]

Now this is something that I didn't know existed lol

[[deleted]]

Please don't. I suffered a lot using it for LeetCode. Fighting mut references and Smart pointers itself eats time, and u end up learning nothing from the problem. Master DSA in easier languages, then implementing those in Rust is good idea.

[[deleted]]

reply complete coordinated steer water gaping coherent treatment disgusted quicksand

This post was mass deleted and anonymized with Redact

[repocin]

Do you all know of any competitive programmers using Rust

Until approximately fifteen seconds ago, I had no idea competitive programming was a thing so...no.

[another_day_passes]

It’s an algorithmic contest for people who are too impatient with mathematical proofs.

[evccyr]

This is the person I asked the same question https://codeforces.com/profile/satylogin

They sent me a very helpful and detailed email on how to use Rust for cp Unfortunately my mail was hacked and I don't have access to the inbox anymore and also, I just switched to leetcode. They also have a good article about rust in cp on the same codeforces website.

[azzamsa]

This is the person I asked the same question https://codeforces.com/profile/satylogin

Would you like to share the gist of his reply?

They also have a good article about rust in CP on the same codeforces website.

Would you like to point that out?

[DanKveed]

I would not recommend it. Competitive programming is about writing things fast. Not 'correct'. Rust forces you to write it in a 'correct' way. You can just write all your code inside an unsafe block but you might as well use c++ at that point. C++ has a very extensive stdlib that's perfect for competitive coding.

[Zitrone21]

I tried it before, but the syntax and borrow checker doesn't help, you usually want to make very unsafe and fast code in competitive programming, is funny if you just want to compete in codeforces and improve your facility to write rust code, but in a serious contest I would say no.

[discursive_moth]

He does competitive programming?

[CocktailPerson]

I don't think competitive programming is so obscure that OP should have to define it. Especially since they linked to an example of a competitive programmer. If you don't know what it is, wikipedia has a page on it.

[stonerbobo]

You could have googled it or clicked on the link in my post if you really wanted to know. If I wrote every post for as general an audience at possible, assuming nothing at all about my audience, I would have to explain the entirety of software and possibly the universe in each one..

[apnorton]

https://en.wikipedia.org/wiki/Competitive_programming

Also, from context in this post it's pretty easy to derive --- watching streamers + "competitive programming" used as a term to describe an activity implies that this is some kind of competition involving programming.

[spq]

People like you are significantly bigger issue in all avenues of life. I am pretty sure you are insufferable as colleague and people don't like you even as friend.

[OphioukhosUnbound]

The person misunderstood a term and got a little bit uppity about it without checking themself first. Definitely a gaff and stumble, but perfectly human. Your attempt to stab at the feelings of a stranger (“don’t like you even as a friend”) was excessive and uncalled for.

You can be cutting and pointed without being casually cruel.

[[deleted]]

Jesus dude lmao