gerzytet's blog

By gerzytet, history, 3 years ago, In English

Background: Github recently released github copilot, a code-generation tool.

Ever since I got access to it, I've been relentlessly toying with it and testing its capabilities.
During this, I found that copilot has the ability to not only synthesize original code, but also translate code from one form to another, such as from python to c++, from code using one naming convention to another, and even to and from pseudocode.
By taking this capability to the extreme, we can write the solution for a CP problem in pseudocode and translate it to working c++ by spamming enter and tab.

Step 1: Paste in your preferred template, and write an outline in pseudocode

For example, here is an outline I wrote for this problem
I prefer to write my solutions as functions, with input data passed in as parameters, because I use a different technique for the input code, so I want it separate from the solution code. A variation of this technique could be used to put everything inside of main.

//outline:
//C is a 2d vector of booleans param
//returns a pair of 2d vectors
//rows is the length of C
//cols is the length of C[0]
//A is a copy of C
//for each row in a:
//    row[cols-1] = true
//for each col in a:
//    for each odd number row in A:
//        A[row][col] = true
//B is a copy of C
//for each row in b:
//    row[0] = true
//for each col in b:
//    for each even number row in B:
//        B[row][col] = true
//return A, B

While writing this pseudocode seems like a lot of effort, almost as much as writing the code directly, copilot's autocomplete is surprisingly helpful for filling it in!
There's no hard rule for what style to use for writing pseudocode. As long as it expresses your algorithm specifically and clearly enough, copilot will generally understand it. My personal style ends up looking a lot like python.

Step 2: Help copilot write the first 4 lines of the solution.

The pattern I have found to work best for accurate code generation is to write the first pseudocode comment, then the implementation for that line of pseudocode, and continue the pattern for the rest of the function.

  1. the first line is the function signature. With a well-written outline, copilot should be able to autocomplete the rest of the signature after you type the first token of the return type.
  2. the second line is the first pseudocode comment that doesn't describe parameter/return information, reproduced exactly from the outline. Type the comment marker and the first word or 2 and copilot will autocomplete the rest. (or copy and paste it)
  3. the third line is the implementation for the previous pseudocode line, which is usually a variable declaration. type the first token and again it will complete the rest.
  4. the fourth line is the second pseudocode comment. Sometimes copilot will suggest it immediately after moving to this line, but if not, repeat step 2.
  5. implementation for the previous line. If copilot doesn't suggest it immediately, you know what to do.

For the outline in Step 1, here are the first 5 lines:

