Google Code Jam and Competitive Programming

Back in 2004, I signed up for the Google Code Jam for the first time. Unfortunately I didn’t make it past the qualifying round.

I was a bit luckier in 2008 and 2010, making it to round 2 both times. In fact in 2008 as I recall I was one of only two participants from the Philippines who made it to round 2, which allowed me to jokingly brag about being the #2 programmer in the country.

I registered again a few times after that, and tried again last year (2016), where I only made it to round 1.

I’m no stranger to programming competitions, although the GCJ was the only one I’ve ever really participated in. Back in college, one of my friends usually joined such competitions, and I had a good time going over some of the problems with him.

Programming competitions don’t usually reflect the kind of programming done in most real-world jobs (although it might be interesting to use competitive programming problems in whiteboard interviews and see what happens). They focus on pushing the boundaries of the programmers talents in problem solving. You also need to be fairly familiar with algorithmic approaches to searching, sorting, and so on. Having a decent background in math also helps a lot.

The Google Code Jam in particular focuses on scaling up your code to handle very large amounts of data – well past the integer limit sometimes. Each question usually has a small and a large input. For the large inputs, you only have a short amount of time (I think it was 5 minutes?) to submit the output. Presumably you wrote and tested your code before starting the timer, so the short time is really only for your code’s execution. You can afford to be inefficient or maybe even brute force your way through the small input, but if you want to solve the large inputs on time you have to be able to optimize your approach.

When I first signed up, I dreamed of winning the entire thing (and of course being able to brag about being the best programmer in the world). But realistically, a lot of the people joining these competitions are “pros” more or less, so the chance of a “casual” like me winning are not that high. They are “pros” not in the sense that they do it for a living, but more of they do a lot of these competitions and regularly practice for them. Websites like TopCoder provide such competitions regularly for those who are interested. Also, I feel like I am very old and rusty, having worked too long in web development stuff where my focus is usually on a different kind of problem.

Still, I think it’s a good idea for programmers of all skill levels to give it a try, just to see where you are at. Who knows, you might even make it all the way! The next Google Code Jam starts soon – the qualification round is on Apr 7. I signed up, although I’m unsure if I will have the time this year even if I advance, due to scheduling problems. But a man can still dream, right? Who knows, maybe I’ll see some of you there too in the final round!

Scary Movies and Games

I’m not a fan of scary movies. I don’t appreciate the idea of paying money to get surprised by jump scares or whatever.

Back when I was a kid I remember my dad watching a Betamax copy of The Gate back home and me and my younger brother were watching with him and the movie seriously creeped me out. There was this one scene where a demonic eye manifested on the lead kid’s palm and that scene stuck with me for a while. (Maybe some latent form of trypophobia – don’t google it.)

Slasher movies I find a bit more acceptable – I watched a few of them in the 90s like Scream and I Know What You Did Last Summer. But the really creepy stuff like The Ring and similar films I’m not particularly interested in.

For scary video games, we played a few of them back on the PC when we were young. The most memorable would definitely be Waxworks, a kind of point-and-click with first-person grid-exploration horror game. I remember my brother and I would play it late at night while the folks were out. There was one time we had to stop because we had been surprised at the sudden appearance of some bad guy in the pyramid stage. We had to turn off the PC and run out to the sari-sari store so that we had some people to talk to. We eventually managed to finish this game, but I think after that part we refrained from playing too late in the night. LOL.

I also played the original jump scare game, Alone in the Dark although I never got into the succeeding series like Resident Evil. These days I don’t bother with scary games anymore. Sometimes I consider playing stuff like Amnesia, but I’m sure even if I’m a grown-up I’d still get creeped out by some of the stuff and that’s not really how I like to be entertained.

 

 

Fake Devs and Whiteboard Interviews

Recently, a developer needed to undergo a tech interview at US immigration:

This may surprise some people I’ve worked with, but I didn’t have formal computer science training in school. I’m not actually a computer science major. Yet I’ve worked as a software developer for more than a decade now. Literally zero times have I needed to write a sorting function or balance a BST.

