Solving Advent of Code Puzzles with GitHub Copilot: Day 1
freddiev4.xyz
freddiev4.xyz
I usually use Common Lisp, and whenever I find myself typing boilerplate of a type that copilot would be able to help with, it's because I haven't used the right abstractions.
As an extreme example of this, I solved day 1 in KAP (my APL dialect) and for the second problem, my solution was 8 characters long. There was no real need to have anything type that out for me.
Surprise, programming languages are more efficient at encoding logic than English.
This will not be easy to see in any kind of coding exercise. It is very hard to come up with coding problems with solutions that have never been written before, at least for a coding competition like Advent of Code. For example, we don't know of polynomial time solutions to the Travelling Salesman problem but it wouldn't make sense to have that as a coding challenge in Advent of Code, or Leetcode, or anywhere else.
Since nobody has ever produced a program solving such a problem, Copilot will not be able to produce a solution either, but it's not designed to do that anyway.
Now, as i said, this was for a class, so it was simple. Sadly work policies at my employer forbids the use of copilot (or anything transmitting code out of the company), so i can't really test it with "real code",
It's not ready for actual use yet though, but any suggestions would of course be appreciated.
I'm one of the founders of https://cogram.com, a coding assistant for data scientists. Cogram brings Copilot-like features to Jupyter Notebook.
You can use Cogram by writing ordinary code (and Cogram will complete it), or by writing comments (in which case Cogram completes the code that matches the comment). We've also launched a web app that generates SQL statements from descriptions in simple language.
We're just starting out and would love it if you could try it out, give feedback, and spread the word if you like. It doesn't cost anything -- we have a generous free tier (1000 completions / month).
sum([arr[i] > arr[i - 3] for i in range(3, len(arr))])
You don't need functions (but that's kind of an opinion, so whatever).
More importantly, to check if a rolling sum is increasing you don't need to compute that sum. I wonder if Copilot can ever figure that out.
If that's the goal, an obvious solution may be to not write useless comments, typing and verbose function names :) Solving day 1 in Python is 10 lines of code without even trying to golf it.
The comment to trigger Copilot would be something like the following:
# Advent day1 part1
Which is that two of the values are the same in both windows you're comparing; you don't actually need to sum anything, just compare the unique values from each (i-3 and i, respectively).
If Copilot is trained on a corpus of average devs...I do worry about what this says about the state of our field.
...and my solution did actually do things the way you described, so I'm not just being defensive about it :P
For example, taking 2021_day1, the naive solution that reads in all of the values and then iterates through calculating and comparing sums is all well and good, it satisfies the end goal of producing a solution.
What if you had 1,000,000,000 values in the input?
* A program that reads in and stores all of the values before iterating through them now consumes a non-insignificant amount of memory.
What if you had to check the differences between the sums of 100,000 consecutive terms?
* A program that calculates and compares the sums (rather than just comparing the two non-common terms) will be doing a lot more unnecessary computation.
What if you had to take a seemingly endless input stream and report the running totals at 1,000,000 iteration intervals?
* A program that reads all of the input before iterating through it is now unsuitable.
..etc..
Programming is not just about getting the answer, it's knowing where you can do the bare minimum to do that, and knowing under what conditions your bare minimum solution will become impractical and what you would have to do to avoid this.
There's nothing stopping people using AoC as a toy to collect all of the stars (surprisingly few people have all 304 stars, it was under 700 last time Eric answered that question in July 2021). But it can also be used for a lot more than that.
Using AoC day 1 is probably not a good example of it however, because a lot of modern languages offer streaming iterators, so the naive, declarative solution will still not need to load all the values into memory at once.
More broadly, it's a neat observation that you can determine the direction of a rolling sum without actually maintaining a sum. And certainly, you can do it without recalculating the sum(s) at every step.
I think you make a mistake in assuming "the" point, as in, singular. From Advent of Code's own website - 'People use them as a speed contest, interview prep, company training, university coursework, practice problems, or to challenge each other.'
We also have seen people use them as an excuse to start doing something in a new language, and, per this post, to play with Github Copilot and understand what it's doing.
So...it's really what you want to make of it. -My- point was simply that if there's an ML model trained with all sorts of approaches devs use to solve sliding window style problems, and it manages to solve the problem but still misses such a generally useful optimization, it does call into question what it was trained on.
Yes, iterators have nothing to do with the 'just compare the two changed values' optimization. I brought them up because the parent brought up issues of eager vs lazy loading and reading infinite input streams in chunk.
lines[i+1] + lines[i+2] + lines[i+3] > lines[i] + lines[i+1] + lines[i+2]
The whole puzzle can be solved in just two lines of Python, but I certainly wouldn't come up with that in 1min it took the person that solved it first, since I had to take a step back and notice quite a few things (even if they're ultimately rather simple observations) to come down to such concise solution.
Because in the example explaining the steps, it shows you that? I.e., 'The measurements in the first window are marked A (199, 200, 208); their sum is 199 + 200 + 208 = 607. The second window is marked B (200, 208, 210); its sum is 618'; even how the text is aligned on the page, the 200 and 208 are almost directly above/below each other.
Sure, yes, if your goal is just to solve it as quickly as possible for the internet points, by all means do the naive thing. But if you already "had to take a step back and notice a few things to come down to such (a) concise solution", it seems like maybe solving it as quickly as possible wasn't your goal.
"Officially counts" - sure, in the sense of being officially counted. Not in the sense of even what Eric recognizes as the reasons for Advent of Code existing (as there are a number of reasons why people might use it in the About section).
Like how you apparently missed the other two bullets the article listed?
Fair that your original comment was about speed, but, you're also dismissing the discussion after that (i.e., you had to notice various nuances to the problem that slowed you down, and that this optimization was something directly noticeable just in the example given in the problem discussion), as well as the comment (i.e., mine) that started this thread, that was about the quality of code being pulled from Github and informing Copilot, and NOT about the speed of coming up with a solution on your own under time pressure, which is unaffected in this instance when using Copilot.
In short, you're saying "It's about speed; everything else doesn't matter", and I'm saying "It neither was about speed in my original post, nor is that the only possible goal". You're insisting the place you moved the goalposts is the only place they've ever existed.
How can I ignore my own argument in this discussion that proves my point? :D
> In short, you're saying "It's about speed; everything else doesn't matter"
Of course not, I'm saying "various people have various goals, and noticing that you can simplify sliding windows doesn't matter when you're after speed and naively calling `sum` is faster to type".
Copilot suggested `into_iter` instead of `iter` and my very first rust experience was a battle with the borrow checker trying to figure out wth is a move.
In my opinion the danger of automation is that anyone who knows less than the machine is not going to recognize a mistake - plus, a robot can do the easy things first and now you have a talent pool problem: no one is paying juniors to learn if a robot can do the work of a junior
This is also something I'm curious about regarding Copilot. I mentioned that "GitHub Copilot has a list of possible solutions to code completions, so I wonder if it’s just luck that the suggested solution was the correct one".
I'm going to test further to see if it just always produces the same code completion, or there's some bit of randomness to the completion.
The Codex model on which Copilot is based had about 30% accuracy on the first solution to a coding problem, but 70% when it was allowed to generate 100 solutions and choose the one that passed unit tests. On the other hand, when the best-of-100 solution was chosen according to the probability assigned to it by the model it scored 45% [1]. So it's kiind of luck.
Basically, Copilot has no way to tell whether it's giving you a right or wrong answer, other than to select the answer with the highest probability according to its training set which usually means the most common answer in its training set. So the probability that the answer you get is the "right" answer depends on the probability that the right anwser is the most common answer to the problem you give it. If that makes sense?
__________
[1] https://arxiv.org/abs/2107.03374
See Figure 1.
While I am not 100% sure of the sources, my use of Copilot makes me pretty sure it uses other open files in the editor, other files in the current project folder (whether or not open in the editor), and to suspect it may use the past history of the current file (at least in the same edit session).
I think it's more simple to assume that "get_*_input" is a common name for a function that reads input from a stream and so that this kind of string is common in Copilot's training data. Again, remember: GPT-3. That's a large language model trained on a copy of the entire internet (the CommonCrawl dataset) and then fine-tuned on all of github. Given the abundance of examples of code on the internet, plus github, most short progams that anyone is likely to write in a popular language like Python are already in there somewhere, in some form.
The form is an interesting question which is hard to answer because we can't easily look inside Copilot's model (and it's a vast model to boot). The results are surprising perhaps, although the way Copilot works reminds of program schemas (or "schemata" if you prefer). That's a common technique in program synthesis where a program template is used to generate programs with different varaible or function names etc. So my best guess is that Copilot's model is like a very big database of program schemas. That, as an aside.
Anyway I don't think it has to peek at other open files etc. Most of the time that would not be very useful to it.
> GitHub Copilot uses the current file as context when making its suggestions. It does not yet use other files in your project as inputs for synthesis. [1]