pair<v<v<bool>>, v<v<bool>>> matrix(v<v<bool>> C) {
    //rows is the length of C
    int rows = C.size();
    //cols is the length of C[0]
    int cols = C[0].size();

Step 3: Generate the rest!

After the initial 5 lines, copilot will have learned the comment-code-comment-code pattern and will begin suggesting the next comment/code all by itself after advancing to the next line. The only thing left to do is spam Enter then Tab like there's no tomorrow!
The final code I got from the outline can be seen in this submission (note that the pseudocode clearly doesn't match the generated code in the "for each col in a/b" lines. This is because of last-minute changes I made to the algorithm without updating the corresponding psudocode.)
If you want to see steps 2 and 3 in action, refer to this video, where I use this outline to generate a solution.
The solution from that video is submitted here

The example in the video happened to go smoothly, but usually there will be multiple copilot hiccups during the process, so you unfortunately still have to look at all the code its generating to make sure it's correct.
One common issue is when copilot simply suggests the next comment without writing the code for the previous one, which usually happens when you write a line of pseudocode that takes multiple lines of implementation. You'll have to write part of the first line of the implementation in this case.
Other times, it just flat out does the wrong thing. Sometimes copilot will write smart implementations that surprise you, but it can also surprise you in the opposite direction

Step 4: write the main() function

For the main function, I personally don't start over from an outline. I just copy-and-paste the input and output section of the problem statement, and from there it can generate at least most of the IO code, although it makes about 3x more mistakes than on the solution code. I see this as an acceptable compromise.

Conclusion

There are both advantages and disadvantages to using this method.
Advantages I have experienced:

  • Pseudocode is very flexible. I can write the first, shortest way I can think of to express an idea without reshaping it into c++, making it faster.
  • Less implementation bugs. Most of the time when the solution was not accepted it was because the algorithm was wrong, not because of a mistake during the generation step. 80%+ of the solutions I've made with this technique have had no implementation bugs, which is far less than I had previously.
  • Less context switching. Writing in pseudocode allows me to think less about the algorithm's implementation details and more about the design, which means I find bugs in the design faster.

Shortcomings of the method:

  • It requires duplicate comments both above the function and in the code, making it bulkier and uglier. In addition, changes made to the pseudocode header must be repeated inside the function, which is an easily forgotten step. However, there are reasons it was necessary to design it this way:
    • without the comments, copilot will restructure the code, making it harder to pin down which pseudocode lines correspond to which implementation lines in case changes are needed.
    • without the comments, It is harder to check the correctness of the generated code, leading to more errors slipping though.
    • without the comments, copilot is more likely to skip implementing parts of the solution, an error that would be more obvious with comments.
  • In general, the comments within the function make copilot behave in more predictable ways. I hope that better methods of using copilot are discovered that do not require this.
  • Copilot has a character limit. Based on experimental measurements, copilot sees approximately 3446 preceding characters of the file to use for its suggestions. For longer solutions, this could mean that the pseudocode falls out of range, and copilot can't autocomplete the comments anymore. The only solution right now is to split the code up into multiple smaller functions.
  • The first 5 lines are extra error-prone and take additional intervention to generate, which must be repeated for every solution. I predict that this could be solved by writing a pseudocode outline for at least one of the functions in the template, so that copilot has already learned the pattern by the time it gets to the solution code.

Additional examples:
note: in these examples, a /**/ marks a place where copilot did not automatically generate a correct implementation, and I had to help it.
https://mirror.codeforces.com/contest/1463/submission/125413254
https://mirror.codeforces.com/contest/1463/submission/125396582
https://mirror.codeforces.com/gym/102944/submission/124793709

here's a good counterexample. copilot had tons of issues and the algorithm ended up failing anyway:
https://mirror.codeforces.com/gym/103076/submission/124801422

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

»
3 years ago, # |
  Vote: I like it +67 Vote: I do not like it

how to do the same thing without github copilot:

  1. paste in your preferred template, and write an outline in pseudocode

  2. delete the template, uncomment the code and submit in python

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

    you can save time by not writing the template in the first place

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It would only save time if the cost of writing the pseudocode + the 4-ish minute translation step exceeds the cost of writing the code directly.
      For me, I've found that using this method saves time because of its better flexibility and fewer implementation errors, more than paying off the translation time.
      However, this is not universal. I imagine that because you're a grandmaster, using this method would have no benefit because you don't suffer from the kinds of problems this is intended to solve, but it might have benefits for others.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    While my pseudocode often looks like python, it wouldn't work as python code without the same kind of manual code-translation that this method avoids.
    Besides, python's performance makes it an unsuitable language for many problems.
    The method described in this post is far from simply writing the code in python, and it has the advantage of being more flexible than any one language could afford.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by gerzytet (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why do i think that this would directly help someone in plagiarism?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hmm... This is a concern I haven't thought about.
    It's true that someone could copy someone else's pseudocode and use it to generate their own solution, if that's the kind of plagiarism you're referring to.
    But because copilot is usually consistent about what recommendations it gives based on the given context, I believe the results would be similar enough to be detectable though conventional means.
    Another consequence is that solutions would be easier to understand and, in turn, hack.
    Perhaps if this method caught on, someone would make an automated tool to remove the comments from final submissions to combat these issues.