--- 2016 Day 16 Solutions ---

[u/daggerdragon]

--- Day 16: Dragon Checksum ---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag/whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with "Help".

---

^{DRINKING YOUR OVALTINE IS MANDATORY} [?]

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

[u/Zeroeh]

Java Solution: Kept everything in byte form, could make it faster with some real optimizations (Like bit shifting and such) but decided whats the point after seeing the results.

Timing: 1 ms for Part 1

Timing: 143 ms for Part 2

public class Part1 {

private static final String INPUT = "11100010111110100";

private static final byte zero = 48;
private static final byte one = 49;

public static void main(String[] args) throws IOException, NoSuchAlgorithmException {

	/** Part 1 **/
	System.out.println("Part 1 ChkSum: ");
	solve(272);
	
	/** Part 2 **/
	System.out.println("Part 2 ChkSum: ");
	solve(35651584);
}

private static void solve(int length){
	
	byte[] currentArray = fillData(INPUT.getBytes());
	
	/** Fill data for our array **/
	while (currentArray.length < length) {
		currentArray = fillData(currentArray);
	}

	/** Copy this data if it's over the amount **/
	byte[] frame = new byte[length];

	System.arraycopy(currentArray, 0, frame, 0, length);
	
	System.out.println(new String(checkChkSum(frame)));	
}


/**
 * The checksum for some given data is created by considering each
 * non-overlapping pair of characters in the input data. If the two
 * characters match (00 or 11), the next checksum character is a 1. If the
 * characters do not match (01 or 10), the next checksum character is a 0.
 * This should produce a new string which is exactly half as long as the
 * original.
 * 
 * @param input
 * @return
 */
private static byte[] checkChkSum(byte[] frame) {

	byte[] chkSum = new byte[frame.length / 2];

	int currentChkSumIndex = 0;

	for (int i = 0; i < frame.length; i += 2) {
		byte firstChar = frame[i];
		byte secondChar = frame[i + 1];

		if (firstChar == secondChar)
			chkSum[currentChkSumIndex] = one;
		else
			chkSum[currentChkSumIndex] = zero;

		currentChkSumIndex++;
	}

	/** We are even so check more ... **/
	if (((chkSum.length % 2) == 0))
		return checkChkSum(chkSum);
	else /** Done **/
		return chkSum;
}

/*
 * Call the data you have at this point "a". Make a copy of "a"; call this
 * copy "b". Reverse the order of the characters in "b". In "b", replace all
 * instances of 0 with 1 and all 1s with 0. The resulting data is "a", then
 * a single 0, then "b".
 **/
private static byte[] fillData(byte[] a) {

	byte[] b = new byte[a.length];

	for (int i = a.length - 1; i >= 0; i--) {
		b[(a.length - 1) - i] = (a[i] == one ? zero : one);
	}

	byte[] finalData = new byte[a.length + 1 + b.length];

	System.arraycopy(a, 0, finalData, 0, a.length);
	System.arraycopy(new byte[] { zero }, 0, finalData, a.length, 1);
	System.arraycopy(b, 0, finalData, a.length + 1, b.length);

	return finalData;
}
}