Google Code Jam 2016

Another year, another Google Code Jam. Similar result this year: made it through qualification and Round 1, but got stymied in Round 2. The competition seemed tougher this year both in quantity and quality. Though the bar for qualification was raised this year, 22,000 coders made it to Round 1, up from 12,000 last year. There are three time slots for Round 1 with 1000 advancing from each slot. In the first slot, over 1000 coders had a perfect score (not me), and as a result 40+ perfect scores didn’t advance from that slot (time was the tie breaker).

Fortunately, the second slot was a little more forgiving and I was able to advance with a score of 56/100, good for position 933. The problem I missed, Technobabble needed a Maximum Flow algorithm for an efficient solution, and I’ve since added one to my toolbox.

In Round 2, I got stuck on the first problem which involved a giant rock-paper-scissors tournament. I did the small version with brute force, and tried multiple algorithms to increase efficiency for the large problem, mostly relying on memoization and symmetry. However, I needed to step back and rethink the problem instead of blasting ahead with code. I eventually did figure out the efficient solution just after time expired. The time pressure of the competition has an effect on thinking that needs to be overcome.

I’ve been using a C++ parallel processing harness for these problems, and that may have made me less concerned about finding the very best algorithm. When you have the right solution, it usually takes less than a second to execute even though you’re given eight minutes to submit results. If a subpar algorithm takes, say, 30 minutes, for all the test cases, there is a chance it could still finish in time with parallel solving of the test cases. But this time, my subpar algorithm would take many hours to execute, so the parallelization couldn’t save.

With that ringing endorsement, I’ve put my parallel solver harness on Github as parallelcodejam. I’ve used it a few years, and I think it was only beneficial once.

The parallel code does have one nice idea, I think, which is to use an atomic integer as an index into a work queue. That way, the queue itself doesn’t need to be thread-safe, and the synchronization overhead is minimal.

Google Code Jam 2015 Round 1

I’ve made it through the Qualifying Round and Round 1 of this years Google Code Jam. You get three chances at Round 1, and this is the first year for me to advance after only one try. This was also the first time I used C++ instead of Java for the contest.

The most interesting problem to me in the qualifying round was Infinite House of Pancakes, where you essentially have to reduce a set of integers to 0 over a sequence of turns with two options at each turn: reduce every number by 1 or split any single number into two numbers (with the same sum). I correctly figured out you could do all the splitting up front, and coded an algorithm that would split the biggest number in half at each turn until the gain wasn’t worth it.

Seemed reasonable, but it failed to pass the small test set for the single number {9}. My algorithm would split it into {5, 4} and then reduce them down in 5 more steps, but it would be better to split it into {6, 3} followed by {3, 3, 3} and then reduce down in 3 more steps. So my halving algorithm had to be rethought. Fortunately there’s no real time pressure in the qualifying round, and I was able to work out a better algorithm that passed the small and the large test cases.

For round 1, the first problem, Mushroom Madness, was straightforward, and I had it completely done in under 15 minutes. I also figured out how to do the third problem, Logging, pretty quickly, but coding it was tricky and took most of my time. The problem involved convex hulls over point sets and I didn’t have any geometry routines handy to speed up the process. I had to get lucky that my code worked without too much debugging.

The second problem, Haircut, was the most interesting for me even though I couldn’t figure it out completely during the contest time limit (150 minutes). Given B barbers operating at different constant speeds and a queue of N customers, you had to figure out which barber the Nth customer would get. Seemed like a straightforward use of a priority queue to simulate all N haircuts. However, just as I was starting to code I noticed the problem said that N could be up to 1 billion, even for the small problem. A priority queue simulation would be about O(N * log(B)) — great for lots of barbers but not for lots of customers.

I coded the simulation anyway hoping it would either trigger a better idea or would be fast enough for the 4 minute time limit (after all, my Mac Pro can do billions of operations every second). It wasn’t fast enough, but I thought of looking for a cycle and noticed the limits for the small problem were 5 barbers taking at most 25 minutes each. That meant I could afford to simulate the least common multiple (LCM) of all the barber times after which the pattern would repeat, and that worked for the small test case.

The large test case allowed 10,000 barbers, and I knew the LCM would be way to big to simulate and didn’t even attempt it. Not having any better ideas, I moved on the the last problem which was fortunate because I needed almost all of the remaining time for the Logging code.

