Facebook Korn Shell Puzzle - heuristic solution

The original problem description is available here at Facebook website (Korn Shell).

The example itself gives a hint on how to start the thinking:
Mike Korn <-what you typed originally
Jodt Dabn
Kafh Flcn
Dlmw Mgzn
Fgjq Jixn
Mike Korn <-what appears eventually

For each character, there is group of characters related to it and they form a closed group {M, J, K, D, F}, {O, A, L, G, I}, {T, H, W, Q, E}, {B, C, Z, X, R}, {N}, the period of each group is 5, 5, 5, 5, and 1 respectively in this case, so the number required to get back to Mike Korn from initially typing this name would be least common multiplier of those period, which is 5 in this case.

Now if we generalize this problem for any name, then the question can be viewed as follow:
For a name containing n distinct characters, how do you divide 26 characters into m (m <= n) groups so that the least common multiplier (LCM) of the cardinality of these m groups can be maximized. The valid value for n is between 1 and 26, but it is obvious that even if n=26, you may still want to divide the characters into fewer than 26 groups to achieve max value.

Let's focus on finding the max value if we divide the 26 characters into m different groups. Let's define f(n, m) as the max value for dividing n characters into m groups.

For m=1, it is easy, the max period is n if we view the n characters as a single group. f(n, 1) = n, n = 26 in the facebook puzzle.

For m=2, we need to divide the n characters into two groups, the max period is

f(n, 2)
{
  max = 1;
  for i = 1 to n/2
    if LCM(i, n-i) > max {max = LCM(i, n-i); }

  return max;
}

For general m, the problem is a bit trickier, we can try to use the following recursive function to get f(n, m)

f(n, m)
{
  if n = m { return 1;}
  if m = 2 { return f(n, 2) as calculated above in m=2 case;}

  max = 1;
  for i=1 to n- m + 1
    if LCM(i, f(n-i, m-1)) > max { max = LCM(i, f(n-i, m-1); }

  return max;
}

If the top-down recursive approach is not preferred, then we can convert the above function into a bottom-up array calculation as follows:

Initialize f[n, n] to all 1;

for i = 1 to n {
  for j = 1 to i {
    if i = j then f[i, j] = 1;
    else if j = 1 then f[i, j] = i;
    else {
      for k = j-1 to i-1
        f[i, j] = max(f[i, j], LCM(i - k, f[k, j-1]));
    }
  }
}

Once you get f[n, m], then for a particular n, the max value will be the one given by max (f[n, i]) where i=1 to n.

In our case, n=26, the result shows that when i=5, you achieve the max value 1260. This means that when the name contains at least 5 distinct characters then there is a way to design the keying function so that you need to type 1260 times to get the correct name. The keying function is designed by dividing 26 characters into groups of 1, 4, 5, 7, and 9, each group containing at least one of the distinct characters in the name.

Now, the above solution gives us O(n^3) time complexity which is awful. Is there anyway we can optimize the solution? After let my mind wondering off some time at work :-) (sorry, I can't help but thinking about this thing ...), it seems that there might be another simpler way to formulate the solution:

Instead of looking at f(n, m), where m is the distinct number of groups that we need to divide the n characters, we can just look at the f(n), which represents the max value obtained by dividing the n character into n or fewer than m groups. Obviously f(1) = 1. The problem now becomes: given f(i) where i < n, how do we get f(n)? We can see that the new divisions allowed are:
- putting all n into one group
- putting i (1~n-1) into one group, while the rest are distributed based on the best case in f(n-i).
As a result, we get the following simplified algorithm:

initialize all f[n] to 1;

for i = 1 to n
   for j = 0 to i-1 
    if(j=0) f[i] = max(i, f[i]);
    else f[i] = max(f[i], LCM(i-j, f[j]);

return f[n];

Again if n=26, then f(n) = 1260. Note that j=0 in the above code is important to cover the boundary case; if you start from j=1 the calculation will be off by one (f[n] actually gives the value for n-1).

Other stuff related to this problem:

1. Function for calculating LCM:

LCM(i, j)
{
  k = i*j;

  //calculate the Greatest common divisor of i and j;
  while i!= 0 {
    if i < j {
      tmp = i; i=j; j=tmp;
    }
    i = i%j;
  }
  return k/j;
}

2. You can notice that in both the complex solution and the simpler solution, there is an important assumption, the calculation of f(n) (f[n, m] in the first case) can be build upon the value calculated in f(i) (f[i, m-1] in the first case) where i is smaller than n. Still need to find a way to prove the above algorithms are correct based on this assumption.