Posted on 13 Aug 2013 19:48
Intro
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 =)
Day I
Task
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…
Bruteforce
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.
Day II
Structure
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…
Screwup
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… =)
Day III
Bonus problems
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…
Screwup
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 =)
Results
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)
Take-outs
- 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 =)
Outro
Thank you for reading through this pile of semi-organized thoughts, hope it didn't make ICFPC less appealing to you =)
And, of course, a huge round of applause to my teammates @koppcapp and @lonlylocly. They are awesome =)
That is all (c)
Rate this entry:
Found a bug?
Thanks for the writeup! We actually had a really similar experience. We started with a simple bruteforce and gradually tried to improve it making it more clever. Unfortunately in the end we got lost so badly and the time was running low that we had to use a very early version of the bruteforce with only minor improvements (iterativeDFS, commutative redundancy elimination). This however worked surprisingly well for all except the bonus problems. We were able to solve 80% despite an extremely tight time limit - we stopped each problem if we couldn't solve it in 10 seconds. Unfortunately we also didn't have the time to write a proper threaded scheduling - naive parallel work would have just lead to massive request throttling by the server.
We also couldn't quite finish our adaption to the bonus problem. In the end I think we would have had a great score if we only focused on the parallel implementation, started the solver early and work out the bonus problem. Instead we tried to chase the perfect algorithm that doesn't fail at a given size.
I also found it really surprising how much fun we had, considering the boring task. I must really say that I was disappointed by MSRE despite not really having high hopes. Seriously how can you come up with "try to guess a function" after "Dig through a sand stone computer", "Rescue an Alien by hacking DNA", .. "Play a functional card game", "Dig lambdas in a mine".
Hey, thanks for reading! Glad my post was of any use to someone out there =)
Fantastic results, mate, simply fantastic! What PL did you use though? Eager languages tend to complicate a lot of issues =)
PS: I didn't like the task, but that's because I prefer ICFPCs where you submit solvers, not solutions. Makes it a lot more fair imho.
We used C++(11). I think it's not too bad for this particular problem. You could probably use lazy languages very well here, but then you have to be very fluent in that language and understand it well enough to specify the algorithm in a way that the language can solve efficiently.
The funny thing is that we did have some serious computing power at our disposal, but didn't use it because we spent all the time on our futile effort to improve the algorithm. So in the end the solver ran almost exclusively on a 5 yr old laptop. I am not sure how much we could have achieved with throwing CPUs at it. I assume the complexity growth is pretty high if the "actual size" increses, so there may be only a small band of problems that can be solved with more CPU. Also if you look at the unofficial stats: labs. skbkontur. ru/icfpc2013/Stats , the high ranking teams still have lots of unsolved 'normal' problems, but get their points from the bonus problems.
What language did you use? Bruteforcers in Haskell and D and some other langs easily cracked problems of size 12-13. I don't understand how you manage to hit a wall at 7-8.
We used C++ (it is subtly mentioned in the write-up), and size limit 7 applies only to the very first super-naive Bruteforcer. Main problems we encountered when raising it were:
Basically, all our Bruteforcers explored all possible schemas (no reduction-by-equivalence) at once (no laziness). After carefully exploring other optimizations, we raised the size limit to 9 for complete search (all possible schema components) and 11-12 for bounded search (schema components constrained by the problem).
Hope that helps to clear things up =)
Ah, yes, if you don't limit search space by problem constraints (at least the set of ops) then it becomes huge earlier.