It’s been many months since I’ve posted here, due mostly to an extreme influx of work from classes and my jobs. But that doesn’t mean I’ve given up on this blog! Rather, I have a huge number of updates, which I will only describe in short detail for now. In no particular order:

After working at the Summer School in Theoretical Computer Science at Princeton, I went to one more conference the week after the school closed out. It was the annual RANDOM/APPROX dual conference, also held at Princeton. It was extremely interesting, with riveting talks by a variety of excellent speakers. I particularly enjoyed the keynote address by David Williamson, who spoke of a new generation of approximation algorithms called “lightweight algorithms” that he believes should and will define the future of the field. I saw a lot of really interesting talks and having taken a graduate course on this last semester, I was able to at least follow a good portion of most talks.

Next, I have begun my fall semester (actually by this point, it’s more than half done..)! I ended up taking two grad courses: Advanced Complexity Theory with Sanjeev Arora and an Advanced Topics course (aka, new courses which may or may not be kept in future semesters) on Information Theory with new professor Mark Braverman. Both are extremely interesting and have gotten very challenging. I think however that complexity theory started off much harder for me since I haven’t taken the undergraduate version of this course first, but as we moved on to new material, I feel like I’m keeping up fairly well with the class. As for information theory, it started off introducing really cool ideas that were pretty straightforward to follow, but our most recent topic of communication complexity is extremely difficult for someone with no prior knowledge or experience with this. The class has a couple of PhD candidates who are very familiar with this material, so I guess that somewhat helps a bit. But it goes very fast and I need to constantly review my material. Nonetheless, it’s a ton of fun! I’m also an undergrad grader for COS 340, which is called Reasoning about Computation. It’s sort of an introduction to theoretical CS through a variety of topics including probability, hashing, algorithmic analysis, approximation algorithms, graph theory, and more. Lots of super interesting material. It’s by no means a trivial course (either to take or to grade..) but it’s an excellent jumping point for anyone interested in theory. I actually haven’t taken this course in the past due to scheduling issues, so I’m enjoying following the material as the class does it too.

We also had a Quantum Computing Day mini-workshop at Princeton. I’m hugely interested in this subj. ct although I have little formal background in it. Nonetheless, I decided to attend anyway. The keynote talk was by Scott Aaronson of MIT, a well-noted theorist in this field. The talk was, as you might expect, brilliant. I’m pretty intrigued by how matrix determinants and permanents keep popping up in so many different places. Aaronson showed the application of those concepts in dealing with fermions and bosons, which given my limited quantum physics knowledge was new to me. There was also another great talk by an IBM researcher; this one a more applied talk about actually building larger multi-qubit gates while dealing with the immensely complicated issues of maintaining the superposition. The talk was very positive and the speaker showed that IBM has made a lot of progress in pinning down some of the problems. Although many believe QC is just a fad and will never actually make it to utility, I’m optimistic to see and follow real progress being made. If for nothing else, for science.

So those are the big news items from the past few months. Hopefully, I will have time to keep this updated more regularly hereon.

EDIT: One more thing! The research that I worked on with a few other undergraduates and my professor from the summer of freshman year has finally been published and presented at IMC 2011 in Germany early in November! The paper is also now online here (I think this might be behind a paywall).

A direct link is also available here.

Posted by on November 23, 2011 in Uncategorized

I’ve been looking for a nice and fast Google Tasks client for a long time. There do exist a lot of them but none that I have encountered matched what I was looking for in terms of functionality and ease of use. Given that I have a bit of free time this summer, I decided to write one myself.

This task would have been really hard and clunky a month ago. Luckily, Google introduced the Tasks API about three weeks ago, a hugely requested feature. I hadn’t worked with Google APIs before so I took it up as a challenge to figure out how it all works and put together my client in a few days’ time. I also decided to go with Python this time, as I’d like to get more practice with the language (which I this is really amazing, by the way). The result of the past three days is a very simple and fast client for Google Tasks that works in the command line.

### Goals

