This is that time of the year once again, when coders gather to take part in some good programming fun, the Facebook Hacker Cup. It’s only the first qualifier round, and while I hoped it will go better than last year, well, it didn’t. Not that I’m really surprised.
I needed one right to qualify, but I wish I haven't messed up the easiest problem.
After that 72 hours results are in, as is the explanation and example source code for the solutions. It’s good that the example solutions are in Python, I might even learn a trick or too.
Alphabet Soup
The problem setting is easy enough. Funny thought that no matter how many times I counted the letters in the world “HACKERCUP”, I didn’t notice that there are two Cs. I mean, duh! As usual, the example input set was designed such that it wouldn’t trigger the bug of miscounted Cs. This carelessness is one thing that comes up quite often in my programming, probably should take better care of it.
Billboards
This problem actually worked, which means I’m in Round 2, but I guess it can be improved quite a bit, make it more efficient or come up with some heuristics. Or maybe it doesn’t matter much.
Auction
This problem was on a whole different level. While the first two had apparently more than 5000 and 3000 correct solutions respectively, this had only 28… I was thinking about it for quite a while, drawing diagrams, trying to use my intuition and imagination to see where the trick is since the naive O(N^2) algorithm is definitely unusable on the N~10^18 level. On the other hand, I might have tricked myself. Reading the solution the trick was completely different than I expected – I thought there’s some weakness in the random number generator that can be used to express everything analytically, while it is actually just about keeping good track of things. There’s no fancy algorithm to break this problem, just pure logical thinking. Now that’ll teach me as well…
Looking out
This of course means that I have a lot more to learn, and most likely I’m not cut out to be a Facebook caliber hacker. That’s no problem, but good to know. Whenever I think about it, the picture that comes to me is the hacking competition scene from The Social Network, where they hire their first employee. I’d love to be in the middle of such brainfest, such intense creation, such inspired learning from one another while having an an amazing time. Well, fortunately there are other places where I can have that experience, like the Startup Bus. And maybe, I can also set out to create that environment over here in Taiwan.
But first, let’s get ready for round 2, should make that one better.
I keep remembering that good ideas start from doing something fun, instead of doing something easy. About a month and a half ago I was reading the Google Doc that I have with some friends, listing ideas about “Changing the World”. It’s all the things that should/could be better in the world and “I wish….” it would be some way.
In the list of a hundred or so I’ve seen one entry that was wishing for a way to see changes to our shared documents in an easier way than going back to the Docs home page and seeing if something has happened. Been thinking that that would be something I myself would totally use. Couldn’t find anything like that yet, but I had sometime in my hand to experiment, so WatchDoc was born….
The interface of WatchDoc with lots of testing documents, emails blurred out just in case.
Getting it done
I haven’t written a Chrome Extension before, but seemed like such a suitable fit, and been looking for a project that I can try myself with. They are practically open source (since you can look into any one of them regardless of where you installed them from) and only using standard web tech, just like making a website (HTML + CSS + JavaScript). Indeed, all Chrome extension are some web-pages displayed in a special way, some javascript running in the background and/or javascript modifying the page you are on. Very neat, I would say…
Since I didn’t know where to start, I tried to find an extension that I can take apart and learn from. Fortunately, there was one, straight from Google, called YouTube Feed. So the first part of the project was slowly gutting that one out and replacing parts until I get something working that I wanted. It is easier to say than do, because the feed reader has somewhat different requirement than the code I had in mind, but at least close enough that most of the internal structure I could keep.
Some notes about the journey:
Authentication: oAuth can be pretty troublesome, but in the end it was easier this time than I expected from past experience. Maybe because YouTube Feed was written reasonably well already
Icons: Wanted to take the icons for the different document types from Google Docs itself. Took some time, but using the developer tools (inspect element) in Chrome I could finally find the links and download them.
More icons: Wanted to use the icons as a CSS image sprite just like the original extension, but couldn’t find some good program to combine PNG files into a single image. In the end wrote a quick Python script to do just that.
Extension icon: For the extension icon I used Google Docs’ own little icon (I think it’s kinda fair to use, especially now that they have changed it, it’s v9 of their icon theme compared to v7 at the time of my programming) and also on a free icon site I had found a matching hi-def icon. I just wish I could find it again for proper attribution, that still nags me.
Buggy notification: Some parts of the extension writing was pretty annoying. For example I wanted to get desktop notification work just the way it does in Gmail. I don’t know how do they do the auto-hiding, but I’m pretty sure not from the standard simple desktop notification type, because that I simply make to hide itself after a certain time. Instead I had to make it the more difficult way of using a HTML page to define content and then internal JavaScript to close it. Took a while to realize that I have to pass my parameters (the data that I wanted to display) as query parameters, but now it works pretty well.
Buggy libraries: this is always fun to have because have to find to work around it or fix it. This time it was a jQuery URL Parsing library that crapped out on corner cases that the developer didn’t thought of but I fortunately run into. Took a while, but fixed it up, let’s see if upstream will incorporate it.
Optimization: it’s good to have things working first and then have them work well. For example originally I re-read the user’s whole feed, now it can read the part of the update feed that can contain relevant information, so I can have fewer requests to the server, and the updates come in several seconds quicker.
Release
After some work I thought it’s better to release first and ask questions later. So I registered on the Chrome Web Store (registration is $5 on time fee to get rid of spammers). Not much hustle, in about 20 minutes everything is done and now you can find WatchDoc in the Chrome Web Store. You can also find the source on GitHub.
The Chrome Web Store seems to have some strange policies, though, eg. didn’t let me update if I didn’t have the right shapes of preview pictures, and sometimes they only told me halfway into the submission of the new release, and I had to scramble to make some test documents and nice screenshots of the right aspect ratio so I can finish the submission. Nevertheless it is pretty easy to handle and useful too.
One beef I have is that I don’t have any way to reply to reviews. Much more people post negative stuff than positive and once I fixed something there’s no way to get in touch with the reviewers to ask for re-evaluation. This makes a very one-sided experience.
It is good – though addictive – to watch the number of +1s grow, as well as installs and users. The site must have some way to check people’s installations because the total number of users did decrease after the initial increase (the high water mark somewhat above 1500, now a bit below 1400). I guess I would need to improve the quality a bit more, and maybe there are not that many people sharing Google Docs with others than I have thought. :) Anyway, I think this is much more than how many people used any other software/site I made, so no ground to complain.
Post-release
The release was picked up surprisingly quickly by other websites, I think there are some automatic ones monitoring the latest submissions to the Web Store, and others take the news from them.
WatchDoc Google Analytics as of date, some review of it in the text, click to enlarge (in new window)
Here’s my Google Analytics since the release. The big spikes in the beginning go up to about 500 visit / day (tiny, but much more I have ever had), and are mostly due to Lifehacker. After that I have basically just a trickle of visitors (about 20 / day), with a little spike recently that is direct traffic, I wonder where from….
Some sites that reviewed WatchDoc (the ones with the highest referral counts)
Addictive Tips, these guys seem to be monitoring the Web Store submissions and react pretty quickly, basically within hours of submission without me advertising it anywhere
I got up a support site on GetSatisfaction as well to be able to have a conversation with those who are persistent enough and submit some feedback regarding bugs. Used it a couple of times, and it’s quite practical. I finally learn how to do product support, which doesn’t mean it became easier. Still surprisingly maddening to debug a problem until it hits me as well by chance so I can check it locally. Got to figure out some superior remote debug system. At this point it seems to work well enough for about 1400 people, but the fact that I have lost about 200 shows that I still have a lot of problems to fix.
Into the future
It was a fun project to work on and it does most of the things I wanted to, but it’s dead ugly. I either find a designer and fix it, or just leave it like this because it doesn’t matter much…
I might work on it a bit more, especially bugfixes, though it would be better to have some ideas what is missing. Everything I can think of would complicate the user experience and that’s not my plan: document preview, ignore updates of certain documents, multiple-logins,…. What else?
Guess it is more likely that soon I will start to work on something else, let me know if you have something fun you wish to see :)
It is very long overdue, since I was looking at Javascript like…. 14 years now? But never really spent time to understand it because I never needed it really. I’m old enough to remember that when I started to browse the web, every time there was a page using Javascript, people’s sentiment was “oh, no, that’s going to be very slow, I don’t even want to check this site anymore”. Pretty much like it was/is with Flash later on.
Compare this to now, how 100% static sites are practically disappeared, and no web developer worth their salt should skip on learning it. I’m glad that browsers spent a lot of time improving performance and that so many interesting projects came out of it.
My impression of the current state of the art is that using HTML + CSS + Javascript now it is easier than ever to make good front-ends for programs. I’m mostly a command-line guy (and that’s pretty easy with many scripting languages as well as Python that I use), but I cannot deny that I’m the minority. Still, when i need convenience, I can even imagine people creating local (meaning not internet-enabled) software with those things.
Since more and more people had similar idea and started to work on it, there are plenty of projects that make this even easier, like jQuery and all its plugins. I don’t think people need a lot of introduction and already can do a lot of things easier using that. One drawback is that many things could be just as easily done in pure Javascript but people quite often don’t know that. I certainly have to learn a lot more.
In this month I was reading a few books and sites that people recommended on Hacker News, as well as I used it to do a few actual projects. Now that’s a change compared to the previous Language of the Month columns.
Projects
WatchDoc: a Chrome extension that notifies you when your shared documents on Google Docs change. Chrome extensions are merely HTML+CSS+JS code, so it was a perfect way to try a few things. (Will write it up here later) (wrote up here).
NowJS real time games hackathon: NowJS is a real-time communication plugin for NodeJS, the JS server. I wanted to make a game for this hackathon, but run out of time. Spent some time working with it, and it’s actually pretty awesome when I started to understand it, I’m do want to finish the game at a later time (it’s a multiplayer trivia game) . (Will write it up here later)
Venus & Mars: a little afternoon project using Facebook to help my friend’s research assignment at her university. Listing people’s status updates separated by gender. It looks awfully ugly, because I just wanted to make it work, but for the fun of it it’s NodeJS so good to practice my JS-foo. (Will write it up here later)
Impressions
I definitely going to learn more of it, because now that I start to understand I quite like it, and I cannot imagine it going away anytime soon. Now that it is just a matter of seconds to set up a project on the web (really, on Heroku, Appengine, dotCloud are all one click away) there’s no good excuse not to do that.
Good
JSON, ’nuff said. That’s just such a good data format that is both human and machine readable. Seem to be pretty much the
No problem (it seems) with Unicode and international characters. Though I think it uses UTF-16 while many other code is using UTF-8, not sure if that makes any difference.
Feels quite light and flexible (from the language point of view, not necessarily the resources needed)
Since the source of websites is necessarily open, it is possible to learn from others’ examples much easier than otherwise.
Bad
Feels like it has a lot of baggage from it’s long(ish) and torrid life, which makes it feel a bit inconsistent. E.g. the first day of the month is 1, but the first month (January) is 0.
People generally seem to write pretty bad Javascript code. Because it’s so easy everyone can make some useful project, but they are full of bugs. Fortunately it’s Open Source, so I can try to figure it out, and I did find a handful of upstream bugs. But the stress…. huh…
Ugly
Formatting of JS code can be pretty unreadable (especially comparing with Python where formatting is not optional). It is made more difficult when I’m editing JS within a HTML file, since Emacs cannot handle that well.
Up until quite recently there weren’t any really good tools to troubleshoot things. Fortunately there’s Chrome and it’s Javascript console, and Firebug for Firefox. There are still some mysterious errors and the debugging has to be planned well ahead.
There are many things that are straightforward but require a lot of typing. Fortunately projects like jQuery are trying to fix that, but still there’s a long way to go.
Just like in Lua, for keys in dictionaries the quotation marks are not required and they are still understood as strings. These kind of magic can be convenient but there are occasions when confusing.
Links
Books
Javascript: The Definitive Guide – how to do things in browser, very modern, even jQuery, teaches some strange practices like single line non {} functions and missing semicolons (for many pages!)
If something, then this is a belated post. Prolog was the language of July and now it’s September. Anyway, before I completely fail, let’s just wrap it up and go on the next language with this one month hiatus in August.
I really enjoyed the language and one month is indeed barely enough to start doing something useful. So I have to come back to it again and maybe keep reading about it in the meantime. It’s actually quite interesting to try to figure out Prolog code on paper, without actually running something. I think one of the books I was reading had plenty of exercises like this: without running the code, can you guess what is it doing? Needless to say, there were plenty of tricky bits/
From the comments
During two months, some additional resources did show up. A dear commenter on the previous post recommended me the following book: Richard O’Keefe: The Craft of Prolog. I got about a third, maybe halfway through it and it’s interesting, written long time ago in a style that since gone out of fashion, unfortunately. It’s a programming book that is fun to read and one can see that the author is very knowledgeable. Some aspects of the book didn’t age very well, though. The author keeps comparing Prolog to other languages – many of them are not very widely available either. Also, some of the language features are specific to his version of Prolog, that wasn’t the same one I was using. Would recommend, though!
This last part, the different implementations of the same language, can be a real problem. Of the three compilers available for me, all of them had specific strengths and weaknesses. Guess they are converging, but not quite yet. So far I was mostly using SWI Prolog, but this might change in the future.
The said commenter also recommended a cross-compiler, doing Prolog-to-C magic, for portability and other goodness. Can grab it from here: http://ftp.shaw.ca/irvinsh/prolog.tar.gz I haven’t had time to try it yet, but once I have, I’ll do a comparison.
This latter one has a Hungarian author so I’m even more intrigued, we used to have great computer scientists (John von Neumann / Neumann János, anyone?), so I hope we keep up that tradition. (Oh, yeah, and had great physicists as well, maybe I can do more on that front later).
I was only skimmed them a little bit, but looks like these will be good addition for my “programming for fun and efficiency” library.
Will update the original LotM:Prolog page with these links as well. Now onto September’s Language, fortunately I have idea what I want to learn for the next ~3.5 weeks. October will be something Artificial Intelligence related since I signed up for the AI-class.
It is again a very different choice, logic programming. Been playing with it for the last two weeks or so, and it really makes me think differently about programming and programs. Logic and complex thinking was always a favorite past-time of me (e.g. solving puzzles and such), but only now I realized that I do have a lot to practice in this area.
Prolog is also one of the older languages (feels like a “classmate” of Lisp and Fortran) so it was the first language in the series where I could actually go to a library, take out some books to learn it, and that book wasn’t hopelessly out of date (try to do the same thing with Python or Ruby…). Since these books were also written by academics and not necessarily computer scientists, their whole approach is different, in a way more curious, though probably less practical.
In the end, I think what I would like to gain is a tool that I can use to attack problems that are intractable or at least very difficult in other languages.
Start
One of the first thing I found hard to figure out was how to actually run a program. So in a nutshell: even if most of the interaction is within an interpreter-like environment, all the basics have to be prepared in a file and loaded.
E.g. I prepare a file like this (based on Ender’s Game), call it ender.pl:
Then starting Prolog I can load the file with the [‘ender.pl’]. form, and ask questions like who is Ender’s sister? Who are Theresa’s kids? Who are Peter’s siblings?
