Dmitry Astapov (_adept_) wrote,
Dmitry Astapov

ICFPC-2020: Space, The Final Frontier

Time to break the long radio silence to treat you to another tale of my ICFPC adventures. For uninitiated, ICFPC stands for ICFP Contest (and ICFP, in turn, stands for International Conference on Functional Programming), and I have been participating in them since ... well, since time immemorial (2004? 2003?) and writing up my adventures here. My most famous writeup (in Russian) about the best ICFPC so far -- 2006 -- could be found here.

This time I am going to do the write-up in English because there would be lots of English text quoted, and because I want my teammate (Hi, Alex!) and colleagues to read it.

TLDR: I liked this contest. A lot. Many aspects of it were nothing but stellar, and would serve as a yardstick against which future contests will be measured. However, the decision to trickle-feed task description through discord during lightning round was very controversial, in my opinion. It meant that you can't just print out the task description and mull it over with a cup of tea. For the longest time, task description was effectively updated every couple of minutes in a small way and periodically there would be large-ish "bulk updates". They would happen ad-hoc, without any schedule, so you had to devote significant time and effort to monitoring Discord. I have no idea what effect this had had on single-person teams, but it was probably not great. In this first post, I will rant about this A LOT (hopefully, in the first post only), because I need to get this off my chest. Then it will get better, I promise. Stick with me...

So, let me tell you a story about ICFPC-2020 (where our team name was Just No Pathfinding, for reasons that would be explained later).

Do you know who else broke radio silence? Some aliens - they were allegedly contacting fictional Pegovka Observatory, sending them mysterious radio signals, which were decoded to zeroes and ones, and further decoded to a series of mysterious images. At least this is how the story went in the teasers of this year's contest.

First mysterious message, containing numbers 0 to 9 (first column)

I missed all this fun, but it seems that starting from Jul 1, 2020 (16 days before contest start) organizers have been posting an image per day, and more active participants flocked to the Discord chat set up by organizers to mull them over.

Organizers posed as scientists from Pegovka observatory and tried to direct the discussion about images and their possible meaning. Over two weeks, fourteen images were posted, seemingly containing the rules for encoding positive and negative numbers, incrementing, decrementing, adding and multiplying them, comparing them, and encoding true and false values and testing them.

Rules for integer multiplication, message #9 (4 * 2 = 8, 3 * 4 = 12, 3 * -2 = -6 ...)

As Discord chat was making sense of the images, organizers were updating documentation hosted on ReadTheDocs that contained all the images and their current perceived meaning. More active participants even wrote some Haskell code to decode the images into numbers and pseudocode like "inc", "dec", "add", etc. Organizers incorporated suggestions from participants in the docs, urged them to submit pull requests, and accepted them.

