Jam-Packed Fun and Games

Did I say “fun”? That was short for function calls. Which are fun too, admittedly. Blah, I always go to such lengths to come up with snappy yet justified post titles and end up achieving neither.

One more complimentary breakfast later:

This is it.

Google Code Jam World Finals.

[Google Code Jam 2015 name tag with my name and handle and country]

Let me take a moment to reflect. Seriously. I do not know how I made it this far this year. I guess I might be a top-500-ish competitive programmer globally, maybe even top-150-ish, but definitely not top-25-ish. And Log Set, the hard problem that got me through Round 3, doesn’t seem like it plays to my forte particularly either. It’s a bit mathy, but the math bits aren’t the hard part; I think it’s largely implementation, with one psychological hurdle where you have to realize that, because of how few distinct integers there are in S′, you can efficiently solve the subset-sum instances you need to produce the lexicographically earliest answer. I’m actually kind of impressed I got that. It seems like the sort of hurdle I usually get stuck on. How did this happen?

Maybe randomness. Maybe I was just particularly clear-minded during the round and wrote less buggy code than usual, because I had no expectation of making it whatsoever and so could look at the contest detachedly (until midway through the contest I accidentally noticed that my rank was under 20, and even then I tried very very hard not to think about it, and it kind of worked).

But it happened, and now I’m here. Time to roll.

In some emails much earlier in the Code Jam logistical process, Google had asked for “requests for changes and/or additions” to the software that would be installed on our competition computers, and I had sent them a long list:

