Thread: Compress DNA sequence using recursion

I am suppose to create a recursive method that will compress a DNA sequence. For example;
DNA.compress("GGCcCTtttTT") => "G2C3T6"

but my code keeps giving me an
java.lang.ArrayIndexOutOfBoundsException: -1
at DNA.compress(DNA.java:41)
at DNA.compress(DNA.java:44)
at DNA.compress(DNA.java:34)
at Test.main(Test.java:36)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Nativ e Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(Native MethodAccessorImpl.java:39)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(De legatingMethodAccessorImpl.java:25)
at java.lang.reflect.Method.invoke(Method.java:597)
at edu.rice.cs.drjava.model.compiler.JavacCompiler.ru nCommand(JavacCompiler.java:272)

for the Test Case tgg

my code is

 public static String compress(String dna){
    String dnaUpper = dna.toUpperCase();
    char[] dnaArray = dnaUpper.toCharArray();
    int len = dnaArray.length;
 
    if(dnaUpper.length() > 1){
      System.out.println("The char at the end is " + dnaArray[len-1]);
      if((dnaArray[len-1] >= 'A') && (dnaArray[len-1] <= 'Z')){ //if the last entry is a letter
        if(dnaArray[len-1] == dnaArray[len-2]){ //if the last 2 entries match
          return compress(dna.substring(0, dna.length() - 2) + dnaUpper.charAt(dna.length()-1) + "2");
        }else{ //if the last 2 entries don't match
          return compress(dna.substring(0, dna.length() - 2) + dna.charAt(len-1));
        }
 
      }else{ //if the last entry is a number
          if((dnaArray[len-2] >= 'A') && (dnaArray[len-2] <= 'Z')){//if the second last entry is a letter
            if(dnaArray[len-2] == dnaArray[len-3]){ //if the second and third last entires match
              return compress(dna.substring(0,dna.length()-3) + (Integer.parseInt(""+dnaArray[dnaArray.length -1]) + 1));
            } else{ //if the second and third last entries dont match
              return compress(dna.substring(0,dna.length()-3) + dna.substring(dna.length()-2));
            }
          }else{//if the second last entry is not a letter
            if(dnaArray[len-3] == dnaArray[len-4]){ //if the third last and 4th last entries match
              return compress(dna.substring(0,dna.length()-4) + Integer.parseInt(dna.substring(dna.length()-3)) + 1);
            }else{ //third and 4th last entries don't match
              return compress(dna.substring(0,dna.length()-4) + dna.substring(dna.length()-3));
            }
          }
        }
    }else{
      return dnaUpper;
    }
  }

if you could help me out, I'd really appreciate it.

Thanks

I've modified to code to not give ArrayIndexOutOfBoundsException anymore. But it is still not giving me the correct output. Some letters seem to disappear or get added to ones that dont match.

new code:

public static String compress(String dna){
    String dnaUpper = dna.toUpperCase();
    char[] dnaArray = dnaUpper.toCharArray();
    int len = dnaArray.length;
 
    if(dnaUpper.length() > 1){
      System.out.println("The char at the end is " + dnaArray[len-1]);
      if((dnaArray[len-1] >= 'A') && (dnaArray[len-1] <= 'Z')){ //if the last entry is a letter
        if(dnaArray[len-1] == dnaArray[len-2]){ //if the last 2 entries match
          return compress(dna.substring(0, dna.length() - 2) + dnaUpper.charAt(dna.length()-1) + "2");
        }else{ //if the last 2 entries don't match
          return compress(dna.substring(0, dna.length() - 2)) + dna.charAt(len-1);
        }
 
      }else{ //if the last entry is a number
          if((dnaArray[len-2] >= 'A') && (dnaArray[len-2] <= 'Z')){//if the second last entry is a letter
            if(dnaArray[len-2] == dnaArray[len-3]){ //if the second and third last entires match
              return compress(dna.substring(0,dna.length()-3) + (Integer.parseInt(""+dnaArray[dnaArray.length -1]) + 1));
            } else{ //if the second and third last entries dont match
              return compress(dna.substring(0,dna.length()-3)) + dna.substring(dna.length()-2);
            }
          }else{//if the second last entry is not a letter
            if(dnaArray[len-3] == dnaArray[len-4]){ //if the third last and 4th last entries match
              return compress(dna.substring(0,dna.length()-4) + Integer.parseInt(dna.substring(dna.length()-3)) + 1);
            }else{ //third and 4th last entries don't match
              return compress(dna.substring(0,dna.length()-4)) + dna.substring(dna.length()-3);
            }
          }
        }
    }else{
      return dnaUpper;
    }
  }

