Necessary and Sufficient

A few weeks back I posted about the JAOO conference giving it a strong thumbs up. Well, it's been less than a month and I've managed to find an event that tops even JAOO. It's the annual Google I/O conference which is Google's developer conference. I've not previously attended one but this year it was held in San Francisco and, despite the risk of swine flu, I gladly made the trek across the Pacific. And boy am I glad I did! The opening keynote on Day 1 was chugging along nicely with Vic Gundotra lauding the capabilities of the new HTML 5 standard with some interesting demos, and then there was the 'Oprah moment'....

"In this little box, you'll find a brand new Android phone with a paid-up AT&T SIM card (data-only) valid for 30 days, and I have one for you, you, and you, and you...Everyone, all 4000 of you will get one!"

Thanks Google. That's, what, a $600 phone? Not bad for a conference that costs less than that to attend. It was in fact a free HTC G2 phone which has impressive specs (accelerometer, touch screen, 3 Megapixel camera, slim form factor, long battery life, etc) but more importantly it runs the latest Android operating system. Within minutes I was connected to my gmail, calendar and a was surfing the web in landscape mode scrolling web pages up and down with my pinky realising how much better the mobile web experience is on a decent phone (and free data access). Don't want to type in that 7 or so character bit.ly url? Point your cameraphone at the QR code on the billboard and an application on the phone scans it, does the image recognition and pops the web browser AT THE URL you just took a picture of.

I'm really excited about the Android vs iPhone shake out. On one hand you have the open platform backed by "the open alliance" and on the other you have the closed-network, controlled walled-garden that is the Apple iPhone ecosystem. Haven't we seen this open-versus-closed ecosystem stouch before?

The keynote on the second day was no less enthralling. Google gave a sneak preview of an awesome new product they are building in the Sydney office - Google Wave. This product was the brainchild of the Rasmussen brothers, the technical geniuses behind the Google Maps product and the reason why Google opened an office in Sydney. Put simply, they have re-invented the communication mechanisms that are prevalent today (email, instant messaging, collaborative document editing) and produced a remarkable product that has a number of innovative features like concurrent, real-time editing, and change playback ability. It has the snappiness of a desktop application but it's a pure HTML5 web app so it comes without the painful deployment/update scenario that desktop apps are laden with. I truly hope more corporations look at it as an alternative to the extremely painful SharePoint product that has become prevalent. In corporations today a development team will share information via numerous mechanisms leaving vital shreds of information in email, IM, Office documents sitting on file servers, in-house wikis, the comments in the version control system, status notes in the task management system for the benefit of the team leader, and in a corporate SharePoint site because we don't have enough data islands already?!?! Enough already. We don't need more tools like SharePoint, we need one tool that replaces them all. That's a huge ask - displacing established mechanisms and hoping people change their habits - but that's why Google is Google. Hyper-ambitious and the "smarts" to have a decent crack at making it happen, and eventually be monetized.

I've been inspired by this product. There's a lot in the technical details that aren't initially appreciated. When you start to dive deeper you'll see the tremendous focus Google places on the user. Many corporations would cite the Pareto principle and not go the extra mile. Maybe because they can't? Or maybe because they believe products only have to be "good enough".

Well done, Lars, Stephanie and the Sydney googlers working on Wave.

Of course, in between 2 knock-out keynotes were also a huge number of very useful technical talks. Android, GWT and AppsEngine were heavily promoted, from an engineering point of view, whilst Wave also had a number of follow-up talks. The more I see of GWT, the more I like it. Anything that makes AJAX development faster and easier has my vote.

Definitely worth going. I'll be back for more some time soon.

Recently I've been digging through the C++ source code for the V8 JavaScript engine inside Google Chrome - in my mind, the best browser on the block by a long shot! Reviewing the internals has been a good refresher on efficient C++ programming though it is hard to adjust back to K-R indenting after using Allman indenting for so long with C# (I wonder how Pythonistas react to all those curly braces when jumping back to C/C++?). The design is very clean and the use of hidden classes for fast property access, and compilation to machine code (yes, MACHINE code) are just some of the secrets to its' speed. Of course with all these hidden classes floating around it was imperative they created an efficient Garbage Collector. I haven't yet been through the GC code so I won't elaborate however, according to Google, V8 uses a "stop-the-world, generational, accurate garbage collector". Looking forward to that! It should be interesting to contrast this approach to the fairly innovative concurrent GC architecture recently unveiled by several Microsoft researchers working on Haskell.

Here's the V8 Tech Lead, Lars Bak from Google, giving a very quick (5 mins) overview of the salient features of V8. He's Danish so trust me - it is English he's speaking:

If you suffer from the same "How does it Work" curiosity as I do you just point your favourite SVN client at:

svn checkout http://v8.googlecode.com/svn/trunk/

and you can read, and contribute to the code. The in-line comments are fairly minimal because the code is fairly self-documenting, but I did notice that the programming gurus at Google have been reading the same books I have. i.e Hackers Delight. The code extract below is from utils.cc. Which reminds me - I must write up a summary of the bitwise operations that come in handy more often than you think, but that's a topic for another post!

// Implementation is from "Hacker's Delight" by Henry S. Warren, Jr.,
// figure 3-3, page 48, where the function is called clp2.
uint32_t RoundUpToPowerOf2(uint32_t x) {
  x = x - 1;
  x = x | (x >> 1);
  x = x | (x >> 2);
  x = x | (x >> 4);
  x = x | (x >> 8);
  x = x | (x >> 16);
  return x + 1;
}

Following on from the text message outrage, the second problem in Round 1C was the "Ugly Numbers" problem. This puzzle involves counting the number of "ugly" numbers that can be formed from a given input string using only addition and subtraction operations. An "ugly" number is one that is divisible by either 2, 3, 5, or 7 (the one-digit primes).

Since there are 3 possible actions: addition, subtraction, and append; and D digits, clearly there are 3^D-1 possible numbers that can be made. Calculating each of these and testing for ugliness is not at all feasible since D can be anything up to 40.

So first let us put our number theory caps on and consider the algebraic properties of the ugly numbers. Listing a few of the ugly numbers is a good starting point:

2, 4, 6, 8, 10, 12, ...
3, 6, 9, 12, 15, ...
5, 10, 15, 20, 25, ...
7, 14, 21, 28, 35, ...

Note that 9 and 10 are ugly numbers because they are divisible by 3 and 5 respectively. However the addition of these two numbers is 9+10=19 which is not ugly.

Also note that 20 and 7 are ugly numbers because they are divisible by 2 and 7 respectively. However the difference of these two numbers is 20-7=13 which is not ugly.

What this tells us is that both addition and subtraction are not closed over the set of ugly numbers.

So how does that help? It doesn't really. It just tells us that a dynamic programming approach based on the number of ugly numbers found using a smaller subset of the digits is not going to work since we don't have the overlapping sub-problem property with this approach.

It is also interesting that the ugliness criteria is based around prime numbers, specifically the set {2,3,5,7}. Hmmm, that might be our hint. Since prime number are only divisible by themselves and 1, then the greatest common divisor (GCD) of any two numbers in this set must be 1. In other words the set is pairwise coprime, and therefore the lowest common multiple (LCM) of the set must be the product: 2*3*5*7=210.

To ascertain ugliness we could write a function like this in C#:

        static bool isUgly(int x)
        {
            return (x%2 == 0 || x%3 == 0 || x%5 == 0 || x%7 == 0);
        }

However, since 210 is the LCM of all the one-digit primes we can pass in x'= x % 210 to this function and still get accurate ugliness checking. That is, the ugliness of x is going to be equivalent to the ugliness of x % 210 because 210 is a multiple of each of the one-digit primes. This is definitely something we can exploit because modular arithmetic has nice algebraic properties. Specifically, if:

So this means that we can take an iterative approach and consider the first i characters, determine all possible resulting numbers but instead of storing all of them we store only the result mod 210. This limits the possible output to 210 numbers (0-209) and also allows us to re-use the results of earlier calculations since addition and subtraction are closed over Z₂₁₀. This now gives us the overlapping sub-problem property that we need for dynamic programming.

First, define c_j,d to be the number of possible ways of producing a mod 210 residual of j when we consider only the characters in the given input string up to, and including, index d (assuming a zero-based index). Since j ranges from 0 to 209 and d ranges from 0 to D-1, we can represent this as a matrix as follows:

And the solution to the problem would be:

where isUgly(x) returns 1 if x is ugly, and 0 otherwise.

Now consider the j-th column vector in this matrix, c_j, and how it can be calculated from the column vector immediately to its left, c_j-1.

All we need to do is to go through all 210 elements of c_j-1 and perform three operations on each non-zero count found: an addition (mod 210), a subtraction (mod 210) and the append operation putting the results of all three into their respective rows in c_j. Addition and subtraction are fairly easy (see formula below) with the only trick being modular arithmetic on negative numbers (you need to add 210), however the append operation is a bit more complicated.

To do the append operation for a given element of the column vector consider the possible ways the residual (x) represented by the count could have been derived. It could be the sum of 2 numbers or the difference of 2 numbers:

Here we know the value of x but we don't know the operands (a and b) or the operator used. Thus we need to maintain more information than just the counts mod 210 in order to solve the problem. If we were to store the position of the last operator and what that operator was (addition or subtraction) for the count we would be able to derive both operands, and thus derive the value of the append operation. This can be done as follows (with all calculations done mod 210):

1. Use d and the position of the last operator to derive b. b will be the number formed by all digits from the position of the last operator to d (mod 210)
2. Use x and b and the sign of the last operator to derive a. That is: a = x - b (mod 210) if the last operator was addition; a= x + b (mod 210) if the last operator was subtraction.
3. Calculate b', the new value of b by appending the new digit to the end of b
4. Calculate the new residual value, x' = a + b' (mod 210) if the last operator was addition, otherwise x' = a - b' (mod 210).

