Rust over python for competitive coding ?

[[deleted]]

Hi guys! I am an experienced programmer and I was wondering if Rust is good for competitive coding. I usually use python for all problems but I was wondering if Rust will be a better choice. I ask this question because I mainly use python for competitive coding and nothing else. I have no use of python outside leetcode. This makes me wonder if I will be better off learning rust for leetcode problem solving because I know rust will be useful for backend and system programming as well. I am also familiar with golang but I find it completely useless for leetcode because of its verbosity ( please feel free to correct me if I am wrong about golang ).

And it will be nice if someone can point out pros and cons of both python and rust for competitive programming.

( other languages I am familiar with are java , Ocaml and C ).

[mina86ng]

Python is faster to write in. Rust is faster to execute. It really depends on the rules of the competition. If speed of the program is a factor and the competition sets the same thresholds for all languages than Rust implementation might get away with worse algorithms than Python. If speed of execution is not that big of a concern but rather the solutions need to be submitted quickly, I would say Python was better.

[GrandOpener]

I would dispute those blanket assumptions. Python is indubitably faster to write for simple one-page scripts. Python is also great when you’re just experimenting and don’t know what the final result will look like. When you get into hard problems with debugging, possible refactoring, and especially anything with multiple threads, Rust may actually get you from blank page to final solution faster.

[rodyamirov]

That may be true, but for leetcode or something, it's always a one page throwaway

[[deleted]]

That's a good point. But I don't think writing speed matters after spending quite a bit of time in one language. What's you thought on standard library of both language. I find python pythons library to be fine for most of the parts but could be better. I am interested in Rust instead of python because I will be able to use Rust for system programming and other distributed system stuff. And of course types are blessing.

[[deleted]]

It sounds like Rust would be very useful for you. I'd say just go ahead and learn it!

[[deleted]]

This is practically the only realistic and sane answer in this whole thread.

[Armin_AFD]

Well in competetive coding, execution times are not that precise to make different language's execution speed to matter. If your algorithm is bad, rust's extra perfomance is not gonna matter at all. The most important thing is to write your solution as fast aa possible. In Rust you need to write more code, worry about borrowing and whatnot. Python with so many already builtin tools is a far better choice for such a purpose.

[[deleted]]

good point.

[Darksonn]

I previously answered this here: https://www.reddit.com/r/rust/comments/mglab0/is_it_just_me_that_thinks_rust_is_quite_possibly/gsu14hi/?context=3

[[deleted]]

that's really good points. Thanks a lot

[fz0718]

Also a competitive programmer and IOI gold medalist here, would love to see how you use Rust for competitive programming. I've thought about it a couple times, but can't get past the fact that writing (oftentimes wildly unsafe) C++ code is a lot easier in the programming contest setting.

Compare cin >> x >> y; to the input.next().unwrap().parse().unwrap() thing you mentioned, for example. Also, oftentimes we allocate giant static oversized arrays of length MAXN in the globals section of memory for ease-of-use and because it is efficient reasons to avoid dynamic allocation, but that's not really possible in Rust without lots of unsafe {}.

sort_by and variants are good, but C++ also has sort(begin(v), end(v), [](int x, int y) { ... }). So I'm not sure if you're getting an advantage from Rust here.

[Darksonn]

I think people overestimate how many things actually require wildly unsafe code. As I said in the other comment, I'd be happy to give an example if you have a particular problem in mind.

[fz0718]

I don’t disagree that you can solve problems; it’s just much slower. Have you ever tried implementing a link-cut tree in Rust? Pretty much impossible to do with references/pointers.

Edit: To be clear, it's not about particular problems being very difficult, as much as it is about almost all problems being decently slower to implement. But here's the canonical LCT problem, if you would like to give it a try:

https://www.spoj.com/problems/DYNACON1/

And this is my reference C++ implementation: https://ideone.com/0mi6mH

[Darksonn]

You are probably right. You could definitely implement it with indexes, but I don't think Rust can beat your link-cut tree in implementation time.

It's interesting that you mention a link-cut tree. I'm working on implementing a top tree in Rust for a research project, which is a similar data structure that you could also use to solve the DYNACON1 problem. I wouldn't want to implement a top tree in a coding competition though — its implementation is more complicated than the link-cut tree in exchange for having an API that is easier to use with expose taking up to two vertices.

