Finding the next number in sequence

Question

I have a question to find the N th number in the sequence.

         1
        11
        21
      1211
    111221
    312211
  13112221
1113213211 

The next number is obtained by saying out loud the number of digits in the previous number.

eg. inital number =1
next number = One 1 = 11
next number = Two 1 = 21
next number = One 2 and One 1 = 1211

Here is my code for getting next number:

private static void nextSequence(int N){

        int i=1;

        StringBuffer current = new StringBuffer(); // to populate current number
        StringBuffer last = new StringBuffer();   // to populate next number

        System.out.println("1");

        // populate next number in sequence
        current.append(1);
        current.append(1);

        while(i<=N){

            int begin=1; // pointer to next index
            int start=0; // pointer to start index 
            int count=1; // count the number of repeats
            int j=1;     // counts the length of characters counted
            while(j<current.length()){

                if(current.charAt(begin)==current.charAt(start)){                   
                    count++;     // count the repeats between start and begin                
                }else{
                    last.append(count);
                    last.append(current.charAt(start));
                    start=begin;
                    count=1;
                }

                begin++;
                j++;
            }

            last.append(count);
            last.append(current.charAt(start));
            System.out.println(last);
            current=last;
            last = new StringBuffer(); // reset the next seq numbe
            i++;
        }
    }

Is this the correct approach? I am able to generate the said sequence, but I am not sure if this is the most efficient. Could you please help me correct if my I made any mistakes?

Answer 1

This is one of those times when working backwards helps... but, before we get to that...

Nit Picks

• Unless you have a really good reason, do not use StringBuffer. Use StringBuilder instead. There are two times to use StringBuffer, when you are modifying the instance from multiple threads, and when you are using a Matcher.appendReplacement() or Matcher.appendTail(). You are doing Neither, so stick with StringBuilder. It's faster.

• You should give values some breathing space... use white-space to make things readable. This is not JavaScript where whitespace impacts download time! Lines like:

  while(i<=N){
  

  should be:

  while (i <= N) {
  

• Having both the variables begin and start is confusing.

• It irks me that you hard-code the first result.... why have:

      // populate next number in sequence
      current.append(1);
      current.append(1);
  

A Better way.

The actual processing for this is simpler if we do some clever backward-forward logic. I spent some time 'doing it differently'... The trick is that you want to extract a function that does it for a single iteration.... so, let's start with the outer function (so it makes sense):

public static final void loopCompute(String input, int count) {
    System.out.println(input);
    for (int i = 0; i < count; i++) {
        input = compute(input);
        System.out.println(input);
    }
}

I have called it loopCompute, and it takes an input String, and a number of times to iterate. It then loops the number of times, and computes the result, and prints the result. It then prints the new result.

So, what about the compute method?

Well, the trick is to count the sequences of digits, but also, the better trick is to start at the end and work backwards, because we can then use those values to build up the output String efficiently working forwards.

private static final String compute(String source) {
    // allocate two mated arrays, one of the digits, the other of the counts.
    // the worst case is that there will be as many counts as input digits
    // so we budget for the worst case.
    char[] digits = new char[source.length()];
    int[] counts = new int[source.length()];

    int pos = -1;
    // work backwards through the input, storing the results forwards in the arrays.
    for (int i = source.length() - 1; i >= 0; i--) {
        if (pos < 0 || source.charAt(i) != digits[pos]) {
            pos++;
            digits[pos] = source.charAt(i);
        }
        counts[pos]++;
    }

    // now work backwards through the counts, and store them forwards in the StringBuilder.
    StringBuilder sb = new StringBuilder(pos * 2);
    while(pos >= 0) {
        sb.append(counts[pos]).append(digits[pos]);
        pos--;
    }
    return sb.toString();
}

Answer 2

I find the code to be a little hard to read because of the many variables. You only really need two counters, start and end, so we can trim out the rest--as a rule, fewer variables ⇒ less code to update them ⇒ fewer bugs. I tried slimming it down, and ended up with this:

  static String nextLine(String prev) {
    final StringBuilder sb = new StringBuilder();
    int start = 0;
    while ( start < prev.length() ) {
      int end = start + 1;
      while ( end < prev.length() && prev.charAt(end) == prev.charAt(start) ) {
        end++;
      }
      sb.append(end - start).append(prev.charAt(start));
      start = end;
    }
    return sb.toString();
  }

Some quick timing taught me that rolfl's snippet was about 5% faster overall (Oracle Java build 1.8.0-b132, 64-bit server), but so far both your/mine as rolfl's approach suffer from a major problem: we blow through all our heap space by about the 70th sequence, so efficiency is a matter of perspective.