Uncategorized

## Adaptive DNS pre-resolution in Google Chrome

I've stated it before, but I'm a big fan of the Google Chrome browser because it's so damn fast! Apart from the awesome V8 JavaScript engine, one of the things that makes it fly is some clever DNS resolution. It's a great example of using concurrent programming to hide latency. In other words, they can't make DNS resolution go any faster but they can pre-fetch and cache to give the illusion of increased speed when you need to resolve.

Here's a great short video from Jim Roskind to explain it in simple terms:

Uncategorized

## Google Code Jam 2010: Snapper Chain

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 108 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...

 K State 0 00000 1 10000 2 01000 3 11000 4 00100 5 10100 6 01100 7 11100 8 00010 9 10010
 K State 10 01010 11 11010 12 00110 13 10110 14 01110 15 11110 16 00001 17 10001 18 01001 19 11001
 K State 20 00101 21 10101 22 01101 23 11101 24 00011 25 10011 26 01011 27 11011 28 00111 29 10111 30 01111 31 11111

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 2N 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:  }`

Uncategorized

## GCJ Africa 2010 - Reverse Words

The Reverse Words problem in the qualification round of Google Code Jam Africa 2010 is trivial. You are given a bunch of space separated words that you need to re-order (just the words, not the characters within the words). The number of words is, at most, 1000 so doing everything in memory is entirely feasible on a modern computer. Just be sure to watch out for the separating spaces in the result. You don't want any leading/training spaces.

Here's some simple C# code that solves it [running time is O(n) for n words. Space required is solely to hold the input values plus a small constant overhead to build the result]:

using System;

using System.IO;

using System.Text;

{

class Program

{

static void Main()

{

const string basePath = @"C:\";

var infile = new StreamReader(basePath + "B-large-practice.in");

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

int n = Int32.Parse(infile.ReadLine());

for (int caseNo = 1; caseNo <= n; caseNo++)

{

var words = infile.ReadLine().Trim().Split(new []{' '});

var answer = new StringBuilder();

for (int i = words.Length-1; i >= 0; i--)

answer.Append(" " + words[i]);

outfile.WriteLine("Case #{0}: {1}",

}

infile.Close();

outfile.Close();

}

}

}

Next »