I have a rudimentary understanding of some sorting algorithms (mostly just bubble sort and selection sort), and I have some idea of how to balance a BST. And if I needed to implement any of those I could probably whip something up after a few tries. (Something buggy and/or inefficient probably.) If I had to interview at a company that used one of these whiteboard interviews, there’s a good chance I wouldn’t pass.

For maybe 90% (or even as high as 99%) of modern-day programming work, it simply isn’t needed to know these things by heart. Those skills are more necessary if you’re doing low level things like writing an OS or a graphics driver or such. For everyday web development or Java or Rails or whatever, it’s an indulgence. And even for those instances that you need them, well, the internet is right there.

I’m not a fan of the idea that not knowing data structures and algorithms means you aren’t a real software developer. I have a couple of developer friends who jokingly refer to themselves as “fake devs”. It’s supposed to mean someone who doesn’t have any formal computer science background and has at best a passing familiarity with data structures, algorithms, and other computer science concepts. As one of them stated “I wouldn’t know how to make a map without using a map.” (I thought about writing a post about that, but it’s surprisingly easy – just look it up.). One of them even asked me to give them a quick crash course in data structures and algorithms because he was applying in a large and well-known software company.

For me, this term is silly. If you’re doing software development work, then you’re a software developer.

I’m not saying knowledge of these things isn’t useful. If you want to do more complicated work it is certainly useful to have these tools in your toolbox. Knowing them also makes you more flexible and expands your thinking. And certainly one should be the type of developer who is willing to seek out that knowledge if it turns out you need to use it.

But the problems with the whiteboard interviewing process isn’t that they require knowledge of these things; it’s that they require it under pressure, off the top of your head, without access to the internet. This doesn’t reflect how programming work happens in the real world, where you often have a team, an IDE, and even the entire internet to help you.

Unfortunately, it’s often far too costly for companies to evaluate you under real-world conditions, so many resort to this common interviewing process. After all, it is difficult to evaluate the performance of even developers you have been working with for months, what more someone who just whipped up a short function on a whiteboard in twenty minutes? We tried some variations on it at our last company, but for me it is a problem yet unsolved. Maybe someday…

 

Sony 4K HDR Bravia X8000D

4k XLocal tech blog YugaTech is doing a giveaway of a Sony X8000D Bravia 4K TV. To be honest I wasn’t sure about using this blog to participate in a promo, but I was already in the market for a new TV since our living room TV is already starting to have some problems.

I checked out the product features of the Sony X8000D Bravia on their website. Some of the features stood out for me specifically:

  • 4K HDR – this means you get to watch high definition 4k videos. Perfect for those who really enjoy high quality displays. The TV also comes with some technologies to enhance your viewing experience such as 4k X-Reality and Triluminos display. And if you have a gamer in the family, this means you can now maximize the Playstation 4 Pro since it supports gaming in 4K resolution!
  • Connectivity – Wifi is a big deal for me because our current TV is a bit old and only supports wired connection. Wifi makes it a lot easier! The TV also has 4 HDMI slots – let me see… that’s one each for the PS4 Pro, Nintendo Switch, and XBox One, plus one more to spare for those times when you want to connect your laptop to a big display (one can dream right?)
  • Android TV – this means all the apps on the Google Play store can be downloaded and run on the TV. That means built-in Youtube, Netflix, etc, without need for a separate device to stream from!
  • Google Cast – oh, I didn’t know this even existed until now! Apparently TV’s can now have Chromecast functionality built-in, without the need for the separate Chromecast device. Awesome! We can just send content from our mobile devices directly to the TV!
  • Netflix recommended – one of the things I’ve been looking for in a new TV is that I want my folks to be able to easily use my Netflix account. Currently the only way they can use it on the TV is through the PS4, which is a bit difficult if you don’t know your way around a controller. Having the TV itself support Netflix will make it a lot easier for my parents to take advantage of Netflix’s library of movies and TV shows!
  • X-Protection PRO – to protect against power surges, this seems like it would be really good especially here in Metro Manila where power supply is not always the most stable. Added protection for your investment!

The model has a lot of other features designed to enhance your enjoyment of audio and video content. With all of these features, the Sony Bravia X8000D could definitely be the perfect home entertainment companion for the modern family!

