[Tutorial] The command line: how to read input from file without #ifdef and much more

Правка en3, от -is-this-fft-, 2022-09-11 12:21:05

Introduction

Instead of algorithms and math, I'll be doing something completely different here. There is something that has bothered me for a long time: people not understanding the tools they use to participate in contests and thus failing to take real advantage of them. And it all goes back to not understanding the command line.

Some of you might say, "well surely, the command line is something obsolete and you're only clinging to it because you [insert ridiculous amateur-psychology here]?" No! The command line is not obsolete, and unless competitive programming becomes so mainstream that software vendors start writing professional-grade tools aimed specifically at us, it won't be. $$$~$$$

What is the command line? Any of these:

As you can see, it comes in many background colors and fonts, but the basic idea is always the same. It's a box you can type commands in, which it will then execute.

Why use the command line?

  • Flexible and very powerful. In competitive programming, there are a number of tasks you have to do to work with your code locally: compiling, running, testing, stress testing and so on. Modern IDEs have tools for these, but they are not really designed with us in mind. Many people have written extensions to do these things comfortably, but what if you need to do something slightly different, something the extension author had not anticipated? You get stuck and have to make-do with some stupid hack. The command line allows you to do all those things, however you want to. It's very possible that just by changing a few small things will allow you to do what the extension author had not anticipated.
  • Submit exactly what you wrote. A very basic thing in competitive programming that you have to do is test your program, at least on the sample tests. The first thing that beginners usually do is they press the "run" button in their IDE and manually type the test case into the black box that appears. This is very error-prone and very time-consuming. A better way would be to read the input from a file, but now what you submit will be different from what you test locally. People will often tell you to use something called an "ifdef", but that also has its issues, see below.
  • Interactive problems. Some contests such as Google Code Jam offer a testing tool for interactive problems; IOI also offers various tools to test problems. If you have never learned the command line, you'll probably have to think for a while about how to run this. With the command line, it is dead simple.
  • Deeper understanding. Understanding the command line means understanding how everything your IDE does actually works. Then you are also in a better position to customize your IDE if you choose to continue using it. I mentioned testing tools for interactive problems above. Usually, you have to pass your program as an argument to them. If you have always relied on an IDE to run your code, you might not even grasp the concept of an "executable" and getting this interaction tool to run will be an impossible task. I've had to teach this stuff to people who were otherwise relatively proficient in competitive programming.
  • Full control. The command line offers you the most fundamental level of control over what's actually happening in your computer.

Update 11.09.2022 More generally still, I've noticed that people often learn the bare minimum when it comes to being able to edit and run programs locally. They find one configuration or setup that works by trial and error and stick with that, even though when you look into it, it may be a ridiculously convoluted Rube Goldberg machine. This will work until the situation slightly changes, and then you're stuck.