So I've got pretty much everything working, except when I start getting double digits. The new code is at the bottom and the part that handles the double digits is bolded. I've code it working well if for example i use a string 10 letters long of a, But if I use 20 letters of A, i would expect A20, but I get A8101. Cannot figure this last part out.

public static String compress(String dna){
    String dnaUpper = dna.toUpperCase();
    System.out.println("The String entered is: " + dnaUpper);
    char[] dnaArray = dnaUpper.toCharArray();
    int len = dnaArray.length;
 
    if(dnaUpper.length() > 1){
      System.out.println("The char at the end is " + dnaArray[len-1]);
      if((dnaArray[len-1] >= 'A') && (dnaArray[len-1] <= 'Z')){ //if the last entry is a letter
        System.out.println("The last Entry is a letter");
        if(dnaArray[len-1] == dnaArray[len-2]){ //if the last 2 entries match
          System.out.println("The last 2 entries match");
          System.out.println("Returned is: "+ "compress(" + dna.substring(0, dna.length() - 2) + "+" + dnaUpper.charAt(dna.length()-1) + "+" +"2)");
          return compress(dna.substring(0, dna.length() - 2) + dnaUpper.charAt(dna.length()-1) + "2");
        }else{ //if the last 2 entries don't match
          System.out.println("Last 2 entries dont's match");
          System.out.println("returned is: " + "compress("+dna.substring(0, dna.length() - 1)+")" + " +" + dnaUpper.charAt(len-1));
          return compress(dna.substring(0, dna.length() - 1)) + dnaUpper.charAt(len-1);
        }
 
      }else{ //if the last entry is a number
        System.out.println("The character at the end is a number");
          if((dnaArray[len-2] >= 'A') && (dnaArray[len-2] <= 'Z')){//if the second last entry is a letter
            System.out.println("the 2nd last entry is a letter");
            if(dna.length() ==2){
              System.out.println("length = 2");
              System.out.println("returned: " + dnaUpper);
              return dnaUpper;
            }else if(dnaArray[len-2] == dnaArray[len-3]){ //if the second and third last entires match
              System.out.println("the second and third last match");
              System.out.println("returned is: compress(" + dna.substring(0,dna.length()-2)+"+" + (Integer.parseInt(""+dnaArray[dnaArray.length -1]) + 1));
              return compress(dna.substring(0,dna.length()-2) + (Integer.parseInt(""+dnaArray[dnaArray.length -1]) + 1));
            } else{ //if the second and third last entries dont match
              System.out.println("the second and third last entries dont match");
              System.out.println("returned is: " + "compress("+dna.substring(0,dna.length()-2)+ ")+" + dna.substring(dna.length()-2));
              return compress(dna.substring(0,dna.length()-2)) + dna.substring(dna.length()-2);
            }
          }[B]else{//if the second last entry is not a letter
            System.out.println("the second last character is not a letter");
            if(dna.length() ==3){
              System.out.println("length = 3");
              System.out.println("returned: " + dnaUpper);
              return dnaUpper;
          }else if(dnaArray[len-3] == dnaArray[len-4]){ //if the third last and 4th last entries match
              System.out.println("returned: compress(" + dna.substring(0,dna.length()-4)+"+" + Integer.parseInt(dna.substring(dna.length()-2)) + 1);
              return compress(dna.substring(0,dna.length()-4) + Integer.parseInt(dna.substring(dnaUpper.length()-2)) + 1);
            }else{ //third and 4th last entries don't match
              return compress(dna.substring(0,dna.length()-4)) + dna.substring(dna.length()-3);
            }
          }
        }[/B]
    }else{
      return dnaUpper;
    }
  }

Edit: I cannot bold any part of the code so its the part near the end between [B and /B], thanks

these are the tests i'm running, from a different class

String a1 = "";
String b1 = DNA.compress(a1);
System.out.println(b1);

String a3 = "Cat";
String b3 = DNA.compress(a3);
System.out.println("tgg: "+ b3);

String a2 = "GGCcCTtttTT";
String b2 = DNA.compress(a2);
System.out.println("ggtttaaaaccccccttttgtgtttgactg : " + b2);

String a4 = "aaaaaaaaaaaaaaaaaaaa";
String b4 = DNA.compress(a4);
System.out.println("expect A20, got: " + b4);

