Protohackers problem 1 retrospective
Sat 27 August 2022Tagged: protohackers, software
I released Protohackers problem 1 on Thursday evening. The problem asks you to implement a server that accepts JSON-encoded requests, tests numbers for primality, and gives JSON-encoded responses. (This post contains spoilers for the problem; if you have not solved it yet, and you would like to solve it, then to avoid disappointment you should not read this until after you've solved it!).
So far, 62 people have signed up for the site (much more than I expected!), of whom 29 have successfully solved the test problem. 19 have attempted the first "real" problem, with 14 having solved it successfully. It's not clear whether the other 5 have been discouraged and walked away for good, or whether they'll be back for another go.
Amusingly, first and second place on the leaderboard were separated by only 2 seconds!
I don't know if these two were communicating or not, but they were submitting different IP addresses, so I assume they were not working together.
Discord server
Two people emailed me and asked about setting up a Discord server for people to join, so now there is one. If you want to join, you can click: https://discord.gg/RqqmGePnWU.
The problem statement
There were a few issues with the problem statement that I hope not to repeat in future problems.
The initial release of the problem statement didn't explicitly allow clients to make multiple requests over one connection! That's bad, because it means depending on your preconceptions of how the protocol is likely to work, you might assume that the client makes a single request, receives a single response, and then disconnects. Multiple people implemented servers that assumed only a single request per session was allowed. I have clarified this now.
The problem statement initially stated that the "number" field of the request object needed to contain a number in order to be considered well-formed, but some people assumed this meant it needed to contain an integer. While I maintain that a thorough and pedantic reading of the problem statement would lead to the correct interpretation, that shouldn't be the standard: a casual reading by a competent programmer should be enough to arrive at a correct understanding, especially when you consider that many users may not speak English as a first language.
Eric Wastl (creator of Advent of Code) says something like:
for each sentence in the problem statement, there is at least one user who reads everything except that sentence.
The intention was that non-integers are still accepted as well-formed requests, but that they are not prime (because only integers can be prime). But this is really just a distraction from the core purpose of Protohackers, which is to write programs that implement network protocols. Annonyingly-pedantic input validation is not the goal. I've updated the problem statement to be more explicit about the intent, and will try to avoid doing this sort of thing again.
One person was confused about exactly what I meant by a "newline character":
Each request is a single JSON object followed by a newline character ('\n', or ASCII 10)
They were outputting the literal string \n (i.e. a backslash followed by an "n"). I'm not really sure what to do about that. Maybe I should hyperlink "newline character" to the Newline Wikipedia page?
The checker
A weird quirk of the protocol is that the correct behaviour, in response to a malformed request, is to send a malformed response, rather than some sort of standardised error response. I just thought this had an amusing symmetry.
Unfortunately, my checker was not correctly interpreting all malformed responses. It only considered invalid JSON to be a malformed response, even though the problem statement said that a response was "malformed" even if it was valid JSON, but had fields missing, or invalid values in the fields. I had failed at making a sufficiently-pedantic interpretation of the problem statement in exactly the same way I was trying to test the users' interpretations of the problem statement. An amusing symmetry indeed. Hoist by my own petard! (This is fixed now).
One of the test cases is a really long number (something like 63 digits long). These are selected at random and almost always have low factors, so it shouldn't be too much of a problem to test them for primality. But sometimes bigints are too inconvenient. What then? At least one person noticed that the only test case that had a number larger than 64 bits also had a spurious extra field in the JSON ("bignumber":true), and he simply tested for this field, and returned a "non-prime" response without even checking the number! Lol.
Logo
I paid a man on Fiverr £15 to design a logo for Protohackers. The brief was something like "I want a logo that will fit with the existing colour scheme, and convey programming and networking". He came up with these three:
I can kind of see what he's trying to do with angle brackets on the first one, although it seems a bit more "HTML" than "HTTP". The second one clearly conveys the Internet, and connectivity, but I can't help seeing it as a cartoon snail. I'm going with the third option, but resized and rearranged to look a bit more subtle on the page:
Still to solve
I haven't yet worked out whether/how to create an "overall" leaderboard that combines the scores from the individual problem leaderboards. The Advent of Code solution is to cap the daily leaderboard at 100 places, assign 100 points for 1st place, 99 for 2nd place, etc. down to 1 point for 100th place, and add up all the points to form the overall leaderboard.
I'd like to find a solution that includes more than the top 100 places (admittedly, a leaderboard with more than 100 names on it is still a fair way off!). One option is to add up the leaderboard position for each problem's leaderboard, and then the lowest sum is the highest ranked on the overall leaderboard, but this has the drawback that people who haven't completed all of the problems can't be ranked on the overall leaderboard.
So I'm looking for a ranking solution with the following properties:
- completeness: rank everybody who has ever completed any problem
- fairness: if Alice and Bob have completed the same subset of problems, and Alice beat Bob on every problem, then she should be ahead of Bob overall
- stability: if Alice is ahead of Bob overall, and then Charlie comes along and submits a solution to a problem that both Alice and Bob have already solved, Alice and Bob's rankings are undisturbed
The Advent of Code global leaderboard satisfies fairness and stability, but not completeness.
Advent of Code also has private leaderboards, where you score points based not on 1..100, but on 1..N where N is the number of people in the private leaderboard. This satisfies completeness and fairness, but not stability, because adding a new person to the group can change the relative positions of people who were already in the group! (Because every submitted problem is now worth 1 more point: someone who got a high score on 1 problem only gets 1 more point, but someone who got low scores on M problems gets M more points).
It may be the case that there is not any possible ranking algorithm that satisfies all 3 criteria. I'm pretty sure this is not a new problem, so I probably just need to do some reading.
If you like my blog, please consider subscribing to the RSS feed or the mailing list: