Rust for competitive programming


#1

Can i use rust for competitive programming like ACM-IPC, Google Code jam, or Facebook HackCup. is it fruitful using rust.


#2

I suppose so. Rust is as capable a language as any other. One thing though. If there’s a time limit in these competitions, you may be at a disadvantage because Rust compiler being far more strict than other compilers, it might add some extra development time.


#3

It’s a mixed bag because in other languages (like Python) you sometimes introduce bugs that waste lot of your time. And the run-time is sometimes small enough that sometimes even with less refined algorithms are enough (this isn’t enough for Google Code Jam, but sometimes it’s enough for USACO).


#4

As a long-time competitive programmer who loves Rust, I’d say C++ is still the best language for this particular niche. The reason is that many requirements go against the ones in the real world. For example, in competitive programming:

  • The code has to be whipped up as soon as possible. Finishing in 4 minutes is better than in 5 minutes.
  • Readability and maintainability don’t matter.
  • Reading input into global variables is commonplace, simply because it’s the easiest thing to do.
  • Almost all variables are mutable. Such is the nature of these problems.
  • Not paying for bound checking is worth it.
  • Holding iterators into a std::set while mutating it is very useful. BTreeSet cannot do that.
  • Dynamic allocation is almost never used. All the memory is typically preallocated in a global variable.
  • Built-in scanf and next_permutation are very useful.
  • UB is rarely hard to debug problem in such small programs.
  • We don’t need safety as in security.

I tried solving a few problems in Rust and it took me much longer than in C++. But take that as a good sign, meaning Rust makes it difficult to write unmaintainable code, as is encouraged by competitive programming. :slight_smile:

By the way, sharing my cheat sheet with various algorithms: https://github.com/stjepang/snippets


#5

I’m using Rust because I no longer write C++ in normal situations. Mainly, type inference is still useful and makes coding fun.

Rust is available on AtCoder and here’s one of a submission I did in past: https://beta.atcoder.jp/contests/arc095/submissions/2350479

Pros:

  • Awesome type system. No metaprogramming hell.
  • Functional paradigms like map are convenient.
  • Built-in test framework.
  • #[derive] allows using arbitrary types with HashMap and BTreeMap. Writing the implementation is a pain in C++, and using C++ tuples makes the code much harder to read.

Non-advantages:

  • Integer casts are explicit. This may be annoying, while it prevents unexpected overflow.
  • Some algorithms are faster (unstable_sort based on pdqsort, super-optimized binary_search)

Cons:

  • Absence of some useful functions, like next_permutation or lower_bound. On AtCoder I can’t use external crates, so I’m forced to copy implementations in these cases.
  • Borrow checker may be annoying.
  • Input parsing requires more boilerplate.

#6

Then let’s add something like that. With streaming iterators you can create a an API nicer than C++ next_permutation one, and similar to Python itertools permutations/combinations/produce.

For lower_bound I think it’s better to take a look at similar searching stuff in the D language standard library (it has strategies like gallopping, trotting, binary search, etc).


#7

In my experience, I have to agree with others. Rust is a great language for maintenance and scalability, but it’s not the best prototyping language. Note that this is generally how it goes and it may be great for your use case.

I’d really like to see a Rust-inspired scripting language (is that what gluon is?) with fp-style programming/optionals/etc. without a strict borrow checker.


#8

Regarding prototyping, one thing to note is that in professional programming environments, what starts out as a prototype often ends up being eventually turned into the final product due to time constraints.

I am not defending this trend, just saying that it often happens that a developer thinks s/he has the time to write a prototype, when the time budget actually only allows for starting work on the real thing right away.


#9

I have tried using Rust to solve competitive programming problems, and while the actual coding in Rust was full of fun, the development speed and the number of unwrap()s were the major pitfalls.

The lack of simple cin/scanf in the standard library makes the code ugly (full of string manipulations and parsing) from the very beginning. I know that there are crates to solve this issue, but I have yet to see the use of external modules allowed for competitive programming.

However, reading this conversation and thinking once again that putting modules that can safely leave in crates is against Rust values, I realized that we can come up with a cargo extension for bundling all the external code and the solution into a single source file, like people do with JS (webpack with tree shaking). There might be some concerns about whether the rules consider code-reuse as cheating, though. What do you think?


#10

I am working on a library for competitive programming, named porus. It is at very early stage of development right now. And, instead of bundling all the source code, I just compile the solution locally and then submit the generated assembly code. It works quite well.


#11

Am I missing something or to build such a solution will require to have the same OS as the solution testing platform?

BTW It is a nice workaround :slight_smile: