Genome Sequencing puzzle discussion

I have the same problem. Have you found any clue for the case “Almost superimposed”?

@Bandersnatch Thx a lot for those inputs. Now I was able to easily spot my bug.

Hey @huys03

I guess i had some crazy bad problem in my logic. Never figured it out.
I rewrote my solution. I have 100% in it now. Can’t help you in what could have been the issue. :smiley:

@ridle_webmaster
Since I couldn’t find a reply to your post, in case you didn’t figure it out, maybe try the following test case:
[‘BACA’, ‘GATTACA’, ‘TT’]
…or a few variants of this case with the order changed.

My code was failing this case, and once I fixed the error, it passed 100%.

1 Like

What is the expected answer in this case?
My algorithm outputs 11 (like “BACAGATTACA”), but it seems wrong…

@bvs23bkv33 & @SaiksyApo

The only test my code fails is the Multi-solutions one, any idea what kind of data we’re talking about?
My algorithm creates 1 solution for every permutation (when there is one) and then picks the shortest one. Can this be a timeout? (max number of permutations is 2880 for 5 subsequences)

Any help is appreciated.

I found the problem, it was timing out because of the size of my possibilities array.
Once I stopped adding duplicate possibilities (those things you know you need to do but forget) i had no problem getting the 100%

I passed 100%, and it took me surprisingly little time to complete.

I made an intuitive assumption that, the problem can be tackled one word at a time, provided the program considers all possible ways of combining the words. For example if there are 3 words, the program will generate all permutations - (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1).

Then it becomes very easy to find the minimum superstring of two words, and working from there, incorporating one new word at a time.

It looks like my code do everything well, even a bit redundant.
Even passed my own test with big strings (without some optimisations it will gave timeout).
Input:
6
AAAAAACCCC
AAAAACCCCC
AAAACCCCCC
CCCCAAAAAA
CCCCCAAAAA
CCCCCCAAAA
Output:
12

But still can’t pass 11-13. Does anybody have idea about what in this cases?

1 Like

I think expected output in your example is 18, not 12.
The shortest string is AAAAAACCCCCCAAAAAA or CCCCCCAAAAAACCCCCC.

1 Like

Hi, here is a test who helped me to solve this particular test:
CA
TCAT
CAGG

This test gave me a lot of trouble, too, but I finally managed to reproduce the error. I won’t explain the bug in my code, so as not to spoil the game, but here’s an input I came up with that would trigger the bug:

3
ATAC
TAC
GT

(note that the sequences had to be presented in this exact order…)

Hi again.

I’m still confused, because my algorithm can solve all the different test cases posted here, but is still failing on validator #4 (“Example 3, but with the first two words nested”).

Can anyone explain me what this test contains ? or at least provide an example of the input sequences ?

Thanks a lot !

Can somebody give me some input for testing multi-solutions? because i did 93% and cant solve only multi-solutions.
Dont need additional input)
i’ve just sorted input and solve 100%

The problem seems to actually be a Traveling Salesman Problem and if allowed N were a little bigger, would call for some dynamic programming method, like Bellman Held Karp algorithm. But maximum N value of 5 is so small, (only 120 permutations) that brute-forcing is feasible.

Guys, I really need help. After submit I gain only 93%, cause “Multi-solutions” fails. Please, can someone give me examples of inputs, so I can detect a bug. Thank you.

Hello, I am searching for an exemple for the case 13 sequence included and disjointed.
Can someone give me an example, to see if my algorithm solve it?

Thank you

Like @your_cereal, I have only 93% because of “Multi-solutions”. I would be interested by an example of inputs, thanks. It’s frustrating to finish at 93% :slight_smile: .

Hello Huys03 !
I had the same problem yesterday evening, and fixed it today : It was a problem of complexity in time.
My fonction to “concatenate” strings was not efficient enough.
Here is what I do now:

  1. how to “concatenate” 2 strings a and b: begin the tests of “superposition” at the beginning of a (not at the end !) --> if a and b ‘almost superpose’, it’s more performing.
  2. to “concatenate” more than 2 strings : concatenate( left half concatened, right half concatened )
    It works for me now !
    Hope this can help you !

I did some optimizations to reduce the search space, and so in my case maximum N among testcases was 3.
This made me wonder what’s the point of even mentioning “dynamic programming” in puzzle description. With such small N brute-forcing over permutations will just be more efficient.
Nonetheless, I have implemented Held-Karp algorithm and tested it on sequences of up to 15-16 elements.

1 Like