First, I had to define what I wanted to accomplish with this project. I wanted a way to retrieve tasks from one or more task lists (I currently have one but have used multiple in the past), have a way to quickly add, remove, and check/uncheck tasks. I wanted the whole thing to work in the terminal, as that’s where I spend most of my time working. And I wanted the commands to be as short as possible, as to minimize the amount of typing necessary. Specifically, I did not want to have to type an entire task’s name in order to perform some action on it. And I wanted the whole thing to take as little time as possible between subsequent operations – I didn’t mind a possibly shutdown if I could have fast removes and adds and toggles while the application was open. Finally, I wanted to have two modes: Normal Mode and Quick Mode. In Normal Mode, the application is opened and kept running, allowing me to make a series of changes to it before closing. In Quick Mode, I perform a single operation fully specified as arguments in the command line. The changes are made (with ambiguities resolved when necessary) and the application closed immediately. And I wanted to have it do authentication in order to access account information from any computer I choose to run the application on.

### Implementation

I was able to accomplish all of these goals by loading all task lists into memory upon startup and committing all changes to the server when closing the application. The Tasks API is still in Labs, which means it could change from the time of this writing, but as of right now, retrieving everything requires $N+1$ API calls, where $N$ is the number of task lists in a given account. So that was fairly quick. I used Google’s sample code almost verbatim for OAuth 2.0 authentication (yay security!) and that’s usually the slowest part of the application. It does cache credentials, but still takes a bit of time to establish a secure connection. Once all the data is retrieved, I decided to store it in memory as a dict of dict of lists of task objects – which are just dicts themselves. That’s a lot of dictionaries, but it made sense since I was able to get to fast accesses, insertions, and deletions. As part of the way I implemented the code, the dictionary of tasks had to be an OrderedDict; if you look at the code, it’ll make sense why. I then performed changes on the in-memory task lists as the user made changes, but those changes were only reflected via flag statuses and not actually performed. Then, when the application is closed, I sent back just the changes, minimizing the number of total API calls.

### Conclusion

The result is a little application that I’m fairly proud of. It does what I need it to do and I actually do use it. There’s currently no documentation beyond what’s in the source code and the code is still a bit rough around the edges. The link to my repository is here. As mentioned on that page, this application requires Python >=2.7, Google API client for Python, and the Fabulous library (used for having bold and strike-through text in the terminal). I have not included the Client ID, Client Secret, or Developer Key values in this code, but you can get those values by registering this application for yourself via the Google API Console. The code itself is fully open-source and you are free to use or modify it as you wish. It’s still in development, so look out for changes in the future.

Posted by on May 31, 2011 in Uncategorized

Tags: , , , , ,

## Fun with CR-48

Another day, another unimaginative title. Anyway, yesterday, I received my brand-new CR-48 Chrome OS netbook for free my Google. First off, thanks Google! You guys totally freaking rock and you made me day and week. 🙂

The following is a sort of review and impressions of what I have experienced so far in about 24 hours with the device. I’ve made some customizations to the software which I will describe below. If you follow any/all of the following things, you’re doing so at your own risk. I’m no expert on this device, but there are tons of resources already online for help. Leave a comment if you encounter any issues.

### Hardware

First of all, the box art is pretty neat. I’m sure you’ve seen tons of pictures of it online, so I won’t put my own up. It just looks all neat/trendy/hipster/etc and I like it. It’s the little stuff that makes me really love Google. For example, the brown information placard that comes with the package. It looks like your ordinary safety and usage notice but it’s written with a ton of humor and it was quite entertaining to give it a read. My absolute favorite part of the whole hardware is that there are no stickers on the whole device. Ah! Beautiful. However, I was fortunate to be in the batch where they started providing stickers along with the computer as well, so I can add those if I like. Love it. The entire outside of the computer and everything except the keyboard has a rubber matte finish. While this feels really good to the touch and avoids shine, I’ve heard reports that the corners have started peeling for some people and that concerns me a bit. But it’s okay, I understand that this is a prototype model and all so I’m pretty forgiving about that. Besides, I got this for free, so I can’t really complain.

The keyboard is nice and responsive. The keys are very comfortable and typing is a pleasure – except for one thing: the touchpad. The touchpad by itself is not bad. It’s very expansive and is a Synaptic one too! That means it support multi-touch and other gestures. However, it’s also so large that my fingers constantly brush up against it and that causes me to change the cursor position and mess up where I’m typing. Grr. There’s also other annoyances which I will get to later.