After sleeping on it (did I mention the contest started at 9pm local time on a Friday night?), I worked out a solution to the large Haircut problem the next day. Though I couldn’t compute b(n) in time, I could compute the inverse, n(b), fairly quickly. Since n(b) is monotonic, I could use a binary search to find where n(b) became the n I was looking for.

Implementing the binary search was a different story because part of my reason for using C++ was to force myself to learn more of the STL and idiomatic C++11. STL has a binary search function called lower_bound which expects to operate on iterators over a container. I couldn’t find a good way for it to operate on an indirect evaluation of a function. I tried defining a custom iterator, but it felt wrong, partly because each iterator needs its own reference to the function. I’ve since discovered Boost ranges which might do the job.

Instead I wrote my own indirect version of lower_bound that took an integer range and a function object to call.

// returns lowest number, n, for which f(n) >= value
// f must be non-decreasing
template<typename I, class T, class F>
I lower_bound_eval(I first, I last, const T& value, F f) {
   I count = last - first;
   while (count > 0) {
      I i = first;
      I step = count / 2;
      i += step;
      if (f(i) < value) {
         first = ++i;
         count -= step + 1;
      }
      else
         count = step;
   }
   return first;
}

That worked, though it took me many hours more than the problem allowed. Without the 22 points for that problem, my final score was 78/100 which put me at #337 out of about 6000 in that round with the top 1000 advancing.

Data Science Specialization at Coursera

Last year, I took the nine online courses in the Data Science Specialization offered by Johns Hopkins University via Coursera. It could have been called “Data Science with R” since one whole course and a good part of the other courses were more about R programming than data analysis. I certainly learned more about R and the R ecosystem than about statistics and data science, but I already had some knowledge of the latter. The nine courses are:

  1. The Data Scientists Toolbox
  2. R Programming
  3. Getting and Cleaning Data
  4. Exploratory Data Analysis
  5. Reproducible Research
  6. Statistical Inference
  7. Regression Models
  8. Practical Machine Learning
  9. Developing Data Products

There’s also a “capstone” course/project, but it’s not offered as often, and the timing didn’t work for me.

Course Structure

Each course was four weeks, and the pattern for most weeks was about 30 minutes of video lectures and a multiple choice quiz. Some courses also had a project involving some data analysis, and those were the most educational parts of the series. There were also practice assignments and online discussion forums, but I found the Coursera site too sluggish to really use those casually.

As would be expected from courses like this, what you get out depends on the extra effort you put in. Someone completely new to the material would have to spend a lot of self-learning time because they’re not going to learn technical material like programming and statistics from a few video lectures. Unfortunately for me, the multiple choice quizzes made it a little too easy to get by with little effort. That’s partly a necessity of an online course, but being able to take each quiz three times seems to undermine any rigor. If you can eliminate just one of the four choices, you’re guaranteed to get each question correct by the third try.

Positives

Instructors. One thing that kept me in the series (besides my stubbornness to finish what I started) was the quality of the instructors, Brian Caffo, Jeff Leek and Roger D. Peng. They obviously have an enthusiasm for the subject and did a great job organizing the material. I especially like that they would often do live R coding during the lectures (I’m sure there were some edits, but still…). Sometimes that’s where the best R tips were learned.

Material. I liked that they spent a good amount of time just on programming and just on reproducible results, two topics that could be ignored or brushed over and still pass for data science. For the modeling, they made of point of avoiding linear algebra, which was a nice change from the standard approach.

Projects. While still constrained by the time available, these longer assignments forced you to apply the material to perform some basic analysis and publish the result. The projects used real data sets which often required some clean-up/preprocessing, which was a good lesson in itself.

Negatives

Peer grading. The longer assignments were better measures, but due to the compressed timing, they had to be kept pretty simple, and due to the large number of students, they had to be peer graded. For peer grading, each student had to grade four others. I can only hope they required some sort of agreement among duplicate graders because the grading guidance was minimal and coarse. (Is there a model provided? Yes/No. Is the model correct? Yes/No…)

The one course I didn’t get high marks in was the course I expected to be my best: Exploratory Data Analysis. I didn’t get good scores on the the long assignment from the peer grading. I knew I wasn’t strictly following the assignment guidelines, but I hoped the graders would be more flexible. The assignment called for a report with something like three pages of text and an appendix with two pages of graphs. I prefer to put the graphs inline with the text, but some graders stuck with the literal guidelines and gave my zeros for that part of the grading (there was often no way of giving partial credit).

