DEV Community: Mark Robert Henderson

EXPOSED: The Leetcode C++ Cheat Code!!

Mark Robert Henderson — Sun, 27 Aug 2023 18:13:45 +0000

Here's a fun story about stdin, stdout, and how Leetcode users use C++'s dark power to game the system a bit.

Strange Things are Afoot at the Circle K

A few days ago, I was minding my own business going through the binary search study plan on Leetcode.

I worked on my C++ submission, optimized it at the Compiler Explorer, and submitted it only to find that while my solution beat over 90% of others in terms of execution time, it only beat 15% of people in terms of memory usage.

When checking the solutions that beat mine, I first saw this:

Your placement in the rankings isn't normally a huge deal - especially in simpler challenges - due to fluctuations in Leetcode's runtime. Sometimes it uses 26.5MB or memory, and sometimes it takes 26.6. Your placement in the rankings is somewhat randomized due to this.

But the difference in this graph is astounding. 26.7MB down to 5.9! That's somehow a 77.1% reduction in RAM usage on a simple binary search.

What is going on?

The Cheat Code

Clicking into each of those < 10MB solutions above all revealed the same thing. The following code was written (likely pasted in), above the actual submissions!



int init=[] {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  ofstream out("user.out");
  cout.rdbuf(out.rdbuf());

  for(string s; getline(cin,s); cout << '\n'){
    string t;
    getline(cin,t);
    int tar = stoi(t);

    for(int i = 0, _i = 1, _n = s.length(); _i<_n; ++I, ++_i){
      bool _neg = false;
      if(s[_i]=='-')++_i, _neg = true;
      int v = s[_i++]&15;
      while((s[_i]&15)<10)v = v*10 + (s[_i++]&15);

      if(_neg)v= -v;
      if(v == tar){
        cout << i;
        goto next;
      }

      if(v > tar)break;
    }

    cout << -1;
    next:;
  }

  exit(0);
  return 0;
}();

Explanation

So what the heck is going on with this code? I had to figure it out myself, so let me try and explain it to you.

IIFE Syntax

The first thing to note is that this code is an Immediately Invoked Function Expression or an IIFE. This means this function is executed (or invoked) immediately after it's defined.

In C++, the syntax is something like []{/* function stuff */}(); You might recognize its counterpart from JavaScript: (() => {})()

Why assign it to init? Long story short: so it will compile.

`ios_base::sync_with_stdio(false);`

By default, the input and output streams in C++ are synchronized with those of its predecessor, C. The theory is not so important for this explanation, because in practice what this means is you're doing duplicate work. This line of code turns this synchronization off.

Note that in this case the ios is "inputs and outputs" and not "iOS".

`cin.tie(nullptr);`

Similarly, C++'s own cin and cout streams are "tied" together in that flushing one will also flush the other. This disables that again preventing extra work.

Redirecting to `user.out`

The next two lines:



ofstream out("user.out");
cout.rdbuf(out.rdbuf());

Next, we redirect cout to a file called user.out, removing the time requirement of actually displaying anything on the console.

The nested `for` and `while` loops

This is the part that took me the longest to figure out - not only in terms of what the code does, but why?

What: In simple terms this part of the code reads in two lines of text, converts the second to an integer, and then returns the index of the first string that matches that integer.

Why: Since all the I/O synchronization and features are turned off above, the code within these loops is responsible for the actual processing of text.

I will admit that figuring out the bit shifting and integer casting of stdin and stdout is outside of my time box for writing this post, but if YOU know - explain it in the comments!

Neovim Config: from init.vim to init.lua

Mark Robert Henderson — Tue, 22 Aug 2023 03:32:30 +0000

It's 9:30PM, I'm on vacation, and I drank an energy drink an hour ago. It's time to shave some yaks as hard as possible.

Of course I'm talking about my Neovim configuration file, and migrating it from the Vimscript-based init.vim to a Lua-based init.lua.

Why would you do this to yourself?

A few reasons:

init.lua is backwards compatible with init.vim, but not the other way around
Lua has applications outside of Vim, and this is a good excuse to familiarize myself with Lua more.
I haven't done any benchmarking whatsoever, but Lua is probably faster than Vimscript, right? I mean, Lua is pretty fast...
I wanted to try some Lua-based plugins like NvimTree
Oh, do you know Vimscript? Yeah, didn't think so.

The API docs for the Lua + Neovim are here: https://neovim.io/doc/user/api.html

Migration Strategy

My overall strategy was pretty simple: first wrap everything in vim.cmd([[ ... ]]) and then pluck things out individually as candidates for conversion to Lua.

The code that follows exemplifies this process, and highlights certain categories of settings and what the Lua code looked like in the end.

vim.cmd

Vim's Lua APIs provide a convenience function vim.cmd that takes a string literal as its only argument. Anything in that string is evaluated as Vimscript. Kind of scary, but since we're controlling what goes into it it becomes extremely convenient for our migration.

Just:

vim.cmd([[
    " the contents of your existing init.vim
]])

And you're off to the races... but where's the fun in that? Where's the Lua?

Settings and Options

The first low-hanging fruit is your Vimscript set directives like set wrap. You have three options here and it can be a little confusing as to which options live where. I hate to sound like one of those vim people, but :help is really good here.

vim.g

This is for global commands, basically anything in the let g:*** Vimscript namespace. For example, let g:mapleader = " " becomes vim.g.mapleader = " "

vim.o

This will likely be the bread and butter of your migration, as it's the most consistent 1:1 mapping of set options and Lua expressions. See for yourself:

vim.o.spell = "yes"
vim.o.splitbelow = true
vim.o.splitright = true
vim.o.swapfile = false
vim.o.synmaxcol = 30

Note they even kept the weird "yes"-instead-of-true convention.

vim.opt

This is a special Lua table (read: hash map or associative array) that allows you to use more Lua-friendly syntax to set options.

For example, vim.opt.listchars is pretty nice:

vim.opt.listchars = {
  tab = "» ",
  trail = "·",
  extends = "›",
  precedes = "‹",
  nbsp = "␣",
}

vim.api: Keymapping and Autocommands

For more advanced functionality like keymapping and autocommands, you have vim.api

vim.api.nvim_create_autocmd({ "FileType" }, {
    pattern = "rust",
    callback = function()
        vim.api.nvim_buf_set_option(0, "tabstop", 4)
        vim.api.nvim_buf_set_option(0, "shiftwidth", 4)
        vim.api.nvim_buf_set_option(0, "softtabstop", 4)
    end
})

vim.api.nvim_set_keymap('n', '<leader>s', ':split<CR>',
    { noremap = true })

Conclusion

These are just some of the ideas and examples I was able to pull out of my experience in migrating to a Lua-based Neovim config. What do you think?

Another highlight of this adventure in yak-shaving is that it makes me review my old configuration code, allowing me to change, edit, and re-contextualize the ideas that I had and my previous intentions.

How about you? Have you done this same migration? Did I miss anything? Have you shaved any good yaks recently? I'd love to hear from you.