Planning / Reacting / Relaxing

At any point in time, what you are doing can be grouped into one of four buckets:

  1. Planning
  2. Executing a plan
  3. Reacting to something
  4. Relaxing (leisure time)

Overthinkers tend to do too much of #1. The most efficient people probably spend most of their time in #2. People whose lives are chaotic do too much of #3. Almost all people don’t get enough #4. (I might be doing too much of #4~)

Running Python 2.x and 3.x on Windows

I’ve been hesitant to try Python 3.x because it’s not backward compatible with Python 2.x which I’ve been using for scripting since forever. But recently I found out that since Python 3.3, they’ve included a launcher in the Windows version that supports having both versions installed.

You can use the launcher to specify the Python version to use at the command line (it defaults to whichever version was installed first):

Even better, the launcher will recognize a header in your .py files that can specify which version of python to use:

#!/usr/bin/env python3

If the launcher sees this header, it will automatically launch the appropriate python version. Handy!

Boxes

We put people into boxes because it is convenient. It’s easier for our mental model of the world to say to yourself things like “This guy works with computers, maybe he can tell me how to fix my printer.” or “This person is from [school] and they are very arrogant.” or “You’re from [country]? You guys do [that country’s thing] right?” or  “This person is a supporter of [politician] so he must support all the things that politician does, even the things I hate.” Or in the modern world, there are even worse stereotypes.

Boxes and stereotypes are convenient because it means we don’t need to relearn our reactions and opinions when presented with a new person. We simply choose a convenient box to put them in and then we convince ourselves we are treating them appropriately.

But the real world is not so discrete. The real world is a lot more granular, a lot more nuanced. While it is inconvenient for your mental model, people will usually not fit exactly into any of your preconceived boxes. Or they may fit in multiple boxes. Or maybe none at all.

Every time you put a person into a box, you discredit her by some amount. In your mind, you shave off some of who he is a person so that he better fits your box. And for many instances, maybe that’s okay. Maybe you don’t have any significant interaction with that person, and the simpler mental model is sufficient. You don’t need to understand the character nuances of every grocery store cashier for example.

But beyond that, in order to pursue any kind of meaningful interaction with another person, that is insufficient. We must be willing to set aside whatever box you have put a person into and be willing to understand all those little bits we set aside. Those nuances characterize and define the individual, not whatever box we have put him into.

Weekend Project: Twitter Trivia Bot

I had been meaning to try writing a Twitter bot for a while now. I figured a trivia bot would be pretty easy to implement, so I spent some time a couple of weekends to rig one together.

It’s (mostly) working now, the bot is active as triviastorm on Twitter, with a supporting webapp deployed on http://trivia.roytang.net/. The bot tweets out a trivia question once every hour. It will then award points to the first five people who gave the correct answer. The bot will only recognize answers given as a direct reply to the tweet with the question, and only those submitted within the one hour period.

Some technical details:

My scripting language of choice for the past few years has been Python 2.7. I’m using Tweepy to interact with the Twitter API, PyMySQL to connect to the database, and Flask to run the webapp. I haven’t used Flask in some time, but it’s still very straightforward. I actually had a harder time configuring the webapp with mod_wsgi on my host.

The main problem with a trivia system is that you need a large and high-quality set of questions. Right now the bot is using a small trivia set –around a thousand questions I got from a variety of sources. If I want to leave this bot running for a while, I’m going to need a much larger trivia set. However, reviewing and collating the questions is a nontrivial task. Hopefully I can add new questions every so often.

Feel free to follow the bot and help test it out. I’d be grateful!

Write Smarter, Not Harder

There’s this well-known idea that it takes ten thousand hours of practice to become an expert in something. But of course, it has to be ten thousand meaningful hours of practice. Meaningful here means that you are actually learning something from your practice. If you are repeating the same hour ten thousand times, that’s not worth very much.

Instead, we should be actively learning while we practice. This means identifying our weak points and learning how we can improve. It requires that we have a feedback loop that tells us whether we are doing well or not. It also means taking on bigger and more challenging tasks. Only then can we walk the path to expertise.