On the day before the contest, this image was posted (message #15), and was subject to heated debate:

Now, those who participated in ICFPC in the past are used to the over-the-top mysterious back-story that gets published before the contest. It usually contains hints that you can understand only in retrospect after the contest is over. It is always mysterious and incomprehensible. Also, you are free to ignore it - it serves to build up the anticipation of the upcoming contest, but is not part of the task, contains no important information, and serves no practical purpose as far the actual contest is concerned. It was never required nor needed to immerse yourself before the contest begins. Well, at least this was the case in all the years that I can remember back to 2004.

This year, everything was different. When the time came, I eagerly refreshed the website to see the problem specification, but what I found instead was that the backstory continues and the problem specification is nowhere to be seen.

Site contained just this:
"Dear participants of the ICFP Contest 2020. We have prepared a great
contest for you! But we have strong reasons to throw it out and ask
you to put your efforts into something else.

Our friend Ivan Zaitsev, a staff astronomer at Pegovka Observatory,
has recently become a part of a very peculiar story. During the last
two weeks, he has received many messages from an unidentified source
which was later recognized as a spacecraft. Ivan has made some
progress in decoding and understanding the messages but recently the
spacecraft has transmitted a lot more.

Please help to decode the messages! The humankind needs your help.

Ivan will be right here with the ICFP Contest organizers. Reach out to
him on Discord."

So, for people who were busy decoding "alien messages" for the past two weeks, nothing much have changed: there was still fictional Pegovka Observatory website with its blog about alien messages, Discord channel on which they were having daily chats, and documentation on ReadTheDocs that they were slowly creating. Nothing new was added to the context with which they were already familiar.

Organizers just posted more images, bringing the total to 42 (hah!), and all the "old-timers" that participated in the back story were ready to start decoding them.

I urge you to see the message posted on discord when contest have started. Scroll a bit up and down and see how all the people active on the channel for the past weeks just took it in stride and got down to work.

From the Discord, T+9 minutes after the start of the contest, one of the active decoders:

Suggestion: things are going to get lost/repeated here unnecessarily, and filing a PR will take time. Instead, let's open an issue corresponding to each message and track ideas about each there.

Remember: I reconstructed all this today, well after the contest had ended. Back then I was just confused that there is no problem description, the Pegovka Observatory site seemingly contained just old messages.

ReadTheDocs site did not look the way it looks like right now: there were just 42 pages with 42 messages, first fifteen of them decoded, and the rest were not -- pages for those were titled "???" and contained just "???" as the description, and there was no indication about their purpose or any direction for participants except "go to Discord and help us decode alien messages".

So, I did just that, arriving with other confused participants.

Participant: so, there's no task and we've got to piece stuff together from the readthedocs site?

Organizers: Yes you are. We know the meaning of the first 15 messages. Now it’s time to decode the rest.

Our team hasn't been keeping up with the messages and their meaning over the last week. How far behind are we in this contest?

Organizers: about 10-15 minutes of careful reading behind I think

I think that "10-15 minutes of careful reading" was an understatement of truly galactic proportions. Yes, you could probably catch up in half an hour if the information was organized in a somewhat linear fashion and if you could ignore the chat.

However, the chat was the only place that promised some answers. Among the throngs of confused, more clued-up people were writing "#17 could be associativity rules" or "#20 could be function composition" or "Ha! Booleans are church-encoded".

I was very confused. How do they know this at 14 minutes after the start of the contest? Did they manage to decode THIS so quickly?

Image 17:
ap inc ap inc 0 = 2
ap inc ap inc ap inc 0 = 3
ap inc ap dec x0 = x0
ap dec ap inc x0 = x0

Image 20:
ap ap ap b x0 x1 x2 = ap x0 ap x1 x2
ap ap ap b inc dec x0 = x0

Organizers were just repeating "Decode messages! Collaborate!", and the thing is: people who where active for the past two weeks knew exactly what to do and engaged with the organizers, and organizers engaged with them.

Many, many other participants were the living embodiment of this meme:

Imagine joining discord on T+27 minutes to see this being posted:

BTW, parser fails for #24: it recognizes block of four dots as x0

Huh? What? Which parser? Where did they get that? In 25 minutes? I started looking at the images. Oh, the first one looks like it encodes numbers! Well, duh - it clearly says that on the docs page. I browsed through the rest of the decoded images and finally reached #16 - the first undecoded one:

Oh, the right-hand column looks like numbers, 0, -1, 1, -2, 2 (it took me a minute to write them down, checking the docs page for numbers). And before that, "c" thing - that is "=". And right before that: numbers, 0, 1, -1, 2, -2.

Oh, so this is negation! Excitement! I switched to discord to share my find. I scrolled through unread messages first, only to see that this was already suggested several times. Furthermore, one of the suggestions had a reply: "yeah, reload the docs page - it is already decoded". I reloaded the page, and indeed, it now said 'Negation' with image decoded into neat numbers.

Organizers were simulating "excited scientist from Pegovka", who was reading the chat and incorporating suggestions into the documentation. As documentation was held in GitHub repo, some people suggested that we need to open PRs to update the docs.

Early doc pages were referencing the Haskell script for decoding the images, so I decided to update it to include suggestions being posted to the chat. I made a PR to submit the changes in the decoder, and kept it updated for a while, eventually realizing that it would be silently ignored, and there is no intention to merge it.

For our team of two, there was no point to try and decode images. Those who were busy decoding pre-contest left everyone else in the dust. Whatever idea you had - they had it earlier already. Everyone was sending suggestions, seemingly at once. Orgs were busy sifting through them and updating the docs accordingly, picking suggestions according to some unknown criteria, and giving little feedback. Updates to docs were steadily streaming in. Every time you pressed "F5" or Ctrl-R, there would be something new on the doc pages. This was quite demoralizing: why try decoding something when there are dozens of people who will beat you to it. This reminded me of the first time I participated in MIT puzzle hunt in a team of 15+ more experienced participants. They tore through all the starter puzzles faster than I was able to make sense of them, and I was able to catch up only when they got to harder puzzles and the tempo slowed down.

Bottom line: as a small team, we were better off just refreshing the docs page and trying to make sense of what is being written there.

But this still left the million-dollar question: why are we doing this at all?. What is the end-goal?

Are we supposed to write a decoder for images like this (with more images incoming)?

Are we supposed to communicate with aliens somehow?

Are we supposed to write code in the alien language (using pictures) for the task that would be revealed soon?

When you registered your team, you were issued a "team key" and directed to a small GitHub repo that contained sample code in many languages that will establish communication with the server that organizers provided, send the key and check if server replied "OK". This seemed to suggest that we will be communicating with organizers somehow, but so far there were no hints on when, how, or why it would happen.

This was certainly unlike any ICFPC I saw before, and I certainly did not like it :)

