Bioinformatics Contest 2017 (task2)

• RNA consists of one strand (chain of ribonucleotides) most of the time, and sometimes it can fold into the secondary structure. In this problem we consider a simpler secondary form than in real life. In this form, some pairs of complementary ribonucleotides build hydrogen bonds between them and each ribonucleotide can build at most one bond. Each bond can be represented as a pair of indices (i,j) (i<j) of the string S that represents RNA. These indices indicate the positions of the symbols in S corresponding to these ribonucleotides.
  Also, in the secondary structure one additional condition holds for each pair of hydrogen bonds (i1,j1), (i2,j2), such that i1<i2:
  
  • they do not intersect i1<j1<i2<j2))
• or the second bond is inside the first one (i1<i2<j2<j1).

My first solution:

import sys
import math


def norm(str1, str2):
    return math.fabs(int(str1) - int(str2))


def check_perfect(s):
    len_s = len(s)
    loops_tops = []
    for i in range(1, len_s):
        if norm(s[i], s[i - 1]) == 1:
            loops_tops.append(i)
    if len(loops_tops) == 0:
        return False    for start in loops_tops:
        step_right = 0        step_left = 1        move = True        while move:
            right = int(s[start + step_right])
            left = int(s[start - step_left])
            if (right == 9) or (left == 9):
                move = False            elif norm(left, right) != 1:
                move = False            else:
                s[start + step_right] = '9'                s[start - step_left] = '9'            if ((start + step_right + 1) >= len_s) or ((start - step_left - 1) < 0):
                move = False            step_right += 1            step_left += 1    new_s = [x for x in s if x != '9']
    len_new_s = len(new_s)
    if len_new_s == 0:
        return True    else:
        if len_new_s == len_s:
            return False        else:
            return check_perfect(new_s)


def check_perfect_if_one_hole(s):
    len_s = len(s)
    if len_s == 1:
        return True    holed_tops = []
    for i in range(2, len_s):
        if norm(s[i], s[i - 2]) == 1:
            holed_tops.append(i - 1)
    for hole in holed_tops:
        s1 = s.copy()
        del s1[hole]
        if check_perfect(s1):
            return True    loops_tops = []
    for i in range(1, len_s):
        if norm(s[i], s[i - 1]) == 1:
            loops_tops.append(i)
    if len(loops_tops) == 0:
        return False    for start in loops_tops:
        step_right = 0        step_left = 1        move = True        while move:
            right = int(s[start + step_right])
            left = int(s[start - step_left])
            if (right == 9) or (left == 9):
                move = False            elif norm(left, right) != 1:
                if (start + step_right + 1) < len_s:
                    if norm(int(s[start + step_right + 1]), left) == 1:
                        s1 = s.copy()
                        del s1[start + step_right]
                        if check_perfect(s1):
                            return True                if (start - step_left - 1) > -1:
                    if norm(right, int(s[start - step_left - 1])) == 1:
                        s1 = s.copy()
                        del s1[start - step_left]
                        if check_perfect(s1):
                            return True                move = False            else:
                s[start + step_right] = '9'                s[start - step_left] = '9'            if ((start + step_right + 1) >= len_s) or ((start - step_left - 1) < 0):
                move = False            step_right += 1            step_left += 1    new_s = [x for x in s if x != '9']
    len_new_s = len(new_s)
    if len_new_s == len_s:
        return False    else:
        return check_perfect_if_one_hole(new_s)



s0 = sys.stdin.readline()
s0 = s0.replace('\n', '')
s1 = s0.replace('U', '2')
s2 = s1.replace('A', '1')
s3 = s2.replace('G', '5')
s4 = s3.replace('C', '6')
s = list(s4)
lens = len(s)
if lens % 2 == 0:
    if check_perfect(s):
        print('perfect')
    else:
        print('imperfect')
else:
    if check_perfect_if_one_hole(s):
        print('almost perfect')
    else:
        print('imperfect')

Hint:

One could notice that the previous Dynamic Programming solution resembles the solutions for problems with bracket sequences. We could see a perfect string as a correct bracket sequence and we check the correctness of bracket sequences using stack!
So, to check if the string is perfect we iterate through bases and maintain a stack:

1. If the current base is complementary to the base on top of the stack, then we pop from the stack.
2. Otherwise, we put the current base into the stack.

If there is no base in the stack, then the given string is perfect.Now, how to understand that the string is almost perfect? The simplest solution will be to delete each symbol and check the resulting string to be perfect. Unfortunately, such solution works in O(|S|2)
time and does not fit into timelimit.
But the way to deal with it is quite easy. Let us perform the solution as in the case of the perfect string. We state that if the string is almost perfect then the base to delete is the middle base of the stack. We remove this base and check that the stack collapses. (In other words, we check that the stack has odd length and it holds a palindrome)

So, suitable solution is:

import sys

def complementary(a, b):
    if (a == 'A' and b == 'U') or (a == 'U' and b == 'A') or (a == 'G' and b == 'C') or (a == 'C' and b == 'G'):
        return True    else:
        return False
def go_stack(str):
    stack = []
    for i in str:
        if len(stack) > 0:
            if complementary(stack[-1], i):
                stack.pop()
            else:
                stack.append(i)
        else:
            stack.append(i)
    return stack


s = sys.stdin.readline().strip()
stack = go_stack(s)
len_stack = len(stack)
if len_stack == 0:
    print('perfect')
else:
    if len_stack % 2 == 0:
        print('imperfect')
    else:
        stack.pop(int((len_stack - 1)/2))
        stack2 = go_stack(stack)
        if len(stack2) == 0:
            print('almost perfect')
        else:
            print('imperfect')