Finding the nth term in a sequence-CodePudding

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.

CodePudding user response：

This is a very cool sequence! I like that it is English based and not mathematical, haha.

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:

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;
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.
If the current character is equal to the previous character, we increment counter by 1.
Otherwise, we concatenate counter and the character being repeated, to y. Remember, to reinitialize counter to 1, not 0.

Technical Errors:

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);

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);
        }
    }
}

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));
  }
}

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:

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.
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.
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.
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 :)

CodePudding user response：

You can use Pattern with forward reference.

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(
            matcher -> matcher.group().length()   matcher.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