At T+2.5h organizers posted this message: We're really amused by the great progress you're making with decoding the messages. We're monitoring the chat in Discord for your suggestions on the meaning of messages and names for unknown symbols appearing in these messages. We're updating the documentation accordingly. Keep going!

At the same time, we have more news from Pegovka Observatory! Our friend Ivan Zaitsev says that a new message which appears to be REALLY HUGE is being received right now. We don't really know if we'll be able to render this message as an image. In this case, we'll post this message as text. That is why it is very important that you give names to unknown symbols in the messages.

We'll make a new post when this REALLY HUGE message is ready.

Well, think clears things up ... not.

Will it be text? Will it be an image? Seems likely that it will be text. What are we going to do with it? What are we supposed to do meanwhile? I don't know about you, but I find working while following an active chat to be quite impossible - but once again, I found the chat to be the only source of _some_ clarity, so you had to keep an eye on it.

Chat was all over the place. "- Seems like language is lazy. - What are we doing? - Hi, I just joined - where is the task description? - #31 looks like syntax for lists - Yeah, we already know this - I don't know any Haskell, what is cons, car, and cdr? - When does the contest begin? - What is a church-encoded boolean?". The signal from this noise was slowly filtered into docs by organizers, and it looked like they were getting overwhelmed, despite four of them working on filtering chat:

xxx: Are suggestions from the chat no longer getting accepted by organizers? If not then I don't even know what we should be working on

yyy: At least it seems like quite some solutions which have been mentioned here multiple times already have not found their way into the docs, which makes it tough to read the last couple messages and also makes me wonder whether taking a walk in the sun now is a safe idea or things are about to start for real soon-ish?

Organizers: We are working. Right now 4 my teammates is merging it. And last message we are get great suggestions until 35 message. Is there any ideas about #36?

Thing is, re-reading the Discord history now I have this strange sense of duality: I still remember being utterly confused back then. But now, when alien pictures are no longer a mystery and I know the goal of the contest, a good deal of Discord messages make sense - yes, this guy is right, and this guy's suggestion was not bad either. Good job, chaps, both of you.

Now I can easily put myself in the organizers' shoes and see how Discord looked like "people are getting it! we are doing great!".

My teammate Alex and I meanwhile were mostly waiting for the REALLY HUGE message.

At T+3.5h organizers said: "FINALLY! We have finished to receive the HUGE MESSAGE and we're processing it now. So, we can try to send them something. What I should choose: the some big number or ( 0 )?"

People in the chat: "Send 0! Send (0)! Send 42! Send 1000! Don't send it! Let's discuss!"

Organizers, two minutes later: "Well, we are sending (0) then!" :)

Immediately after, this post went up: When Ivan Zaitsev read the suggestion to transmit something to the spacecraft again in regard to the message #36 in Discord, he was energized. We modulated a list of a single zero element for Ivan, and he transmitted that message with his antenna at Pegovka Observatory.

And… he got the response! This one: 110110000111011111100001001111110101000000.

When Ivan repeated the transmission after approximately 10 seconds, he received another response: 110110000111011111100001001111110100110000.

Neither Ivan, nor we have any idea about the meaning of these responses. That's why now we're going to create a proxy so any team is able to transmit something and get something in return.

Can't wait to share this proxy with you!

Did I mention already that you had to keep an eye out for updates in the chat or on twitter at all times? :)

At this point, I posted that messages obviously decode to the gliders from the Game of Life, but very few people rose to the bait :)


Shortly after, information about accessing the "proxy to radiotelescope" went up:
"We've added a few AlienApi methods to the API we've already prepared for the contest and glued them to the antenna at Pegovka Observatory. Hope it'll be working flawlessly.

All you need is the API key from your team profile.

Proxy was HTTP server that organizers ran, responding to POST requests. You could've POSTed "(0)" there, and it will reply with the long string of ones and zeroes, or you could send something else, and it will reply with "1101000", which was alien encoding for (0).

Alex and I decided to work on encoder/decoder for these numbers (at this point organizers already released enough information about encoding and decoding schemes for simple numbers and lists of them) to do SOMETHING.

It was still not clear what lightning round will be about. "Lightning round" is the first 24 hours of the contest that is usually restricted to a subset of the full task and has a separate set of prizes. This message on Discord got 29 likes and 1 dislike:

So hooray for a very involved background story and all, and I don't want to sound ungrateful, but I actually traveled to another country to meet my team members to do some coding together and while I understand that there is fun to be found in everybody decoding stuff together we are really uncertain since some hours now whether and when our expected experience of coding together and competing against others will start.

Is this the format of the lightning round and the conclusion will be that discord is very suitable for rapid prototyping?
Or are we about to get into the coding vs others part any moment now?

At T+4h there was still no HUGE MESSAGE to be had...

To be continued here (and it will get better, and I will rant less, I promise) This entry was originally posted at Please comment there using OpenID.
Tags: icfpc

Comments for this post were disabled by the author