// Alessya Labzhinova
// CSE 417
// Homework 5
// RNA folding

import java.io.*;
import java.util.*;

class RNAFold {
   private String sequence;
   private int[][] OPT;
   private int[][] TRC2;
   private String[] TRC;

   public RNAFold(String input){
		sequence = input;
		OPT = new int[sequence.length()][sequence.length()];
		TRC = new String[sequence.length()];
		TRC2 = new int[sequence.length()][sequence.length()];
   }

   public static void main(String[] args) {
	
      //  get the sequence 
      System.out.print("Enter an RNA sequence (consisting of A, U, C, G). Type q to quit.");
	  System.out.println();

      //  open up standard input
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      String input = null;
	  do {
      	try { 
				input = br.readLine().toUpperCase();;
				if(!input.equals("Q")){
					RNAFold sequence = new RNAFold(input);
					// calculate and output the results
					sequence.output();
					System.out.print("Enter an RNA sequence (consisting of A, U, C, G). Type q to quit.");
					System.out.println();
				}

      	} catch (IOException ioe) {
         		System.out.println("IO error trying to read your input");
         		System.exit(1);
      	}

	} while (!input.equals("Q"));
   }

   public void output(){
	    System.out.println();
		// output the sequence
		System.out.println("RNA Sequence: " + sequence);
		long start = System.currentTimeMillis();
		// calculate max folding
		nussinov();
		
		// sequence lenght
		int len = sequence.length();
		
		System.out.print("Traceback: ");
		trace(0, len-1);
		for (int j=0; j < len; j++){
			if(TRC[j] == null)
				System.out.print(".");
			else
				System.out.print(TRC[j]);
		}
		System.out.println();
		
		// output the matrix
		if(len < 25){
			for (int i=0; i < len; i++) {
	         for (int j=0; j < len; j++) {
	            System.out.print(" "+OPT[i][j]);               
	         }
	         System.out.println();
	       }
		}
		
	   // output the number of pairs
	   System.out.println("Maximum pairs: " + OPT[0][len-1]);	
	   long stop = System.currentTimeMillis();
	   long time = stop-start;
	   System.out.println("Sequence length: " + len + " / Runtime: " + (long)time+"ms");  
	   System.out.println();
   }

 public void nussinov(){
        int total_max, current_max, j, var1, var2;
        int len = sequence.length();
		int index;
		for(int k = 5; k<len; k++){
			for(int i=0; i<len-k; i++){
				j = i+k;
				index = len;
				total_max = OPT[i][j-1];

				current_max = valid(i,j) + OPT[i+1][j-1];
				if(j-i < 4 && current_max > total_max)
					index = i;
					
				for(int t=i; t<=j; t++){
					if(t < j-4 && valid(t,j) == 1){
						try { 	
							var1 = OPT[i][t-1];
						} catch (ArrayIndexOutOfBoundsException e) { var1 = 0; }
						try { 	
							var2 = OPT[t+1][j-1];
						} catch (ArrayIndexOutOfBoundsException e) { var2 = 0; }
						current_max = var1+var2+1;
						if(current_max > total_max){
							total_max = current_max;
							index = t;
						}
					}
				}
				OPT[i][j] = total_max;
				if(index < len)
					TRC2[i][j] = index;
				else
					TRC2[i][j] = -1;
			}
		}
   }


	public void trace(int i, int j){
   		int t = TRC2[i][j];
   		if(t != -1)  {
     		TRC[t] = "("; 
     		TRC[j] = ")";
     		if (4 < t-1-i  )
       			trace(i,t-1);
     		if( 4 < (j-1)-(t+1) )
       			trace(t+1,j-1);
   		} 
   		else{ 
     		if( 4 < j-1-i )
        		trace(i,j-1);
   		}  
	}
	
   public int valid(int i, int j) {
	  char a = sequence.charAt(i);
	  char b = sequence.charAt(j);
      if ((a == 'A' && b == 'U') || (a == 'U' && b == 'A') || (a == 'C' && b == 'G') || (a == 'G' && b == 'C'))
         return 1;
      else
         return 0;
   }

}