Tuenti Challenge 8

Challenge 5 - DNA Splicer

HURRY! We need your help!
We have a machine that we use to split, compare and match DNA samples, but it's been misbehaving and mixing the split samples with some others parts.
Given the parts can you reconstruct any of the original samples?

Example:


We have two samples 'aaccGgTTC'. One was split as 'aacc' 'GgTTC' and the other as 'aaccG' 'gTTC'. However these were mixed with parts 'aaaa' 'cccc' and 'gttc' from another experiment.
Given the input 'aacc GgTTC aaccG gTTC aaaa cccc gttc', the only possible original sample is 'aaccGgTTC', which can be formed twice with parts 1,2,3,4

Notes

You'll need to connect to 52.49.91.111:3241, and then type TEST or SUBMIT. But don't worry, you can reconnect and try as many times as you want.
Daemon info messages start with '>'.
You'll get a line with strings separated by ' '. These strings are the parts.
You'll need to provide the 1 based indices ascending order of the parts that form the two chains when concatenated.
You have to be fast! There's a timeout in each case.
You're allowed at most 3 errors. The 4th error will disconnect you.
The string given is 300 chars long maximum.
There are at most 18 parts.
It's guaranteed that there is at least one valid solution in each case.
Chars a and A are different, same applies for c, C, t, T, g and G

Sample Input as provided by the daemon

aacc GgTTC aaccG gTTC aaaa cccc gttc
TATaCaACcCG aAgGacctcTtGgt TAttaCAtaTtA CgG TAttaCAtaTtAC CTATaCaACcCGcGg CCcCTaGcATaC cTgTGGAGAg cGgCgG

Sample Output as required by the daemon

1,2,3,4
1,3,4,5,6,9

Test your code

You can test your program against both the input provided in the test phase and the input provided in the submit phase. A nice output will tell you if your program got the right solution or not. You can try as many times as you want to. Be careful with extra whitespaces, the output should be exactly as described.

Test your program against the input provided in the test phase

Download test input

Program output:

Test your program against the input provided in the submit phase

Download input

Program output:

During the submit phase, in some problems, we might give your program harder inputs. As with the test token, a nice output will tell you if your program got the right solution or not. You can try as many times as you need.

In the actual contest you first need to solve the test phase before submitting the code, you must provide the source code used to solve the challenge and you can only submit once (once your solution is submitted you won't be able to amend it to fix issues or make it faster).

If you have any doubts, please check the info section.

Problem stats

Completion time: min: 0:45:59 h
10th percentile: 2:28:45 h
90th percentile: 49:29:38 h
max: 102:49:45 h
Test phase time: 10th percentile: 1:41:50 h
90th percentile: 38:16:57 h
Submit phase time: 10th percentile: 0:00:58 h
90th percentile: 6:11:51 h
# of completions:137