# Solving the DNA Splicer

In Challenge 5 of the 2018 Tuenti Challenge, we are given DNA strands (strings containing a mix of `aAcCgGtT`), and asked to find how we can recombine the strands into two matching sequences. Not all of the strands need to be in the final identical sequences. For example, given the input `aacc GgTTC aaccG gTTC aaaa cccc gttc`, we need to discover that the sequence `aaccGgTTC` can be built twice: `aacc+GgTTC` and `aaccG+gTTC`. We then return the positions of the parts we used to create the two identical sequences, in this case 1, 2, 3 and 4.

This is an interesting problem, and I encourage you to take a few minutes to think about how you would solve this before reading on.

The maximum number of parts (18) combined with the time constraints rule out the option of enumerating all the possible combinations of parts. We need to find a slightly more efficient algorihtm.

Let’s start by assuming a certain part, call it X, is the first part of one of the final sequences. Then we know that there must be another part, Y, where one of the following is true:

1. Y is longer than X, and starts with all the characters in X, or
2. Y is shorter than X, and all its characters match with the first characters of X, or
3. Y is exactly equal to X, in both length and value

If there is no such part Y, our hypothesis is invalidated, and X cannot be the start of the final sequence. If there is a part Y, we can now ignore all the matching characters in X and Y, and continue. In our example above, let’s say we found X = `aacc` and Y = `aaccG`. The remaining characters that did not match, in this case `G`, now becomes the new X, and we repeat the procedure from before, remembering that we can’t use part X or Y anymore. We know that there must be another part where one of the 3 cases from above is true. If there is not, we backtrack until we find another X, Y pair that has not yet been considered.

If we ever hit case 3 (i.e. X and Y match exactly) we must have two identical sequences, and we are done! If we consider every possible starting part as X, then we must have covered all the possible combinations. We just need to keep track of the parts we used to get to case 3, and then return those parts as the answer. The following Python code implements this algorithm. (You can ignore the telnet-related code: it is for interacting with the challenge server.)

``````from __future__ import print_function, unicode_literals, division

from collections import namedtuple, defaultdict, deque
import itertools
import telnetlib

def find_identical_dna_sequences(parts):
"""
Recursively check string concatenations and eliminate
impossible branches quickly.
"""
used = [0 for i in range(len(parts))]
for i, part in enumerate(parts):
X = part
Y = ""
used[i] = 1
ans = _find_matching_parts(X, Y, parts, used)
if ans is not None:
return ",".join([str(i+1) for i in range(len(used)) if used[i]])
used[i] = 0
return None

def _find_matching_parts(X, Y, parts, used):
# case 3
if X == Y:
return used

if len(Y) > len(X):
X, Y = Y, X

diff = X[len(Y):]
for i, part in enumerate(parts):
if used[i]:
continue

# case 1 and 2
if part.startswith(diff) or diff.startswith(part):
used[i] = 1
ans = _find_matching_parts(X, Y+part, parts, used)
if ans is not None:
return ans
used[i] = 0

return None

tn = telnetlib.Telnet("52.49.91.111", port="3241")
tn.write("SUBMIT\n".encode('ascii'))
while s:
s = s.decode('ascii').strip()
if not s or s.startswith(">"):
continue
ans = find_identical_dna_sequences(s.split(" "))
print(ans)
tn.write((ans + "\n").encode('ascii'))