The recent example that prompted me to write this comes from Meta Hacker Cup. There, you have to run the program locally on your computer within a 6-minute window, on a test file that may be quite large (let's say, 60 MB). For a number of people, the workflow included opening these files and copy-pasting their content somewhere else. With files this size, it is quite impractical and can easily crash editing programs that are not optimized for large files (regardless of the speed of your computer).

Learning the command line means learning how your computer works. Understanding this stuff means that you can take advantage of it and streamline your setup for testing locally.

About editors and IDEs

As far as text editors go and what I've seen people use to write code, there are basically four categories.

  1. Classical text editors. Examples: Emacs, vi, gedit, nano, Far Manager, Notepad.
  2. Lightweight modern code editors. Examples: Visual Studio Code, Sublime Text.
  3. Full-fledged IDEs. Examples: Visual Studio, CLion, Xcode.
  4. Code::Blocks.

This is obviously not some objective classification, and the lines between the categories get very blurry, but I hope on an intuitive level you understand what I mean.

My advice: don't use items in category 3 for competitive programming and don't use items in category 4 for anything. Full-fledged IDEs are meant to be used for medium-to-large software projects and are designed with that in mind. They want you to create a Solution and then a Project, then set up a Build Configuration and so on. This is all very good and important if you are maintaining a real software project with hundreds of classes and nontrivial build sequences, but utterly pointless if all your programs are in a single file, which is what you have to do in competitive programming. Many people copy-paste their code into the box on CF simply because amid all this complexity, they have no idea where their .cpp file actually is.

Moreover, although they are very powerful, you won't use any of this power. But you still have to pay for that power by having to deal with long loading times if you have a weakish computer, and using a lot of RAM.

Lightweight code editors, on the other hand, are great. They provide some of the simpler utilities of full IDEs, such as a "rename this variable" function, without introducing all the bloat of full IDEs. In addition, they usually provide easy access to the command line, giving you all the benefits I mentioned above.

The moral of the story is that you should use appropriate tools for different tasks. Software engineering very different from competitive programming, and require different tools. I use GNU Emacs for competitive programming and JetBrains Rider at work, and I would never want to do it the other way around.

Basic tasks using the command line

This section is organized as a "lab". If you are new to the command line and want to learn it, I recommend doing everything I tell here. Of course, this is more of a tutorial on "how to do essential tasks for competitive programming", not a comprehensive tutorial on how to use it in general. But I will go through other necessary commands anyway.

Setup

For this "lab", I suggest using the simplest possible program to code. Forget your good IDE for a bit to avoid any temptations. Don't worry, later we will come back to the fancy editors and using the command line there.

The first step is actually opening the command line.

  • On Windows, open the Start menu and search for "cmd.exe".
  • On Mac, open the Finder and search for "Terminal".
  • On Linux, it depends on your distribution, but you can usually find it by opening some kind of menu and searching for "Terminal". But if you use Linux, you probably already know.

Windows actually has two kinds of terminals: cmd.exe and PowerShell. Both have their ups and downs, but the commands are different. In this blog, I will provide commands for cmd.exe but not PowerShell.

Once you have got it open, type ls (Linux/Mac) or dir (Windows) and press Enter. You should see a list of files and folders located in the folder you're currently in.

Compiling and running your code

I'll be assuming you work with C++, since that is the most common scenario in competitive programming. First, we shall write a program. Of course, you already know how to do this, so there is no point in lingering about it.

I've written a program. Save it as program.cpp.

program.cpp

Now, we need to compile and run it. The first step is to actually locate the file in the command line. In some ways, the command line is a lot like a file browser on your computer:

At any given time, it is in a certain folder, and you can navigate to other folders. But instead of double-clicking a folder, we use commands like cd. You can use:

  • cd some_folder to go to a folder called some_folder located in the current folder.
  • cd .. to go to the parent folder.
  • pwd (in Linux/Mac) or cd without any extra stuff (in Windows) to print the folder it is currently in.

The first task is to use these commands to find the folder you saved your file in. Since I don't know where you saved it, you're going to have to find it on your own.

What happens when you press that "Run" button in your IDE is actually two things.

  • First, your code will be compiled from human-readable code into a magic binary file that the computer knows how to execute.
  • Second, the computer will run that binary file.

If you are using Windows, you might first need to install a C++ compiler. A version of GCC is bundled in MinGW. It is a bit cumbersome to install it, but there are many good guides online. After that, you can type g++ like the rest of us. In Linux and Mac, GCC is already installed (on Mac, it's actually clang, but that's not important right now).

In modern IDEs the difference between these steps can be very blurry and also, it's not like that for every programming language. On the command line however, you have to understand that these two things are separate steps, and you have to run them separately. First, the compilation. Type

g++ program.cpp -o program

This tells another program, called g++ (the real name is GNU Compiler Collection, g++ is just a shorthand to run it in the console for C++) to compile the file program.cpp into a binary and save it as program (-o is for "output"). program will now be another file in the same folder. This file is one that the computer knows how to execute. To run your program, you can now simply write ./program (in Linux/Mac) or program.exe (in Windows). I'm not going to write (or program.exe in Windows) every time, so if you're using Windows just keep in mind that if I tell you to write ./program, you should write program.exe.

The ./ can be confusing. On Linux/Mac, when you run a program that is in the same folder as you are, you have to add that ./. There is a good reason, but I can't get into it right now, so I'll just say that this is just how it is.

Now, you can type in the two numbers, press enter, and it will print their sum.

There are a couple things to note here. Since compiling and running are separate steps, you should know that:

  • If you want to run the same program multiple times, for example to test it with multiple different inputs, there is no need to compile it twice.
  • However, if you modified the code, you also need to compile it again for the changes to take effect.

Finally, in case you get stuck in an infinite loop, Ctrl-C will stop the program.

Simple testing

Once you have written and compiled your code, it is now time to test it, at least on sample tests.

Many beginners do it like this. They click the "run" button on their IDE, then a black box opens. They write the test case to the box manually. This is very error-prone and very time-consuming if your program has a lot of bugs and you have to run and edit it many times before it works.

There are other problems with this approach as well. On some IDEs, the black box immediately disappears once the code has run, which means you haven't got the time to check whether the output is correct. The correct approach here is to figure out how to change the IDE settings so it doesn't do that, but a lot of students instead apply hacks such as adding int trash; cin >> trash to the end of their code so that it will wait for input and not close immediately. Of course, this means that you have to change the code to submit it, which you will forget to do, thus you get a "Wrong answer" or "Idleness limit exceeded" verdict.

In local olympiads, we have discovered that many new-ish students have completely given up testing their code locally, including testing on sample tests, because of such difficulties. Of course, this has a direct and dire effect on their contest performance.

The better approach is to read input from files, but now you have a new problem: how do I make my program read input from files locally but from standard input in the judging system. The wrong solution students come up with is writing their code to read from files and then changing it before submitting. A slightly less wrong solution is to use #ifdef, but then you have to figure out how to compile the code in a special way.

There is a better way! We have already learned how to compile the file program.cpp into an executable called program, and how to run it using ./program. Now, make an input file called input.txt and paste the test case in there. Put it in the same folder as the file program. For example:

input.txt

Now, from the command line, run the following:

./program < input.txt

The < here is the key. It tells the computer to forward the contents of input.txt into the standard input, as if you manually entered 3 7. With any luck, you should see 10 on the screen.

Similarly, you can write

./program > output.txt

Now, you have to manually write the input, but the output will be written not to the screen, but to a file called output.txt. If the file does not exist, it creates it; if it does exist, it will be overwritten.

You can even combine the two as such.

./program < input.txt > output.txt

And of course, you can replace input.txt and output.txt with any file names you choose.

This will be useful later, in the "stress testing" section.

Stress testing

Suppose you get a "Wrong answer" or "Runtime error" verdict. What will you do? Well, the first step is usually to just look at the code and try to spot obvious mistakes. But it will happen, and it will happen often, that you get stuck. What do you do then?

The first thing to do is to reproduce the error; find an actual test case where your program fails. Then you can debug the code, to find out where it does the wrong thing. This method is very effective for finding mistakes in your implementation, but also to find out that your idea was wrong and exactly why your idea was wrong.

Sometimes you can find such a test case simply by manually testing some case that might be suspicious. Sometimes, you can download the test cases for the problem, for example AtCoder and many olympiads publish all test cases after the contest. But this doesn't help you during a contest; also it may happen that the test case you failed at is very large, which you effectively can't manually debug.

There is a better way! Many of you have seen this comment of mine:

Have you tried the following:

  • Write a very naive and simple solution to the problem (maybe exponential complexity) (if you can, you may also just copy someone else's solution)
  • Write a program to generate thousands of small (!) test cases
  • Using those two, find a test case where your program gives the wrong answer
  • Use print statements or a debugger to see where exactly your program does the wrong thing.

The problem. Now, we are going to learn how. First of all, we need a problem to solve, because I don't think anyone is going to make a mistake on the A + B problem we were solving before. So, let's look at CSES 1090 — Ferris Wheel (thanks de_sousa for suggesting it!).

Someone might come up with the following solution:

Sort the children from lightest to heaviest and process them in that order. If a child is too heavy to fit in the current gondola, send that gondola on its way and take a new one. Otherwise, just add the child to the current gondola.

I have implemented it here. Save it as ferris.cpp and compile it as usual to ferris.

ferris.cpp

If you submit it, you will see that it gets WA on 7 of the 12 tests. Now you might wonder whether you've made a mistake in implementation or if the idea is wrong altogether. To do so, it is best to look at an actual test. Now, on CSES you can actually view the failing test, and there are some small ones, but let's ignore this for the purposes of demonstration, because a lot of the time, this isn't going to be the case. Instead, we are going to find a failing test case by stress testing.

The naive solution. Now, let's look at, line by line, the instructions. The first line is:

  • Write a very naive and simple solution to the problem (maybe exponential complexity) (if you can, you may also just copy someone else's solution)

We can't copy someone else's solution on CSES, so we are going to have to write one ourselves. How should we go about it? Here are a few guidelines.

  • It doesn't matter how fast or slow this naive and simple solution is. You're only going to run it on small test cases.
  • It is best to make this as simple as possible, using as little logic as possible. Make it so simple it can't be wrong.

For this problem, here's an idea. Instead of sorting the list of children, let's try all possible orderings. One of them has got to be right: if you visualize an optimal solution, we can put the gondolas in a line and read the children in this order, then that will be an order for the children. It might be that our solution would put some children in earlier gondolas, but that can't increase the number of gondolas, and it can't decrease either because the set of gondolas is optimal.

I have implemented it here. Save it as ferris_naive.cpp and compile as usual to get ferris_naive.

ferris_naive.cpp

It's a bit suspicious that I reused some code from earlier, but if the idea is wrong, we will still find a countertest.

The generator. The second line:

  • Write a program to generate thousands of small (!) test cases

The way to do this is to write a program that generates one random test case. Some guidelines again:

  • This code can be very quick-and-dirty. During a contest, you shouldn't spend time polishing things like that. Whip it out as quickly as you can.
  • The generator doesn't need to generate any possible test with equal probability or anything like that. All you need is a program that could reasonably well produce any valid small test case.
  • As a consequence, even though rand is evil, it's totally fine to use rand() here to generate random numbers.
  • It's a good idea to take the random seed from an argument and not set it by time, so you can easily regenerate a test if you need to.

I have implemented a simple generator for the Ferris Wheel problem here. Save it as ferris_gen.cpp and compile as usual to produce ferris_gen.

ferris_gen.cpp

The code is pretty self-explanatory; the main question you might have is "what are argc and argv"? Another brilliant feature of the command line! Once I have compiled the code, I can run it from the command line as such: ./ferris_gen 5 3 8. The stuff after the program name are its arguments, and they can be accessed through argc and argv. argc is the number of arguments; in this case, 4. argv is the list of arguments. In this case, argv will be an array containing ["./ferris_gen", "5", "3", "8"]. This allows me to change the random seed or input size without changing the code or reading it from input.

The script. Now, the third line.

  • Using those two, find a test case where your program gives the wrong answer

Now, how do we combine our three programs to actually find a failing test case? There is one more important part of the command line that we have to talk about: scripting. You don't have to type everything into the command line manually. It is possible to save lists of commands as scripts. When you execute one, it will run all these commands sequentially. Scripts also support familiar features of programming languages such as ifs and loops, so you can write little programs this way.

Our task is now to generate thousands of test files, run both the naive and the correct solution on them. To do it, I have written a script file.

For Linux/Mac: save the following as script.sh

for i in `seq 1 100`; do
    # prints the current test number
    # I like to do this so I can see progress is being made
    echo $i 

    ./ferris_gen $i 4 5 > input.txt
    ./ferris < input.txt > output.txt
    ./ferris_naive < input.txt > answer.txt

    diff output.txt answer.txt || break
done

For Windows: save the following as script.bat

@echo off

for /l %%i in (1, 1, 100) do (
    echo %%i

    ferris_gen.exe %%i 4 5 > input.txt
    ferris.exe < input.txt > output.txt
    ferris_naive.exe < input.txt > answer.txt

    fc output.txt answer.txt || goto :out
)

:out

The syntax is weird, but it is essentially a for-loop. How those lines in the middle work has been discussed already:

  • use ferris_gen to generate a test case, forward it to input.txt,
  • run ferris with the input in input.txt, save the output to output.txt,
  • do the same for ferris_naive, save the output to answer.txt this time.

All that's left to do is to check if output.txt and answer.txt are the same. diff (fc in Windows) is a command that does that. If the files don't match, it will print the mismatched lines and exit with a nonzero exit code. The part after || is executed only then, and it is just a break.

If this code breaks early, the script has found a test case where the naive and wrong solution disagree. It will be available in input.txt. Otherwise, it found no countertest. In this case, try varying the input size parameters, or run it on more cases.

On Linux/Mac, to run the test, you first need to give yourself permissions to run it; to do that, use

chmod +x script.sh

And finally you can run it as: ./script.sh (Linux/Mac) or script.bat (Windows).

In my case, it found a countertest on the very first try:

4 5
4 2 3 1 

Indeed, the greedy solution will sort them and come up with this partition: $$$\{\{1, 2\}, \{3\}, \{4\}\}$$$. But there is a better way: $$$\{\{1, 4\}, \{2, 3\}\}$$$. We have identified, that the greedy idea is probably wrong or incomplete. It's now time to rethink the solution.

Once someone told me "I already have little time to practice and now you're telling me to write MORE code? What's WRONG with you?" after I explained this. In reality, writing these extra bits of code will only take a few minutes if you can code fluently, while trying to debug code without an actual case can take hours. Yes, I actually use this method regularly during contests.

Measuring time taken

Sometimes, you need to know exactly how much time your program took. Maybe you're not sure whether it will TLE or barely pass. Maybe you're optimizing the constant and need to know if you're on the right track.

Something people will do is measuring the time taken in the code:

int main () {
  auto start = duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();
  // insert awesome algorithm here
  auto stop = duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();
  cerr << "Took " << stop - start << "ms" << endl;
}

There is a simpler way! On Linux/Mac, from the command line, you can simply write

time ./program < input.txt

I don't know how to do this on Windows.

The time command will run everything after it as normal, and report the time taken. Now, this doesn't make in-code time measuring completely pointless, especially if you want something more fine-grained such as measuring how much each step took, but a lot of the time it is unnecessary, and the time command will do just fine.

Testing interactive problems

Testing interactive problems is hard. One way is to manually type inputs, which can be fine, except a lot of the times it isn't. One way is to write your own (simple) interactor to see if your code works properly. Now you have the problem: how do I make the two processes communicate with one another?

There are ways to do it with "pure" command line (with mkfifo and so on), but I think it is simplest to just use Google Code Jam's tool, which I have linked here. Now that you know how to run programs from the command line, it should be simple to run this one to test your program. You can simply write

python3 interactive_runner.py ./judge -- ./solution

Using the command line in code editors

So, am I telling you to stop using any modern code editing tools, going back to the 80s? No! People who create IDEs are generally aware of how useful the command line is and have provided ways to access it.

GNU Emacs

By M-x ansi-term. Or, in normal people' language, by typing Alt-X, then "ansi-term", then enter.

Visual Studio Code

By using "Terminal" in the top menu:

Sublime Text

By installing the Terminus extension.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский -is-this-fft- 2022-09-11 12:21:05 1116
en2 Английский -is-this-fft- 2022-04-27 00:43:41 174
en1 Английский -is-this-fft- 2022-04-26 23:46:08 28238 Initial revision (published)