ICFPC 2013 posted on 13 Aug 2013 19:48
These are some of my thoughts on the just finished ICFPC 2013. Our team (i.e., @koppcapp, @lonlylocly and yours truly) got 638 points total, 116 in the lightning round, which places us somewhere around 110-115 place in the final rankings and god knows how low in the lightning round ones =) If you're interested in how we managed to get that low, please continue reading =)
For those of you who are lazy enough not to open the task description, here's a fast recap:
Given an input-output relation for a 64-bit vector transforming black box (and some additional constraints as well), you have to guess what's inside the black box in a given amount of time
Sounds simple enough? Well, in a way, it is. The first idea that comes to mind is…
One of the constraints is the size of the black box internals (its schema). If you know that, why not just burn your way through all possible schemas of a given size and be done with it? Exactly! With that in mind, we quickly created our first Bruteforcer that easily cracked schemas up to size 7…
Of course, you know what happened next. We expected that as well. Just as any other ICFPC problem, this one has exponential complexity and memory consumption. And it hits you like a truck.
All the classic tricks like eval memoization, schema caching, etc. combined allowed us to raise the size limit to 8. Pretty happy with that, we decided to call it a day and headed home, while our little baby was earning our first 116 points in the lightning round.
If you can't bruteforce your way out of a problem, you have to use the problem's structure to simplify it. Underlying our problem is a simple lambda calculus with a limited set of operations, which (luckily) have some nice properties:
- (or a b) == (or b a)
- (not (not a)) == (a)
- (not (or a b)) == (and (not a) (not b))
- (if0 0 a b) == (a)
Implementing some was easy, but most of them required some kind of pattern matching, and C++ is lacking hugely in that department. That, combined with @koppcapp's jetlag, stopped us from fully utilizing this option.
These optimizations upped the size limit to 9. Not good enough to solve everything, but we kinda hit a wall with the bruteforce itself and decided to switch problems. Solving TFold problems seemed the easiest — and easy it was.
TFold (i.e., top fold) is a problem with a nice little structure of:
(lambda (x) (fold x 0 (lambda (x y) bdy)))
From the bruteforce's POV, TFold problem of size N equals a regular problem of size (N - 4), and after snapping together a specialized TFoldBruteforcer, we scored additional 50+ points from TFolds of sizes up to 13. And called it a day. If not for…
After coming home and reading a note from the organizers about "low hanging fruit"1, yours truly decided to sacrifice problems of 25+ size and bruteforce the hell out of them, hoping that size limit 9 would be enough. But! some unneeded «sanity» checks that were left in the code completely wasted the idea and costed us around 100 points. A good example of why you should test your code before shipping, I guess… =)
On Sunday we decided to focus on bonus problems, while our fixed and optimized yet again Bruteforcer was slowly crunching through the rest of the regular problems. Bonus problems, like TFold ones, have a special structure of:
(lambda (x) (if0 (and cnd 1) tru fls)))
If Bonus has size 3N, then all of cnd, tru and fls have sizes close to N. And getting them is quite easy.
First, you have to find branch candidates — schemas that are similar enough to the problem, and by similar we mean «have the same input-output relation in more than X% cases» — the good old Bruteforcer can do that just fine.
Then, you find candidate pairs that completely cover the black box and try to find an input-splitting condition which selects the correct branch. After implementing a special Pruner, we tried it on a couple of training problems and succeeded. "Phew!" — we said and scheduled the new BonusBruteforcer to run right after the old Bruteforcer.
6 hours till the end, we've got 638 points, BonusBruteforcer starts working, and…
Another funky bug (more of a typo, really) found its way into the Pruner and made it generate way more candidate pairs than it should, exploding the search space and making every bonus problem time out. Unfortunately, I noticed that too late to make a difference (i.e., after the contest ended). I got the Least Valuable Coder award this year, that's for sure =)
All in all, our first Bruteforcer did all the work.
If we'd optimized it straight away (and had understood that small schemas can solve a lot of large problems), we could've scored much better in the lightning round.
If we'd had better testing, we'd have had less screwups and scored more points.
Hindsight is 20/20.
Having fun while hacking is awesome =)
What we didn't use (but considered using)
- Byte-based encoding for schemas (implemented coder/decoder, didn't get any noticeable improvement)
- Reduction-by-equivalence (to reduce search space)
- Iteratees (to make Bruteforcer nice and lazy)
- Data mining (to collect frequent subschemas)
- Bruteforce early and bruteforce a lot. It works. If it does not, it gives you ideas.
- Get together and stay together. Commute is horrible. Change of pace is terrible.
- Prep your bag of tricks early. Builds, VCS, testing should be sorted out before the contest starts.
- Stay focused on the contest 24/7. If you can't, someone else should.
Funny how I said the very same things in 2010. Hopefully, I'll remember to fix these next year =)
Thank you for reading through this pile of semi-organized thoughts, hope it didn't make ICFPC less appealing to you =)
That is all (c)
Comments: 6 : Rating: 0