Saturday, April 27, 2013

Caption Captain

Before I write a post about my most recent project, I thought it would be a good idea to write about the thing I did before that. It had a much smaller scope, and I made it so long ago now that I'm in danger of forgetting absolutely everything what I did.

Before I start the explanation, I should just provide a link to the site - Glad that's out of the way! So Caption Captain is a game that picks one image and three titles at random from reddit, and the goal is to pick the title that the image was submitted with. With a subreddit like Reaction GIFs this is a pretty fun game and an entertaining way of browsing the latest submissions. The game also works with other subreddits, but obviously the ones that are not image-heavy will not work too well, and the captions are sometimes pretty obvious for subreddits like funny or gifs.

The main reason I wanted to make this was both to have a bit of practice with Dojo and Bootstrap, and to see what I could do with a site when I limited myself to having a minimal infrastructure - I wanted to implement everything in pure HTML and JavaScript and have no server-side logic. That means no database, no server to access remote URLs, and no URL routing. The site could be served as a single HTML file, but I split it up a bit for clarity. It's currently running on Amazon S3 so it has minimal cost and maintenance.

This post will probably be light on the code, but I've put up all the source on GitHub so you can follow along by going there.

The first problem I encountered was due to my technology choices. Bootstrap (the JavaScript part at least) is generally written to be used alongside jQuery instead of Dojo. I would also prefer to use jQuery, but I knew I had to use Dojo for another thing I was working on, so I wanted to get at least a little bit of practice with it. Thankfully, some kind soul has done the hard work and re-written Bootstrap's JavaScript modules in a format that works well with Dojo and they creatively named it Dojo Bootstrap. All I wanted to use was Bootstrap's Modal functionality, and with Dojo Bootstrap this was as easy as require-ing the Modal module and putting the right tags into the HTML.

The next problem to solve was thinking about how to get subreddit data. Usually I'd just write some code into the server to query reddit, then return that as part of a site or ajax request, but since I didn't want to actually use a server this was not possible. Luckily, reddit's JSON API supports the usage of JSONP, which means we can call it on the client side and use the response inside a JavaScript function. Using this I made a function that would attempt to get the next image and set of captions, and if there were not left it used JSONP to get some more images and captions from reddit before returning one of them. All of the image loading logic is in imageLoader.js but to summarize - getNextImage is the main function, this will return an image if we have it, otherwise it calls _loadImages. _loadImages calls a set of query functions asynchronously, one for a few different sort orders of the subreddit, and that function (_getDataFromReddit) is a fairly generic JSONP call. Once all of these queries finish, the results are filtered to make sure that the link is an image and that its score isn't too low, then it's separated into a set of images and captions that are ready for use.

The rest of the code and HTML (mainly in index.html and controller.js) is pretty standard scaffolding code so I won't go through most of it, but the last thing I wanted to mention was the solution to the problem of URL routing when not using a server. I wanted to support the selection of different subreddits, but the usual solution of having a unique URL for each subreddit and using URL routes to detect the subreddit would not work in a plain HTML page. However, JavaScript does have access to the full URL, including query string, so all we need to do is redirect to index.html with e.g. ?subreddit=reactiongifs, detect that on page load, and the problem is solved.

So that's it, the main thing I learnt is that I don't really like using Dojo as much as jQuery, at least for the "utility" functionality. I still think it's pretty good for UI work, and the rest of it has improved a lot recently, but it's hard to beat jQuery for things like AJAX and async calls. I also quite enjoyed the challenge of making a single-HTML page, and if I ever think of something else that would work in that form I'll have another go at it. It's just lovely to be able to shove something on S3 and forget about it while it keeps running happily in the background.

Saturday, April 13, 2013

Code Jam 2013

Having recently finished my hobby project (more on that later ... probably), I was looking for something else to start working on. Coincidentally, the Code Jam was starting, so my choice was basically made for me. I had a go at the competition back in 2010, mainly to keep my knowledge of Python up to date, but for the next 2 years, it was scheduled in times that meant I couldn't dedicate enough time for it, but I had no such excuses this year!

Given my recent work in TypeScript and Node.js, I figured that would be an ideal choice as a platform, but I left it a bit late and didn't even start on the template code that I could use for all the problems until a few hours after the competition started. In the end, I managed to finish full solutions for 2 of the questions, a partial solution for 1, and an important learning experience for the last question. I'll quickly go through my experiences and some things I learned.

