Frozen Heart Plains : Blog

More gibberish wisdom posted on 23 Feb 2014 06:29

The greatest weapon against stress is our ability to choose one thought over the other.

The art of being wise is the art of knowing what to overlook.

(c) William James

Tags: blog philosophy quotes

Comments: 0 : Rating: 0

There comes a time... posted on 20 Feb 2014 18:06

…in your life when you have to choose to turn the page, write another book or simply close it. And this choice is never pretty.

Tags: blog philosophy quotes

Comments: 0 : Rating: 0

In a bar... posted on 17 Feb 2014 20:07

…it's inevitable that people will leave. That's the same with people we meet in life. No matter how difficult, you have to give it your all, or else you will regret it. And this regret will last a lifetime.

(c) Minoru Higashiyama, «Bartender», chapter 108

Tags: blog manga philosophy quotes

Comments: 0 : Rating: 0

Happy New Year 2014 (belated) posted on 03 Jan 2014 22:50

So, yet another (this time somewhat belated and chaotic) sitrep from yours truly on how year 2013 went for him. Here goes:

  • I fell in love. I'm serious. I fell completely and utterly in love. With fricking C++11. Java, you've been a great partner, but it's over now. I won't be coming back. Ever.
  • Saint-Petersburg hosted a bunch of AAA conferences like CAV and FSE. I visited only a couple of workshops (didn't have the time or the money for the main course), but enjoyed them immensely.
  • After mixing up a lot of things here and there, I'm really starting to feel old. Teaching stuff to inexperienced students does very little to help with this feeling =)
  • A bunch of friends and colleagues had their firstborns. Nothing to add here except for: Congratulations!
  • A lot of really-really awesome stuff happened at the very end of 2013. Won't be spoiling here, don't wanna jinx it =)

And, as usual, Happy New 2014, mates! May the Fun be with you! =)

Cheers!

Tags: blog news

Comments: 0 : Rating: 0

ICFPC 2013 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:

black-box.jpg

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)

Tags: blog icfpc news

Comments: 6 : Rating: 0

Happy New Year 2013 posted on 31 Dec 2012 19:46

What I did this year:

  • Had my second internship at MSR. Was fantastic. Met a bunch of awesome folks there, both old friends and new ones. Michael, Gena, Sveta - you're the best!
  • Attended my first ICSE. This is some sick stuff, mates. The sheer amount of brains gathered in one place is staggering. Deals quite a blow to your self-esteem as well.
  • Tried out C++11. First time using C++ as a main language in a serious project. Variadic template magic may and will fry you. Other than that, it went better than I expected.
  • Reconnected with a couple of old friends. It's amazing how that can just happen out of thin air when you least expect it. But it happened, and I'm very happy for that.
  • Missed yet another two of my friend's weddings. Why doesn't anyone like to have a winter wedding for a change, huh?
  • Did a talk about Scala at ADD 2012. Went horrible from the presentation point of view, but was very refreshing non the less. Note to self — do practice a little bit more…

I'm positive I missed a lot of other things, but that's not the point.

The point is — Happy New Year, mates! May the new 2013 bring you even more stuff to do, places to visit and fun to have!

Cheers!

Tags: blog news

Comments: 0 : Rating: 0

marat-akh.in posted on 24 Jun 2012 06:00

Just a small (and kinda useless) update - on some strange whim decided to buy myself a new domain. And did it - this blog (or whatever) is now accessible under marat-akh.in. Cheers!

Tags: blog news

Comments: 0 : Rating: 0

Life Update - MSR Again posted on 15 May 2012 07:13

Yup, that's right, mates, I got accepted to MSR for an internship. Again. And I started here at Redmond. Today. Woot-woot!

This being my second time here gave me a nice edge compared to all the first-time interns. Was really nice to know how everything works and what you should and should not do right from the start =)

But the project ideas my team has are … very challenging, to say the least. The possible impact is quite big as well, and that's good. Makes you actually wanna do stuff and all =)

I won't promise you to do regular updates, but will try to do so. Cheers!

PS: Weather here in Seattle area is fantastic at the moment. Hope it stays that way till August =)

Tags: blog msr redmond

Comments: 0 : Rating: 0

ADD 2012 posted on 12 May 2012 13:30

Hey mates, just finished my talk about Scala and Java EE at ADD 2012. Loved the discussion very much, was a very enjoyable conversation. Thank you all for coming (if you're reading this).

And if someone missed the talk and wants to fix it, here are the slides.

UPD: Here's video of the talk itself. Feel free to bash on it:

I personally think the talk was horrible, what about you? =)

UPD2: Комментации на русском приветствуются! (добавлено по просьбе анонима)

Tags: blog news

Comments: 0 : Rating: 0

Happy New Year 2012 posted on 31 Dec 2011 20:19

OK, so without any ado, Happy New Year, mates!

This year's been really intense and packed with both interesting and … not so interesting stuff. Huge projects done, crazy conferences visited, MSR internship finished, new languages learned, some awards won and many-many more things happened to me. I didn't have a lot of time to reflect on everything and … I like it. Makes you feel alive and kicking =)

I want the 2012 to be even more interesting and intense. And I wish the same to you, mates.

Happy New Year 2012! Kanpai!

Tags: blog news

Comments: 1 : Rating: 0

page 1 of 6123456next »

Facebook

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License