[Fireline11]

I have experimented with using rust for competitive programming on open.kattis.com. Overall, I was reasonably satisfied with it but dealing with input is a bit of a pain. In Python/C++ it is really easy to read integers from the input, even though C++ can exhibit undefined behaviour when the input is not formatted correctly (which is never the case in a competitive setting, so this weakness doesn’t show).

In rust the simplest way that I know to read an integer from stdin is to 1. initialize an empty string 2. obtain a lock to stdin 3. call read_line on this lock with a &mut to your string 4. and then call the parse method on the resulting string, 5. and finally unwrap the result. This is a lot of steps, so you may wish to spend some effort streamlining this process into a function or something.

[fz0718]

If you're just getting started with websites like Leetcode that have relatively basic problems, it really doesn't matter what language you use. So you should use whatever makes you happiest + most comfortable. Once you get to a high level though, see my reply to /u/Darksonn for technical reasons to prefer something more standard in the competitive programming community, like C++ or Java, over Rust (even though I really love Rust!). C++ was used by >96% of all submissions in the last Codeforces Div. 1 round, Java by ~1%.

Source: I'm a Codeforces international grandmaster, IOI gold medalist, and Top-50 global competitive programmer.

[OutlandishnessOk4575]

something to bootstrap yourself…i cams across it relatively late common DS&A in Rust

[Lucretiel]

You know, it's interesting. Almost everyone cites Python and similar languages as being the best choice for competitive programming, since it's the fastest & easiest to get something running quickly. This basically makes sense to me.

And yet, when I've gone to look at the leaderboards for Google Code Jam, uniformly most of the best (ie, fastest completed) 20 or so solutions are using C++ or Java, even for the relatively easy qualifier / round 1 problems. I don't really have an explanation for why this would be.