As an example, I’ve been posting on this blog on a regular basis since 2016. Aside from that, I’ve also been trying to write fiction in my spare time. So I figure I’m getting a lot of writing practice and I’m doing well, right?

I recently took an online exam about how well I would do in editing work. Now, I’m pretty confident in my grammar and spelling, so it was no surprise that I got perfect scores in those categories. Yet I got poor scores in diction and sentence parallelism and style and such things. My overall score was still above average, but the test highlighted some weaknesses that I can work on.

To help with those, I’ve started going through the Chicago Manual of Style. It’s a bit boring, especially near the start, but I’m learning a lot. I also found out about this webapp Hemingway which scores your writing for readability issues. I’ve found it pretty useful – already I can see that my blog posts use way too many adverbs and have a lot of hard-to-read sentences.  My 2016 Nanowrimo manuscript got a higher score on this app compared to my posts though. (But I’m not proud of that work for nontechnical reasons haha). I’m also looking into a few other tools that can give me some feedback on how good my writing is.

The best feedback of course, would be from those of you who for some reason deign to read my posts. I already corrected my tendency to not end paragraphs with punctuation since someone called me out on it. So I would appreciate any further feedback about how I write and where I can improve.

Review: Duelyst

After Hearthstone, I tried out a couple of other digital CCGs: Spellweaver and Eternal, but neither one hooked me. The one I enjoyed the most and did pick up to play regularly was Duelyst. So this review is written from the perspective of someone who has played both Magic the Gathering (MTG) and Hearthstone (HS).

Hearthstone, Spellweaver and Eternal played like digital MTG with some advantages, as I outlined in the HS post linked above. Duelyst keeps many of the same elements and advantages, but adds an extra dimension. Besides being a card game, Duelyst is also a board game.

Board game

In a game of Duelyst your General (the analogue to Hearthstone’s hero) and his minions are played into a 9×5 board. Minions can only be summoned on empty spaces adjacent to one of your units. During your turn, each unit can either: attack an adjacent enemy; or move up to two spaces, then attack an adjacent enemy.

Having a board and unit movement greatly enhances the “positioning matters” mechanic as compared to Hearthstone. In HS, it only mattered whether minions were adjacent, to the left or to the right. In Duelyst, you can position minions to prevent enemies from reaching your General, or to restrict enemies from moving completely.

That means a number of spells and abilities care about positioning too. Each of the available Generals has a Bloodborn spell (BBS), the equivalent of Hearthstone’s Hero Power. One of the Generals has a BBS which allows her to deal damage to all enemy units in the same column as the opposing General. This means you have to be careful where you place your minions whenever her BBS is active! There are spells that affect a small area (2×2 or 3×3 and so on). There are spells that care about adjacency (“Destroy target minion that is not nearby any general”). And so on.

Factions and Generals

Hearthstone has different heroes, and each hero has a different card pool available. By contrast, Duelyst has factions and Generals. Each faction has its own card pool, and of course there is a global or “neutral” card pool as well. Each faction also has two Generals, each of which has a different BBS. The factions and Generals encourage a lot of different playstyles.

Some factions like the Songhai are more focused on spell-based damage and backstabs. The Lyonar focus on cheap, efficient creatures. Vetruvian has obelisks that can generate temporary minions. Abyssian focuses on swarm tactics and shadow creep. The Vanar rely on placement and trickery. My favorite General, the Magmar Vaath, likes to go toe-to-toe with the enemy General and punch him in the face!

Keywords

As expected, many of Duelyst keywords care about positioning, and thus have no meaningful equivalent in either MTG or HS. Namely:

  • Airdrop – minions with Airdrop can be summoned anywhere on the board
  • Backstab – this unit deals extra damage when attacking from behind (yes, even facing matters!) and doesn’t receive a counterattack
  • Blast – attack hits all enemies in the same row or column
  • Flying – may move anywhere on the battlefield
  • Frenzy – normal attacks hit ALL adjacent enemies
  • Infiltrate – gains bonus effect if its on the enemy’s starting side of the board
  • Provoke – somewhat like HS’s Taunt. Adjacent enemies cannot move and must attack a Provoke unit if there is one nearby
  • Ranged – can attack from anywhere on the board
  • Shadow Creep – this is a modifier that can be added to board tiles. An enemy standing on Shadow Creep takes 1 damage at the end of the Shadow Creep owner’s turn
  • Zeal – gains bonus effect as long as it’s next to the General

