Assemble DNA payload strings from tagged fragments
Overview
This question evaluates proficiency in string manipulation, sequence assembly, and labeled-graph path reconstruction—skills involved in ordering fragments by matching start/end tags and concatenating payloads—and it belongs to the Coding & Algorithms domain.
You are given a list of DNA-like fragments. Each fragment is a tuple:
-
start_tag: string -
end_tag: string -
payload: string
A valid DNA chain is formed by ordering fragments so that the end_tag of one fragment matches the start_tag of the next fragment. The assembled DNA string is the concatenation of payloads in chain order.
Assume tags are arbitrary strings (e.g., "AAA", "AAC").
Q1: Single forward chain
Given fragments that form exactly one continuous chain using the rule prev.end_tag == next.start_tag, assemble and output the final concatenated string.
Example:
Input:
-
(XXX, ATG, "Hello") -
(ATG, GCA, "World") -
(GCA, TAG, "!") -
(TAG, YYY, "Done")
Output:
-
"HelloWorld!Done"
Q2: Chain can be traversed in either direction
Now treat each fragment as connecting two tags, and you may traverse the final chain either in the forward direction or in the reverse direction.
- Forward traversal outputs payloads in forward order.
- Reverse traversal outputs payloads in reverse order.
- Either output is acceptable.
For the example above, valid outputs include:
-
"HelloWorld!Done"(forward) -
"Done!WorldHello"(reverse)
Q3: Multiple DNA chains
Now the input fragments may form multiple disjoint chains (still assuming they can be arranged into simple chains with no branching within a chain). Output all assembled strings, one per chain, in any order.
Output format
- Q1/Q2: a single string
- Q3: a list/array of strings (one per chain)