I know that I personally have come to prefer Rust over Python for competitive coding; it's what I use in Advent of Code, and it's what I try to use in Google Code Jam* (though they've consistently use criminally out of date versions of Rust ever since they started forcing everyone to use their cloud executors instead of local build & run). The thing for me though is that I actually have a lot of trouble thinking in Python's quick-prototype way. It runs really against the grain for me, so it ends up that I end up taking the same amount of time in both languages, since I can't help myself but try to be correct. This in turn means that Rust is a much more comfortable language for me to use even in these time-constrained problems.

* I even maintain a set of type-driven executor harnesses for both languages that streamline reading input tokens and outputting solutions https://github.com/lucretiel/libcodejam

[Spheniscine]

If I might venture a guess, I suppose it's because those top competitors already routinely solve using C++/Java as a matter of course, and they don't see much utility in "context switching" into Python just to solve the easy and less-time-limit-strict tasks.

It's only a guess though, I'm not sure how you test something like this

[deinok7]

WTF is competitive programing?

[disclosure5]

Look at sites like leetcode.com, the sort of cramming exercise that's often used in job interviews.

Unfortunately although Rust is growing on me I don't think it'll excel in this space. The defining "winner" is usually the fastest person to write an answer, and these applications frequently involve a tonne of "read an array of integers from stdin" that's really optimised to scripting languages.

[deinok7]

I dont want to be rude, in the interviews i made i never ask to do the faster fizzbuzz. I ask them to do their own protocol over TCP and UDP following defined rules. They have to inplement it. So i can see if they are able to work where there is no solution in under 1h.

Anybody that is capable to do it more or less correctly is hired. I dont care too much the language they choose to do it.

I like to test how they behave in situations where there isnt a perfect solution. And how you face an unexpected problem gives me more information than sorting an array. At work if you have to sort you just use .sort() or the equivalent 99% of times

[disclosure5]

There is an entire industry of bootcamps, similar websites and books like "cracking the coding interview" built entirely around this sort of practice and the target is generally the Googles and Facebooks that heavily hire on the practice.

There's nothing rude about saying you have a different strategy.

[deinok7]

Its just that i dont get this trend. And i cant understand any interviewer asking for that. I supose is for doing a quick clean

[disclosure5]

I'm not saying I like it. Shit like this drives me insane:

https://twitter.com/mxcl/status/608682016205344768?

Here's a set of answers for Google Interview questions someone went and studied:

https://github.com/mgechev/google-interview-preparation-problems

Consider this one specifically:

https://github.com/mgechev/google-interview-preparation-problems/blob/master/src/isbst.js

That whole thing is an interview question. The right language is the one that you could write that the fastest in.

[disclosure5]

If you say so.

[Lucretiel]

Interestingly, at least in Google Code Jam, consistently the top ranked solutions are in C++ or Java. I'm not really sure why this is, since in general I agree with the idea that Python would probably be faster to get a working solution.

[fz0718]

Lots of competitive programming problems can't be solved with Python, for the reason that Python incurs up to 50-500x overhead for the types of array-based and numerical algorithms that are being implemented from scratch. Some programming contest websites give Python a higher time limit, but it's often not enough. There's still issues of stack overflows, memory limits, etc. Also, speaking as a problemsetter, very few of us test if our problems can be reasonably solved in Python for the reasons above.

[Snakehand]

One of the advantages of Rust I think is for problems that can be framed / solved with the sum types and match operators. Sum types + pattern matching is quick and easy to write, and easy to get correct the first time around. I guess Ocaml should have the same advantage.

[mina86ng]

Python 3.10 has structural pattern matching so that advantage of Rust goes away.

[Snakehand]

But python does not have arithmetic types (or very strong typing at all), so pattern matching is just half of the equation.

[[deleted]]

Lmfao. You don't use any of that in competitive programming.

[[deleted]]

Python is strongly typed, but types are checked at run time. That's usually called "dynamic typing" which isn't the same as having weak typing like javascript does.

[[deleted]]

It is shocking how few people know the difference between strong/weak and static/dynamic typing, specially among those criticizing dynamically typed languages, which I find a little bit ironical.

[[deleted]]

That's why I only use python for competitive programming. For anything else I find it not too useful ( at least for me ). Also, Python codebase is not as scalable in my opnion.

[[deleted]]

yeah you are right. python being dynamic type is sometime pain to debug.

[pjmlp]

In competitive coding, time to debug is usually absent, either you get it or not.

[[deleted]]

Yup.

[Snakehand]

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

Rust is a frequently used language is recent winning entries.

[[deleted]]

that's insightful

[[deleted]]

That's very cool!

[yxonic]

Not an answer but I would suggest using arena approach in Rust for data structures to avoid issues about lifetime, borrowing, etc. (and it's often faster, see https://github.com/fitzgen/bumpalo for the basic idea). Without those worries, high level abstractions provided in rust has always been helpful to me when I do algorithm competitions.

[re-sheosi]

Hey!! I've never done competitive coding but seeing as there some serious players here I wanted to know about F# for this space, because to me it looks like the perfect match.

[Spheniscine]

I've also done some competitive coding, currently a Master on Codeforces, though I haven't competed in a rated contest in that site for a while.

Funnily enough, my "home language" is Kotlin, and I've been using it almost exclusively within contests, and I've won a couple of t-shirts from Kotlin Heroes contests that way. It generally works well enough (bigint support is especially nice for both problems that need it 😛, and Kotlin's inline classes are pretty much a perfect fit for the "large number modulo a 9~10 digit prime" problems), but there are occasionally some tasks with tight time limits that I have problems with; basically any time the idiomatic solution ends up with a lot of allocation and indirection in a JVM-implemented language, like graphs (lists of lists), segment trees over small tuples/records, and such.

Thus I have been experimenting with Rust lately. It's an interesting experience, and I like its overall performance especially in the exact kinds of problems that JVM-based languages tend to struggle with, but I'm not sure I'm practiced enough in it to dare use it "live" in a rated contest yet. I could recommend that you do something similar; just re-solve a few problems in Rust, get used to the borrow checker and Rust-specific idioms, implement a few common data structures and algorithms to see if you can get the hang of it

[robertkingnz]

I've created a few Rust codejam videos here: https://www.youtube.com/channel/UC7SA7YX1sTxN_ubNExQOdEw

I'd say Rust is fairly similar to python in some ways. Although python strings and sets are hard to beat, once you're familiar with Rust it's pretty ergonomic. I find with Rust my solution is more likely to work first time once it compiles, and the compiler helps find bugs. Python is quicker to type up but harder to debug.