Here’s a short report on how our Team spent 72 hours last weekend (August 7–10). We were participating in the annual ICFP Programming Contest (if you don’t know anything about it — Wikipedia will help you out).
There were a lot of things we’ve already noted on our published solution at Github, but there are a few things that we still need to tell you about!
Preparation
This year we were prepared for this competition. At least, we called it “prepared”. We almost decided what language we would use this year, prepared the project base structure with Scala, Java and Kotlin support. As we were preparing, there were 6 of us who had decided to take part in the competition this year. Since each teammate had a preferred language, we decided to write this year’s solution in Scala, so everyone (or definitely at least one of us) took a look at an interactive Scala Tutorial and had some fun there.
We decided to use Slack for the communication channel and added a few integrations there — news and tweets from everyone who posted about the ICFP contest were automatically transferred to our #news channel in Slack. Also, we created an application at Parse.com with a background job that looks for icfpc repositories on Github every 15 minutes, and lets us know about them (This one didn’t work, because someone forgot to schedule this job).
The Team on Day One
This should have happened :) On Day One only two of us were able to start on time :) Plus, there was another guy, who joined us just before the contest. And then, as soon as we got the task, which was about something like hexagonal Tetris with some additional fun interesting stuff, we started to implement our awesome solution in Scala.
Now we know that watching tutorials like “tryscala” and installing IDEA IDE is not enough to start writing on Scala. Of course, we had had functional experience before, but trying the new language, or rather the new ecosystem, created unexpected challenges. That’s not the optimal way to go when you have only 72 hours.
Switching Language
Maybe it wasn’t a good idea, but at least, we tried. During three last years we were programming in Java, and this year we decided to break this tradition. After four hours of struggling with Scala, we capitulated. Even after some tutorials, we weren’t able to do a real-world task correctly. If only we’d had three months instead of three days!
So, after spending four hours with Scala, we then had JSON parser, which was able to parse task input, and a Congruent Linear Generator, which also was mentioned in the task (what a speed!).
At the end of the working day, our team had grown to five people and we started to choose the language (not again!). At that moment, two of us were trying to write the solution in Objective-C, two of us were guys with rich functional-language experience, and the fifth one was from the world of Java.
We decided that in order to be able to have different solutions, we need to create the Core, which can be used by different languages and answer on questions like “if I do X, what it will do with game state?”.
It’s hard to imagine that the team that originally prepared for JVM languages and maybe Objective-C decided to use Node.js.
How Javascript Infiltrated
A few hours after the contest started…
(T+3) One of the team members implemented (stole) a simple hex map visualization (using JS of course). And what’s the easiest way to set up a simple HTTP server? Node.js, of course!
(T+20) Simple visualization expanded to full-blown-bell-n-whistles-kinda-IDE for contest.
(T+24) Oh my, so many dependencies on Javascript… During the post-lightning-round call we realized that JS is the common denominator language for the whole team. And so it goes.
— Whaaat? Where did it come from? Why?
— Don’t know! We just decided to use it.
— OMG, God Bless you!
So, Javascript! :)
Working Hard
Javascript isn’t a hard language, so pretty much everyone was able to write some constructions and we added Mocha tests to our solutions. In previous years we were actively using TDD to create core parts of our solutions, and it helped a lot. This year we decided to use tests too. From the start, you think that this is a waste of time, but spending some time on tests on the first day will help you a lot on the third day when you start to optimize things.
Linear Congruential Generator in JavaScript
At the moment I started to implement LCG in Javascript, we already had two working solutions — one in Scala and the other in Objective-C. So from that point,it’s really easy to implement another one in JavaScript, right?
Wrong! Wrong! Wrong!
JavaScript doesn’t support 64-bit integers! :(
And I spent the next three hours that night trying to implement it.
Finally, I was able to do it by checking each step of the already implemented algorithm and algorithm in JS. Only after that I realized that with a maximum 53-bit precision, which JS gives us, I would not be able to create LCG correctly. But thanks to the Open Source, there’s a Library which allows you to work with “Long”(64 bit) types.
Idea
Our idea was pretty simple: we needed a visualizer to see the map and understand what was going on, an “estimator” to select targets for each unit, and an algorithm to move to those targets. Sounds simple. Heh.
Of course, we implemented A*.
We were implementing it again and again during almost every #icfpc. That’s the way it goes, I guess.
And this year’s A* resulted in some funny situations. Like: “Ohhh, we’ve changed the structure of the map, do you need it?”. And, “Ouch, four hours of debugging to find the missing RETURN statement”. Fun yeah!
Infinity Loops
Our program was pretty straightforward.
Take the map (aka “problem”). Each map had a set of units (hex figures) that appeared on the top of the map and moved to the bottom. Each map may have contained more than one sequence of units (so the map was the same, but figures appeared in a different order). For every set of units (aka “seed”) our algo started solving the problem. The algo stopped working when it found a path for all units from a sequence or when it couldn’t find more moves.
Magic phrases
The solution was a sequence of commands (move left, right, down-left, down-right, rotate clockwise, rotate counterclockwise), that was written as letters. The tricky thing was that one command can be encoded as any one of six symbols (f.e. move to left/east could be encoded as ‘b’ or as ‘c’ or even as ‘e’). So the real result was a looooong line of symbols like ‘alalalalbgdhaldpa’.
But there are ‘power phrases’ that you can use in the result line. These phrases are initially hidden and you need to find and use it. Running through contest channel’s tweets and looking for some weird words was fun, they could even appear on the board as a sequence of falling down hexagons in shape of letters. Go detectives! Magic words dramatically increase your scores. We were quite good in finding phrases, but our algo wasn’t optimized to use them. That’s one of the reasons why we have so little scores.
We’ve built post-processing function that takes letters line and tries to find sequences that could be replaced by magic phrases. Sometimes we had 1–2 magic words from such post-processing, but no more.
HAL 9000
— Don’t know how to write a cool algorithm that solves your problem?
— Need at least something instead of nothing?
— Want to spend time having fun?
Write a random solution generator! Yey! We added some randomness in almost every one of our #icfpc solutions. No, really.
While one guy was working on A* and the estimator, others were creating a random solution algorithm. Well, it wasn’t really random, but it decided where to move a unit using simple criteria. For example: don’t rotate one-cell figures, because rotation is quite useless and harmful; according to the rules units shouldn’t appear in the same place twice. Also, don’t move to the west if the previous move was to the east because of that restriction. I can’t say that random is a great solution, but it generated some points for us.
When you have random inside your code, it means that the solutions may change every time you calculate. We built a tiny “rendering farm”. The office was empty during the weekend so we took some macs and made them solving maps. Every solution that was better than the previous one was posted to the server and saved (automatically, of course).
We aren’t good at those things.
Well, suddenly it appeared that hexagon geometry is quite tricky, but we found an awesome site http://www.redblobgames.com/grids/hexagons/ that solved our confusion about rotating hexagons. However, even after looking at nice charts on that site, we still spent some time on debugging the simple behaviour of our hexagons.
Results
Hello from LoserWill. We took 122nd place out of over 300 teams. Bad-bad-bad result. Still, there was a lot of adrenaline, a lot of updates in the last hour, and a lot of fun. :)
Retro
- The Team. Handling things in a dynamic team is always complicated. It was hard for many of us to allocate half of Friday (the contest started at 3 PM in our timezone), the whole weekend and half of Monday. That’s why team members were constantly coming and going during the contest.
- Tests. You should write tests when you implement specification. It’s way better to use tests than debugging.
- Decide which language to choose before starting the contest. It’s probably easier to share some thoughts between two independent teams, than to try to force everyone to work with some new language.
- In case you decide to work as one team, give people who will participate at least 80% of the time to decide which language to use.
- Learn some algorithms and when to use them, and try to implement them from time to time (it will help you!). Because of a lack of knowledge of those, we were inventing our ideas instead of using some good, well-known solutions.
- It was a good thing to try new technologies and new tools. We’ve tried WebStorm on our solution, and since we’re already using AppCode and Intellij IDEA on our projects, we were able to switch fast to WebStorm.
- We’ve used Trello to share tasks among project members and it’s a good thing, but we didn’t use Trello as one source of truth — this is a bad thing.
P.S.
Our team: @Kilew, @vixentael, Fix, @Alex Voronov, @Lampapos, Silver. Moral support: @bexcite, @vandalko.
P.P.S.
You can read our previous year’s report.
If you like the post, please recommend it.