There’s also a webcam on this thing, which works reasonably well. I’ve heard that there are two ambient light sensors on either side of the webcam which is neat and allows for automatic brightness modulation. The power brick is very, very tiny (the smallest I’ve seen on a netbook) but the power cord is still 3-prong.

Apart from that, the left-hand side has a VGA output and the right-hand side has a power outlet, USB port, 3.5mm headphone jack, and an SD card slot. It surprised me that there is no microphone jack as far as I could tell and there is no Ethernet port (!). How does a web-connected machine running a cloud OS not have an Ethernet jack? Luckily, there are Ethernet-to-USB cables that help with that – unless you have any other peripherals that also need USB. It’s kind of annoying that there’s only one USB port, considering my Dell Mini 10v netbook has three. Apart from that, there’s a large, powerful battery underneath. Inside, I’ve heard that there’s a 1.66Ghz Intel Atom processor, an a/b/g/n wireless card, 2GB RAM (!), and a 16GB SSD. Apart from that, the hardware is entirely simple.

### Software

Now let’s talk software. I played around with Chrome OS for a while and I felt that a lot of it is really pretty polished. Things generally work as they should. Booting up the computer for the first time, I was first asked to connect to the Internet and it worked completely flawlessly and quickly, which was impressive. I wonder what people will do if they have a a MAC-filtered wireless network, since you can’t find out the MAC address from that step yet. It then performed an update which was pretty fast and then asked me to log in. The whole process was fast and nearly perfect. The only thing is that the animations on the Help tutorial were pretty laggy, but this is an indicator more of the machine’s hardware than software.

Flash works decently, although not perfectly, well on this. I watched a few 360p videos and they streamed somewhat decently. I need to do more testing to determine how much farther I can push this machine. This was all fine and dandy until I realized that I can’t do much unless I have a text editor and a way to write code. I looked up John Resig’s review of his CR-48 and he seemed to have the same issue, expect that he just SSH’d into wherever he needed and coded like that. Which brings me to my first happy surprise that there’s a terminal built into Chrome OS, with the familiar Ubuntu-esque shortcut Ctrl-Alt-T. Nice – except that it’s severely limited. In fact, apart from messing with the network connection, pretty much the only thing you can do is SSH. Resig talked about how this stripped-down SSH implementation doesn’t even allow for key-based authentication (!). A bit of a bummer. The other sad part of the terminal is that it seems to only support about 8 colors. While that’s more than 1 and that’s good, it’s not the 256 that I’ve been spoiled with, using gnome-terminal in Ubuntu. Lack of pretty Vim colors makes me sad.

Speaking of which, I still don’t have a text editor by default. Okay minor correction: qemacs is a text editor built into Chrome OS, but getting there as well as doing anything substantial under the hood requires me to switch into development mode.

All this was fine and dandy, but I wanted to do more.

### Ubuntu

It takes little thought to realize that this machine is pretty much the idyllic Ubuntu box. It’s small, powerful, and has a good battery life. There are effectly two ways to get Ubuntu running on there: the easy way and the freaking hard way. The hard way is by the Chromium OS team and requires VirtualBox, a 64-bit separate Linux machine, and many, many hours of time. The easy way is an elegant script that someone wrote. It’s readily available online and you can find it. That’s the path I used, mostly because my laptop is running 32-bit Linux (sigh, I know). Anyway, the instructions were perfect and the whole installation went without a hitch. I did lose wireless connection once during the download, but the script is smart enough to realize that that’s a possibility. Rebooting and continuing downloaded the half-downloaded file and the remaining and performed the installation.

I was then in Ubuntu 10.10 (as I am now)! I was able to run an update and grab real Vim with sweet 256-color goodness. I was really surprised to see that the build of Ubuntu I had downloaded came with Compiz built into it! And it’s fast. Like surprisingly fast. And the boot time is unbelieveable. We’re talking like a ~10sec boot time here, guys. It’s insane (the same goes for Chrome OS too – very, very fast booting and near instantaneous Suspend). I’m actually writing this article in Vim on Ubuntu on a CR-48 right now and I’m happy, except for this stupid touchpad.

