2. Orphan Black

What is the Problem?

In the season finale of the Canadian TV show Orphan Black, the main characters discover a message written into their DNA using binary coded ASCII (pronounced “ASKee”). ASCII is a system for numbering letters and other printable characters. Binary coded ASCII uses 8-bit binary integers instead of regular decimal integers. The table below shows the decimal and binary ASCII codes for uppercase letters and the space character.

Binary integers are just like regular decimal integers except that the only digits allowed are 1 and 0 and instead of place values rising by 10s they rise by 2s. In decimal integers, the rightmost digit is the 1’s place, then 10’s then 100’s and so on. In binary the rightmost digit (bit) is the 1’s place, then the next is 2’s, then 4’s and so on.

DNA comes in a double strand made up of four bases (A, C, G, and T). A pairs with T and C pairs with G so that in a double strand, A’s and T’s are always across from each other and so are C’s and G’s, like this:

CAACACGTGGCGTGCCAGTGACCTTGGCAGGTTGCGTCGAAATCCC

GTTGTGCACCGCACGGTCACTGGAACCGTCCAACGCAGCTTTAGGG

To turn the above DNA into a binary string, just assign one of the base pairs (AT or CG) to be a 1 and the other to be a 0. So the above DNA string might represent this binary number:

1001011011110111010101100111011001110110000111

Or it might represent this one:

0110100100001000101010011000100110001001111000

In this case, the correct one is the second one and the message starts at the fourth position with a few bits left over at the end:

DATA11.txt (DATA12.txt for the second try) will contain 10 test cases. Each test case will consist of two lines representing a pair of chromosomes. Each pair contains a coded message as described above, with from 0 to 7 extra bits on the beginning and another 0 to 7 extra bits at the end (the chemists who read the DNA weren’t exactly sure where the message was). The messages themselves consist entirely of the capital letters A through Z and space characters.

Sample Input

ACCAATGTAGATATCATACTCTCTTGCTATGTTCGTTACATGCCCAA

TGGTTACATCTATAGTATGAGAGAACGATACAAGCAATGTACGGGTT

ACACTTTTGGTGTTCGTATCAACCGCAGATCCGATGTTACACTTCATATTTGATCGTCACTATCTC

TGTGAAAACCACAAGCATAGTTGGCGTCTAGGCTACAATGTGAAGTATAAACTAGCAGTGATAGAG

CCAGACGAGTAGTCCGACAGAGCCTGTGAGAGGGGCGTCGGGGGTGCCGTAGTCCGGCTGAGCAAGCCAGGTTCACC

GGTCTGCTCATCAGGCTGTCTCGGACACTCTCCCCGCAGCCCCCACGGCATCAGGCCGACTCGTTCGGTCCAAGTGG

AACCCCACTAATCCTGAAATTCTGTGTAGTTGTGAACATGTCCTAGATCATATTTGTTGCGGTCAAGCCTAAA

TTGGGGTGATTAGGACTTTAAGACACATCAACACTTGTACAGGATCTAGTATAAACAACGCCAGTTCGGATTT

ACCAGTTATACTACATAAAAGATTACTTACTTTAATCTTTAGCTTGTTTTATGTTAGTTA

TGGTCAATATGATGTATTTTCTAATGAATGAAATTAGAAATCGAACAAAATACAATCAAT

ACGACGCAGTCGACCGCCGAGGCTTCCCACGCCCGTGGCTTTCGACGGCGGAGGAGCCCC

TGCTGCGTCAGCTGGCGGCTCCGAAGGGTGCGGGCACCGAAAGCTGCCGCCTCCTCGGGG

AACCTGGTGGTCCACCGGGCTCCACTCCCAGGCGGCTCGAGTAGGTGGCCGGAGGATGG

TTGGACCACCAGGTGGCCCGAGGTGAGGGTCCGCCGAGCTCATCCACCGGCCTCCTACC

ACAGTGGTACTGGTGCCCGGTCCATACGCAGCGCGCTGGAATACGAGGGCCCTGTGGGCA

TGTCACCATGACCACGGGCCAGGTATGCGTCGCGCGACCTTATGCTCCCGGGACACCCGT

CACTGGCTGGAGCCCGGTGAGCACGCTCCGCCGACACCTAGCAGGCGCCTCTCTGGCAACAC

GTGACCGACCTCGGGCCACTCGTGCGAGGCGGCTGTGGATCGTCCGCGGAGAGACCGTTGTG

CACCCACACACTCTCGACGCCGGACTCTACGCTCCGGGGACAGTAAGCACGCGGGTGATGGCC

GTGGGTGTGTGAGAGCTGCGGCCTGAGATGCGAGGCCCCTGTCATTCGTGCGCCCACTACCGG

Sample Output

HELLO

CLONE ME

KEEP CALM

CARRY ON

A B C D

E F G H

I J K L

M N O P

Q R S T

U V W X