Lost In Permutation

FizzBuzz without multiplication or division, part 3

This is the finale of a three-part series: Part 1, Part 2.

FizzBuzz is a good problem for interviews because it allows you an adaptive scale of interesting things to ask. If the candidate struggles to get the most basic solution working, you can spend the whole hour working with them on improving their solution, and let them leave with a good feeling about your company. If the candidate is a super-literate programmer, you get to explore issues such as testing, readability, and maintainability. This is one possible exploration of maintainability.

Suppose that, instead of the specific game of FizzBuzz, we want to write a program that can play any variant of the FizzBuzz problem, for which FizzBuzz is one specific instance.

PeriodicReplacement ConstructFizzBuzz() {
  char* words[2] = {"Fizz", "Buzz"};
  int replaces[2] = {3, 5};
  return CreatePeriodicReplacement(2, words, replaces);
}
  
void FizzBuzz(int n) {
  // `static` - only need to initialize 1x
  static PeriodicReplacement fizzbuzz = ConstructFizzBuzz();
  
  ExecutePeriodicReplacement(fizzbuzz, n);
}

To do this, we need to define three things: the type PeriodicReplacement, and the two functions used to create and execute periodic replacements. The type itself is simply to abstract away the difficulty of C array management.

typedef struct {
  int Length;
  char* Format[];
} PeriodicReplacement;

ExecutePeriodicReplacement is simply the code from Part 2 modified slightly to use our PeriodicReplacement type instead of a local array and magic number 15.

void ExecutePeriodicReplacement(PeriodicReplacement orders, int n) {
  int ix = 1;
  
  for(int i=1; i<=n; i++)
  {
     printf(orders.Format[ix], i);
     
     ix++;
     if(ix == orders.Length) ix = 0;
  }
}

The meat of the problem is in the CreatePeriodicReplacement function. It is passed any divisors and their replacements, along with the count, and does all the precomputation necessary to create an array like rg in Part 2. In order to reduce the number of reallocations, the shortest possible PeriodicReplacement.Length will be calculated as the least common multiple of the divisors.

int LeastCommonMultiple(int c, int r[]) {
  int* counters = calloc(c, sizeof(int));
  for(int i=0;i<c; i++) counters[i] = r[i] - 1;
  int lcm = 0;
  int zeros = 0;
  while(zeros < c) {
    zeros = 0;
    lcm++;
    for(int i=0;i<c; i++) {
      if(counters[i] == 0) { counters[i] = r[i] - 1; zeros++; }
      else counters[i]--;
    }
  }
  
  free(counters);
  return lcm;
}
  
PeriodicReplacement CreatePeriodicReplacement(int c, char* words[], int replaces[]) {
  PeriodicReplacement rval;
  rval.Length = LeastCommonMultiple(c, replaces);
  rval.Format = calloc(rval.Length, sizeof(char*));
  int* counts = calloc(c, sizeof(int));
  
  for(int i=0; i < rval.Length; i++) {
    bool set = false;
    
    for(int r=0; r < c; r++) {
      if(counts[r] == 0) { 
        StrConcat(rval.Format, words[r]);
        counts[r] = replaces[r] - 1;
        set = true;
      } else {
        counts[r]--;
      }
    }
    
    if(!set) rval.Format = "%d";
    rval.Format = StrConcat(rval.Format, "\n");
  }
  
  free(counts);
  return rval;
}

This approach has the nice quality that precomputation can be saved in a static variable for future iterations, if necessary. I've ignored cleanup code and elided over StrConcat, as they distract from the core of the problem.