Now, the biggest issue I have so far is that I lost multi-touch in Ubuntu and in fact I have no settings at all for the touchpad. Actually, I have no installed drivers for the touchpad either! There are some lengthy solutions I’ve read that involve downgrading Xorg and making all kinds of copies of library and scripts from Chrome OS over to Ubuntu but I haven’t ventured into that yet. Using mouseemu, I was able to get some hack at scrolling (Alt + finger slide) scrolls right now and it’s not too bad. I just wish I could disable the touchpad when I’m typing but I haven’t gotten that to work yet. Gsynaptics picks up a PS/2 Synaptics TouchPad but I still don’t have a Touchpad tab in Mouse Preferences. That’s a definite To-Do.

Apart from that, I still have to boot back into Chrome OS to ensure I haven’t screwed that up too much. There’s a command you need to run if you want to boot into the other OS and I just put that in a script that I can run from either OS. I’m yet to test that. I’m getting about 8 hours of battery life on this, which is a far, far cry from the 2.5-3 hours my poor Mini 10v gives me and so I’m thrilled.

### Conclusion

There’s a lot I’ve gotten done in the first 24 hours of having this device, but there’s still some stuff I need to do. Hibernation seems like an impossibility under this current configuration since I do not have enough disk space. I have about 2GB free space left after installation of Ubuntu, which is not nearly enough for a memory dump partition needed for hibernation. And I don’t have multi-touch and I’m really wary of getting knee-deep in Xorg again. Last time I tried to enable two-finger scrolling, I ended up reformatting my installation. Yeah, it was that bad. Anyway, that’s a wrap for now. I’m overall extremely pleased with the CR-48 and I can’t thank Google enough. You’ve made at least one loyal consumer very, very happy 🙂

1 Comment

Posted by on January 26, 2011 in Uncategorized

## Wow, Technology.

It’s days like this that I wish so damn much that I could go to events such as CES (Consumer Electronics Show) 2011, going on right now. One day, I swear I’ll go. Really.

I was just reading my usual roundup of tech blogs for the day and couldn’t help but realize that I got just about 217 items just in the past 24 hours regarding CES and all the ridiculously cool new technology they’re featuring there. Take for example Sony’s 27(!) new HDTVs, many of which are 3D-enabled and all of which are incredibly elegant-looking. Or Samsung’s new razor-thin televisions (seriously, how much thinner can they make it?). Or the tons of new cameras and camcorders, now at a phase where 10MP is just barely making it (yes, I know pixel quantity is not everything, but it does count for something). Or like the dozens and dozens and dozens of new phones featured today. Like that new Motorola Droid Bionic with 1080p output. Seriously? Full HD output from a freaking phone?! Wow. (I’m looking at you, rate-limited HDMI-output Evo).

And the elephant in the room for me, the announcement of Android 3.0, or Honeycomb, for tablets. To be completely honest, I’m not totally quite into this tablet frenzy that’s been stirred up in the past few months with everyone and their mother announcing a new tablet, but if there’s anything like Honeycomb running on it, I might just be interested. Arguably, the Galaxy Tab running Froyo is the best Android tablet on the market (are there others? Yes there are. Very few). But I played with one and felt like it was a bit of a letdown. For one, it was just too laggy for my taste and the cosmetic changes that made it distinctive from a large phone (iPad?) were too minimal. However, the new sneak peak of Honeycomb on the Google Mobile blog today is pretty impressive. Of course the video is extremely and almost annoyingly flashy enough to be taken straight out of Tron, but it gave a pretty neat exposition into how Android will look on a completely different form factor. I entirely disagree with Apple’s UX choice to literally scale up the exact iPhone interface for the iPad. A dedicated OS for specifically that form factor is the right idea and I think Honeycomb is looking good so far.

