peltorator's blog

By peltorator, 22 months ago, In English

C++ is an excellent language for competitive programming, and most of the top performers use it. However, it has many flaws. Lately, Rust is getting increasingly more popular on CodeForces. I haven't yet written a single program in Rust in my entire life, however from what I have heard about it, I feel like there is actually a possibility that in 15 years it will be the most popular CP programming language as now is C++ and as 15 years ago was Pascal (don't quote me on that).

So this Saturday, January 21st at 11:00 AM UTC I will be streaming and trying to solve a CodeForces round using Rust, learning it along the way and seeking help from viewers. Additionally, we will be raising money for a great non-profit organization that helps Ukraine. More details at the beginning of the stream.

The link to the stream.

  • Vote: I like it
  • +149
  • Vote: I do not like it

»
22 months ago, # |
  Vote: I like it +51 Vote: I do not like it

Rust is a great language, but not for competitive programming. It may increase in popularity as competitive programmers who also have real jobs switch to it for work and will be more inclined to keep it as their primary language for competitive programming, but even if Rust completely replaces C++ in the real world, I seriously doubt it will ever reach a double-digit share on platforms like CodeForces because the barrier of entry is so much higher compared to C++ and most other languages,

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +44 Vote: I do not like it

    I'd argue the barrier of entry is not that high, but even knowing Rust relatively well, I don't use it for competitive programming, mostly because CP requires you to write lots of code fast, and even if the code has UB, you don't care about that as long as the particular compiler you're using does what you expect it to. Rust is neither fast to write in, nor lets you say "I don't care about UB" (clearly, even wrapping everything in unsafe is not quite enough).

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      CP requires you to write lots of code fast

      That's an interesting take.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      tbh I think this is matter of habit more than anything. Of course you probably would be slower first month after switch, but benefits of having language that does not try to kill you on every corner outweights time spent to learn it

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      I don't think writing lots of code fast is really important. It saves little time. I think problems of C++ eat much more time on average.

      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +31 Vote: I do not like it

        Can you elaborate which problems do you mean? I definitely know a few aspects where Rust is better than C++, but I don't see how they are really applicable for CP, especially, having in mind that a huge part of even high-rated community prefers printf over debugger in all cases and text editors over IDEs.

        Don't get me wrong, I like to upsolve problems on Rust, but on more important contests I still stick to C++, because with enough discipline you can write C++ code as you do it in Rust (i.e. always having either one mutable reference or any number of immutable, etc.), but when you need to do something tricky to make your life a little bit easier, you almost always can do that in C++ and in Rust it is often not as easy.

        One of such things is that in C++ you can wrap any short, but complex piece of code into a lambda and then use it, but Rust has some obstacles on this path. For example, if you are writing some dp, you may want to write a lambda "please, make sure that this state is computed", but it is impossible in Rust, because it captures dp as mutable. Obviously, you can make a function and pass everything to it, but then it probably would not be short anymore (e.g. if you need to compute sum of products of values from three different dp's as in problem F from the last contest). I also have similar issues when I need to compute a lot of simple things in dfs. Mutable y-combinator is easy in C++, but I simply don't know how to do it in Rust. Another problem is that C++ templates are superior, so for metaprogramming in Rust you have to go to macros earlier and macros code is undebuggable.

        for in Rust is much nicer, though

        • »
          »
          »
          »
          »
          22 months ago, # ^ |
            Vote: I like it +28 Vote: I do not like it

          Recursive lambda in Rust

          Yes, it is formally undefined behavior, but I use it extensively and had not had any problems yet

          • »
            »
            »
            »
            »
            »
            22 months ago, # ^ |
              Vote: I like it +11 Vote: I do not like it

            Well, it definitely is a solution, and it is cool that it exists and works, but the fact that it looks messy even to C++ standards just drains all the happiness

            But, honestly, I was wondering if it is doable in safe Rust without unreasonable overhead

            • »
              »
              »
              »
              »
              »
              »
              22 months ago, # ^ |
              Rev. 4   Vote: I like it +1 Vote: I do not like it

              "Recursive closures" are definitely possible in safe Rust, here's an example: https://pastebin.com/QJ7bJbu5 (snipped from my submission to an AtCoder problem: https://atcoder.jp/contests/abc231/submissions/27948026)

              I do admit it can be a tad unwieldy to code on-the-fly though (hence why for most DFS problems, I simply continued using the iterative DFS tricks I picked up from Kotlin to prevent StackOverflowException), but I haven't yet learned how to do a similar thing in C++, so I can't compare.

              • »
                »
                »
                »
                »
                »
                »
                »
                22 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                pastebin is somehow down for me, so I read the AtCoder submission, and, as far as I understood, you use RefCell to deal with mutability. Although, it is not too much, it is still unreasonable overhead I mentioned.

                In C++ and for immutable case in Rust you can simply write y-combinator and it will be fine. You can find an implementation for Rust here, for example.

                The example does not reflect it, but you can use it like this

                Similar code for C++ works both for mutable and immutable case because C++ does not care, but in Rust replacing Fn with FnMut does not seem at least straightforward (you can read this as "I failed to do that"). Your code overcomes these problems with RefCell that does all the checks in runtime which is probably still fine, but still carries some overhead with the sole purpose of shutting the compiler up.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  22 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Oh thanks, I didn't know about Y-combinator, that makes things much cleaner (well, except for the need for either RefCell or pointer-hacks, but it shouldn't be too much of a problem for the majority of the problems I'd use it for)

                  Not sure I have the ability to actually understand it, but at least it's pretty copy-pastable

            • »
              »
              »
              »
              »
              »
              »
              22 months ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              What do you mean by "look messy"? Because usage site is not really messy, and why do you care about messiness of your library code during contest? And I do not think there's any real performance overhead

              • »
                »
                »
                »
                »
                »
                »
                »
                22 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Usage and performance are great, I agree. I meant the implementation. It has unsafe, UB, macros and some boilerplate all in one place. I don't use prewritten code during a contest except for short (about 70 lines long) template for reading input and multitests, so at the end of the day, I indeed write my library code. It makes a lot of sense when you are mostly competing under ICPC rules, although, now I probably can start building a library.

                In general, I don't mind the complexity of the solution. I even don't really mind unsafe, but I don't see any fundamental reasons for its necessity in this case. However, when you have to put up with UB, with things that completely avoidable in C++, like macros killing all the assistance from your IDE and boilerplate, and also with unsafe as the cherry on top of that in return for checks for rare occasions that you messed your references up, it kills all the fun of using Rust.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  22 months ago, # ^ |
                    Vote: I like it +3 Vote: I do not like it

                  It is necessary here because we need to pass lambda as argument at the same time as we invoke it, hence we have more than 1 mutable reference (which is theoretically UB)

                  As for other things — macros is not that black of a box for clion now, and c++ templates have same problem. Also we are not only talking about memory safety as applied to CP — amount of sugar that rust gives that is very relevant to CP is staggering

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  22 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Yes, I agree that this exact solution would not work. However, in fact, what we are trying to achieve is to create an anonymous object that has references to whatever we want to capture and also is able to call itself. Again, I see no fundamental reasons for it to be impossible for mutable references.

                  Maybe I missed some specific extension for CLion that helps with macros specifically, but currently the way I write macros when I need them looks like

                  1. Implement needed functionality for some particular case.

                  2. Wrap into macros and generalize using search and replace.

                  3. Fix errors that you can't even locate.

                  4. Cry if you need to add something later.

                  C++ template are much more debuggable in that sense. At least, you can read compiler errors and understand them. Errors even in normal Rust are sometimes misleading, but with macros it gets even worse. In general, I believe that in terms of debuggability Rust generics $$$\gg$$$ C++ templates $$$\gg$$$ Rust macros $$$\gg$$$ C++ defines. But in C++ you can do everything you need using only templates, while in Rust you have to occasionally use macros.

                  And yes, I agree that whenever you don't need anything too complex, using Rust is much more comfortable, except for a few very annoying things like using only usize and not isize for indexing, but, even to this day, C++ offers considerably more capabilities

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  22 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  They've added recursive expand which makes stuff way easier to write. But thing is I never needed to write something like that during the contest, and time is not that much of constraint when writing library. I'm not sure if rust or c++ better to use without library, but I do not have this alternative, I have libraries in both of them

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Obviously, you can make a function and pass everything to it, but then it probably would not be short anymore

          why not atcoder-style where you pass one mutable struct?

          https://github.com/rust-lang-ja/ac-library-rs/blob/master/src/internal_scc.rs#L60-L79

»
22 months ago, # |
  Vote: I like it +16 Vote: I do not like it

January 21st is Saturday though

»
22 months ago, # |
Rev. 2   Vote: I like it +80 Vote: I do not like it

Rust is getting increasingly more popular on CodeForces

13 people in #844, 6 in #843 — the same as 7 months ago...

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I mean the bigger scale picture. Compared to 5 years ago. And I did not look at the statistics, but just submissions of people I befriend on codeforces.

»
22 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Well, I had a hard time reading input in Rust without having a prewritten scanner. If the contest doesn't go well, I suggest you to do first several projecteuler.net problems (the rules of PE allow streaming and spoiling first 100 problems wherever you want); or maybe even start the stream earlier and practice them prior to the codeforces contest, as it seems more logical to do it in this order (basic stuff first, reading input second).

I am not a rustacean and speak from the position of somebody who also tried to take a glance at Rust in the recent past.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Great suggestion. Will probably do that. Thanks!

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    Well, it is definitely easier to do competitive programming in Rust when you already have prewritten IO code.

    I'd suggest abstracting out all the parsing logic to a separate struct/function, otherwise, there will be too many unwraps in the code, and it will be very hard to write and read.

    I solved the same task as you — see the submission 189675119. I have a Scanner, which has just one method next, which returns the next token and parses it to whatever type you want. So if you want to read i32, you can just write let x:i32 = scanner.next() or scanner.next::<i32>().

    I'd recommend peltorator to just copy Scanner code from my submission, and spend time on more interesting parts of Rust instead of parsing :)

    • »
      »
      »
      22 months ago, # ^ |
      Rev. 2   Vote: I like it +18 Vote: I do not like it

      Your Scanner has a problem, being unusable for interactive problems

      Here is a much better one, modified version of which I use all the time and had no problems with.

      Though it uses some unsafe, so I did my best to create a better one without unsafe: https://pastebin.com/qRsQwBQe

      Also, if you were using clippy, you would notice that next is definetly not the best name choice for the method, because it's usually used by iterators and they return a predefined type instead of generic one

      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, I know my version doesn't work for interactive problems.

        The idea was to show a very short implementation, which works in most cases and is understandable even for people, who use Rust for the first time. I definitely can't say the same about the unsafe version you suggested :)

        Though the unoptimized version from your first link is pretty good.

        I do agree using Clippy is a good practice in general, but in this specific case, it is not so important.

»
22 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Note: Sorry for being odd one out among all red coders.

Peltora stream about to begin. This stream is going to make or break my Saturday. But very much excited for this. Hope to see some cool stuffs.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi,

I certainly agree that Rust is gaining popularity very fast. Here is good resource to start competitive programming in Rust.

Competitive Programming in Rust

It has basic functions at least start Competitive Programming in Rust.

Thank You

»
7 months ago, # |
  Vote: I like it -16 Vote: I do not like it

bro, you really wanna deal with borrow checker when you're a power user in CP? yeah no, I reckon python is the future.

»
4 months ago, # |
  Vote: I like it -22 Vote: I do not like it

why this code is failing to solve the problem https://codeforces.net/problemset/problem/1883/C 1883 C. Raspberries

use std::{ collections::VecDeque, fmt, io::{self, BufRead}, str::FromStr, };

struct Scanner { tokens: VecDeque, }

impl Scanner { pub fn new() -> Self { let stdin = io::stdin(); let mut tokens = VecDeque::new(); for line in stdin.lock().lines() { for token in line.unwrap().split_ascii_whitespace() { tokens.push_back(token.to_owned()); } } Self { tokens } }

pub fn next<T: FromStr>(&mut self) -> T
where
    <T as FromStr>::Err: fmt::Debug,
{
    T::from_str(&self.tokens.pop_front().unwrap()).unwrap()
}

}

fn main() { let mut input = Scanner::new(); let tests: i32 = input.next();

for _ in 0..tests {
    let n: i32 = input.next();
    let k: i32 = input.next();

    let mut myvec: Vec<i32> = Vec::new();
    let mut mysecondvec: Vec<i32> = Vec::new();
    let mut x: i32 = 0;

    for _ in 0..n {
        let num: i32 = input.next();
        myvec.push(-num % k);
    }

    if k == 4 {
        for i in 0..n {
            mysecondvec.push(myvec[i as usize] % 2);
        }
        mysecondvec.sort();
        x = mysecondvec[0] + mysecondvec[1];
        myvec.push(x);
    }

    let mut min_value = myvec.iter().min().unwrap();
    // Added this line to print the minimum value for each test case
    println!("{}", min_value);
}

}

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am not sure modulo for negative numbers works the way you think it works

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it -29 Vote: I do not like it

      well it did worked for python see R = lambda: map(int, input().split()) t, = R() while t: t -= 1 n, k = R() a = [-x % k for x in R()] print(min(a + [sum(sorted(x % 2 for x in a)[:2])] * (k == 4)))

      i think the logic of mod should not change for rust . now see the code and tell me why it is failing i am not able to understand that how the same logic is working for one language could not work for other language .

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +28 Vote: I do not like it

        Python uses different logic for modulo for negative numbers. For python -13 % 5 = 2. For c++, rust, java, etc, -13 % 5 = -3

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          Thank you , it finally got accepted. I used k — num % k when num % k != 0, and when it was equal to zero, I pushed 0 inside the vector. It got accepted. Thanks

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        i think the logic of mod should not change for rust

        now see the code and tell me why it is failing

        i am not able to understand that how the same logic is working for one language could not work for other language

        you are funny

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

it seems like it until you gotta as usize as i64 and as i32 1 million times

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you have a lot of primitive type conversions you likely write non-idiomatic code