Necessary and Sufficient

Code Jam 2010 started with a qualification round that was harder than previous years. The first problem, Snapper Chain, involves a series of N switches arranged in sequence, that toggle when you snap your fingers if they are receiving power. The problem asks that you indicate if a light plugged into the end of the chain of N switches will be on after K toggles. A brute force evaluation of the state of the light would have a run time ~ O(NK). This isn't feasible since the upper limits on N and K are 30 and 10⁸ respectively. That would take far too long to evaluate. Intuitively you know there must be some sort of pattern so in an effort to get clarity on it it's best to list the states for some toggles. So let's start with N=5 and see what we find...

Now it becomes clear how things work. The first switch toggles with every snap so it's immediately obvious that after an even number of snaps the light cannot be on. Conversely, if N=1 then the light would be on for all odd values of K. If N=2, then we can see that the light would be on when K=3, 7, 11, 15, 19, 23 27,31. That seems to be a pattern with common increments of 4. If N=3, the light would be on when K=7,15, 23,31 - common increments of 8. And for N=4, the light is on when K=15,31 - an increment of 16. It seems that the increments are powers of two. In other words, for a given N and K we can hypothesize that the light is only on when K satisfies the following formula:

Here c is any non-negative integer. In other words, the light is on after a certain number of snaps and it comes back on after a cycle of 2^N more snaps. Since N << K the summation term here is not a major concern. It is in fact the sum of a geometric progression so the summation could be replaced with a simpler term but since N is fairly small (<30) I didn't bother to optimise it further. I did add memoization to remember the sum of N items so we only ever need to calculate the sum of 30 items once. Here's some C# code to solve the problem:

   1:  using System;

   2:  using System.Collections.Generic;

   3:  using System.IO;

   4:   

   5:  namespace GoogleCodeJam2010.Qualificiation.SnapperChain

   6:  {

   7:      class Program

   8:      {

   9:          static void Main()

  10:          {

  11:              const string basePath = @"";

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

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

  14:   

  15:              var termSum = new Dictionary<int, ulong>();

  16:              var cycle = new ulong[31];

  17:              ulong sum = 0;

  18:              ulong current = 1;

  19:              for (int i = 0; i < 31; i++)

  20:              {

  21:                  sum = sum + current;

  22:                  termSum[i] = sum;

  23:                  current = current * 2;

  24:                  cycle[i] = current;

  25:              }

  26:              

  27:              int t = Int32.Parse(infile.ReadLine());

  28:              for (int caseNo = 1; caseNo <= t; caseNo++)

  29:              {

  30:                  var data = infile.ReadLine().Split(' ');

  31:                  int n = Int32.Parse(data[0]);

  32:                  ulong k = UInt64.Parse(data[1]);

  33:   

  34:                  string answer = "OFF";

  35:   

  36:                  if ((k - termSum[n-1]) % cycle[n-1] == 0)

  37:                      answer = "ON";

  38:   

  39:                  outfile.WriteLine("Case #{0}: {1}", caseNo, answer);

  40:              }

  41:              infile.Close();

  42:              outfile.Close();

  43:          }

  44:      }

  45:  }

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

What are the access modifiers available in C#?
Public, internal, protected, protected internal or private.

What is the difference between "protected" and "internal"?
Protected means within the same inheritance chain, internal means within the same assembly.

What access modifiers can be used against non-nested classes in C#?
Public or internal - the same goes for Interfaces. Note that non-nested classes cannot be private since it makes no sense for such classes to be private.

What access keywords can be used against nested classes in C#?
Public, internal or private.

What is the default accessibility of classes in C#?
Internal is the default if no access modifier is specified for a class and also for interfaces.

What access modifiers can be used against class members in C#?
Public, internal, protected, protected internal or private.

What is the default accessibility of class members in C#?
Private. Same goes for struct members.

Can you add access modifiers to interface members?
NO. The point of an interface is to describe a contract between an implementing type and users of the interface. Outside callers aren't going to care and shouldn't have to care about implementation. If an interface is public then every part of that contract has to be public, otherwise it would mean one thing to friend/internal classes and a different thing to everything else. If you need default implementation then it's best to use an abstract class.

Can you add access modifiers to Enum members?
NO. Enum members are always public, and so no access modifiers can be applied.

Does the "protected internal" access modifer mean OR or AND?
It means protected **OR** internal. Not both.

What is an "inconsistent accessibility" error?
A derived class, or a member function in another class that returns a type cannot expose a type with greater visibility than that defined in the class itself. It is a sign of a faulty design if this situation happens and the compiler tells you so.

What access modifiers can be used against structs in C#?
Public or internal. This is the same as non-nested classes.

What access modifiers can be used against struct member functions in C#?
Public, private, or internal. Note that struct members cannot be declared as protected because structs do not support inheritance.

How is a "Friend Assembly" created?
You can enable specific other assemblies to access your internal types by using the InternalsVisibleToAttribute. This attribute is applied to the AssemblyInfo.cs file of the assembly granting the permission, and takes a parameter indicating the assembly receiving the permission. Note that private member functions and types will still remain inaccessible to the friend assembly.

What access modifiers can be used against instance constructors in C#?
Any of the 5. Public, internal, protected, protected internal or private.

What access modifiers can be used against class destructors in C#?
None. It's not your call dude! The garbage collector owns this puppy.

What access modifiers can be used against user-defined operators in C#?
Only public. It makes no sense to redefine an operator for a given class or struct and then have an access modifier other than public on it.

What access modifiers can be used against delegates in C#?
The public, protected, internal, and private modifiers control the accessibility of the delegate type. Depending on the context in which the delegate declaration occurs, some of these modifiers may not be permitted.

What is the default accessibility of delegate types in C#?
Internal.

Can namespaces have access modifiers?
No. All namespaces are implicitly public.