It also shows the power of Android at extensibility to different kinds of hardware. About a month back, Google so kindly sent me a free Google TV device (the Logitech Revue) for my contributions to Google Code and I got around to playing with it. Initially, I thought this was just a simple, standalone OS/firmware but quickly realized that it was actually Android 2.1. When I played around with the interface, I actually didn’t believe it until I saw the version number on the device itself. Needless to say, it looked and felt entirely different (although imperfect in a couple of ways). Now we will soon have a version of Android designed specifically for tablets. Which brings me to the next question. Where does Google Chrome OS play into all of this? From whatever I’ve read, there seems to be a bit of ideological gap between the Google Chrome OS team and the Android team as far as objectives. Yes, they’re different but they’re also getting closer and closer to the same types of hardware. I could definitely seen Chrome OS running on a tablet device (since a fair assumption is that a portable device like that will be always connected to the Internet). So eventually one is going to win. Now if only I got one of those CR-48 netbooks, I might be able to pick a side fairly..

Posted by on January 6, 2011 in Uncategorized

## So What’s New?

It’s been a few weeks since I last updated this with a real post, so here it is.

I finished my research for the summer a few weeks back. I’m probably going to continue it again once the school year starts, but I decided I wanted at least some time to work on different things during the summer as well as catch a break. At the time that I ended, most of the major tasks assigned to me had been completed. That is, all but one program module had be written and polished and most of it had been used to generate at least first-run data. I can’t go very much into the details about what the modules did exactly, but the broad concepts are the same: write software that parses the millions of lines of log data efficiently and offers a way to gain greater insight into it

Despite the fact that some of this code will only be run once, I decided to nevertheless invest the time into making it nice and modular, etc. This is a time when I truly saw the importance of good code design. Code that I had written at the beginning of my research period, about two months back, really does look alien if you’ve lost touch with it. Among the people I was working with, I started first, so there was no code to start off from. I ended up making up my own standards for how to run certain modules – a certain combination of command-line flags and stdin/stdout redirects and all. In this process, of course a lot changed and later parameter paradigms greatly differed from the early ones. At some point, I realized that it was a major pain to remember how to run each program so rewrote lots of my previous code to accommodate for that. For example, there was a certain little script that I used to run the same program on many log files over a period of time. This little script started off first as an inline bit of Bash fu that I could start in the background and let it run through the day and into the night if necessary. It then evolved into a script of its own, became more standardized to accept the executable and as my knowledge of Bash improved, was written more efficiently. In fact, it even went on to become so commonly used that I included it in nearly module I wrote. The same goes for implementations of commonly used data structures – these were soon put in a common lib/ folder and linked to from various modules. Even commonly used functions that mapped to all elements of those data structures were placed in a specials utils.c file. Another useful little macro directive that I used to help with (possibly careless, irresponsible, and brash) memory management was a wrapper on GNU free that was double-free safe. So, every single free() call was replaced with nxfree() with the following implementation:

#include <stdlib.h>

/*
* Convenient wrapper for nfree().
*/
#define nxfree(s) nfree((void**)&s)

/*
* Wrapper for GNU free. Checks for NULL and sets pointer to NULL
* after freeing. Avoids accidental double frees.
*/
#define nfree(p) {if(*(p)) free(*(p)); *(p) = NULL;}


So, pretty simple, but useful. I ended up using many such little snippets of code to make my life easier. In addition, I also rewrote my original Makefiles to be more modular. I ended up creating a standard template for all Makefiles, with only trivial changes to customize it for the module in question. The template is generic enough for use pretty much anywhere gcc works and is below:

CC = gcc
CFLAGS = -Wall
CDBGFLAGS = -Wall -g
LIBS =