Hi,
Here are some things I’d like if they were installed, in decreasing order of priority:

  1. The Vim plugin syntastic ( https://github.com/scrooloose/syntastic )
  2. a Haskell compiler (probably Haskell Platform 2014.2.0.0 https://www.haskell.org/platform/ even though it’s a year old)
  3. the Haskell package hdevtools ( https://hackage.haskell.org/package/hdevtools ) so that the above two may be integrated
  4. (I don’t have enough Linux experience to name a specific thing to install, but command-line utilities that are the equivalent of pbcopy and pbpaste on Mac OS X, which allow me to redirect text into or out of the clipboard from the command line easily)

Of course, this is my first Code Jam and I don’t know how reasonable these requests are. Any nontrivial subset would be appreciated.

Continue reading

Chi Banner

Okay, I think I’m figuring this out. When I make a filler post for the streak, it should be an unabashed filler post, so I can accumulate some of the blogging time I find each day to work on a serious post (and for doing the other important stuff I should be doing!) instead of wasting it right away.

Life. I’m programming something for Dad involving a parser using Jison, and one of the tasks involved stuffing a custom lexer into the parser. I was struggling to get my custom lexer to track locations properly. I thought this might be because I didn’t properly understand which components of which location went in which variables of the lexer, which seemed to be a plausible source of trouble since I had glanced at the sample code and it seemed to have a weird half-open range of columns and lines that I didn’t understand how to mimic in my code.

Then I looked more closely at the sample code.

this.yyloc = {
    first_column: 0,
    first_line: 1,
    last_line: 1,
    last_column: 0
};

In literary terms, this is called a chiasmus — the term comes from the shape of the Greek letter χ, chi — or possibly the more specific variant antimetabole. Both of these terms are courtesy of my TIL log, 2014/11/16. (Wow, it’s been a while.)

But why would you ever build an object like this?? Why???? This pattern of declarations doesn’t belong in code. It should be banned.

So, anyway, that wasn’t the issue; the issue turned out to be that neither my code nor the parser code made defensive copies of .yylloc (the l stands for “lookahead”), so my mutations leaked into the rest of the parser. Darn. It’s my fault, but I miss the functional paradigm.

(Bonus puzzle: as you might have suspected, the title and its incorporation into the narrative is quite forced. What is its significance?)

[IOI 2014 Part 2] One Line to Solve Them All

I started trying to sleep at 9 the night before the contest, tossed and turned in bed until 10, then fell asleep and got up at 3:35 in the morning. Blah. At that point, I went to the bathroom and applied some chapstick before trying to go back to sleep until 6. After breakfast, I grabbed a few minutes of sleep on the bus to the convention center where our contest would be, then slept on a sofa outside the actual contest hall alongside most of the rest of our team as we waited for a very long time until it was okay for us to enter. Competitions really mess with one’s sleep schedule.

Then, much too soon, we could enter. Day 1 of the contest was about to start.

The laptops were as yesterday, although they were protected with a white screensaver that indicated my name and ID as well as a countdown to the start of the contest. I was glad to see that my mousepad and all my writing utensils had survived without me. Somebody had the sense of humor to project an online stopwatch with an animated bomb fuse onto the screens to indicate the remaining time, which, once again, there was a lot of.

I conferred briefly with Paul (TZW (alphaveros (?))) about vim settings for a bit, but there were still fifteen minutes left or so. I idly stretched, practiced typing my .vimrc on an imaginary keyboard, and watched as the US dude two tables to my left unplugged his laptop’s mouse and rearranged absolutely everything on his table using the surface under his chair as swap space. (Well, that was how I mentally described it at the time, pending further revelations. (hint hint))

Then it began.

Continue reading

[IOI 2014 Part 0] Waiting

Yes, I know day 1 of the contest already ended and is probably a more interesting topic to blog about, but I finished writing this last night just before the internet was cut off to quarantine the contestants from the leaders, who received the problems and began translating them. I didn’t know about this until it was too late, which is why I’ve been waiting since yesterday to post this.

To provide a counterpoint to the last post, one of the many, many advantages of entering an international competition is that you get to meet a lot more people you already know, so there’s less time spent being socially awkward. While waiting for stuff to happen, aside from all the expected time spent with the Taiwan team, I also talked to, played games with, and otherwise entertained a whole lot of people I already knew, including my schoolmates (no less than fourteen of them were volunteers) and some of the college students who had shepherded us around during olympiad training.

Which is a good thing, too, because there was a lot of waiting.

First I waited for my teammates; my parents had decided to take me to the hotel (Fullon Shenkeng) directly, since I had a lot of stuff, and I had arrived early. This took about an hour, after which we had lunch. Then I waited for the hotel to give us our room cards, which took about five hours, after which we had dinner. Finally, at night, I waited for the Codeforces system tests. Very nerve-wracking. But I’m getting ahead of myself.

Advantage #2 of being the home team: you can talk to all of the organizers and volunteers fluently, so you can get them to help you more quickly. Although we waited for our room cards for an obscenely long time, I got the volunteers to replace my pinyin-name-card with a legitimate one that said “Brian” on it really quickly.

Unfortunately, after I talked to a few more people, it looks like they aren’t going to change my name in the database. So if anybody reading this chances to look at the IOI live ranking and is unable to find me, look for the first name “Po-En”.

Continue reading

#pyconapac2014

Late post. As usual.

It started with an online competition — write programs, solve problems, get points. I wouldn’t call the problems easy, but they weren’t hard either. So I solved all of them. To make it even less impressive, only about twenty people submitted anything at all.

But the result was just what it was: I ended up with a free ticket to PyCon APAC 2014.

I’d prefer a conference about a more functional programming language, but I’ll take what I get. Another adventure!

Continue reading

Rise from the Ashes

After the first stage of selection camp, I was very nervous because I was fifth place in a selection sequence that would finally result in a team of four.

I screwed myself over on the first mock test by committing to a bad implementation method on a problem that was hard to get points on. My method seemed simple, but the memory usage leaked out in a way that was confusing and hard to patch; unfortunately, I tried to patch it in increasingly desperate and convoluted ways rather than scrapping the method, and thus missed out on many of the points elsewhere.

During the second test I failed to read the last problem carefully and spent too much of my time on the second problem, once again missing out on a lot of relatively easy points. I had optimized and optimized and pushed my quadratic runtime down to linearithmic, which would allow me to get the points for the last subtask — or so I thought. But with 10 minutes left I had all but one testcase right, and after desperately rereading my code, I realized that I had a string comparison stuck in an inner loop that could make my runtime degenerate to quadratic if the input string had lots of the same digit. In order to have a solidly linearithmic algorithm, I would have to implement a suffix array. Ten minutes? I gave up. (The problem setters told me afterwards that hashing would have worked too; I didn’t think of that at all. Oops.) I spent the 10 minutes reading the last problem and still failed to read it carefully. So that did not go very well.

But, as the title probably gave away, during the third and fourth mock tests everything went much better than expected. 🙂

Continue reading

Adventures in Cabal Installations

First Google Code Jam!

The format of this competition, allowing us to run programs on our own machines, brought up a very interesting issue for me: what programming language should I be using? (I had had similar considerations for IPSC 2013, but GCJ’s problems are closer to the traditional ACM-ICPC style.)

The obvious choice is C++, the language I use for roughly every other competition, but its safety (or lack thereof) is not very appealing. I need speed, but not that much speed. Unfortunately I still haven’t gotten around to learning any other friendlier mid-level languages (on the list: D, Go, or Rust), so I have no close substitutes for C++ right now.

Python is certainly available for a reliable arbitrary-length integer type, if nothing else.

As for non-candidates, Java has BigInteger and memory safety, but all in all I decided the benefits are too minor and it’s too ugly without operator overloading. Scala is probably way too slow. So I don’t expect to be writing either language.

The only difficult choice I have to make is, of course, Haskell — which can be quite fast, even while it’s ridiculously type-safe and expressive and referentially transparent and easy to reason about, once you’ve:

  1. figured out how to do the problem
  2. scrapped step 1 and actually figured out how to do the problem functionally
  3. gotten the thing to compile

Even if I can handle step 1, step 2 is by no means a simple task, as my struggle to implement a mere Sieve of Eratosthenes efficiently shows. That is fun, but not at all intuitive; I am doubtful I can do this under contest conditions. It is extremely difficult to transfer my skills in learning how to implement, say, a segment tree or treap into this language.

But! Google links to the programming language breakdown for 2010 Qualification Round as an example, and much to my surprise, Haskell ranks somewhere between sixth and tenth place in popularity (depending on what you sort by), so there are functional superprogrammers who can presumably do something like this.

As it happens, I ended up implementing all four solutions to the qualification rounds in Haskell, because of the relaxed time limit and lack of any involved algorithms and data structures. I think it was worth it.
Continue reading