test class:

public class Test{
  public static void main(String[] args){
    String a1 = "";
    String b1 = DNA.compress(a1);
    System.out.println(b1);
 
    String a3 = "Cat";
    String b3 = DNA.compress(a3);
    System.out.println("tgg: "+ b3);
 
    String a2 = "GGCcCTtttTT";
    String b2 = DNA.compress(a2);
    System.out.println("ggtttaaaaccccccttttgtgtttgactg: " + b2);
 
    String a4 = "baaaaaaaaaaaaaaaaaaaa";
    String b4 = DNA.compress(a4);
    System.out.println("expect BA20, got: " + b4);
 
  }
 
}

DNA class(updated):

public class DNA{
 
  /******************************************************************** 
    public static String compress(String dna)
 
    input: a non-null string consisting only of the letters G,A,T and C.
          (this is the long form representation)
          (they may be upper, lower, or mixed case)
    output: a string that represents a condensed version of the input string.  
            o) Each occurrence of a single letter (its neighbours are different) 
               is copied to the new string. 
            o) Each occurrence of a sequence of a single letter that
               is repeated two or more times is replaced by
               that letter and number of occurrences in the new string
            All letters in the output should be capitalized.
    examples: DNA.compress("GGCcCTtttTT") => "G2C3T6"
              DNA.compress("Cat")         => "CAT"
              DNA.compress("")            => ""     
  *********************************************************************/
  public static String compress(String dna){
    String dnaUpper = dna.toUpperCase();
    System.out.println("The String entered is: " + dnaUpper);
    char[] dnaArray = dnaUpper.toCharArray();
    int len = dnaArray.length;
 
    if(dnaUpper.length() > 1){
      System.out.println("The char at the end is " + dnaArray[len-1]);
      if((dnaArray[len-1] >= 'A') && (dnaArray[len-1] <= 'Z')){ //if the last entry is a letter
        System.out.println("The last Entry is a letter");
        if(dnaArray[len-1] == dnaArray[len-2]){ //if the last 2 entries match
          System.out.println("The last 2 entries match");
          System.out.println("Returned is: "+ "compress(" + dna.substring(0, dna.length() - 2) + "+" + dnaUpper.charAt(dna.length()-1) + "+" +"2)");
          return compress(dna.substring(0, dna.length() - 2) + dnaUpper.charAt(dna.length()-1) + "2");
        }else{ //if the last 2 entries don't match
          System.out.println("Last 2 entries dont's match");
          System.out.println("returned is: " + "compress("+dna.substring(0, dna.length() - 1)+")" + " +" + dnaUpper.charAt(len-1));
          return compress(dna.substring(0, dna.length() - 1)) + dnaUpper.charAt(len-1);
        }
 
      }else{ //if the last entry is a number
        System.out.println("The character at the end is a number");
          if((dnaArray[len-2] >= 'A') && (dnaArray[len-2] <= 'Z')){//if the second last entry is a letter
            System.out.println("the 2nd last entry is a letter");
            if(dna.length() ==2){
              System.out.println("length = 2");
              System.out.println("returned: " + dnaUpper);
              return dnaUpper;
            }else if(dnaArray[len-2] == dnaArray[len-3]){ //if the second and third last entires match
              System.out.println("the second and third last match");
              System.out.println("returned is: compress(" + dna.substring(0,dna.length()-2)+"+" + (Integer.parseInt(""+dnaArray[dnaArray.length -1]) + 1));
              return compress(dna.substring(0,dna.length()-2) + (Integer.parseInt(""+dnaArray[dnaArray.length -1]) + 1));
            } else{ //if the second and third last entries dont match
              System.out.println("the second and third last entries dont match");
              System.out.println("returned is: " + "compress("+dna.substring(0,dna.length()-2)+ ")+" + dna.substring(dna.length()-2));
              return compress(dna.substring(0,dna.length()-2)) + dna.substring(dna.length()-2);
            }
          }else{//if the second last entry is not a letter
            System.out.println("the second last character is not a letter");
            if(dna.length() ==3){
              System.out.println("length = 3");
              System.out.println("returned: " + dnaUpper);
              return dnaUpper;
          }else if(dnaArray[len-3] == dnaArray[len-4]){ //if the third last and 4th last entries match
            int x = Integer.parseInt(dna.substring(dna.length()-2));
            int y = x + 1;
              System.out.println("returned: compress(" + dna.substring(0,dna.length()-3)+"+" + x+"+" + 1);
              System.out.println("Integer.parseInt(dna.substring(dna.length()-2))="+ x +" + 1 = "+ y);
              return compress(dna.substring(0,dna.length()-3) + y);
            }else{ //third and 4th last entries don't match
              return compress(dna.substring(0,dna.length()-4)) + dna.substring(dna.length()-3);
            }
          }
        }
    }else{
      return dnaUpper;
    }
  }

results
Cat: CAT
GGCcCTtttTT: G2C3T6
expect A20, got: A20
Expect BA20: got: a20

--- Update ---

ok so I got it working, here's the code I've used to compress DNA sequence recursively. Thank for all your help guys:

public static String compress(String dna){
    String dnaUpper = dna.toUpperCase();
    System.out.println("The String entered is: " + dnaUpper);
    char[] dnaArray = dnaUpper.toCharArray();
    int len = dnaArray.length;
 
    if(dnaUpper.length() > 1){
      System.out.println("The char at the end is " + dnaArray[len-1]);
      if((dnaArray[len-1] >= 'A') && (dnaArray[len-1] <= 'Z')){ //if the last entry is a letter
        System.out.println("The last Entry is a letter");
        if(dnaArray[len-1] == dnaArray[len-2]){ //if the last 2 entries match
          System.out.println("The last 2 entries match");
          System.out.println("Returned is: "+ "compress(" + dna.substring(0, dna.length() - 2) + "+" + dnaUpper.charAt(dna.length()-1) + "+" +"2)");
          return compress(dna.substring(0, dna.length() - 2) + dnaUpper.charAt(dna.length()-1) + "2");
        }else{ //if the last 2 entries don't match
          System.out.println("Last 2 entries dont's match");
          System.out.println("returned is: " + "compress("+dna.substring(0, dna.length() - 1)+")" + " +" + dnaUpper.charAt(len-1));
          return compress(dna.substring(0, dna.length() - 1)) + dnaUpper.charAt(len-1);
        }
 
      }else{ //if the last entry is a number
        System.out.println("The character at the end is a number");
          if((dnaArray[len-2] >= 'A') && (dnaArray[len-2] <= 'Z')){//if the second last entry is a letter
            System.out.println("the 2nd last entry is a letter");
            if(dna.length() ==2){
              System.out.println("length = 2");
              System.out.println("returned: " + dnaUpper);
              return dnaUpper;
            }else if(dnaArray[len-2] == dnaArray[len-3]){ //if the second and third last entires match
              System.out.println("the second and third last match");
              System.out.println("returned is: compress(" + dna.substring(0,dna.length()-2)+"+" + (Integer.parseInt(""+dnaArray[dnaArray.length -1]) + 1));
              return compress(dna.substring(0,dna.length()-2) + (Integer.parseInt(""+dnaArray[dnaArray.length -1]) + 1));
            } else{ //if the second and third last entries dont match
              System.out.println("the second and third last entries dont match");
              System.out.println("returned is: " + "compress("+dna.substring(0,dna.length()-2)+ ")+" + dna.substring(dna.length()-2));
              return compress(dna.substring(0,dna.length()-2)) + dna.substring(dna.length()-2);
            }
          }else{//if the second last entry is not a letter
            System.out.println("the second last character is not a letter");
            if(dna.length() ==3){
              System.out.println("length = 3");
              System.out.println("returned: " + dnaUpper);
              return dnaUpper;
          }else if(dnaArray[len-3] == dnaArray[len-4]){ //if the third last and 4th last entries match
            int x = Integer.parseInt(dna.substring(dna.length()-2));
            int y = x + 1;
              System.out.println("returned: compress(" + dna.substring(0,dna.length()-3)+"+" + x+"+" + 1);
              System.out.println("Integer.parseInt(dna.substring(dna.length()-2))="+ x +" + 1 = "+ y);
              return compress(dna.substring(0,dna.length()-3) + y);
            }else{ //third and 4th last entries don't match
              System.out.println("compress(dna.substring(0,dna.length()-3)) = " + dnaUpper.substring(0,dnaUpper.length()-3) +" + " + "dnaUpper.substring(dna.length()-3)=" + dnaUpper.substring(dnaUpper.length()-3));
              return compress(dnaUpper.substring(0,dnaUpper.length()-3)) + dnaUpper.substring(dnaUpper.length()-3);
            }
          }
        }
    }else{
      return dnaUpper;
    }
  }

Thanks for the help, I got it working and posted the working code above.