LIBOBJS = ../../lib/*.o   #Shared Library Code Path

TARGET = <Release Target Name>
DBGTARGET = <Debug Target Name>

OBJS = <All Source Files Names, with .o Extensions>
DBGOBJS = <All Source Files Names, with Dbg.o Extensions>

$(TARGET) :$(LIBOBJS) $(OBJS)$(CC) -o $@$^ $(CFLAGS)$(LIBS)

$(DBGTARGET) :$(LIBOBJS) $(DBGOBJS)$(CC) -o $@$^ $(CDBGFLAGS)$(LIBS)

%.o : %.c
$(CC) -c -o$@ $<$(CFLAGS)

%Dbg.o : %.c
$(CC) -c -o$@ $<$(CDBGFLAGS)

all: $(TARGET) debug :$(DBGTARGET)

clean:
rm -f $(TARGET)$(DBGTARGET) $(OBJS)$(DBGOBJS)

clobber:
make clean && rm -f *~



Now after research was done, I got a bit more time to work on the Mozilla Crowdsourcing project I’ve mentioned before. We completed Phase 1 a few weeks back (check the Mozilla Labs’ blog for all sub-teams findings and here for just my sub-team’s). After that, we got started on Phase 2, which consists of designing a Design Challenge using our findings that took into account the various things we picked up along the way. The final result of the Crowdsourcing team’s designs will eventually replace the current model of the Lab’s Design Challenges. Last Sunday was the deadline for that and our sub-team had a pretty concrete set of guidelines. These will soon be written up and fleshed out into a blog post. Once this stage is complete, we will take our three sub-teams’ designs and combine them into one, which will be our official proposal. Then come the actual implementation of the proposal, which may include some actual development and/or extension of existing software. I’ll speak more of this as it comes up in the next few weeks.

Well that’s what’s keeping me busy right now. I’ve got about two weeks before college starts again, so I’m prepping myself as necessary for that. I expect this year to be pretty challenging again, but at least I know I will enjoy the classes even more now, having had more flexibility in choosing them. In the meantime, I think I’ll finally take a look at Google Code University and see what they offer – been wanting to do that for quite a while.

Posted by on September 1, 2010 in Uncategorized

## Google Code Jam Global Round 1A

Okay so I didn’t make this time. I had enough solutions right to qualify but didn’t do it fast enough. And considering that the competition was on the same weekend that I had to move out of Princeton, I didn’t have the time or energy to do compete in Rounds 1B or 1C. But it’s all okay because I had a fun time and now summer is here! At least for the next two weeks before I have to get back and start summer research.

But regardless, below I have posted my solution to the first problem of Round 1A. I had a somewhat fast algorithm but nothing too special. Regardless, here is the source:

import java.util.*;
import java.io.*;

public class Join
{
private String filename;
private char[][] board;

public Join(String f)
{
filename = f;
openFiles();
}

private void openFiles()
{
Scanner s;

try
{
s = new Scanner(new File(filename));
int ct;

ct = s.nextInt();

for (int i = 0; i < ct; i++)
{
int N = s.nextInt();
int K = s.nextInt();

board = new char[N][N];

for (int j = 0; j < N; j++)
{
String line = s.next();

for (int k = 0; k < N; k++)
board[j][k] = line.charAt(k);
}
output(i + 1, process(K, N));
}

s.close();
}
catch (Exception e)
{
System.err.println("I/O error: " + e);
System.exit(0);
}
}

private String matchesRed(String tmp, String retval, int K)
{
String regexRed = ".*R{" + K + "}.*";

if (tmp.matches(regexRed))
{
if (retval.equals("Red"))
return retval;
if (retval.equals("Neither"))
retval = "Red";
else
retval = "Both";
}

return retval;
}

private String matchesBlue(String tmp, String retval, int K)
{
String regexBlue = ".*B{" + K + "}.*";

if (tmp.matches(regexBlue))
{
if (retval.equals("Blue"))
return retval;
if (retval.equals("Neither"))
retval = "Blue";
else
retval = "Both";
}

return retval;
}

private String process(int K, int N)
{
String retval = "Neither";
gravity(N);

// Check vertical
for (int i = 0; i < N; i++)
{
String tmp = new String(board[i]);

retval = matchesRed(tmp, retval, K);

if (retval.equals("Both"))
return retval;

retval = matchesBlue(tmp, retval, K);

if (retval.equals("Both"))
return retval;
}

// Check horizontal
for (int j = 0; j < N; j++)
{
String tmp = "";

for (int i = 0; i < N; i++)
tmp += board[i][j];

retval = matchesRed(tmp, retval, K);

if (retval.equals("Both"))
return retval;

retval = matchesBlue(tmp, retval, K);

if (retval.equals("Both"))
return retval;
}

// Check diagonal 1
for (int i = 0; i < N; i++)
{
int orig = i;
String tmp = "";

for (int j = 0; i >= 0;)
tmp += board[i--][j++];

retval = matchesRed(tmp, retval, K);

if (retval.equals("Both"))
return retval;

retval = matchesBlue(tmp, retval, K);

if (retval.equals("Both"))
return retval;

i = orig;
}

int i = N - 1;

for (int j = 0; j < N; j++)
{
int orig = j;
String tmp = "";

for (; j < N;)
tmp += board[i--][j++];

retval = matchesRed(tmp, retval, K);

if (retval.equals("Both"))
return retval;

retval = matchesBlue(tmp, retval, K);

if (retval.equals("Both"))
return retval;

i = N - 1;
j = orig;
}

// Check diagonal 2
for (int j = N-1; j >= 0; j--)
{
int orig = j;
String tmp = "";

for (i = 0; j < N;)
tmp += board[i++][j++];

retval = matchesRed(tmp, retval, K);

if (retval.equals("Both"))
return retval;

retval = matchesBlue(tmp, retval, K);

if (retval.equals("Both"))
return retval;

j = orig;
}

int j = 0;
for (i = 0; i < N - K; i++)
{
int orig = i;
String tmp = "";

for (; i < N;)
tmp += board[i++][j++];

retval = matchesRed(tmp, retval, K);

if (retval.equals("Both"))
return retval;

retval = matchesBlue(tmp, retval, K);

if (retval.equals("Both"))
return retval;

j = 0;
i = orig;
}

return retval;
}

private void gravity(int N)
{
int j;

for (int i = 0; i < N; i++)
{
String tmp = "";

for (j = 0; j < N; j++)
if (board[i][j] != '.')
tmp += board[i][j];

int diff = N - tmp.length();

for (j = 0; j < diff; j++)
board[i][j] = '.';

for (; j < N; j++)
board[i][j] =  tmp.charAt(j - diff);

}
}

private void output(int caseNum, String result)
{
System.out.println("Case #" + caseNum + ": " + result);
}

public static void main(String args[])
{
Join app = new Join(args[0]);
}
}


So basically, I first took the input and put it inside a two-dimensional character array. Then, I implemented gravity (if only it were so easy always!). I made the observation that all gravity does is move the non-period characters to the right side and pushes all intermediate period characters to the left. Originally, I had a recursive algorithm to do this, but this was way simpler. So, I parsed each line and collected the non-period characters in a temporary string. Then, I added sufficient periods as padding and then just threw my collected string at the end of each line. Do this N times, and you’re done. Of course, I could’ve used some regex fu to make this even faster, but it was straightforward enough and did the job in $\mathcal{O}(N^2)$ which is the best asymptotic performance you can get (gotta read every character..).

Then, I did a series of checks to see if any K consecutive letters had been formed as a result. To do so, I decided that the simplest way to do so would be to just read in my array vertically, horizontally, and by diagonals and check to see a match. Rather than dealing with messy DFAs, a one-line regex check did the trick. Here, the regex I used was constructed as the following: ".*R{" + K + "}.*" for the red pieces. It’s a really simple one and basically it just looks at an arbitrary number of lead characters (“.*”) and then checks for exactly K characters of value “R” (R{K}) and then ignores an arbitrary number of characters that trail (“.*”). Of course, the regex string has to actually have a number in the place of K, which is why I constructed in this way. Similarly, to check for blue pieces, I just used ".*B{" + K + "}.*";.

You can check out the code to see how verbose, ugly, and unoptimized it is. But given that the largest value for N was 50, doing about 5 traversals of a 50×50 grid was acceptable. And in fact I was correct on this point. For the small input, the code run in 0.298s and for the large input, it runs in 0.980s. Good enough.

Posted by on May 24, 2010 in Uncategorized

Tags: , , ,

## Google Code Jam 2010 Qualifying Round Solutions (Part 3)

Finally, my solution for the Theme Park problem. For this one as well, I had a somewhat optimized solution that brought down $10^8$ iterations to at most 2000, with an average case of around 500-750 iterations. The solution, again in Java, is below:

import java.util.*;
import java.io.*;

public class Theme_large
{
String filename;
ArrayList<Group> groups;

public Theme_large(String f)
{
filename = f;
openFiles();
}

private void openFiles()
{
Scanner s;

try
{
s = new Scanner(new File(filename));
int ct;
long R, k;
int N;

ct = s.nextInt();

for (int i = 0; i < ct; i++)
{
R = s.nextLong();
k = s.nextLong();
N = s.nextInt();
groups = new ArrayList<Group>();

for (int j = 0; j < N; j++)

//System.err.print((i+1) + ": ");
output(i + 1, process(R, k, N));
//System.err.println();
}

s.close();
}
catch (Exception e)
{
System.err.println("I/O error: " + e);
System.exit(0);
}
}

private long process(long R, long k, int N)
{
long r = 0;
int n = 0;
long totEarn = 0;
long k_i;
int n_start = 0;
long first;

if (N == 1)
return groups.get(0).getSize() * R;
// loop as many times as necessary to start at same spot
// again.
while (r < R)
{
k_i = 0L;
n_start = n;

// check if you've already started here - a cycle
if (groups.get(n_start).isHit())
break;

// set earnings at start
groups.get(n_start).setEarn(totEarn);

while (true)
{
// if adding the next group will exceed k, break
if (k_i + groups.get(n).getSize() > k)
{
totEarn += k_i;
// hit the one you started on.
groups.get(n_start).hit();
groups.get(n_start).setR(r);
break;
}
else
{
k_i += groups.get(n).getSize();
n = (n + 1) % N;
}

// one group can't ride more than once at the same
// time!
if (n == n_start)
{
totEarn += k_i;
// hit the one you started on.
groups.get(n_start).hit();
groups.get(n_start).setR(r);
break;
}
}

r++;
}

if (r == R)

long loopCt = groups.get(n_start).getR();
first = groups.get(n_start).getEarn();

long quo = (R-loopCt) / (r-loopCt);
// how many full cycles will exist; round down

totEarn = first + ((totEarn - first) * quo);
// find that totEarn
r = loopCt + ((r-loopCt) * quo);
// effectively performed that many cycles

// do loop again to take care of remainder, ignore hits

while (r < R)
{
k_i = 0L;
n_start = n;

while (true)
{
// if adding the next group will exceed k, break
if (k_i + groups.get(n).getSize() > k)
{
totEarn += k_i;
break;
}
else
{
k_i += groups.get(n).getSize();
n = (n + 1) % N;
}

// one group can't ride more than once at the same
// time!
if (n == n_start)
{
totEarn += k_i;
break;
}
}

r++;
}

}

private void output(int caseNum, long result)
{
System.out.println("Case #" + caseNum + ": " + result);
}

public static void main(String args[])
{
Theme_large app = new Theme_large(args[0]);
}
}

class Group
{
private long size;
private boolean hit;
private long totEarn;
private long r;

public Group(long i)
{
size = i;
hit = false;
totEarn = 0;
r = 0;
}

public void hit() { hit = true; }

public boolean isHit() { return hit; }

public long getSize() { return size; }

public void setEarn(long e) { totEarn = e; }

public void setR(long rr) { r = rr; }

public long getR() { return r; }

}


In this solution, I realized that we should just think of the line as a cyclic graph component (or, equivalently, a circular linked-list) and think of the roller coaster car as moving around the cycle. Eventually, I thought, we’re going to start someplace we started before. And if we do it once, we’ll probably do it again and again. But we already know how much money will be earned by that! So, the code first begins executing normally, but dropping “markers” every time it starts somewhere. If it sees that it has already start here, we have just found ourselves a cycle! The additional fields in the Group class just store information about how many rides there are in a cycle and how much money is made in a cycle. From this information, we can jump ahead many, many simulations of the roller coaster until we have fewer rides remaining than the length of  a cycle. From this point on, the program executes in a very simple fashion to the end. A slightly better approach would be to store the amount made in each Group element and so compute the remaining amount in constant time. But nevertheless, I was happy with this solution. The solution, on a 2.53 GHz Core 2 Duo processor, ran in 0.442s.

And that concludes this Google Code Jam solution series.