PSET6 DNA Sumbit50 not matching with usual output

Question

Hello,

After a lots of effort I was finally able to implement DNA and it works correctly ! but Submit50 shows correct output for text file (1-5) but incorrect for rest

The text file which have failed are from large.csv

I guess it was due to large time complexity , but output takes approx. 30 secs to be displayed.

I have attached code , output and check50 snippet

Code:

from sys import argv

import csv

import math


def main():

    # checking if user has entered correct arguments
    if len(argv) != 3:
        print("Usage: python dna.py data.csv sequence.txt")

    # extracting names of files
    csvfile = argv[1]
    txtfile = argv[2]

    # opening the text file
    txfile = open(txtfile, "r")
    txt = txfile.read()

    # opening csv file
    file = open(csvfile, "r")
    rear = csv.reader(file)

    # getting name of csv fields
    for i in rear:
        lis = i
        break

    # tracker to check if str is continous
    contracker = 0

    # tracker to check if all attributes of str match
    tottracker = 0

    # variable to count no of str matching, maximum str
    no = 0
    max = 0
    found = 0
    index = -1

    # seperating name of str
    leng = len(lis)
    strname = lis[1: leng]
    lis1 = [0] * (leng - 1)
    lenc = len(txt)

    # iterate over each str value
    for i in strname:
        lens = len(i)
        max = 0
        den = lenc - lens
        index += 1

        # calculate starting point for text
        for initi in range(den):
            dif = lenc - initi
            div = dif / lens
            ren = int(div)

            # iterate over string in text
            for j in range(ren):
                prod = lens * j
                yo = prod + initi
                st = txt[yo: yo + lens]

                if st == i:
                    no += 1
                    contracker = 1

                else:
                    contracker = 0

                # checking if str is continous
                if contracker == 0:
                    if max < no:
                        max = no
                    no = 0

        lis1[index] = (max)

    # iterate over each candidate
    for row in rear:
        tottracker = 0
        for i in range(leng - 1):

            # matching str count with required value
            if int(lis1[i]) == int(row[i + 1]):
                tottracker += 1
            else:
                break



        # checking if all attributes match
        if tottracker == (leng - 1):
            print(f"{row[0]}")
            found = 1
            break

    if found == 0:
        print("No Match")

    txfile.close()
    file.close()

Thanks in advance

EDIT 1: So I found a hack in this particular case and checked for only first three Gene names and it took 1-2 secons but submit50 is still not getting correct output : (I changed this strname = lis[1: 3] )

Answer 1

output takes approx. 30 secs to be displayed.

That's definitely the issue. I just ran my solution and for 15.txt for example, it too 0.022 sec.

30 seconds is far too long. check50 will timeout after only a few seconds.

I'd suggest you reconsider how you are iterating over the text. You've got 3 nested for loops. That's a big O of n³!