10
\$\begingroup\$

I am doing this problem on HackerRank and I'm failing test cases because it's taking too long to run when n and k get over 8000. I believe the dictionary lookup should be \$O(1)\$ while lists are \$O(n)\$. Would it be faster to store the DNA string in another dictionary where the array position is the key? I'm not sure of any other optimizations I can make.

Essentially, given a string of n characters, iterate through that string k times while swapping values according to dictionary key/value pairs. So a string 'AAC' would look at 'AA'->'A', 'AC'->'C', and because of wrap-around, 'CA'->'C'. So after one iteration, 'AAC' becomes 'ACC'. Now repeat k times.

inp = input().split(' ')
n, k = inp[0], inp[1]
proteins = input()
#generated the dictionary with other python scripts since it's unchanging
#see challenge on Hackerrank for original table
#matrix['fromLetter+toLetter']='mutatedLetter'
matrix = {'AA': 'A', 'BD': 'C', 'AC': 'C', 'AB': 'B', 'AD': 'D', 'BB': 'A', 'BC': 'D', 'CC': 'A', 'CB': 'D', 'CA': 'C', 'DB': 'C', 'DC': 'B', 'CD': 'B', 'DA': 'D', 'DD': 'A', 'BA': 'B'}

for i in range(k):
    pos = 0
    mutated = ''
    while pos<n:
        #handle the protein wrap-around
        if pos == n-1:
            mutated += matrix[proteins[-1]+proteins[0]]
        else:
            mutated+= matrix[proteins[pos:pos+2]]

        pos+=1
    proteins = mutated
print(proteins)
\$\endgroup\$
12
\$\begingroup\$

I encourage you to abandon your present approach.

Instead, try expressing each of your A/B/C/D proteins as integer numbers. Then express those integer numbers in binary form, and see if you can determine the operation(s) underlying the very, very regular pattern visible in the table given in the problem.

If you transcode the "protein sequences" to a series of 2-bit numbers, I believe you can profitably perform your mutations at a high rate of speed.

\$\endgroup\$
  • \$\begingroup\$ Happy to (not) help. ;-) \$\endgroup\$ – Austin Hastings Oct 9 '17 at 1:12
  • \$\begingroup\$ Have you found a working solution for large enough n and k? Obvious solutions on this vain are being too slow for me \$\endgroup\$ – Oscar Smith Oct 9 '17 at 4:16
  • \$\begingroup\$ @OscarSmith I had to take Austin's advice to get it to work for large values of n/k. I have to admit, the level of refinement required for the full solution caught me off guard, but I guess that's why it's a 'hard' question. :) \$\endgroup\$ – UnclosedParenthesis Oct 9 '17 at 12:55
  • \$\begingroup\$ @UnclosedParenthesis Can you do k%n rounds instead of k? \$\endgroup\$ – JollyJoker Oct 9 '17 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.