Duelyst also has a number of keywords that are analogous to abilities in MTG and HS. Rush is the same as MTG’s Haste and HS’s ChargeOpening Gambit and Dying Wish are the same as HS’s Battlecry and Deathrattle. (I worry that at some point new cardgames will run out of names for “enters the field” and “leaves the field”.) And so on – no need to cover everything here.

Skill Level, Competitive Play and F2P

The added dimension of positioning means that Duelyst is strictly more skill-based than HS. This is obvious if you note that there are a lot more choices for where to place minions. Hearthstone is also more reliant on RNG than Duelyst is, although I can’t say that will hold for the future. I enjoy some level of RNG as it creates variance, but the randomness means a higher chance of losing due to bad luck.

I find competitive play on the ranked ladders for both Duelyst and Hearthstone to be about the same. I’m not saying either meta is healthy, but as I see it there are more viable decks in Duelyst ladder as compared to HS.

Since I’ve already spent a bunch of money in MTG, I don’t like spending money on digital card games. So for both HS and Duelyst, I am strictly free-to-play (F2P). Both games offer similar monetization models (pay money for booster packs/cosmetics) but I was able to get further up the ladder in competitive Duelyst.

In my first full month (December), I was already able to get to Duelyst’s Gold Division. This should be similar to around rank 10 in HS. After a lot (and I mean a lot) of grinding from Diamond rank, I managed to hit the S-Rank Division last month. This is the equivalent of HS’s Legend rank. The highest rank I ever got in HS was around rank 6 or 7.

If I think Duelyst is more skill-based than HS, why did I find it easier to get to S-Rank than HS’s Legend rank? Two reasons come to mind:

  1. I found Duelyst games more fun. This means I was playing Duelyst on a daily basis since it started. At the start, I played regularly because I wanted to get Steam Achievement completion. But I found myself enjoying the game and continuing to play even after that. There are also a lot more variance in decks being played on the Duelyst ladder. By comparison, HS ladder seemed to be almost 50% the one best deck (used to be Midrange Shaman, nowadays Pirate Aggro…) while the other 50% are trying to beat it.
  2. It was easier to get the powerful cards and build the tier one decks in Duelyst. The pricing of packs is about the same (100 gold), but on average I could earn around 100-150 gold per day from Duelyst’s quests, compared to 40-60 for HS. The drop rates for Legendaries (highest rarity in both games) is higher in Duelyst as well. Unlike HS, Legendaries in Duelyst are not restricted to one per deck, you can play as many as three. This meant you need more of them, which annoyed me at first. But I think that’s counterbalanced by the higher drop rate. For comparison, I’ve been playing HS for more than a year and have only gotten two premium (golden) Legendaries. Three months into Duelyst and I’ve opened the same amount of premium (prismatic) Legendaries. (Well, this comparison may be skewed since I open more Duelyst packs due to the increased gold rate.) Another factor was the Bloodborn expansion, which you could complete by playing enough to grind 3900 gold. That expansion came out in December, and I completed the set early in January. This set gave me access to many useful cards that were important in the meta. This allowed me to build a tier one deck and reach S-Rank in January. Even after that deck was nerfed, I was also easily able to shift to another tier one deck from another faction. In HS, I still haven’t found a new competitive deck after Midrange Shaman.

The Future

At first I told myself I would stop playing Duelyst after I completed the Steam Achievements. Then I said I would stop playing after I got to S-Rank. But I’m still playing it now. By comparison, I now launch HS once or twice a week, and I don’t clear the quests.

Duelyst is still a young game – the second expansion just came out last December. So in the future it may yet be plagued with the problems Hearthstone currently has. The developers have shown themselves to be responsive in nerfing problematic cards and shaking up the meta though. Whether they are able to keep this up remains to be seen. In the meantime, I’m willing to keep playing as long as the game is still enjoyable.