Coursera. Besides the sluggish forums and grading limitations already mentioned, I would like to go back to review parts of the material (partly so I could be more specific in this review), but the archives are no longer available. Last month at least some of the course archives were available, but now none are. Given the scope of the material, providing later access seems essential.

Bottom Line

For someone new to the field, I think these courses will be too brief to learn the material well, but they provide a great tour from some great tour guides and will help frame further study.

Benchmarking resizable arrays versus linked lists in C++

The second half of Herb Sutter’s recent talk, “Modern C++: What You Need to Know,” explores the question of how many items do you need before it’s better to use a std::list instead of a std::vector for an insertion sort. The conventional wisdom is that eventually the cost of moving half or so of the vector to make room for a new element will overtake the overhead of the linked list traversal. However, testing showed the answer is never and underscored the importance of memory locality in modern computers (with lots of prefetched cache data).

I decided to try it out on my own machine, but before I got too far with the code I looked around to see if someone already had code I could use. Soon enough, I found C++ benchmark – std::vector VS std::list VS std::deque on Baptiste Wicht’s blog. He ran lots of tests (not just insertion and removal)  on lots of data types (not just integers). Like Herb Sutter, Baptiste also found arrays to be faster than linked lists for small objects, but lists were better for large objects. The meaning of large varied depending on the algorithm. For sorting, large was 16 bytes, for insertion, large was more like 64 bytes. He didn’t explore arrays of pointers to large objects.

In trying out his year-old code on my Mac, I encountered a couple compile errors and one logic error. Since the code was on GitHub, I thought it would be a good chance to try it out. I set up a GitHub account, forked his code into my account, fixed the issues, and made a pull request for my changes to be merged back into Baptiste’s original code. A couple days later, he accepted the changes — the internet works!

Here are some results from my runs. I went up to n = 1,000,000 for two operations and two data sizes.

vectlist

 

Looks like for my PowerMac, large is somewhere between 8 and 32. The real hero is deque, which is segmented vector that can easily grow at both ends.

 

Hacker Cup 2014 Round 1

I was both disappointed and happy with my Round 1 results in the Facebook Hacker Cup (scoreboard and problems). I was disappointed that I got two of the four problems wrong, but happy I did well enough to advance to round 2 (and came close on the two I missed). The round lasted 24 hours, so I should have taken the time to study and test the problems more that I did.

Problem 1 was essentially about representing a number in a given base with a given digit alphabet. The only trick not covered in the test set was the case where the “base” was 1. Fortunately, I caught that before submission.

Problem 2 involved finding the optimal strategy for a coin game. Not much programming involved, but I was off in my analysis of what the optimal strategy was and missed this one.

Problem 3 required a search for the longest path through a grid with a couple constraints, including being limited to one “backward” string of moves. I used a dynamic programming solution with a 4D array to represent the longest path from a given position (2D), backward-usage (1D) and incoming direction (1D).

Problem 4 required the most analysis, which I mostly got right, but overlooked one detail. The problem boiled down to adjusting a set of up to 20 numbers so that the sum is minimal and every pair has the same greatest common divisor (GCD). My optimized search of the problem space seemed to be good enough, but the detail I missed was in handling of GCD when one of the numbers was 0.

The moral (at least for such lengthly rounds) is to augment the test cases before declaring victory and submitting. Doing so saved me for problem 1 and could have saved me for problem 2. However, the next round lasts only 3 hours, so there is more cost to doing more testing.

Round 2 Update: I completed one problem and thought I completed a second, but had a problem submitting the solution. I accidentally ran my code twice and then got an “invalid character” error after trying to clean up the outputs. However, I had no time for the others and wouldn’t have advanced anyway.

Hacker Cup 2014 Qualification Round

I passed the Facebook Hacker Cup qualification round last week-end (problems). Unlike other rounds, there’s no real time pressure in the qualification round. I normally use Java for these competitions since the most productive IDE I have is JetBrains’ IntelliJ IDEA. However, since I’m trying to become more adept at the new idioms of C++11, I also tried that (using Xcode) for two of the problems.

