Necessary and Sufficient

I recently saw a nice chart on Kathy Sierra's blog depicting the user's hierarchy of needs. What immediately struck me was the different aim points that different types of organisations shoot for, and the level of satisfaction that team members get from being exposed to projects which exhibit these various aim points.

Before we go much further lets take a look at the diagram.

Along the left hand side are my annotations to the original diagram which indicate some "aim points" relative the to needs scale given in the centre column that I've observed amongst various organisations I've worked for over the years. Now, sure, there are going to be some gross generalisations here but bear with me and you'll see the big picture I'm getting to.

Starting at the very bottom, consultancy type organisations, or businesses building internal line-of-business applications are not trying to create show-stopper software. They are trying to meet a need at minimal cost. That need is usually manifest in a specification or briefing document and the main emphasis of the team is to give the client this functionality - no more and no less - whilst trying to keep budget under control. Programmers who DON'T want to become rock stars by going above-and-beyond enjoy this kind of work, and project managers should staff their teams with such programmers. Technical geniuses are wasting their times on such projects and will be out of there faster than you can say "internet job board". Good things for management to focus on during interviews are adherence to deadlines since the scope has already been mandated more or less.

A little further up the scale we have organisations selling the software / service they create, labelled here as "shrink wrapped" despite the fact that most software is downloaded these days. Such organisations are more focused on the quality of their offerings as it has a direct impact on their business profitabilty. Often these organisations have multiple product offerings and can take a broadshot or portfolio-based approach to product management where the more successful products subsidise the not-so-successful products in the portfolio.

In order to differentiate their products from those of their competitors and attract a user-base, the software produced needs to be considerably better than average. That entails more emphasis on usability and internal product efficiency. You'll find all manner of programmers in these projects as they require a mix of people who really care and those that prefer to get the job done with minimial fuss. Regrettably, what most of these organisations fail to recognize is the economic benefits achievable by realising the negligible marginal costs associated with quality improvements. That is, the additional cost by doing extra work to improve the quality of the product can be apportioned over the entire user-base since the cost of duplicating software is effectively zero, hence the marginal cost of that quality improvements is negligible.

At the furtherest extreme of the chart we have the must-win software projects. In these cases the organisation is usually solely devoted to, and completely dependent on a sole product offering. Internet startups are the classic case of this hence I've labelled this aim point as such. Since the survival, not just the success, of the firm is entirely dependent on the product/service being developed it has no choice but to be best-of-breed, or pitched at a price point compelling enough to move customers from incumbent products to your own. This is not an easy thing to do and the failure rates of such companies are usually very high because of this. If you are heading in this direction you need rock-star programmers. A group of mediocre programmers will, more than likely, not care enough to pursue the levels of technical excellence and user harmony you need to shoot for, and most definitely will lack the ability to, as Joel Spolsky elegantly put it, "hit the high notes" ! Technical teams working on these projects will often be doing very innovative things technically and will be paying particular attention to what it's early adopters and existing users are telling it about the product.

So at the end of the day what does all this mean? Well, technical managers need to be realistic about what their aim points is - some simple economics helps - and staff their projects accordingly. On the flip side, developers should, based on their own personal ambitions, seek out the types of projects that have aims aligned with their personal goals. If there is a mismatch then job satisfaction is guaranteed to be unacceptably low. Some folks refer to this as "cultural fit" but I'd just say it's good management and common sense.

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:  }