Genome Sequencing puzzle discussion

Puzzles
#46

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

#48

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

#49

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:

#50

@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
#51

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

#52

@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.

#53

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%

#54

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.

#55

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
#56

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

1 Like
#57

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

#58

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…)

#59

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 !

#60

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%

#61

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.

#62

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.

#63

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

#64

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: .

#65

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 !
#66

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