# ECOO 2014 Local - Problem #2: Orphan Black

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

 Space 32 00100000 A 65 01000001 B 66 01000010 C 67 01000011 D 68 01000100 E 69 01000101 F 70 01000110 G 71 01000111 H 72 01001000
 R 82 01010010 S 83 01010011 T 84 01010100 U 85 01010101 V 86 01010110 W 87 01010111 X 88 01011000 Y 89 01011001 Z 90 01011010
 I 73 01001001 J 74 01001010 K 75 01001011 L 76 01001100 M 77 01001101 N 78 01001110 O 79 01001111 P 80 01010000 Q 81 01010001

Binary integers are just like regular decimal integers except that the only digits allowed are 1 and 0 and instead of palce 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 the 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:

011 01001000 01000101 01001100 01001100 01001111 000
H        E        L        L        O

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 message themselves consist entirely of the capital letters A through F 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

## My solution (in Java):

import java.util.Scanner;
import java.util.ArrayList;
import java.io.File;

public class Problem_2_Orphan_Black {

public static void main(String[] args) {

/*
ALGORITHM:

I assume there is only one message that can possibly be decoded from the input.

First thing, test both cases of the binary strings. Their bits will just be flipped from one another, but either one could be correct.

There are up to 7 bits extra bits on the beginning and end of the binary string. So I test every possible case:
I use a for-loop from 0 to 7 (index positions in the string - 7 bits) and in each iteration, I scrap the number
of bits up to that index position. On the first iteration, no bits are scrapped. It takes the substring from the 0th index
which is the whole string. Next iteration, it takes the substring from the 1st index position, which means it discludes the
first character in the string. And so on, up until it finally discludes the first 7 bits of the binary string.

In each iteration, I test if the bytes contain a message, and display it if I find that all of the whole bytes do.

What you don't see is me scrapping any bits from the end. This is because the algorithm takes care of that already.
If I test every case of scrapped bits from the beginning, and then only look at the WHOLE bytes after that, it will
have to disclude the scrap bits at the end, due to them not being part of the set of WHOLE bytes. The scrapped bits
at the end will never be included in my tests. because they are UP TO 7 bits. This means the scrap bits at the end
will ALWAYS be discluded from the test because I only test whole bytes.

Think about it like this, the number of whole bytes that could possibly contain the message will always be the same in every case
because on either side of the message, there are scrap bits that can't be an entire byte. If no more than a byte can be scrapped,
then the number of bytes in the message has to be the same for every case.

With that said (this is just an example), if there are 46 bits, that means there have to be 6 scrap bits that can be divided in any way
at the beginning and back, always. There are only 8 whole bytes that can go into 46, which is 40 bits. So, there could be 0 scrap bits
at the beginning and 6 at the end, or 1 and 5, etc. But either way, as the iterations go from 0 to 1 to 2, etc., it will in turn
scrap the bits at the end, like 6 to 5 to 4, etc. If you drew it out, you would see that as you move the whole number of bytes along,
it makes room for scrap bits on one end and pushes the scrap bits off of the other end.
*/

try {
Scanner scanner = new Scanner(new File("F:\\data\\DATA22.txt"));
ArrayList<String> list = new ArrayList<String>();

// read in the file to the ArrayList
while (scanner.hasNextLine()) {
}

// skip every other line because it's just the opposite pairs and the conversion is the same
for (int l = 0; l < list.size(); l += 2) {

String line = list.get(l); // this line in the loop

// two binary string cases
String binaryString1 = dnaToBinaryString1(line.trim());
String binaryString2 = dnaToBinaryString2(line.trim());

// up to 7 bits of scrap bits at the beginning
// so test for each case
for (int scrapBits = 0; scrapBits < 8; scrapBits++) {

// disclude the scrap bits from each binary string (from the beginning)
String s1 = binaryString1.substring(scrapBits);
String s2 = binaryString2.substring(scrapBits);

// number of whole bytes (sets of 8 bits) with the discluded scrap bits from the beginning
int numberOfBytes = s1.length() / 8;

// array of bytes (one for each case)
String[] bytes1 = new String[numberOfBytes];
String[] bytes2 = new String[numberOfBytes];

// for every whole byte, assign the next byte in test binary string to the array of bytes
for (int k = 0; k < numberOfBytes; k++) {
// multiply counter by 8 to skip 8 chars (move onto the next byte) every new iteration
// and substring that part of the binary string for 8 more chars (the whole byte) with the counter + 1, then multiplied by 8
bytes1[k] = s1.substring(k * 8, ((k + 1) * 8));
bytes2[k] = s2.substring(k * 8, ((k + 1) * 8));
}

// if the array of bytes for the first binary string case contains entirely valid message bytes
// i.e. if this number of scrapped bits taken off has left a message in the bytes
if (areBytesValid(bytes1)) {
// print out the message (each byte in the array of bytes converted to a its char)
for (String b : bytes1) {
System.out.print(byteToChar(b));
}
System.out.println();
}

// if the array of bytes for the second binary string case contains entirely valid message bytes
// i.e. if this number of scrapped bits taken off has left a message in the bytes
if (areBytesValid(bytes2)) {
// print out the message (each byte in the array of bytes converted to a its char)
for (String b : bytes2) {
System.out.print(byteToChar(b));
}
System.out.println();
}
}
}

} catch (Exception e) {
e.printStackTrace();
}

}

/* returns whether or not the parameter string can be represented as a valid
byte for the message (capital letters A through Z or a space) */
public static boolean isValidByte(String b) {
if (b.length() != 8) return false; // doesn't even have exactly 8 bits

// get the decimal value of the parameter binary integer byte
// represents the ASCII value of the character
int n = byteToDecimal(b);

// if the ASCII value is between 65 and 90 (meaning between capital letters A through Z)
// or if the ASCII value is 32 (a space) then it is a valid byte
return ( (n >= 65 && n <= 90) || n == 32 );
}

/* Uses the isValidByte method on each element in the parameter array of bytes
to determine if the entire array contains valid bytes for the message */
public static boolean areBytesValid(String[] bytes) {
for (int i = 0; i < bytes.length; i++) {
if (!isValidByte(bytes[i])) // not valid byte
return false;
}
return true; // hasn't found a not valid byte, so it's a valid array of bytes
}

/* returns the decimal value of the parameter binary integer byte*/
public static int byteToDecimal(String b) {

// variables names represent the place values for a binary integer
// but values are either 0 or 1
int oneTwentyEight  = Integer.parseInt(b.substring(0, 1)); // leftmost bit
int sixtyFour = Integer.parseInt(b.substring(1, 2));
int thirtyTwo = Integer.parseInt(b.substring(2, 3));
int sixteen = Integer.parseInt(b.substring(3, 4));
int eight = Integer.parseInt(b.substring(4, 5));
int four = Integer.parseInt(b.substring(5, 6));
int two = Integer.parseInt(b.substring(6, 7));
int one = Integer.parseInt(b.substring(7, 8)); // rightmost bit

return oneTwentyEight*128 + sixtyFour*64 + thirtyTwo*32 + sixteen*16 + eight*8 + four*4 + two*2 + one*1;
}

/* returns the char representation of the parameter binary integer byte */
public static String byteToChar(String b) {

// get the decimal value of the parameter binary integer byte
int n = byteToDecimal(b);

// return the char representation corresponding to that decimal ASCII value
return String.valueOf((char)n);
}

/* Converts DNA to a binary string with C and G pairs as "0" and A and T pairs as "1"*/
public static String dnaToBinaryString1(String dna) {
String re = "";
for (int i = 0; i < dna.length(); i++) {
if (dna.substring(i, i+1).equals("A") || dna.substring(i, i+1).equals("T")) {
re += "1";
}
else {
re += "0";
}
}
return re;
}

/* Converts DNA to a binary string with A and T pairs as "0" and C and G pairs as "1"*/
public static String dnaToBinaryString2(String dna) {
String re = "";
for (int i = 0; i < dna.length(); i++) {
if (dna.substring(i, i+1).equals("A") || dna.substring(i, i+1).equals("T")) {
re += "0";
}
else {
re += "1";
}
}
return re;
}
}