The first problem involved identifying a square of ‘#’ characters in a field of ‘.’ characters. After some messy Java code that analyzed the grid as it was read in, my C++ effort read in the whole grid into memory first. The following C++ felt decent for finding the first and last rows not consisting of all ‘.’ characters:

string blank(n, '.');
auto isntBlank = [&blank](const string & row) { return row != blank; };
auto firstRow = find_if(grid.begin(), grid.end(), isntBlank);
auto lastRow = find_if(grid.rbegin(), grid.rend(), isntBlank);

However, I couldn’t subtract those variables to find the difference because the types are different (one is a forward iterator and the other is a reverse iterator). The base() method converts a reverse iterator to the underlying forward iterator, so the count is determined by

  lastRow.base() - firstRow

A few applications of similar find logic provided a solution that contains no explicit loops, which is a nice result.

I implemented the second problem dealing with basketball substitution patterns using a pair of priority queues for each team: one queue for the players on the court and another for the players on the bench. I don’t think there’s a clean way to allocate an array of generic collections in Java, and I ended up with the following for the bench of the two teams:

@SuppressWarnings("unchecked")
PriorityQueue[] bench = new PriorityQueue[2];
...
bench[t] = new PriorityQueue<>(n, new Comparator() {
   @Override
   public int compare(Student a, Student b) {
      if (a.minutes < b.minutes)
         return -1;
      if (a.minutes > b.minutes)
         return 1;
      if (a.draft < b.draft)
         return -1;
      if (a.draft > b.draft)
         return 1;
      return 0;
   }
});

C++ has a built-in pair<> template class that makes the comparison part more compact, but I never found a clean way to declare the array. For each type of queue, the players and the bench, requires a different comparison function, so it can’t be built-in to the object class itself. There’s a constructor to supply a separate comparison function for that case, but I couldn’t get the constructor argument to match the generic comparison type so I ended up specifying the type in the template argument list. It seems to violate the C++ DRY goal, but it’s not too bad using a typedef.

auto benchLess = [](Student const & a, Student const & b)
   { return make_pair(a.minutes, a.draft) > make_pair(b.minutes, b.draft);};
typedef priority_queue<Student, vector, decltype(benchLess)> BenchType;
BenchType bench[]{ BenchType(benchLess), BenchType(benchLess)};

The third problem involved a dynamic programming style probability calculation and contained the statement, “It is guaranteed that the output is unaffected by deviations as large as 10-8. ” I’m now not sure what that means. I took it to mean that conditional probabilities could be rounded to 10-8 and values less than 10-8 could be ignored in order to get the required 6 digits on accuracy. As an optimization I ignored values less than 10-10. However, that led to one of my answers having just less than the required accuracy, so there must be some other meaning to the statement.

Hoping to try round 1 next week.

 

Google Code Jam 2013 Round 1

Like last year, it took me three attempts to get through Round 1 of the Google Code Jam, having to get compete at 5am Sunday. For the first two attempts, I essentially skipped the easy (small) problems and went straight into solving the large versions of each problem, which would simultaneously solve the small problem, too. But that strategy didn’t make the cut (top 1000 scores), so I focused on solving the small problems first for Round 1C and finished in the top 300 to move on to Round 2.

I did solve the large version of Problem A, Consonants, after working out a dynamic programming solution. And I almost finished the large version of Problem C, The Great Wall, but it took me an extra 20 minutes after the contest ended to get it right. It’s nice that Google lets you keep trying for practice even when the contest is over.

In finishing the problem, I learned about a Java API I didn’t know about, NavigableMap. I was looking for something like C++’s std::map::lower_bound/upper_bound for iteration through a subrange of an ordered map, but I didn’t see anything in the Java Map API. Fortunately I found NavigableMap, whose floorEntry and higherEntry provide similar functionality. The problem called for keeping track of repeated attacks/fortifications to a wall. For the small solution I stored the wall as an array using an element for each unit-length segment, but that wasn’t efficient enough for the large solution. I needed each stored element to represent a run of similar segments and support splitting of segments as new attacks occurred while staying ordered for fast look-up. The balanced binary tree implementation of NavigableMap fit the bill.

A great feature of Code Jam is being able to examine other competitors’ entries after the contest is over. I checked one top scorer’s solution and he didn’t use such a data structure. Instead, he made two passes through all the wall attacks. On the first pass he recorded where all the splits might occur. Then he could allocate an array for those segments without needing to split elements on the second pass.