I used a simple struct to hold the count and the position of the last operator along with the operator type. If the position is positive or zero, it implies addition was the operator. If the position is negative it implies that subtraction was the last operator. This enables us to store 2 bits of information in a single signed integer. Furthermore, because a given residual can be obtained by numerous combinations of operators and operands we need to store a list of these structs for each point in the matrix above.

Here's my C# code for this problem:

   1:  using System;

   2:  using System.Collections.Generic;

   3:  using System.IO;

   4:  using System.Linq;

   5:   

   6:  namespace GoogleCodeJam.UglyNumbers

   7:  {

   8:      class Program

   9:      {

  10:          const int lcm = 2 * 3 * 5 * 7;

  11:   

  12:          static void Main()

  13:          {

  14:              

  15:              const string basePath = "";

  16:              var infile = new StreamReader(basePath + "large.txt");

  17:              var outfile = new StreamWriter(basePath + "output.txt");

  18:   

  19:              int testCases = Int32.Parse(infile.ReadLine());

  20:              for (int caseNo = 1; caseNo <= testCases; caseNo++) 

  21:              {

  22:                  string input = infile.ReadLine();

  23:                  var c = new List<Pair>[lcm,input.Length];

  24:   

  25:                  for (int y = 0; y < input.Length; y++)

  26:                  {

  27:                      int digit = input[y]-'0';

  28:   

  29:                      if (y == 0)

  30:                      {

  31:                          c[digit, y] = new List<Pair> {new Pair(1, 0)};

  32:                          continue;

  33:                      }

  34:                          

  35:                      for (int x = 0; x < lcm; x++)

  36:                      {

  37:                          if (c[x, y - 1] != null && c[x, y - 1].Sum(p => p.Count) > 0)

  38:                          {

  39:                              if (c[(x+digit)%lcm,y] == null)

  40:                                  c[(x+digit)%lcm,y] = new List<Pair>();

  41:   

  42:                              c[(x+digit)%lcm,y].Add(new Pair(c[x,y-1].Sum(p=>p.Count),y));

  43:   

  44:                              if (c[(x-digit+lcm)%lcm,y] == null)

  45:                                  c[(x-digit+lcm)%lcm,y] = new List<Pair>();

  46:   

  47:                              c[(x-digit+lcm)%lcm,y].Add(new Pair(c[x,y-1].Sum(p=>p.Count),-y));

  48:   

  49:                              foreach (var pair in c[x,y-1])

  50:                              {

  51:                                  int ind = pair.LastSignPosition;

  52:                                  var b = Parse(input.Substring(Math.Abs(ind),y-Math.Abs(ind)),lcm);

  53:                                  var bDash = Parse(input.Substring(Math.Abs(ind),y-Math.Abs(ind)+1),lcm);

  54:   

  55:                                  if (ind >= 0)

  56:                                  {

  57:                                      if (c[(x-b+bDash+lcm)%lcm,y] == null)

  58:                                          c[(x-b+bDash+lcm)%lcm,y] = new List<Pair>();

  59:   

  60:                                      c[(x-b+bDash+lcm)%lcm,y].Add(new Pair(pair.Count,ind));

  61:                                  }

  62:                                  else if (ind < 0)

  63:                                  {

  64:                                      if (c[(x+b-bDash+lcm)%lcm,y] == null)

  65:                                          c[(x+b-bDash+lcm)%lcm,y] = new List<Pair>();

  66:   

  67:                                      c[(x+b-bDash+lcm)%lcm,y].Add(new Pair(pair.Count,ind));

  68:                                  }

  69:                              }

  70:                          }

  71:                      }

  72:                  

  73:                  }

  74:   

  75:                  long sum = 0;

  76:                  for (int x = 0; x < lcm; x++)

  77:                      if (x % 2 == 0 || x % 3 == 0 || x % 5 == 0 || x % 7 == 0)

  78:                      {

  79:                          if (c[x, input.Length - 1] != null)

  80:                              sum += c[x, input.Length - 1].Sum(p => p.Count);

  81:                      }

  82:   

  83:                  // write out the results

  84:                  outfile.WriteLine(String.Format("Case #{0}: {1}", caseNo, sum));

  85:              }

  86:              infile.Close();

  87:              outfile.Flush();

  88:              outfile.Close();

  89:          }

  90:   

  91:          static int Parse(string num, int mod)

  92:          {

  93:              //return UInt64.Parse(num) % mod;

  94:              int result = 0;

  95:              for (int i = 0; i < num.Length; i++ )

  96:                  result = (result*10 + (num[i] - '0')) % mod;    

  97:              return result;

  98:          }

  99:      }

 100:   

 101:      internal struct Pair

 102:      {

 103:          public long Count;

 104:          public int LastSignPosition;

 105:   

 106:          public Pair(long count, int lastsign)

 107:          {

 108:              Count = count;

 109:              LastSignPosition = lastsign;

 110:          }

 111:      }

 112:  }