## My test cases (as .txt files):

Using their sample input:

ACCAATGTAGATATCATACTCTCTTGCTATGTTCGTTACATGCCCAA
TGGTTACATCTATAGTATGAGAGAACGATACAAGCAATGTACGGGTT
ACACTTTTGGTGTTCGTATCAACCGCAGATCCGATGTTACACTTCATATTTGATCGTCACTATCTC
TGTGAAAACCACAAGCATAGTTGGCGTCTAGGCTACAATGTGAAGTATAAACTAGCAGTGATAGAG
CCAGACGAGTAGTCCGACAGAGCCTGTGAGAGGGGCGTCGGGGGTGCCGTAGTCCGGCTGAGCAAGCCAGGTTCACC
GGTCTGCTCATCAGGCTGTCTCGGACACTCTCCCCGCAGCCCCCACGGCATCAGGCCGACTCGTTCGGTCCAAGTGG
AACCCCACTAATCCTGAAATTCTGTGTAGTTGTGAACATGTCCTAGATCATATTTGTTGCGGTCAAGCCTAAA
TTGGGGTGATTAGGACTTTAAGACACATCAACACTTGTACAGGATCTAGTATAAACAACGCCAGTTCGGATTT
ACCAGTTATACTACATAAAAGATTACTTACTTTAATCTTTAGCTTGTTTTATGTTAGTTA
TGGTCAATATGATGTATTTTCTAATGAATGAAATTAGAAATCGAACAAAATACAATCAAT
ACGACGCAGTCGACCGCCGAGGCTTCCCACGCCCGTGGCTTTCGACGGCGGAGGAGCCCC
TGCTGCGTCAGCTGGCGGCTCCGAAGGGTGCGGGCACCGAAAGCTGCCGCCTCCTCGGGG
AACCTGGTGGTCCACCGGGCTCCACTCCCAGGCGGCTCGAGTAGGTGGCCGGAGGATGG
TTGGACCACCAGGTGGCCCGAGGTGAGGGTCCGCCGAGCTCATCCACCGGCCTCCTACC
ACAGTGGTACTGGTGCCCGGTCCATACGCAGCGCGCTGGAATACGAGGGCCCTGTGGGCA
TGTCACCATGACCACGGGCCAGGTATGCGTCGCGCGACCTTATGCTCCCGGGACACCCGT
CACTGGCTGGAGCCCGGTGAGCACGCTCCGCCGACACCTAGCAGGCGCCTCTCTGGCAACAC
GTGACCGACCTCGGGCCACTCGTGCGAGGCGGCTGTGGATCGTCCGCGGAGAGACCGTTGTG
CACCCACACACTCTCGACGCCGGACTCTACGCTCCGGGGACAGTAAGCACGCGGGTGATGGCC
GTGGGTGTGTGAGAGCTGCGGCCTGAGATGCGAGGCCCCTGTCATTCGTGCGCCCACTACCGG

