Algorithm Alley
by Tom Cargill


Listing One     
String compress(String input) {
  Properties dictionary = new Properties();
  for( char letter = 'a'; letter<='z'; ++letter )
    dictionary.put(""+letter, ""+letter);
  int generatedCode = 0;
  String output = "";
  String last = "";
  for( int i=0; i<input.length(); ++i ) {
    String current = last + input.charAt(i);
    if( dictionary.get(current)==null ) {
      output += dictionary.get(last);
      String newCode = "("+generatedCode+")"; 
      dictionary.put(current, newCode);
      ++generatedCode;
      last = input.substring(i,i+1);
    } else
      last = current;
  }
  output += dictionary.get(last);
  return output;
}

Listing Two
void generateCompressMapping() {
  String run = "";
  for( int i=1; i<=20; ++i ) {
    run += 'a';
    String compressed = compress(run);
    System.out.println((i<10?" ":"")+i+": "+compressed);
  }
}

Listing Three
String encodeRun(char input, int repetitions) {
  String output = ""+input;
  int index = ((int)Math.sqrt(8*repetitions+1)-1)/2;
  for( int i=1; i<index; ++i )
    output += "("+(i-1)+")";
  int triangle = index*(index+1)/2;
  int remainder = repetitions-triangle;
  if( remainder==1 )
    output += input;
  if( remainder>1 )
    output += "("+(remainder-2)+")";
  return output;
}





1

