Finding the nth term in a sequence

Question

I have a sequence, and I am trying to make a program to find the nth term of the sequence.

The sequence is as follows:

1, 11, 21, 1211, 111221, 312211...

In this sequence, each term describes the previous term. For example, "1211" means that the previous term; the previous term is "21" where there is one occurrence of a 2 and then one occurrence of a 1 (=1211). To get the third term, "21," you look at the second term: 11. There are two occurrences of a 1 which gives us "21."

import java.util.*;
class Main {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
        System.out.println( Main.num(n-1, "1"));
  }
    public static String num(int times, String x){
        if(times == 0){
            return x;
        }else{
            //System.out.println("meow");
            String y = "" + x.charAt(0);
            int counter = 0;
            for(int i = 1; i < x.length(); i++){
                if(x.charAt(i) == x.charAt(i-1)){
                    counter++;
                }else{
                    y += "" + counter + x.charAt(i-1);
                    counter = 0;
                }
            }
            return num(times--, y);
        }
        //return "";
    }
}

My code uses recursion to find the nth term. But, it gives us errors :(

First, I start of the method "num" by passing it the number of terms-1 (since the first term is already given) and the first term (1).

In the method num, we start off by using a conditional to establish the base case (when you are done finding the nth term).

If the base case is false, then you find the next term in the sequence.

Answer 1

This is a very cool sequence! I like that it is English based and not mathematical, haha. (Though now I wonder ... is there a formula we could make for the nth term? I'm pretty sure it's impossible or uses some crazy-level math, but just something to think about ...)

In your solution, the recursive logic of your code is correct: after you find each term, you repeat the method with your knew number and find the next term using that element, and end when you have determined the first n elements. Your base case is also correct.

However, the algorithm you developed for determining the terms in the sequence is the issue.

To determine the next element in the sequence, we want to:

Logical Error:

1. Create a empty variable, y, for your next element. The variable, counter, should not start at 0, however. This is because every element will ALWAYS have an occurrence of at least 1, so we should initialize int counter = 1;

2. Iterate through the characters in x. (You did this step correctly) We begin at i = 1, because we compare each character to the previous one.

3. If the current character is equal to the previous character, we increment counter by 1.

4. Otherwise, we concatenate counter and the character being repeated, to y. Remember, to reinitialize counter to 1, not 0.

Technical Errors:

5. Once we reach the end of iterating x, we need to concatenate our final counter and character to y, since the else statement for the final characters will never run in our for loop.

This is done with the following code: y += "" + counter + x.charAt(x.length() - 1);

6. Finally, when you are doing your recursive call, you should do --times instead of times--. The difference between these two parameters is that with your original code, you are post-decrementing. This means the value of times is decreasing after the method call, when we want the decreased value to be sent into the method. To solve this, we need to pre-decrement, by doing --times.

import java.util.*;
class CoolSequence {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    System.out.println(num(n, "1"));
  }
    public static String num(int times, String x){
        if(times == 0){
            return x;
        }
        else{
            String y = "";
            int counter = 1;
            for(int i = 1; i < x.length(); i++){
                if(x.charAt(i) == x.charAt(i - 1)){
                    counter++;
                }
                else{
                    y += "" + counter + x.charAt(i - 1);
                    counter = 1;
                }
            }
            y += "" + counter + x.charAt(x.length() - 1);
            return num(--times, y);
        }
    }
}

Testing:

6
13112221

An alternative approach would be using an iterative method:

import java.util.*;
class CoolSequence2 {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    ArrayList<String> nums = new ArrayList<String>();
    int n = scan.nextInt();
    String val = "1";
    for(int i = 0; i < n; i++){
      String copy = val;
      val = "";
      while(!copy.equals("")){
        char curr = copy.charAt(0);
        int ind = 0;
        int cons = 0;
        while(ind < copy.length() && curr == copy.charAt(ind)){
          cons += 1;
          ind += 1;
        }
        val += String.valueOf(cons) + copy.charAt(cons - 1);
        copy = copy.substring(cons);
      }
      nums.add(val);
    }
    System.out.println(nums.get(nums.size() - 1));
  }
}

6
13112221

In this method, we use a for loop to iterate through n terms. To determine each element, we do a similar method to your logic:

1. We create an empty string, val, to hold the new element, and store our current element in copy. We also initialize a cons, similar to your counter.
2. While copy is not empty, we iterate through copy and increment cons until there is an element that is not equal to the next element.
3. When this occurs, we concatenate cons and the repeated element to val, like in your code. Then, we cut out the repeated elements from copy and continue the process.
4. We add the new value of val to nums, and keep iterating through the n elements.

I hope these two methods of approaching your problem helped! Please let me know if you have any further questions or clarifications :)

Answer 2

You can use Pattern with backreference.

The regular expression "(.)\\1*" matches any single character ("(.)") and zero or more sequences of the same character ("\\1*"). "\\1" is called a backreference, it refers to the string enclosed in parentheses 1st.

For example, it matches 111, 22 and 1 for 111221.

replaceAll() calls the lambda expression specified by the argument each time it matches. The lambda expression receives a MatchResult and returns a string. The matched string is replaced with the result.

The lambda expression in this case concatenates the length of the matched string (match.group().length()) and the first character (match.group(1)).

static final Pattern SEQUENCE_OF_SAME_CHARACTER = Pattern.compile("(.)\\1*");

static String num(int times, String x) {
    for (int i = 0; i < times; ++i)
        x = SEQUENCE_OF_SAME_CHARACTER.matcher(x).replaceAll(
            match -> match.group().length() + match.group(1));
    return x;
}

public static void main(String[] args) {
    for (int i = 1; i <= 8; ++i)
        System.out.print(num(i - 1, "1") + " ");
}

output:

1 11 21 1211 111221 312211 13112221 1113213211