And the output to that is:

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

Using their first judging test input:

CACCCTCGCGGAGTCTGGTTGCTCGGCCCTGACACCCAGCAGCCCACGGAGACGTGCCGGGTCACCTCGAGCTCCGGAGTAGGAGTGAGACGGTGGTCGGGTGCATGACGACGCCCCTGGCTCCCTGCCAGACAGAGCATCTGCTGCACTCCGTTAGTCGAAAGGACCGTGTGAGGCACGGCTGGGCCCACTCTCCCTGCTATTGCTGCCGCGTCGGCACGACCAAAACTCTGAGTGTGGTTTGGACGCGTACACGGACTACAAC
GTGGGAGCGCCTCAGACCAACGAGCCGGGACTGTGGGTCGTCGGGTGCCTCTGCACGGCCCAGTGGAGCTCGAGGCCTCATCCTCACTCTGCCACCAGCCCACGTACTGCTGCGGGGACCGAGGGACGGTCTGTCTCGTAGACGACGTGAGGCAATCAGCTTTCCTGGCACACTCCGTGCCGACCCGGGTGAGAGGGACGATAACGACGGCGCAGCCGTGCTGGTTTTGAGACTCACACCAAACCTGCGCATGTGCCTGATGTTG
ACACCACAGATAGACCAGGGGAGCGCCACTCACAGGGGAGCGCGCACCCGTTCTCCTATTCAGTCTCTGAGCTTTCGACTGACGCAGACCATCCAGCGGGGTGGACGTGAGTCCATCCTGGGCGCTGTGTGCGTCGAGCCCACCCCCTCACAGACCGCACCGCGCTGACTCCGTGGTGGGGAGCCTGACCAGCGCGGTCAGCTCCTCGAGCCCAGAAGGTCTGGAACTCTCCCAGACAGACGATAACCCC
TGTGGTGTCTATCTGGTCCCCTCGCGGTGAGTGTCCCCTCGCGCGTGGGCAAGAGGATAAGTCAGAGACTCGAAAGCTGACTGCGTCTGGTAGGTCGCCCCACCTGCACTCAGGTAGGACCCGCGACACACGCAGCTCGGGTGGGGGAGTGTCTGGCGTGGCGCGACTGAGGCACCACCCCTCGGACTGGTCGCGCCAGTCGAGGAGCTCGGGTCTTCCAGACCTTGAGAGGGTCTGTCTGCTATTGGGG
CACCCCTCGGTCGGACCCTGACTGTGCTACACGTCCAGACCGTTAGACGATAGGACCCAGTGACGCTGCCCACCGGGGACTCTCGGACCATAAGCTGCGCCGACGGAACGTGGTGCAGTCGATCCCTCGTTCGCCAGCCCGCTCAACCTGTCCAATTGTGAGTCACACTCGAGGGTCCGCGGACGAAGTGAGCACCAGTGGTTAGCACCCTCG
GTGGGGAGCCAGCCTGGGACTGACACGATGTGCAGGTCTGGCAATCTGCTATCCTGGGTCACTGCGACGGGTGGCCCCTGAGAGCCTGGTATTCGACGCGGCTGCCTTGCACCACGTCAGCTAGGGAGCAAGCGGTCGGGCGAGTTGGACAGGTTAACACTCAGTGTGAGCTCCCAGGCGCCTGCTTCACTCGTGGTCACCAATCGTGGGAGC
AAAAAATCTTGCGAACAAGCCCTGACACGGAAGATAATTGTGTGATACATCAATTCTAAATCAGACTGTAAACATATATCTGCTAGTCTTCCCGACAGTGTCACTCAGGTACAATGACTTGAATTATCACAACAAGAATGTCTGATATTGACATCGATTCTACTTGACACCACATCTATGTCAGATTCATATCAATAAACTCACAAACAACTATTGATTCACATGTAATTTGAGTATTACTCATCAACTTGAAGTCATACTATGTAACAGTGTGAAGGAAGTTTTTTCTTTAAGTCTGTACTTGAGTAGAACATCTACTCTCTCGTACAATGAGACATAGTTC
TTTTTTAGAACGCTTGTTCGGGACTGTGCCTTCTATTAACACACTATGTAGTTAAGATTTAGTCTGACATTTGTATATAGACGATCAGAAGGGCTGTCACAGTGAGTCCATGTTACTGAACTTAATAGTGTTGTTCTTACAGACTATAACTGTAGCTAAGATGAACTGTGGTGTAGATACAGTCTAAGTATAGTTATTTGAGTGTTTGTTGATAACTAAGTGTACATTAAACTCATAATGAGTAGTTGAACTTCAGTATGATACATTGTCACACTTCCTTCAAAAAAGAAATTCAGACATGAACTCATCTTGTAGATGAGAGAGCATGTTACTCTGTATCAAG
CAACTCACCCTCTTTGTGATCATTTTACTTACCGACTTCCGGTGAGAGTATAGAAATATCACAGAAAGATGCCGATCTAAAATCTGTTATACACACTGAGATCGTGTGAGAAATATGAAATATCTCAGAAACATGATAACTTTGTGATCAATAATGTCTACGTGTGAGTAAGTGTGTGTGAATCGTAGTATCGTTAGATTATACTCTGTATCTTGGCCTACAAATAAGTTGCTCAGTAATTCAGTTCAGCTCAATGAGAAGTATTTAGACTCACAGAGATGCATCATATTACAGTCTATGAACCCGACTGTCAGACTTTGGGACTTCATAA
GTTGAGTGGGAGAAACACTAGTAAAATGAATGGCTGAAGGCCACTCTCATATCTTTATAGTGTCTTTCTACGGCTAGATTTTAGACAATATGTGTGACTCTAGCACACTCTTTATACTTTATAGAGTCTTTGTACTATTGAAACACTAGTTATTACAGATGCACACTCATTCACACACACTTAGCATCATAGCAATCTAATATGAGACATAGAACCGGATGTTTATTCAACGAGTCATTAAGTCAAGTCGAGTTACTCTTCATAAATCTGAGTGTCTCTACGTAGTATAATGTCAGATACTTGGGCTGACAGTCTGAAACCCTGAAGTATT
ATCAATCGTTCTGTTCTACATGCGCAGATCGTCATCTTATTTCAGACAAACTAGATAAGTATCACTAGTAATTAGAAGAAAAGATTCAGAGATATAGTCACTAGTACTGTGAAAACAC
TAGTTAGCAAGACAAGATGTACGCGTCTAGCAGTAGAATAAAGTCTGTTTGATCTATTCATAGTGATCATTAATCTTCTTTTCTAAGTCTCTATATCAGTGATCATGACACTTTTGTG
CAACACAAGTAGACTGTCATACTCTAGCAAGTATTTACAATTAGTTGTTATAACACTACCTGACTCTTTCATTTACTCTCTTGTAGAGTGAAAAGATTTTAGAAATTGTACTAAAAAGACAGCCACTTGCGCTCTGTTGTTCAAGACGAACTTATATGTACGCGTCAAAGCTTAGTTATTACTAAATGACAGAAGTTCTGTCAAAC
GTTGTGTTCATCTGACAGTATGAGATCGTTCATAAATGTTAATCAACAATATTGTGATGGACTGAGAAAGTAAATGAGAGAACATCTCACTTTTCTAAAATCTTTAACATGATTTTTCTGTCGGTGAACGCGAGACAACAAGTTCTGCTTGAATATACATGCGCAGTTTCGAATCAATAATGATTTACTGTCTTCAAGACAGTTTG
CCACCTCACTCGCTGCATTTCCTGGCGCCTGACGACCTCCCACTGAGAGTAGGTCCTTAACTCCTTGCCAGACACACTGTGTCCGACCTGGTGACGTAAACTCCAAAGCAGCAGGTCAGTAGACCTCGCTCTCGACCGCCCTGCATCAGAGCGCGTGTGCTCAACTCCCACAGGTGCGGGCTCCCCGACCTGCGGGCACGGCAAGTCCACCGGAGCCGGACAGGATTCGTGCCTTAGACCCTGAGGACGGGGCACGATAGGACCATAACAGACACGGTCGACGGGTCCACGTGTCCAAACCAGCCATACACTCCATCCTCGGCCGTGAGGTTCAGTGACGGACACGTGCACGCCCACAGCAATGCAGGCAATGTCGCAGAACAAA
GGTGGAGTGAGCGACGTAAAGGACCGCGGACTGCTGGAGGGTGACTCTCATCCAGGAATTGAGGAACGGTCTGTGTGACACAGGCTGGACCACTGCATTTGAGGTTTCGTCGTCCAGTCATCTGGAGCGAGAGCTGGCGGGACGTAGTCTCGCGCACACGAGTTGAGGGTGTCCACGCCCGAGGGGCTGGACGCCCGTGCCGTTCAGGTGGCCTCGGCCTGTCCTAAGCACGGAATCTGGGACTCCTGCCCCGTGCTATCCTGGTATTGTCTGTGCCAGCTGCCCAGGTGCACAGGTTTGGTCGGTATGTGAGGTAGGAGCCGGCACTCCAAGTCACTGCCTGTGCACGTGCGGGTGTCGTTACGTCCGTTACAGCGTCTTGTTT
AAACAAGAGTGCGCGACCCTCAGTGCTTTAGACTGGGCCAGGTTCCCAGCCTCACGTCCCCCGAGACCCCGTGCCTGTCAGCATTTGTGTCCGGCAGGAAGGGTGCCTCACGTGGGCGGACTCATACACGGACAGGTCGCCGCTCGCGGACAGACGTGGTCCGACTCCTGCGGCGACAGACGCAGCAGCCGACCGTGACGTCGCGCCAGACCTTCACCCGCAGAGCATGACTGCGTGTCCACCA
TTTGTTCTCACGCGCTGGGAGTCACGAAATCTGACCCGGTCCAAGGGTCGGAGTGCAGGGGGCTCTGGGGCACGGACAGTCGTAAACACAGGCCGTCCTTCCCACGGAGTGCACCCGCCTGAGTATGTGCCTGTCCAGCGGCGAGCGCCTGTCTGCACCAGGCTGAGGACGCCGCTGTCTGCGTCGTCGGCTGGCACTGCAGCGCGGTCTGGAAGTGGGCGTCTCGTACTGACGCACAGGTGGT
AAACTTGGGTTGATGGGGTTCAATTAACACAGCCACTAAGACTCTCTTCTAGATAGTGTACAATTTACTTGGCATGAACCCGACAGTCTAATGTATTTAGACAGAAACTTCATTACTTTCTCTTGTATAATCACTTCCACAAAAACACTTGCTGACTATGTC
TTTGAACCCAACTACCCCAAGTTAATTGTGTCGGTGATTCTGAGAGAAGATCTATCACATGTTAAATGAACCGTACTTGGGCTGTCAGATTACATAAATCTGTCTTTGAAGTAATGAAAGAGAACATATTAGTGAAGGTGTTTTTGTGAACGACTGATACAG