First - the template. In case anyone is unfamiliar with the competition, Code Jam is a set of coding questions that are presented as a set of textual inputs, resulting in a set of definite results. You are given an explanation of the problem, a small sample set of inputs, and the expected outputs for those inputs. After you've confirmed that your solution works for that sample set, you can download a small set of other inputs, and upload your solutions for them, and after that you get download a larger set of inputs and upload your solution for those. The input files are usually just a set of numbers or characters, one set for each test case, and the output format is standard, so it is very helpful to have some "framework" code put together to handle the input and output of the problems, so that you can quickly jump in and write the code specific to the problem without needing to reinvent the wheel every time. My template code is fairly boilerplate, so I'll mainly leave it to the code to tell the story, but I will mention one unexpected benefit of the choice to use Node.js - asynchronicity. When I was using Python, I was running tests one at a time, but using the lovely async package I was able to very easily tell node to run as many tests as possible at the same time. The basic idea of my template is that I read in the input file, convert it to an array of test cases, then instruct async to "map" that array through a solver function to a results array, and output those results when all the processing has been finished. I'm not really even sure if this ended up being necessary, but it still made me fall in love node just a bit more.

The first problem - tic-tac-toe-tomek - is understandably fairly easy to solve. The idea is that we have to have a look at the state of a game similar to tic-tac-toe, and say if someone won, if it was a draw, or if the game was not yet finished. The differences between the game and tic-tac-toe are that it's played on a 4x4 board, before players start placing Xs and Os a single T can be randomly placed on the board, and to win, a row or column or diagonal must contain all Xs and Ts, or all Os and Ts. Given that the board never got larger than 4x4, I chose to do this in a brute force-ish way and just iterate through all the rows, columns, and diagonals for each test case and check for the existence of dots, Xs, and Os (ignoring Ts completely). A dot meant that there was no winner in that row/column/diagonal, otherwise no Xs meant that O won and no Os meant that X won. My solution only took a few seconds to churn through the large dataset, so I was off to a good start.

The second problem - lawnmower - was a bit trickier, I was given a set of heights of square sections of grass, and needed to figure out if those heights could be created by the usage of a lawnmower with an adjustable trim length that must move across or up and down the whole yard. Thinking about this for a little while, and given that the set of heights was constrained to a maximum of 100 different lengths, I figured that this could be efficiently calculated by working through the heights one at a time from shortest to tallest. If we find any rows or columns that are completely made of up height 1, we can mark that row or column as "safe". Moving up the lengths, we can treat a row or column as safe if it either contains that height, or the exceptional row or column is also "safe". Figuring out the data model for this was another interesting challenge, but I think that the code explains that better than words could. I'm not exactly happy with all of the code, but it was getting late and it solved the large dataset in milliseconds so I called it a day.

The third problem - fair-and-square - was one that I didn't get a chance to complete fully. The problem involved finding all numbers between two limits that satisfied some constraints. The number must be a palindrome (same forwards and backwards), and it must be the square of another number that is a palindrome. I decided to take the easy way out for this one and I picked a solution that I knew would work for the first large dataset (where the largest possible limit was 10^14) but would definitely not work for the second large dataset (largest limit of 10^100). The easy way out was to just pre-calculate all possible numbers that satisfied the constraints, then iterate through that list for each test case, considering only the numbers that are between each test cases's limits. Since the number must be a square, we only need to go through each number up to the square root of the largest limit, which in the case of 10^14 is "only" 10^7, so as long as we can check 10 million numbers fairly efficiently, we are good to go. In the end this only took about a second and I'll leave it to the code to explain the details. When I had a look at the set of valid fair-and-square numbers, there was a pretty obvious pattern that I'm sure I could have extrapolated to the larger case if I tried hard enough, but I never quite got around to it.

The fourth and final problem - treasure - taught me a lesson that I had strangely enough been reminded of a few days ago - "your strongest intuitions are the ones that you should question first". The problem was that, given some keys of various types, and a set of treasure chests (along with information about the type of key that is needed to open the chest, and the keys that are inside the chest), we needed to work out if it was possible to open all the chests. I realized that this could be modeled as a graph traversal problem, with the nodes being the set of keys in hand and chests left unopened, and the edges being the act of using a key to open a chest. Since I was having a love affair with node's asynchronicity, my intuition told me that I could us an inefficient solution, as long as I paralellized the investigation of each set of edges. This, of course, turned out to be completely incorrect, but I only realized this after spending way too long trying to get my heard around how to use the async library, which often happens whenever I do anything tricky and try to do it aysnchronously. When I realized that my solution wasn't going to work, and I only had about an hour before the competition was over, I decided to throw in the towel. I still thought it was a pretty fun problem to work on, and I look forward to being able to see the solution and whatever the trick was to minimizing the number of graph traversals that needed to be made. I'm guessing there is some sort of smart look-ahead shortcut that can be used but it's still a bit of a mystery to me.

And that's it - I ended up placing at about 3500 out of 20,000 entrants and qualifying for the next round. Not a great result, but not too bad considering the fact that I went into it "blind", without a framework set up and without knowing too much about the libraries I would be using.