And the output to that is:

AS THE RHYTHM DESIGNED TO BOUNCE
WHAT COUNTS IS THAT THE RHYMES
NOW THAT YOUVE REALIZED THE PRIDES ARRIVED
WE GOT TO PUMP THE STUFF TO MAKE US TOUGH
FROM THE HEART
ITS A START A WORK OF ART
TO REVOLUTIONIZE MAKE A CHANGE NOTHINGS STRANGE
PEOPLE PEOPLE WE ARE THE SAME
NO WERE NOT THE SAME

And that is exactly the expected output.

Using their second judging test input:

ACAGGCGAAGACCGCGAGAGACTCTGACTCCAAGAGGGTGTGCTCCCCCGACTCATTCACCGACAGGACCGGCCTCCCTGGCTCCATTTGTGCATACGTGACTCGGGTGCCGCGACGAGAAGAGCTAACCAGGTTAACAGACAATCGAGGGCCCTCTCTCCGAGCAGCGCAGGCAGTGCTCGCCGGACCCTATGTCGCGGTCTGCTAGACTCGGACTC
TGTCCGCTTCTGGCGCTCTCTGAGACTGAGGTTCTCCCACACGAGGGGGCTGAGTAAGTGGCTGTCCTGGCCGGAGGGACCGAGGTAAACACGTATGCACTGAGCCCACGGCGCTGCTCTTCTCGATTGGTCCAATTGTCTGTTAGCTCCCGGGAGAGAGGCTCGTCGCGTCCGTCACGAGCGGCCTGGGATACAGCGCCAGACGATCTGAGCCTGAG
ACACACTCTGACCCAGTACTTATGTTTTTGTGTGTGAATTGTATTATGTCACCCAGTTACACTAGTTTAATGTACGGTTGATTGTCTCTTTCTCAGAATGTAAAGTTTTAAGAACTACTCTCTAGGTACTTATTACATAATCAGTCAGCCACAATATCAGACTAGATGTATGACAGAAGCCTTCATTCACAGTGAACGTGAGTAGGACCACC
TGTGTGAGACTGGGTCATGAATACAAAAACACACACTTAACATAATACAGTGGGTCAATGTGATCAAATTACATGCCAACTAACAGAGAAAGAGTCTTACATTTCAAAATTCTTGATGAGAGATCCATGAATAATGTATTAGTCAGTCGGTGTTATAGTCTGATCTACATACTGTCTTCGGAAGTAAGTGTCACTTGCACTCATCCTGGTGG
CACCACTGTGTGGCTCAAACTGTTCAATAATGATATGGTGTATTAGACTAGGGATCTCTCTAAAGTATTAACTTTCCCTCTTACTGAGTGAGTTTAGTTAATAGTAAACCTGAATTAGTCTGATCTTCAAAGTGTGTTCCTATGATTCTGTCAGATCCACTCATCGAC
GTGGTGACACACCGAGTTTGACAAGTTATTACTATACCACATAATCTGATCCCTAGAGAGATTTCATAATTGAAAGGGAGAATGACTCACTCAAATCAATTATCATTTGGACTTAATCAGACTAGAAGTTTCACACAAGGATACTAAGACAGTCTAGGTGAGTAGCTG
CACTTGGACTGCAATTCTCACTCAGCTGCCCGGAGTGCTAGTCGGGGAGTGAAGCAGCTGCCCGCACAGTTTGACGACCGGAGCGGCACACTCTGCGCAGCCCGCTGGTGCTCACAGGAAGGACGGGGCTCACTGGGAGCTGCCCACCAGGAGACTCGAA
GTGAACCTGACGTTAAGAGTGAGTCGACGGGCCTCACGATCAGCCCCTCACTTCGTCGACGGGCGTGTCAAACTGCTGGCCTCGCCGTGTGAGACGCGTCGGGCGACCACGAGTGTCCTTCCTGCCCCGAGTGACCCTCGACGGGTGGTCCTCTGAGCTT
AAAGAACGAGAGAGCTTCATGTAATATGTTAAGATGAAACTCTGATGCTAACAACGCGTCTGACGATCTATGTGTCTTTCTATACATTTTTGAACGTATGATTCACTGAGACTTAGTGTTCCTACAAATTTCTATGGCTGATACACAGTCAGTAAAGATTAATCTTACTTAGTAGGCGACTGTGGGAGTAGGCTATGATAATAGAGAGAAAGTACCGGATGTTTATTGTAAAGTACTCTCTCTGTGAACCTGTAGAACTGATGGCTTGATAGAGACACTTCCTCTGATCGAACAC
TTTCTTGCTCTCTCGAAGTACATTATACAATTCTACTTTGAGACTACGATTGTTGCGCAGACTGCTAGATACACAGAAAGATATGTAAAAACTTGCATACTAAGTGACTCTGAATCACAAGGATGTTTAAAGATACCGACTATGTGTCAGTCATTTCTAATTAGAATGAATCATCCGCTGACACCCTCATCCGATACTATTATCTCTCTTTCATGGCCTACAAATAACATTTCATGAGAGAGACACTTGGACATCTTGACTACCGAACTATCTCTGTGAAGGAGACTAGCTTGTG
ACCAAGACGTTCTCTCGGTCAGAGGTTTGCAGTCTCCGTCCGGGTGTCCATGCCGTGCCCCGTGAGGTTCACGCTCACAGGATGGGACCCAAGCCACGGGGGTGGCTGCCTCCCAGTGAGCCATGCTCCGAGAGTGGTTACCACTCCAACTGGACCTCTGTGTAGCTGGGAGTGCACGGCGCAGCCATCGTCGTGGTCTCAGTCCCTCCAATCCTCCCTCACAGTCCATCACAGGTTCA
TGGTTCTGCAAGAGAGCCAGTCTCCAAACGTCAGAGGCAGGCCCACAGGTACGGCACGGGGCACTCCAAGTGCGAGTGTCCTACCCTGGGTTCGGTGCCCCCACCGACGGAGGGTCACTCGGTACGAGGCTCTCACCAATGGTGAGGTTGACCTGGAGACACATCGACCCTCACGTGCCGCGTCGGTAGCAGCACCAGAGTCAGGGAGGTTAGGAGGGAGTGTCAGGTAGTGTCCAAGT
CAACATGTACGAGTCAAAAAGTCTAGAGCACAAAGTGAACATAAAAGAAACTCTCAGACGTACATACAGACACAAGATGACGAAGTCTAATGAAGATGGGCTGATTGAATGTCGTTCTTGATATTTCTCTACCAGATACACTGAATGAGCACAC
GTTGTACATGCTCAGTTTTTCAGATCTCGTGTTTCACTTGTATTTTCTTTGAGAGTCTGCATGTATGTCTGTGTTCTACTGCTTCAGATTACTTCTACCCGACTAACTTACAGCAAGAACTATAAAGAGATGGTCTATGTGACTTACTCGTGTG
ACTCCACCAGACCAAACCCACGCCCGTCCTTTTGTCTGGTGGTGCCTCGGACGGAGTCACAGCTGCCACGCCCCTCTCTGCGTCCTTATCCAGGGCGGTCGGTAGGTCGACGACAGGCATTGTCGACGGCACACTCGGGAGGCGCCACTGAGGCAGGTCCGGAGCGTGACGTCGCCGGTGTGGGGGACCAAATCACTCAAAGACCGAGAGTCACGTCCTGACCTTGGTCGCCGCACTGTCGCTGGACGGGTGCCGCTCTGTCAGGGGTGGCGGCACCCCTCCAGGCTCT
TGAGGTGGTCTGGTTTGGGTGCGGGCAGGAAAACAGACCACCACGGAGCCTGCCTCAGTGTCGACGGTGCGGGGAGAGACGCAGGAATAGGTCCCGCCAGCCATCCAGCTGCTGTCCGTAACAGCTGCCGTGTGAGCCCTCCGCGGTGACTCCGTCCAGGCCTCGCACTGCAGCGGCCACACCCCCTGGTTTAGTGAGTTTCTGGCTCTCAGTGCAGGACTGGAACCAGCGGCGTGACAGCGACCTGCCCACGGCGAGACAGTCCCCACCGCCGTGGGGAGGTCCGAGA
ACCCAGGTAGGCACCGACAGACCATGTCTGGTTCACACGGAGTCCTGGGCCGTGCAGCCGTGGGACACTCCCCGACACAGCTGCGTCGCCCGTGTTGCTGACCATTACACAGAGAGGACCCCCGTGAGCTAGACCGGCTCTGATGGA
TGGGTCCATCCGTGGCTGTCTGGTACAGACCAAGTGTGCCTCAGGACCCGGCACGTCGGCACCCTGTGAGGGGCTGTGTCGACGCAGCGGGCACAACGACTGGTAATGTGTCTCTCCTGGGGGCACTCGATCTGGCCGAGACTACCT
CCACCCGTGCGTTCCAGCACCACTCGGAAAGAGGACCCGACTCAGCCCTGGCCCGACAGTGCCTCGACCGCACCCAGAGGACCGCCGAGTGGCGCACCAATAGTGACTTAGAGCCTCTCTGACGTGCC
GGTGGGCACGCAAGGTCGTGGTGAGCCTTTCTCCTGGGCTGAGTCGGGACCGGGCTGTCACGGAGCTGGCGTGGGTCTCCTGGCGGCTCACCGCGTGGTTATCACTGAATCTCGGAGAGACTGCACGG

And the output to that is:

CAUSE WE DONT KNOW THE GAME
WHAT WE NEED IS AWARENESS
WE CANT GET CARELESS
YOU SAY WHAT IS THIS
MY BELOVED LETS GET DOWN TO BUSINESS
MENTAL SELF DEFENSIVE FITNESS
MAKE EVERYBODY SEE
IN ORDER TO FIGHT THE POWERS THAT BE
LEMME HEAR YOU SAY
FIGHT THE POWER